Wikipedia:Reference desk/Archives/Mathematics/2011 June 9

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 9

Total ordering

Can ZF (without choice) prove every set can be totally ordered? Not well ordered, just total. Money is tight (talk) 04:28, 9 June 2011 (UTC)

No. If every set can be totally ordered, then you can always find a choice function for any set of unordered pairs, which is not provable in ZF. (Suppose you have a set of unordered pairs, then linearly order the corresponding set of ordered pairs, and from a pair {a,b}, choose a if (a,b) appears before (b,a) in the linear order, otherwise b.) --Trovatore (talk) 04:33, 9 June 2011 (UTC)

Actually I guess it's a bit simpler than that — just linearly order the union of all the pairs, and then from each pair, take the lesser one in the linear order. Of course that just pushes the question back to why you can't prove in ZF that there's always a choice function on sets of pairs. I don't know the answer to that for sure. I want to say that a choice function on pairs of equivalence classes for the Vitali relation will somehow give you something that can't exist in a model of ZF+AD, say a non-measurable set of reals or one without the property of Baire, but the details escape me. --Trovatore (talk) 04:51, 9 June 2011 (UTC)

Ah, I think I can do it. Suppose there's a choice function on all pairs of equivalence classes of the Vitali equivalence relation. Graph that on the plane, meaning that we put (x,y) into the graph just in case, when you apply the choice function to the pair ([x],[y]), where [x] means the equivalence class of x, the choice function gives you back the equivalence class of x, not the equivalence class of y.

OK, what can we say about this graph? It has to be invariant under rational shifts: If (x,y) is in the graph, then so is (x+r,y+s) for any rational r and s; that's just by the definition of the Vitali relation. Moreover, it's complemented when you reflect it across the main diagonal, in the sense that if (x,y) is in the graph, then (y,x) is not in the graph (except for the case that x is a rational shift of y, which we should easily be able to argue is a meager set of exceptions).

So now suppose this set in the plane has the property of Baire. That implies that either (i) it's meager, which it can't be because then the plane would be the union of three meager sets, namely the set, its reflection across the main diagonal, and the set such that x is a rational shift of y. Or (ii), there's some little neighborhood on which the set is comeager.

But in case (ii), cut that little neighborhood down to something nice, say a circular disk or a square. Then when you reflect across the main diagonal, you have to get a neighborhood on which the set is meager, by the complementing property we discussed.

But surely there's some rational shift that takes the neighborhood mostly onto the reflected neighborhood. Now you have a contradiction.

Anyone see any mistakes? --Trovatore (talk) 11:01, 9 June 2011 (UTC)

Thanks. Money is tight (talk) 00:15, 10 June 2011 (UTC)

How many observations are needed to reach a certain accuracy?

Say you wanted to see what cloud cover was for each month of the year and put up a machine that took 1 reading an hour for 5 years.

So you might get something like Jan 0/10 38%, 1/10 5% ... 9/10 4%, 10/10 25%;  Feb 0/10 34% etc. or whatever.

You'd be 50% sure of being how close to the real value? What about 95%? What formula do I use? Is it 1/√(trials)? Then again, I've seen months when a weather system or high pressure stays stuck over the area for 10, 14 days in a row when days are supposed to be close to a random bag here. Get one of those in your month and your accuracy would be pretty much thrown off, right? Maybe you really need 30 years like the climatologists use?

The observations are not independent, that is if you have clouds on day one this changes the probability of clouds on day two, compared to no data for day one or no clouds on day one.  So before you can say anything about the accuracy of your observations you would need a model for that dependency.  Taemyr (talk) 19:36, 9 June 2011 (UTC)

I don't know what the dependency is but from about 1 decade of noticing I'd say streaks are usually 1, 2, sometimes 3 days, within the same day gets more correlated, 5 days in a row on the weather forcast and I start noticing, last month there were 10 days in a row when clouds rolled in maybe twice, and only for a few hours (no rain that long makes allergies really bad), it was pretty much overcast 10/11 days in a row in June of '09, and I saw almost no sun for a half month in 2005. Dependency is like this year round, except in early summer much of the rain comes from quick thunderstorms so an otherwise sunny day will be dark+pouring and back again in 3 hours. Sagittarian Milky Way (talk) 22:40, 9 June 2011 (UTC)

I don't completely understand your question. What do you mean by "what cloud cover was for each month of the year"? What does "Jan 0/10" mean? --Tango (talk) 19:36, 9 June 2011 (UTC)

They list cloud coverage for all 12 months in "percent of the time that the sky is 0/10ths covered", "percent of the time it's 1/10ths", "percent of the time that it's 2/10ths", 3/10ths, etc. up to 10/10ths., presumably because the instrument that asseses area is not that accurate. Sagittarian Milky Way (talk) 22:40, 9 June 2011 (UTC)

Ok, so where does the error come in? If you are measuring it, then surely you are getting it right... What is it you are actually trying to work out? --Tango (talk) 23:09, 9 June 2011 (UTC)

Ignoring the details, our articles on standard error (statistics) and confidence intervals probably address your question. Looie496 (talk) 22:52, 9 June 2011 (UTC)

...if you can make sense of them, that is. The quality of writing in those articles is pretty pathetic. Looie496 (talk) 22:55, 9 June 2011 (UTC)

Triangular calculation equation

Probably due to lack of sleep, I just can't wrap my brain around what I am sure is a simple problem. I have an array indexed 1, 2, 3, 4... Each index in the array has an integer such that the value in the index is less than the index before it. An example: {5,4,3,2,1}. That is optimal. Each index is exactly one less than the one before it. However, this program sometimes has one (and only one) occurrence where one index will be two less than the one before it: {6,5,4,2,1}. In this case, I want to remove the far right value and distribute it among the other values to get the optimal distribute: {6,5,4,2+1} = {6,5,4,3}. Sometimes, it won't work easily: {6,5,3,2} = {6,5,3+2} = {6,5,4} with a remainder of 1. I am doing this with a loop, removing one column on the right at a time. Isn't there a way, given the number of columns, value of the left column, and the column in which the value is 2 less than the previous column, that I can perform a single calculation to see how many columns I need to remove and distribute? -- kainaw™ 12:41, 9 June 2011 (UTC)

I think it depends on the factorization of the sum, call it p say. If p is a prime then there are only going to be one or two possible arrays. For example with p=23 there are only {23} and {12,11}. If you have a factorization of p then there is a calculation, but without it it's probably not possible.--RDBury (talk) 15:55, 9 June 2011 (UTC)

2ⁿ has only a single representation as a sum of consecutive integers: {2ⁿ}. Gandalf61 (talk) 16:11, 9 June 2011 (UTC)

Thanks, but the problem I was working on doesn't require a perfect distribution. It looks for an optimal distribution in which there is a remainder left over that, compared to the size of the columns, is negligible. As I showed with {6,5,3,2}, the optimal solution is {6.5.4} with one left over. So, given the number of columns (C=4), the size of the left-most column (S=6), and the column in which the error occurs (E=3 if we count them 1, 2, 3, 4), how many columns will be left in the optimal solution (O=3) - and the remainder can be included (R=1). This is an easy problem to solve by iterating over "remove the far-right column and place them on E, E+1, E+2, E+3... until all columns have been filled. If E!=O, do it again." I am trying to get O=f(C,S,E) without the iteration because the size I'm working with is around C=1,000,000, S=1,000,000, and E=250,000. After calculating O and R, I have to go to the next step of grouping the R's together for another task. -- kainaw™ 17:18, 9 June 2011 (UTC)

Now that I'm awake, I can explain why this is hard for me to think about... Assume you look at it and you realize that you need 10 to fill the top row (and also assume the far right column has a value of 1). So, it is easy to calculate that 1+2+3+4 = 10. Therefore, removing the right 4 columns will give you the necessary amount to fill the top row - but that won't work. You just removed 4 columns. You only need 6 to fill the top row now. The correct answer was that removing 1+2+3 = 6. But, you only removed 3 columns this time. You need 7 to fill the top row. The original answer was the correct one. Remove 4 columns and have a remainder of 4. It is the removal of columns that makes it harder than simply calculating 1+2+3+...+n = X for some value X. -- kainaw™ 19:08, 9 June 2011 (UTC)

Take your case {6,5,3,2}. Why can you not go {6,5,3,2}->{6+1,5,3+1}->{7+2,5+2}->{9+7}->{16} with no remainder? — Preceding unsigned comment added by Taemyr (talk • contribs) 19:29, 9 June 2011 (UTC)

The goal is not to trick the problem into a trivial solution. The goal is to find out how many columns are required to fill the incomplete top row. -- kainaw™ 19:36, 9 June 2011 (UTC)

OK. So you can only add points below the gap? (Or rather what you are trying to optimize is maximizing the number of colums, the remainder is irrelevant). Take the case where you need 10 points. This means that your set goes {...12,10,9,8,7,6,5,4,3,2,1}? you remove the one so you are left with needing 8(the value of the one+ one colum less to fill). then the 2, at which point you need 5. After the 3 you need 1, and when you remove the 4 you are done and have a remainder of 4.

If this is correct then:

(n+1)+(n+2)+...+(n+m)=n*m+(1+m)m/2 which will be the value you redistribute if you remove m colums where the least has value (n+1).

To this we must add the number of colums removed so (n+1)*m+(1+m)m/2.

We want to find the lowest m such that (n+1)*m+(1+m)m/2>=target.

0.5m^2+(1.5+n)m-target>=0.

Switching n such that we look at the least value beeing n, rather than n+1, we get

0.5m^2+(.5+n)m-target>=0

So roof(.5+n+sqrt((.5+n)^2+2*target)) columns needs to be removed.

Baring misunderstandings or outright mistakes on my part. Taemyr (talk) 20:19, 9 June 2011 (UTC)

Thanks. I was having extreme difficulty thinking yesterday. I just couldn't make the jump to reducing the columns required to fill as the columns were being used. -- kainaw™ 12:38, 10 June 2011 (UTC)

Tetrahedrons and triangular graphs

I've used triangular graphs before, and the requirements for one (as I know the term, seems there's another) to be valid could be said to be {x,y,z} where x+y+z=100%. I've been trying to picture, without success, a hollow tetrahedron (OK so far!). Then there's some point within the tetrahedron with lines coming from it perpendicular to each of its sides - four of them. At the point they touch the sides, that point is read like a triangular graph. How many unique values does it create, I can't think how many of the 12 values are duplicates? If so, how does that change the requirement for it to be valid? Thanks, Grandiose (me, talk, contribs) 19:23, 9 June 2011 (UTC)

I don't understand this question. Could you explain what you mean by "triangular graph"? —Bkell (talk) 18:12, 10 June 2011 (UTC)

Something like this. So each point in the triangle has three components that sum to 100%. Grandiose (me, talk, contribs) 09:22, 11 June 2011 (UTC)

You reference is an awful graph. The shadows on the font makes things very hard to read. Anyway your triangular graph could just as easily be draw as a standard x,y graph (at right angles) and you can come along afterwards and mark in the derived z coordinate lines. Similarly a hollow tetrahedron could be drawn as a standard x,y,z 3-D graph. Everything else is derived from that - any u v or w coordinates you may choose to invent. My "tetrahedron" will not have the "right" sold angle (0.55 steradians), but will have 0.5pi (1.57)steradians and again you can come along afterwards and mark angled planes of constant u, v, or w. Does this help at all? -- SGBailey (talk) 20:34, 11 June 2011 (UTC)

Other than explaining why no concept occurs in mathematics, not really (it's a bit over me :)). It's the "Similarly a hollow tetrahedron could be drawn as a standard x,y,z 3-D graph." I'm struggling, mostly as to the consquences, as with the original tetrahedron. If our original triangle was actually two values, and a third derived one, and you think the tetrahedron can be shown to be a 3D one, does that mean that the tetrahedron is actually based on three values, and therefore of the 12, it is possible to identify a point with only three? That would be a very useful answer to my question. Grandiose (me, talk, contribs) 20:51, 11 June 2011 (UTC)

A hollow tetrahedron is surface. There are simple functions that will map this surface onto a flat plane - just unfold it. Once on the flat plane, then x,y is sufficient to define a point. Thus two coordinates is still sufficient to define all coordinates on the tetrahedron. However there will now be a mixup of unfolded x and y against whatever the parameters you have on the tetrahedrons edges are - you have 6 edges, so you have 3 triangular graphs abc on the base, ade on one side, bef on another side and cfd on the third side. I've no idea what such a shape could meaningfully plot and I don't know where you get "12" from. -- SGBailey (talk) 23:15, 11 June 2011 (UTC)

The triangular graph is an example of barycentric coordinates. This can be extended to three dimensions. Gandalf61 (talk) 21:27, 11 June 2011 (UTC)

Thanks both, but I don't think I've quite managed to explain clearly enough, although Gandalf's link is the right thing I'm still struggling on the impact. Each of our data points would be a point inside the tetrahedron. If there were lines from that point to each of edges (perpendicularly), now we have four intersection points; we could read off the two values and a third derived one from each. So superficially that makes twelve. However, we could define every point in usual three dimensional coordinates, so it's clear that there are only 3 underlying numbers behind the twelve readings, just as there are actually two behind each point on a triangular graph. Putting that aside from the moment, how many of the 12 are necessarily the same? How do they relate to each other? If we can say that a+b+c=100% for a triangular graph, what similar things can we say about the tetrahedron version? Thanks Grandiose (me, talk, contribs) 15:17, 12 June 2011 (UTC)

Uncountable Godel Theorem

As I understand it, Godel's theorems only apply to logical systems in which it is possible to enumerate all the theorems. Suppose we had a system of uncountably many mutually independent axioms for arithmetic. Then, it would be impossible to enumerate all theorems, or even all axioms, simply because there would be too many of them. Would Godel's theorem, or some modern variant, still apply to this fattened system? (I think that such a system could be constructed as follows: Let 0 stand for PA, and N stand for "for M<N, all the axioms of M plus 'M is consistent.'" Then by induction up the countable ordinals, there must be an uncountable such system, in which all axioms are independent and in some sense self-evident. Is this correct?) Black Carrot (talk) 23:20, 9 June 2011 (UTC)

To clarify, you're asking about Godel's Incompleteness Theorem. Godel has another famous theorem confusingly known as the Completeness Theorem.

To answer your question, yes, the incompleteness theorem requires in an essential way that the theorems can be effectively enumerated. You don't need to go uncountable to see this, though; just let T be the theory consisting of all sentences which are true in $(\mathbb {N} ,+,*,0,1)$. Then it's trivially complete and consistent.

Your method of building an uncountable system doesn't work, though; just by counting, there are only countably many sentences expressible in the language of PA, so it can't go uncountable. The reason your recursive construction breaks is that at some countable ordinal, there's no way to code "M is consistent", since M isn't a computable set. I suspect this happens at $\epsilon _{0}$, but I'm not sure.--121.74.111.168 (talk) 04:53, 10 June 2011 (UTC)

You can go way past ε₀. It's pretty clear what to do up to $\omega _{1}^{CK}$, the first non-recursive ordinal. My understanding is that if you iterate to $\omega _{1}^{CK}$, you get a (non-computable) theory that proves all true $\Pi _{1}^{0}$ statements.

I imagine someone has tried to push it further, but I don't know exactly in what way. Some new idea would be required. --Trovatore (talk) 20:23, 10 June 2011 (UTC)

Interesting. Do you know where I could look to find out more about that? Is that a new result, or has it been known for a long time? Black Carrot (talk) 23:08, 10 June 2011 (UTC)

It seems like I saw a paper, or at least a citation of a paper, that mentioned it, sometime in the last year, but I can't remember the details and I'm not sure even what search terms to use. If I come across it I'll try to let you know. I think it might be a reasonably standard result in the theory of proof-theoretic ordinals, which is something I don't know too much about. --Trovatore (talk) 10:20, 11 June 2011 (UTC)

Try Beklemishev, L. D. (2003). "Proof-theoretic analysis by iterated reflection". Arch. Math. Logic. 42: 515–552. doi:10.1007/s00153-002-0158-7. --Trovatore (talk) 01:21, 12 June 2011 (UTC)

If you feel like trying to prove it yourself (almost always more enlightening than reading someone else's proofs), you might first learn about ordinal notations, if you don't already know about them, and think a bit about how you might do your iteration relative to an ordinal notation. Then think about whether two notations for the same ordinal give you the same theory if you iterate along them. I'm not sure whether they do or not. If they don't, maybe they give the same $\Pi _{1}^{0}$ theory; try to prove that. --Trovatore (talk) 10:24, 11 June 2011 (UTC)