Wikipedia:Reference desk/Archives/Mathematics/2009 June 7

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 7

Hypothesis testing, backwards?

So far, I have learnt how to carry out a hypothesis test using the binomial expansion in the following way:

A company believes that 80% of the lightbulbs it makes are not faulty. They test a sample of 15, and find that six are faulty. Can their initial claim be justified?

Hence, X~B (15, p) and H₀: p = 0.8, where p is P (Not faulty). $1-{\frac {6}{15}}=1-0.4=0.6<0.8\therefore$ H₁: p < 0.8.

Or something along those lines. Anyway, then you use cumulative binomial tables to figure out whether H₀ can be accepted or rejected at a given percentage tail. That's all well and good, but how would one go about doing this backwards, as it were? Id est, if one began by carrying out that test and finding that p = 0.6, how would one find out the range of H₀s that one could reasonably fob off on people (without changing the result of the test, of course)? It Is Me Here ^{t / c} 09:09, 7 June 2009 (UTC)

The binomial distribution, that out of n bulbs you find i faulty ones, is ${\binom {n}{i}}P^{i}(1-P)^{n-i}$ where P is the probability that any bulb is faulty. The very same expression describes an (unnormalized) beta distribution for the likelihood density of P, knowing n and i. The formula for the mean value ± the standard deviation is $P\approx {\frac {i+1}{n+2}}\pm {\sqrt {{\frac {1}{n+3}}\cdot {\frac {i+1}{n+2}}\cdot \left(1-{\frac {i+1}{n+2}}\right)}}.$ When i = 6 and n = 15 you get $P\approx {\frac {7}{17}}\pm {\sqrt {{\frac {1}{18}}\cdot {\frac {7}{17}}\cdot {\frac {10}{17}}}}=0.412\pm 0.116.$ The believed probability P = 1−0.8 = 0.2 that a bulb is faulty, is (0.412−0.2)/0.116 = 1.8 standard deviations away from the mean value. Based on this the initial claim (P = 0.2) cannot be rejected. (See [[1]]). Bo Jacoby (talk) 16:26, 7 June 2009 (UTC).

What the original poster asks for is a confidence interval for p. Certainly there are reasonable approximate confidence intervals based on the normal approximation to the binomial distribution. I'm not sure if we have an account of exact confidence intervals for this situation somewhere on Wikipedia. More later.... Michael Hardy (talk) 03:34, 8 June 2009 (UTC)

I cannot tell if the above method is original research, so I did not include it in Wikipedia, even if it solves a commonly occuring problem. A confidence interval, 0 < a < P < b < 1, with confidence level 0 < L < 1, satisfies ${\frac {\int _{a}^{b}P^{i}(1-P)^{n-i}dP}{\int _{0}^{1}P^{i}(1-P)^{n-i}dP}}\geq L.$ This is computationally more difficult than computing the exact mean value and standard deviation of the beta distribution by the above formula, and then using the Chebyshev inequality to estimate an exact confidence interval pessimistically, or the normal distribution to estimate an approximate confidence interval more realistically. Bo Jacoby (talk) 07:03, 8 June 2009 (UTC).

Connected sets

Following my question on June 6, there's a bigger problem I need help with. I'm trying to find a space that contains two non-empty closed subsets A and B such that they are disjoint and A is disconnected, and their union is connected. I have a possible model:

Let C1 be the circle with radius 1 centered at the origin, C2 be the circle of radius 1 centered at x=1.5 y=0 and C3 be the circle with radius 1 centered at x=3 y=0.

Let X=union of these circles, and its topology be generated by the 3 circles. Let A=complement of C2, B=complement of ((C1)U(C3))

Clearly they are disjoint, and closed because they are complements of open sets, and also A is disconnected because it can be dissected by C1 and C3. But is AUB connected? It seems impossible to check with all the possible open sets... I really need an answer... And please say it's correct, I've spent 2 days working on this problem now...Standard Oil (talk) 09:55, 7 June 2009 (UTC)

But there is no such a space, because A and B would be closed also in their union wrto the relative topology. So, just by definition, their union can't be connected. --pma (talk) 10:08, 7 June 2009 (UTC)

Are you talking about disjoint closed sets can be separated by open sets? Yes that's exactly what I'm trying get around because there are non-normal spaces... Can you give me two disjoint open sets that dissect AUB?Standard Oil (talk) 10:14, 7 June 2009 (UTC)

Yes: A and B. --pma (talk) 10:19, 7 June 2009 (UTC)

But how can you get A and B from just performing union and intersection on the circles? Maybe I just don't see it... Can you write the process to attain A and B? —Preceding unsigned comment added by Standard Oil (talk • contribs) 10:24, 7 June 2009 (UTC)

It is simpler than that: if A and B are disjoint closed subset of any space X, then they are both open and closed in AUB since they are the complement of each other in AUB. In general, it can be useful for you to reflect on useful equivalent forms of the definition of a connected topological space X, e.g.:

• X is not union of 2 nonempty disjoint open sets;
• X is not union of 2 nonempty disjoint closed sets;
• The only clopen (i.e. both closed and open) subsets of X are the empty set and X itself;
• The only subsets of X with empy boundary are the empty set and X itself.

--pma (talk) 10:19, 7 June 2009 (UTC)

Ohhhhh I see what you mean... There's a misunderstanding between us here, my mistake. Your talking about connected space. I should have said connected set, meaning a set A such that you can't find two open disjoint sets V1 V2 in the embedding space that dissects A (V1 intersection A and V2 intersection A both non-empty, and A is a subset of (V1)U(V2)). What I'm asking here is, is it possible to find two disjoint open sets in X that dissects AUB, so I'm not asking whether AUB is a connected space in its own right, but rather is AUB a connected set in X.Standard Oil (talk) 10:39, 7 June 2009 (UTC)

OK. So what you want are two nonempty closed disjoint subsets A and B of a topological space X, that are not separated. Briefly, (X,A,B) is a counterexample to normality. Moreover, you wanted A disconnected (say, in the stronger sense that it is union of two separated closed subset of X).

Consider X':=X U {*}, with * a clopen point, and A':=AU{*} and B. Is it what you want?

Remark: In any case by "connected set" of a topological space people universally mean the same thing as "connected subspace" that is as a topological space with the subspace topology. The same convention is standard with any quality of topological spaces (so a compact subset, paracompact subset, metrizable subset etc all refer to the induced topology). --pma (talk) 11:38, 7 June 2009 (UTC)

I don't understand exactly what you mean by clopen point, you mean like the singleton is clopen? Furthermore, having A and B not separated doesn't mean their union is connected (in my sense), because we can well have 2 disjoint open sets both containing parts of A and parts B. Is my example right though? ThanksStandard Oil (talk) 12:05, 7 June 2009 (UTC)

Oops. --pma (talk) 12:13, 7 June 2009 (UTC)

Thanks for your help, maybe I'm just too confusing (a beginner can't be too lucid). Let's say that for a set A, you can find two open disjoint sets V1,V2 such that V1 intersection A and V2 intersection A are both not empty, and furthermore A is a subset of (V1)U(V2). There are 4 conditions here, and we'll just call A dissectable. So, what I want is two non-empty disjoint closed sets A and B satisfying: A is dissectable, AUB is NOT dissectable.Standard Oil (talk) 12:20, 7 June 2009 (UTC)

Here's an attempt at constructing a topology with the properties you want. Our space X will be {1, 2, 3, C, D}, with A = {1, 2} and B = {3}. Consider the topology whose open sets are generated by {1, C}, {2, D}, {3, C, D}; the idea is that we took the discrete topology on {C, D} and added three generic points 1, 2, and 3, which "touch" {C}, {D}, and {C, D} respectively (i.e. whose closures include those sets). Since {1, 2, C, D} and {3, C, D} are open, their complements A and B are closed.

Now {1, C} and {2, D} are disjoint opens which "dissect" A, but I claim no disjoint opens can dissect A union B = {1, 2, 3}. Indeed, assume we have two disjoint opens covering A union B. Any neighborhood of 1 includes C, and the same is true of 3, so 1 and 3 must be in the same open set. But any neighborhood of 2 includes D, and the same is true of 3, so 2 and 3 must be in the same open set. This shows that A union B is not dissectable.

As a final (and tangential) comment, this may seem like a horribly arbitrary topology, and it is. But it seems to me it should be possible to find some ring so that this example arises as the Zariski topology on spectrum of a ring, which would at least show that such topologies can arise in nature. Tesseran (talk) 08:16, 11 June 2009 (UTC)

A particular quotient space.

I'm having difficulty trying to show that the unit square, quotiented out by the relation that identifies $(x,y)$ with $(1-x,1-y)$, is homeomorphic to S². I've had no luck simply trying to stretch the space around and gluing the relevant points together (I can't find a way to carry this out in a finite number of steps, there are always points left unglued) - the closest I came was to put a half twist in, then join one pair of opposing edges together (like a Moebius strip), but that just gets me into a mess. I've noticed the square (with identifications) has half-turn symmetry, but I can't see how to use that fact. It seems at first that any line drawn on the square, passing through the centre, is a great circle on the sphere (since the ends are identified), which seems like a good avenue to head down, but then you have to perform subsequent gluings to pairs of points on the great circle, which gets into a bit of a mess.

I've tried thinking about it purely in terms of open sets of each space and the like, but I'm never really sure how to do that generally. Any help would be much appreciated, thanks! Icthyos (talk) 12:48, 7 June 2009 (UTC)

I assume your unit square has edges identified so that it has the topology of a torus (without some such identification of edges, your square has a boundary so cannot be homeomorphic to S²). Cut the torus in half and work out how to sew up the cut edges so that $(x,y)\sim (1-x,1-y)$. Gandalf61 (talk) 16:07, 7 June 2009 (UTC)

Ahh, yes, the exercise sneaked in at the begin that it was a further identification, on top of the torus, which I missed. I think I can see why the two are homeomorphic - if you cut the torus in half in such a way that it corresponds to cutting along the diagonal of the square, you get it so that the two halfs are identified with each other, so all that's left to do is clamp, say, the top half shut, with two 'hinges' on opposite sides of the boundary (one being on the longitudinal (...meridional?) circle where we originally glued to get the torus), which gives us a surface which we can easily deform into a sphere! Is that correct? I'm not terribly confident at this. It doesn't help that it's so difficult and hand-wavey to explain just what you're doing in your head! Thanks a lot, Icthyos (talk) 18:16, 7 June 2009 (UTC)

Yes, that is correct. Parameterise your torus with parameters (θ,φ) with θ and φ taking values between 0 and 2π. Cut it in half say along the circles φ = 0 and φ = π. Then join each point (θ,0) to (2π - θ, 0), so your "hinges" are at (0,0) and (π,0). Do the same along the circle φ = π, with "hinges" at (0,π) and (π,π) and you are done. Gandalf61 (talk) 22:40, 7 June 2009 (UTC)

I'm not following this so far (maybe I will after I've thought it through....). If all this is correct, there should be a two-to-one continuous mapping from the torus to the sphere that's locally one-to-one everywhere and whose local inverse is continuous. As if you had a torus-shaped map of the earth on which every location appears twice. Can you specify that mapping? Michael Hardy (talk) 20:53, 8 June 2009 (UTC)

OK, maybe I am seeing it. For any point on the surface of the earth, there are two points on the torus where the tangent plane is parallel to the tangent plane to the earth at that point and the side of the plane that's in the interior of the torus is the same side as the side of the tangent plane to the sphere at the point in question. Someone who's good at computer graphics should be able to start with an ordinary globe and create a picture of this thing. Michael Hardy (talk) 20:57, 8 June 2009 (UTC)

...but the point (1/2, 1/2) corresponds only to itself, so that won't work. And also, the way I describe it, more than two points on the torus would correspond to the north pole (if you oriented things that way). OK, back to the drawing board. I suppose I should try to do this systematically instead of looking at it like this. Michael Hardy (talk) 21:02, 8 June 2009 (UTC)

See torus - "The 2-torus double-covers the 2-sphere, with 4 ramification points". The ramification points are the images of Icthyos's "hinges". They only have one pre-image on the torus; every other point on the sphere has two pre-images. On the original unit square the ramification points are at its corners (only one point on the torus); mid-points of its sides (two points on the torus); and at its center. There is a nice diagram on p194 of Peter Cromwell's Knots and Links (that page is, unfortunately, not accessible in Google books). Gandalf61 (talk) 22:49, 8 June 2009 (UTC)

Thank you, Gandalf.

Sometimes a page that seems not accessible by google books becomes accessible by cleverly altering the search terms. But you might have to think of some words that occur together only on that one page. Any ideas along those lines? Michael Hardy (talk) 05:00, 9 June 2009 (UTC)

OK, the discussion on page 193 of Cromwell's book is enough to make it clear that the quotient space is topologically a sphere. (I haven't gone to the library yet to see the picture.) That the mapping is conformal—or can be chosen conformal—is not clear to me yet. Since the Wikipedia article you linked to (torus) says that the cross-ratio of the four points on the sphere determines the conformal type of the torus, I'm suddenly thinking: does that mean there's such a thing as a cross-ratio of four points on a torus? Or does it just mean there's such a thing a the cross-ratio of a torus? If "conformal type" means what I think it means, then there would be no conformal mapping between two toruses if those two cross-ratios were different.

Mapping the sphere onto the cylinder is a known thing in cartography, but mapping the whole sphere onto a cylinder of finite length is something I've never thought about, and having the circular boundary correspond to an arc of nonzero length on the sphere, rather than to a single point on the sphere (e.g. the north pole) is not something I'd have thought of. Michael Hardy (talk) 22:13, 9 June 2009 (UTC)

I'd forgotten this thing I should have remembered: doubly periodic holomorphic functions from C to C ∪ {∞} assume every value twice. That means that is a double covering of the sphere by the torus, and it's conformal. Michael Hardy (talk) 02:10, 10 June 2009 (UTC)

For an application, see Peirce quincuncial projection. Gandalf61 (talk) 11:35, 11 June 2009 (UTC)

Could it turn out that no axiomatic system is consistent?

Could it turn out to be the case that no axiomatic system of mathematics is consistent? If that happens, would Mathematics as a discipline then turn into a branch of Physics, or what? 94.27.225.206 (talk) 15:57, 7 June 2009 (UTC)

No. Presburger arithmetic is consistent. Taemyr (talk) 20:51, 7 June 2009 (UTC)

I don't think we exactly say with the kind of certainty being requested that Presburger arithmetic is consistent, I mean, sure, we can prove its consistency from Peano arithmetic, but if Peano arithmetic is inconsistent, then it can prove anything. For that matter, there are self-verifying theories that prove their own consistency, but again, who knows if they are really consistent?

We also have proofs that Peano arithmetic is consistent (Gödel's incompleteness theorem only proves that systems like PA can't prove their own consistency, not that their consistency can't be proven from "outside"). The first one, Gentzen's consistency proof, uses an induction principle on trees that turns out to be equivalent to PA but is still "intuitive"; another, in Gödel's Dialectica interpretation, uses higher-order functions, subject to the same problem.

Presberger arithmetic and Peano arithmetic both contain a "successor axiom" that says that every integer has a successor, i.e. there are infinitely many integers. There are actually a few mathematicians (see ultrafinitism) who reject that axiom and say there is a largest integer, which means all proofs relying on the successor axiom are wrong. Doron Zeilberger has written some interesting articles about this. Zeilberger is of the view that we are approaching an era when mathematics indeed is becoming like physics, where we have a lot of observations that we can experimentally seem to confirm, but which are beyond our capability to prove. Gregory Chaitin says similar things but from a different philosophical standpoint. 67.122.209.126 (talk) 03:12, 8 June 2009 (UTC)

Your first two paragraphs seemed to have some valid points, though anyone who doesn't accept the consistency of both Presburger and Peano arithmetic is probably just being a bit too anal. The last paragraph, however, I have to say seems to be confusing the issue between consistency and truth of an axiomatic system. The question had nothing to do with whether the system is "true" in any sense. A better approach, for the purpose of answering the OP's question, would be: are there mathematicians who will claim that those basic number theoretic systems mentioned are somehow inconsistent? Note: I mean that they will claim that the system absolutely is inconsistent, not that inconsistency is a possibility, as you have pointed out already. --COVIZAPIBETEFOKY (talk) 14:31, 8 June 2009 (UTC)

I have never heard of a serious mathematician saying "such and such theory is inconsistent, but I just haven't found the inconsistency yet; be patient".

However Edward Nelson has put effort into trying to find a contradiction in the extremely weak theory Q (Robinson arithmetic).

Also there was somebody whose name I can't remember for certain — I want to say Wette but the only remotely close hit I get is for an Elisabeth Wette, and I thought this was a man — who was claiming actually to have found a contradiction in, I think, Peano Arithmetic. As I remember it no one could find the error, because no one could actually follow the argument. --Trovatore (talk) 18:11, 8 June 2009 (UTC)

(Update: I did a little more searching, and I think it was Edward Wette. This is based on second-hand info, like Usenet posts. I can't find out very much about him in more traceable sources. He does appear to have a paper in a symposium for Goedel's sixtieth birthday.) --Trovatore (talk) 18:30, 8 June 2009 (UTC)

Pairwise intersecting sets of bounded size

For every natural number k there is a natural number G such that if each member of a set C is a set of size at most k and any two members of C have a non-empty intersection, then there exists a set A of size at most G such that the intersection of A and any two members of C is still non-empty.

This statement is not hard to prove. What I'd like to know is whether it is known, and where it appears in literature. I'd be interested about anything similar too.

The draft of the proof is this. Given C, construct a set A_p by induction on p such that for every element X of C either X and A_p share at least p elements or X intersects every member of C even in A_p. Once you have A_p, choose one element X of C for each possible intersection of X with A_p, and then choose A_p+1 as the union of these sets. The size of these A_p can be bounded by a number depending only on k and p.

This also proves a slightly stronger variant of the above statement, namely that you can have X and Y and A intersect for any member X of C and any set Y that intersects all members of C.

– b_jonas 20:13, 7 June 2009 (UTC)

Pity. – b_jonas 11:19, 10 June 2009 (UTC)

The thing that first came to my mind was the Erdős–Ko–Rado theorem, though it's not clear to me at the moment that these are related. —Bkell (talk) 14:42, 10 June 2009 (UTC)

It is slightly related. The Erdős-Ko-Rado theorem tells what the maximum size of an intersecting set can be when the size of the ground set is bounded. There's even a theorem on the next largest intersecting set, that is, one that gives its maximum size when there's no one element that's a member of all sets – in this case for a fixed k the order of magnitude of the maximum size is $O(n^{k-1})$ whereas in the general case the Erdős-Ko-Rado theorem gives $O(n^{k})$. There are also completely different intersecting sets, like the set of lines of a finite projective plane, these cannot be extended to larger intersecting sets even if you increase the ground set; and there are lots of constructions in between. So what I wanted to know is a way to characterize how even if the size of the ground set is not bounded, the intersecting set is still small in some way, even if its size can grow. – b_jonas 18:20, 10 June 2009 (UTC)