Wikipedia:Reference desk/Archives/Mathematics/2011 January 15

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.

January 15

Sums of squares of normal random variables with the same distribution

Can anyone suggest the quickest way to prove that if $\forall i\in \{1,...,n\},\,X_{i}\sim N(0,1)$ are independent normal random variables, $\sum _{i=1}^{n-1}X_{i}^{2}$ and $\sum _{i=1}^{n}(X_{i}-{\bar {X}})^{2}$, where ${\bar {X}}={\frac {1}{n}}\sum _{i=1}^{n}X_{i}$, have the same distribution? Certainly if they both have the same -type- of distribution, which I believe is chi-square, then I can probably show they have the same parameters, but the second distribution looks a lot messier to work with than the first. Could anybody suggest a quick way of doing this? Thankyou! 86.30.204.236 (talk) 01:40, 15 January 2011 (UTC)

Cochran's theorem is often used in situations like this. Robinh (talk) 07:57, 15 January 2011 (UTC)

Linear algebra: The vector whose components are

$X_{i}-{\overline {X}}\,$

for i = 1, ..., n is the orthogonal projection of the vector whose components are

$X_{i}\,$

onto a certain (n − 1)-dimensional subspace. Because the normal distribution is spherically symmetric, it's just as if we'd looked at a certain other orthogonal projection:

${\begin{bmatrix}X_{1}\\\vdots \\X_{n-1}\\X_{n}\end{bmatrix}}\mapsto {\begin{bmatrix}X_{1}\\\vdots \\X_{n-1}\\0\end{bmatrix}}.$

(The right inner product to use is the one given by the inverse of the covariance matrix—in this case that's just the identity matrix!) Michael Hardy (talk) 19:12, 15 January 2011 (UTC)

Sum of multipliers

Please forgive if this seems very elementary, but I'm reading a paper written by two PhD students and it has the following comment: "Given x and y as the factors of a, we simply use a to determine the sum of x and y." What!? I read this as having a value a (ie: 21) and you don't know x and y. It is not, to my knowledge, possible to calculate the sum of x and y. Even though this paper further defines x and y to be positive integers, there are two possible sets of x,y terms if a is 21: 1*21 and 3*7. One set has the sum 22 and the other has the sum 10. So, is this just me or is there some other possible meaning by this? The paper doesn't define how the they determine the sum of x and y. It just gives an a and then a sum of x and y. The actual value of x and y are not used elsewhere in the paper. -- kainaw™ 04:04, 15 January 2011 (UTC)

Is $a$ constrained in some way? If $a$ is known to be the product of two primes, $x+y$ is uniquely defined given the value of $a$. --173.49.14.139 (talk) 05:19, 15 January 2011 (UTC)

kainaw's example is a product of two primes. The sum is uniquely defined when $a$ is a prime. --COVIZAPIBETEFOKY (talk) 18:03, 15 January 2011 (UTC)

Nevermind. After going over this paper a third time, I can see that their algorithm only works with x and y are powers of 2. Nowhere in their paper do they mention that x and y are powers of two. So, I added that note to the critique. Then, since there is that restriction on x and y, the possible values of x and y are limited to the point of making the calculation of x+y rather trivial. -- kainaw™ 18:11, 15 January 2011 (UTC)

Now you've got me confused. If x is 2³ and y is 2⁵ how do you get 40 rather than 32 or 68 or 130 or 255 from 2⁸? Dmcq (talk) 18:22, 15 January 2011 (UTC)

They are trying to optimize x and y. They are given a. Because x and y are powers of 2, the possible values for them is limited. The algorithm they are using optimized by calculating the sum of x and y - each possible sum. Then, it goes from there. Since the paper didn't claim x and y were powers of 2, I thought that the time required to calculate every factor pair of a would make the algorithm useless. Since they are both phd students, I gave them the benefit of doubt and assumed that I was mistaken rather than both of them. -- kainaw™ 15:00, 18 January 2011 (UTC)

mathematical realism

Is it reasonably conventional mathematical realism to assert that both of the following are true?

• The true von Neumann universe V_true exists as a unique object in some notion of objective reality
• The true real number line R_true exists as a unique object in some notion of objective reality

If both are true, is it also the case that the unique R_true is an element of the unique V_true? If not, and if R_true is a set, then what kind of "universe" is V_true?

One can carry out some construction of the reals in V_true, say with Dedekind cuts starting with the integers as finite ordinals, and call the result (say) V_trueR. This set is of course isomorphic to the true R (added hmm, actually, I'm not sure of that). Is there reason to think that it actually is the true R? That would be horribly ugly, I'd think. Is N_true (the true natural numbers) the same thing as the ω sitting in V_true? Maybe that's not as bad.

Here is a pretty cool talk[1], based on sort of an uber-Platonism that says every model of ZF has its own objective existence.

I can't bring myself to take any of this stuff seriously, but of course there are some pretty smart people out there who embrace it.

67.122.209.190 (talk) 07:26, 15 January 2011 (UTC)

Interesting talk; thanks for pointing it out. I don't agree with Hamkins here, but it's well presented. In particular I don't agree that the view he presents is actually realism at all. If there are these different models, then we should be able to ask, does one of them have a real that another one doesn't? Does one have a set of reals that another one doesn't? Once these questions are admitted to be well-specified, CH must have a definite truth value. Well, granted at least that the powerset axiom is true — a possible alternative view is that the powerset axiom is false and V=HC, the collection of all hereditarily countable sets, and that HC is therefore a proper class. V then contains many models that believe the powerset axiom, but they're wrong about that.

The realist view is actually not quite that V exists as an object. If it existed as an object, it would in fact have to be a set, but we know that it is not a set. Therefore it actually exists as a predicate rather than an object. All of its elements, however, exist as objects. --Trovatore (talk) 09:03, 15 January 2011 (UTC)

I have a stupid question about V. In normal mathematics to make a model of something (like real numbers, product of groups/spaces etc.) we express within ZFC what these models are by some instance of comprehension/replacement; we also make models of ZFC within ZFC. What's confusing me is that if we're not a formalist/constructivist then by making these construction we are already assuming some totality of "all possible sets", i.e. V. Of course, V "is not a set" in that it's not a member of itself, but its still a collection and philosophically we may regard it as a set. Why should the sets "stop at V"? Why can't we go further? Imo the construction of sets can never stop, so by V do we just mean think of some giant collection whose members are called sets together with a binary relation that satisfy the axioms of ZFC and all of mathematics is done within this giant collection? Money is tight (talk) 11:29, 15 January 2011 (UTC)

I believe that yes, that is what Trovatore is saying, V is a giant collection etc. I'm still interested to know where R fits into it. 67.122.209.190 (talk) 19:36, 15 January 2011 (UTC)

What I'm saying is that V is kind of like the way some of the intuitionists think of N; it doesn't exist as a completed totality, but everything in it exists. On this view, the intuitionists weren't wrong, they just stopped too soon. Oh, except excluded middle is true, of course; that's just part of logic. --Trovatore (talk) 20:07, 15 January 2011 (UTC)

"If there are these different models, then we should be able to ask, does one of them have a real that another one doesn't?" In Hamkin's system, for every (class) model M there is a (class) model N extending M and having more reals. Of course this is not a revelation for people who are used to "forcing over V". The main novelty is that Gitman and Hamkins have a relative consistency proof that if ZFC is consistent then their "multiverse axioms" are also consistent. In particular, you won't run into any inconsistencies if you assume in the metatheory that, whenever you have a class model M and you force over it, the forcing extension also exists as another class model. — Carl (CBM · talk) 20:44, 15 January 2011 (UTC)

If you take that view, what you are really saying is that V=HC and the powerset axiom is false. --Trovatore (talk) 20:49, 15 January 2011 (UTC)

I never understood that argument. The powerset axiom is true in every model of ZFC, and I don't see what model you could be looking at when you say that it would be false. The satisfaction relation requires both a sentence and a model. — Carl (CBM · talk) 20:55, 15 January 2011 (UTC)

Take a set x in a wellfounded model M. There is a forcing partial order in M such that x is countable in any M[G], where G is generic for the partial order over M. But now if you take the view that such M[G] is a real thing, then x really is countable, because the witnessing bijection between ω and x contained in M[G] is a real thing. Therefore all sets are countable; therefore V=HC. --Trovatore (talk) 21:00, 15 January 2011 (UTC)

It seems like you are identifying "for every set, there is a model of ZFC containing that set in which the set is countable" with "there is a model in which every set is countable". One thing that unfortunately seems to be missing in the Gitman/Hamkins paper is a rigorous description of the metatheory, but presumably one can only quantify over models and sets within models. So presumably "For every M, for every S in M, there is a model N extending M, in which S is countable" is a legal statement in the metatheory, but "S is countable" and "V=HC" are not legal statements. It would be nice to see a more rigorous treatment of this. — Carl (CBM · talk) 21:19, 15 January 2011 (UTC)

No, I'm certainly not saying there is a model (of ZFC) in which every set is countable; that's trivially false. I'm saying that if you take the view described, then you are asserting that every set is in fact countable. --Trovatore (talk) 21:23, 15 January 2011 (UTC)

I think that from that viewpoint, "every set is countable" is more like "every polynomial has a root". On the one hand, we know that we can always adjoin a root to a polynomial over any field containing its coefficients. On the other hand, the question "does that polynomial in fact have a root?" is pretty meaningless, and nobody ever says "you know there are really no irreducible quadratic polynomials". Instead, "having a root" is best understood as a binary relation between a polynomial and a field that contains its coefficients, not an intrinsic property of the polynomial.

Similarly, from the viewpoint being discussed, "is countable" is best understood as a binary relation between a set and a model of set theory containing the set. — Carl (CBM · talk) 21:52, 15 January 2011 (UTC)

No, that just doesn't work, in an account that wants to be considered "realist". If there is a bijection between the set and ω, in any model, then the set is countable, period. --Trovatore (talk) 21:55, 15 January 2011 (UTC)

Most mathematicians are realists about algebraic objects, but they don't worry about the fact that every polynomial splits in an extension field. If I told some mathematician that she was actually asserting "Every polynomial has a root", she would almost certainly explain that a question like "Does x₂+1 have a root?" is meaningless until we specify what field we are talking about. What she means is that we can't even write "Every polynomial has a root" as a theorem in the metatheory, we have to write "Every polynomial has a root in some field".

Similarly, "is this set countable?" is only a valid question for the metatheory once we have specified a model of set theory to test. There's no reason that someone who knows that every set is countable in some model would agree that they are asserting "every set is countable", because this isn't even something that could be asserted in the metatheory. — Carl (CBM · talk) 22:20, 15 January 2011 (UTC)

I'm not talking about metatheories and such. That language only serves to muddle something that's completely clear at an intuitive level. Take a set x, and take the natural numbers. Can the elements of x be matched up with the natural numbers, or not? They either can or they can't; it isn't necessary to relativize to a model. It's just either true or false. --Trovatore (talk) 22:32, 15 January 2011 (UTC)

But the same analysis would allow a field theorist to prove "Every polynomial has a root" – given a polynomial, she can always find a root in the splitting field, so the polynomial has a root, right? This is clearly an improper deduction, because it mixes object-level and meta-level statements. The deduction of "Every set is countable" from "Every class model of set theory embeds as a countable set in another model" is invalid for exactly the same reason. I think you are reading "Every set is countable" as a just a synonym for the different statement "Every set is countable in some model". But that isn't correct if we have a metatheory that cannot quantify over sets. So perhaps you would assert that "Every set is countable in some model" implies "Every set it countable", but that doesn't mean that someone who is working in a different metatheory would even be able to express that implication. — Carl (CBM · talk) 23:57, 15 January 2011 (UTC)

If you have a metatheory that cannot quantify over sets, you're not a realist. --Trovatore (talk) 02:33, 16 January 2011 (UTC)

(I shouldn't say "sets" exactly. If you have a metatheory of models that can't quantify over the objects in the models, you're not a realist.) --Trovatore (talk) 02:40, 16 January 2011 (UTC)

The motivation that Hamkins claims for the Gitman/Hamkins work on multiverses is to treat forcing over V (Baumgartner-style forcing) as real instead of fictitious. It's a pluralistic realism, sure, and somewhat analogous to plenitudinous platonism, but it's still a form of realism. Realism only holds that mathematical objects exists in some sense independent of the human mind; it does not imply there is only one field, only one geometry, or only one universe of sets. The other option – to treat forcing extensions of V as purely fictional – is less "realistic" in a clear sense. — Carl (CBM · talk) 02:55, 16 January 2011 (UTC)

Realism requires that there be only one truth. If you have a set, and you can match up its elements with the naturals in any model (that has something isomorphic to the true naturals), then that set is countable, period. So if you're a realist, and you also insist on all these forcing extensions existing in a real sense, then you must accept that all sets are really countable, even though there may be useful models that cannot witness their countability. --Trovatore (talk) 03:02, 16 January 2011 (UTC)

← As I have always understood realism, there is nothing in it that requires only one truth. For example, "every pair of lines has a point of intersection" is neither true nor false "in reality", its truth value depends on what geometry you choose. This holds even if we believe, as realists, that all the models of various geometries actually exist independent of humanity. The point here is that we recognize now that there is nothing in the mere concept of "line" that answers the question whether they all intersect with each other. The concept of "set" is similar: there is no compelling evidence, at the moment, that the mere concept of "set" is enough to address various set-theoretical questions, and quite a bit of evidence to the contrary. — Carl (CBM · talk) 03:10, 16 January 2011 (UTC)

Well, in that example you don't have different truths, just different notions of "line". And yes, you can also have different models. But if you're a realist, you have to be able to compare the models, or at least explain why not. If two models (subject to some minor correctness conditions) have the same object, and one thinks it's countable and the other doesn't, then the one that thinks it's countable is correct, period, because its witness that the thing is countable shows that it really is countable.

So from the point of view being described, all sets are really countable. --Trovatore (talk) 03:15, 16 January 2011 (UTC)

So you also accept that every polynomial has a root, period? — Carl (CBM · talk) 03:17, 16 January 2011 (UTC)

Carl, that is not analogous. Whether something is countable or not is a purely structural question. Can you match it up with the naturals? You either can or you can't. It has nothing to do with metatheories or set-theoretic universes. --Trovatore (talk) 03:21, 16 January 2011 (UTC)

I find it completely analogous. Whether a polynomial has a root in a field is a purely structural question: is there an element of the field such that, when you plug it into the polynomial, you get 0. (All you have to do is raise the root to powers, multiply by coefficients, and compare with 0; presumably, if you know what the root is, you can do this without knowing about any other fields or metatheories,) According to your analysis, if a polynomial has a root in any field, that field is "right", and we can just say "the polynomial has a root". Fields that don't have a root for a particular polynomial happen to be wrong, but they don't matter, because once any field has a root for the polynomial then we can assert that, really, the polynomial has a root. — Carl (CBM · talk) 03:31, 16 January 2011 (UTC)

That's fine — in that sense, yes, it has a root. But the difference is that we don't traditionally say that that is what we mean by "it has a root", period. On the other hand, the notion of being matchable-up with the naturals is directly accessible to the intuition (as being well-specified; I'm not claiming your intuition necessarily gives you the right answer). And by that natural meaning, we must absolutely maximize the possible countings. If there is one in any model, then there is one, period.

Nontrivial forcing extensions, though, are not (I believe) models at all, because they do not exist at all. Not in any sense. It is useful to sometimes talk as though they exist, and we know in what ways we can get away with it, because of alternative formulations such as Boolean-valued models. --Trovatore (talk) 04:27, 16 January 2011 (UTC)

It's not clear to me that being matchup-able with the naturals is a well-specified notion; it depends on the notion of an arbitrary function, which is ambiguous even given the natural numbers. The cleanest way to solve the ambiguity problem, for realists, is just to fix some arbitrary model of ZFC and call it V. In this way "all sets" becomes a shorthand for "all sets in the model at hand". This doesn't commit a realist to the notion that there is no other model of ZFC with more sets. It also resembles, somewhat, Zermelo's idea that the ordinals are so infinite that not even a class model of ZFC can contain them all, because as soon as a class model exists as an object, more ordinals appear above it.

There's also a pragmatic question, related to plentitudinous platonism: if enough mathematicians work with some kind of object, realists have to eventually accept that the object is real, simply because realists are committed to the proposition that all mathematical objects are real. For example, the field with one element will be an interesting problem for realism sometime soon. — Carl (CBM · talk) 05:07, 16 January 2011 (UTC)

I disagree that there is any ambiguity. I say it is completely well-specified. --Trovatore (talk) 05:10, 16 January 2011 (UTC)

Oh, OK, here's the actual point: "depending on the notion of an arbitrary function" is not problematic — if you are a realist about arbitrary functions!!! This is exactly why the "plenitudinous platonist" view is not actually realism at all.

If you try to make it realism, then you are forced to accept the notion that all sets are countable. That's a possible view; Dana Scott has hinted at something of the sort. But I think it's ontologically impoverished. --Trovatore (talk) 05:22, 16 January 2011 (UTC)

It seems like you're looking not just for realism, but for some kind of monistic realism; I don't have a name for it. The Gitman/Hamkins approach has a pluralistic realism about arbitrary sets which says that each model of ZFC corresponds to a unique concept of "arbitrary set", each of which is as valid as any other, and that many such models really exist. From that viewpoint "all sets are countable" is a meaningless phrase, neither true nor false. This is what we already do with the concept of "arbitrary line", for example; we don't expect that there is a unique concept of "line", and we don't claim that non-Euclidean geometries are fictional. — Carl (CBM · talk) 05:44, 16 January 2011 (UTC)

It's not analogous. If you take arbitrary functions seriously as real objects, there is no possible ambiguity. The universal rule is just to maximize which ones you allow; then pluralism is not possible, unless the ones that there are simply cannot be collected into a completed totality (that is, that the powerset axiom is false). --Trovatore (talk) 07:43, 16 January 2011 (UTC)

"The powerset axiom is false" has the same metatheory/object theory issue as "every set is countable". It's a statement that can only be true or false in a model of set theory; if the metatheory isn't set theory then we can't assert it in the metatheory. This has nothing to do with whether we consider functions to be real objects.

By comparison, in any field we can assert "every nonzero x has an inverse" but we can't assert this in the metatheory we usually work in, because the metatheory isn't a model of the field axioms. It's just nonsense if I walk up to someone and say "You know, every nonzero x has an inverse". Similarly for "the powerset axiom is false". It's a statement that only has a meaning in the context of a model. — Carl (CBM · talk) 13:38, 16 January 2011 (UTC)

No, this is not analogous. If you're a realist about sets, then I think in your terminology, your metatheory is essentially required to "be set theory" in your terms. Or to be something that includes set theory, or encodes it. If arbitrary bijections are real objects, then between an arbitrary set and the naturals, there either is a bijection or there isn't. No model required. --Trovatore (talk) 20:16, 16 January 2011 (UTC)

If lines are real objects, does the mean that for any two lines, either they intersect or they don't, even if one is in a hyperbolic plane and the other is in the Euclidean plane? Just because things are real does not mean that they can be handled with no regard for context. It's common to think of sets as not requiring a model of set theory, but not lines or elements of fields – but this is just a matter of convention. — Carl (CBM · talk) 02:51, 18 January 2011 (UTC)

Huh? Of course any two given lines either intersect or they don't. --Trovatore (talk)

If one of them is in the real Euclidean plane and another one is in the Fano plane? There's no incidence relation that could test for intersection. I picked the example because it's not a well-posed question: there's not even a definition of what it would mean for two such lines to intersect, since intersection is only defined relative to a given geometry. Nevertheless all the lines involved exist, for a realist. — Carl (CBM · talk) 04:04, 18 January 2011 (UTC)

If they're in disjoint structures, then they don't intersect, clearly. I suppose your point is that the structures could be chosen to have overlapping universes, so they could intersect for some silly reason. But that's just a quibble.

That's not going to get you ambiguity as to whether a set is countable or not. If you're a realist, the set is a real thing, its elements are real things. Either there is, or there is not, a real thing that matches the set's elements up with the naturals. If there is, anywhere, then the set is countable. --Trovatore (talk) 04:12, 18 January 2011 (UTC)

My point is that if they are in different structures the very concept of "intersection" is undefined. You might as well ask whether the number 5 intersects the color blue, or what you get by multiplying elements of two different groups. There's no definition that would apply to whether a line in the real plane intersects a line in the Fano plane, so they neither "intersect" nor "don't intersect", because both of those are are undefined. I describe this by saying the question of intersection is ill-posed.

Similarly, the concept of "countable" is only defined relative to a model of set theory. If you work in a set-theoretic metatheory, then you can express these things in the language it gives you. But there's nothing about realism itself that forces there to be only one model of set theory, any more than there is something in realism that requires there to be only one geometry or only one group. Both the real plane and the Fano plane exist for realists, they just give incompatible concepts of geometry. It's neither true nor false that "every pair of lines intersects", even in the metatheory that you are talking about. — Carl (CBM · talk) 04:24, 18 January 2011 (UTC)

It's frustrating that I can't make you see this, Carl. It's so very clear. I wonder if you're seeing it and just not wanting to admit it.

There is no model of set theory involved in saying whether a set is, in an absolute sense, countable. It's a question of pure structure. The difference between set theory and geometry is that set theory is essentially the distillation of pure structure; if you have structure around, you get set theory back. --Trovatore (talk) 04:31, 18 January 2011 (UTC)

I do know the position you are arguing, and it has its advantages. I am pointing out that it is not the only form of realism (=mathematical objects really exist). We know from experience that which sets exist in a particular model can vary greatly. For this and other reasons, it's far from clear that the concept of "set" as pure structure is enough to uniquely describe a model. We already have examples, such as geometry, where we know that the concept of a "plane" is very far from being categorical. As I understand it, the point of the Gitman/Hamkins work is to treat sets in a similar way: keep the realism, but abandon the idea that the natural-language term "set" has enough meaning to uniquely describe a model. I think there is an analogy between "imaginary" numbers and "imaginary" forcing extensions there. — Carl (CBM · talk) 04:41, 18 January 2011 (UTC)

I'm repeating myself here, but I just don't think it works. You need some unmotivated reason that you're not allowed to look inside the different universes and compare them. I don't believe that this is realism. Or, as I say, it could be realism, if you believe V=HC. --Trovatore (talk) 04:48, 18 January 2011 (UTC)

To continue the repetition, you can only quantify over sets if you're working in set theory. Things like the definition of "countable" are phrased in the language of set theory, which is our object theory when we study set theory. There is no reason that the metatheory we use must also be set theory (this issue is often invisible in set theory books, which essentially ignore the entire issue of what metatheory they are working in, and only work in the object theory. This means that we might as well assume that we are always working in some fixed model of ZFC.) The very definition of V is made in the object theory of set theory, not the metatheory, and there is no reason to think that "V" has to refer in the metatheory. If "V" does not refer, then the question whether V=HC is ill-posed.

What I think you're trying to say is that if we believe in natural language that some "sets" exist, then we can ask about properties of these "sets". But it's far from clear that the natural-language word "set" has a well-defined meaning if we don't just pick a model of set theory and call its elements sets (same problem with "ordinal"). In the multiverse approach, one would abandon the idea that "V" refers to anything in the metatheory (after all, "V" is an object theory definition). Therefore one might not assert, or believe, that V=HC, because the statement would be ill-posed. This is not to say that you couldn't interpret what they say as "V=HC", but it is not something that a multiverse theorist would be forced to assert. — Carl (CBM · talk) 05:20, 18 January 2011 (UTC)

Well, they don't have to be sets, per se. It's just structure. As I say, you get sets back, in a categorical way level-by-level, from pure structure.

Let me put it another way: If it's the case that all these forcing extensions exist, then the continuum does not exist. The continuum understood as a single structure that encapsulates all possible ways of choosing some natural numbers and not-choosing others, all ways from any context whatsoever. I do insist that this is an irreducible requirement for saying that the continuum exists in a realist sense, and it is clear that if these forcing extensions exist, then the continuum cannot. That is what I would express by saying the powerset axiom is false and V=HC. You can put it in other language if you like, but it is still an ontological restriction. --Trovatore (talk) 07:24, 18 January 2011 (UTC)

← Under that reasoning, geometries doesn't exist, and numbers don't exist. There's more than one concept of number (I would say every field is a different one), but this doesn't stop them all from existing separately. We just don't try anymore, in the metatheory, to make a field that has "all possible numbers" from every context whatsoever. We know that given any field we can always add a lot more transcendentals, so there is no universal field.

This is meant to illustrate there is a difference between (1) something not existing at all and (2) more than one version of the thing existing. We no longer think that "number" is enough, on its own, to uniquely specify a model. Similarly, it's not all clear that "all sets" uniquely specifies anything. This may be an ontological restriction, but it's still compatible with realism, although perhaps not the form you're arguing for. — Carl (CBM · talk) 12:30, 18 January 2011 (UTC)

Hmm? no, nothing I said implies geometries don't exist or numbers don't exist. Sure, lots of things exist separately. But if a set of naturals is a real thing, then for every natural, it's either in the set or it isn't. If a "candidate continuum" is a real thing, then all of its elements are things such that every natural is either in it or not. For it to be the true continuum, it must comprise all possible choices. If you take another putative continuum from another context, and take a set of naturals from it in that context, then the first putative continuum must have a corresponding set in its context that makes exactly the same choices about the naturals.

If there is no such object, then the continuum does not exist. This is all very simple. People who try to obscure it with talk of "multiverses" are simply not realists. --Trovatore (talk) 19:50, 18 January 2011 (UTC)

Well, from a first-order point of view, "all possible choices" may be a countable set, if I'm not mistaken (you have to be able to write down a formula for each choice). But, I'd expect realists to be ok with infinitary theories and metatheories (I mean theories with infinitely long sentences), which supposedly give rise to unique models even for set theory, though I'm not sure why that is (I'd have thought there were still too many choices to make). 67.122.209.190 (talk) 07:19, 20 January 2011 (UTC)

Reviving an old topic: Ambiguity in Number Theory

As long as we're talking about realism, let me return to this old question. My question was about ambiguity in number theory versus ambiguity in set theory, and I feel like it was never properly addressed, or, if it was, no one bothered to point out that my last post in that section was an incorrect perception of the presented arguments.

My intuition that number theory should be an unambiguous framework in which no statement can conceivably be thought to be absolutely unanswerable is due to the fact that all of the objects considered directly in pure number theory can be named within a finite number of steps. This includes all of the natural numbers, sums, products, exponents, etc. Obviously, 'finite number of steps' is a term that can easily be misinterpreted in some models of axiomatic systems intended to represent number theory, but we would reject such models as clearly ludicrous. We know what we mean be the term 'finite'! Just because we can't state it as precisely as we may wish we could axiomatically, doesn't automatically mean it is an ambiguous concept!

On the other hand, set theory doesn't seem to present itself any 'natural' idea of what should be 'clearly true'. There are no clear (axiomatic or otherwise) principles on which we can definitively state about a model that it has "not all possible sets", or "has some 'bad sets'", or in some other way is clearly incorrect.

(Last time I brought up the specific example of CH, but I was not really interested in the specific case; I was just pulling out a generic unanswerable question. I think my discussion got a bit lost with Trovatore arguing that CH does have an undiscovered definite answer.)

Are these ideas ludicrous? Are there serious mathematicians who have stated similar ideas with more precise reasoning, while avoiding such silly arguments as stating that there is only one model of number theory within a given model of set theory, up to isomorphism (unless, of course, they can explain why that argument isn't silly)? Are there serious mathematicians clearly opposed to this idea that number theory is unambiguous, or that set theory is ambiguous, with well-reasoned arguments against the notion? The anon above posted a set of lecture slides by Joel David Hamkins, who appears to agree with my position about set theory. --COVIZAPIBETEFOKY (talk) 17:29, 15 January 2011 (UTC)

This is a reference desk rather than a discussion board. There isn't any real problem with discussing something like his once, but there is no good reason to start it up again. Dmcq (talk) 18:17, 15 January 2011 (UTC)

My question was never addressed. It's not a request for a discussion so much as a request for reference material in the stated direction(s). --COVIZAPIBETEFOKY (talk) 18:19, 15 January 2011 (UTC)

I think the best-known article on set-theoretic Platonism is Penelope Maddy's "Believing the axioms"(Part 1part 2). For the view that number theory is ambiguous and/or bogus (in particular, the exponential function $x\mapsto 2^{x}$ is not total and the further reaches of the so-called primitive recursive functions do not exist), see the papers of Edward Nelson here. This talk[2] is a fun place to start; he also has an entire book "Predicative arithmetic" on the theory, available here.

It is certainly not the case that number theory (let's take this to mean sentences in the same signature as Peano arithmetic) deals only with finite objects: the theory's quantifiers range over the completed totality of all the natural numbers, and finitists consider the very concept of such a completed infinite totality to be bogus. It's hard to ascribe meaning to, say, a $\Pi _{0}^{100}$ sentence without reference to the infinite. (Correction: I meant $\Pi _{100}^{0}$) 67.122.209.190 (talk) 18:23, 15 January 2011 (UTC)

Thanks a lot; I'm glad someone finally understands what I'm looking for. :)

Maybe I'm not being clear about what I mean by "number theory" (and in retrospect, understandably so, since my definition is probably nonstandard). I think my definition lines up with yours in Peano arithmetic, though; I'm referring to a collection of statements that quantify over natural numbers alone. Any statement that quantifies over collections of natural numbers is excluded from my definition of a number-theoretic statement. So the objects quantified over are all finite. And, though we can have nested quantifiers to a degree which, as you say, would make the statement difficult to interpret without reference to infinite sets, we could still say that any statement with a single quantifier is either true or false, and then when you add a second quantifier, that asserts the existence/universality of a natural number making the inner statement true, etc. So absolute truth as a consequence of the fact that all objects are unambiguously describable (at least in theory) does not seem to be lost. --COVIZAPIBETEFOKY (talk) 18:36, 15 January 2011 (UTC)

Sure, the natural numbers in PA are all finite, but PA is still an infinitistic theory because its quantifiers range over an infinite set. As I understand it, that infinitism was why the Hilbert program aimed to prove the consistency of PA in PRA, which has no such infinitary quantifiers and was considered more finitistically acceptable. Nelson of course rejects even PRA. 67.122.209.190 (talk) 18:44, 15 January 2011 (UTC)

Further, there are interesting formulas that only deal with natural numbers but that can't be expressed in PA, for example the truth predicate T([φ]) which says whether an arbitrary arithmetic formula φ is true or false ([φ] refers to φ's Gödel code). By Tarski's indefinability theorem, T can't be expressed as an arithmetic formula. But, it can be expressed as a hyperarithmetic formula involving set quantifiers. 67.122.209.190 (talk) 18:53, 15 January 2011 (UTC)

Peano's axioms aren't enough for ordinary arithmetic without even invoking Gődel, see Paris–Harrington theorem for instance. BTW Arithmetical hierarchy describes that notation above if you were wondering about it. Dmcq (talk) 19:01, 15 January 2011 (UTC)

The Paris-Harrington theorem can certainly be stated in the language of Peano arithmetic; the PA axioms merely can't prove the theorem. But the truth predicate can't even be stated in PA's language. 67.122.209.190 (talk) 19:28, 15 January 2011 (UTC)

Uh, yeah, if I'm understanding that article correctly, I would not qualify a $\Pi _{0}^{100}$ statement as being a pure number-theoretic statement, unless it can be made equivalent to a statement which only quantifies over natural numbers (am I incorrect in thinking that can't always be done?). I would qualify a $\Pi _{100}^{0}$ statement as falling in my category, though. --COVIZAPIBETEFOKY (talk) 19:22, 15 January 2011 (UTC)

Oh wait, I got the subscripts/superscripts reversed further up. I meant a sentence with 100 nested quantifiers ranging over the naturals, which is an arithmetic formula in the usual sense. 67.122.209.190 (talk) 19:28, 15 January 2011 (UTC)

Interesting. I'm not sure whether I would consider such a statement to be "number-theoretical" (again, by my definition, not by some other established standard). --COVIZAPIBETEFOKY (talk) 19:10, 15 January 2011 (UTC)

As I've said before, what I'd really be interested to read about are mathematicians who accept the notion of number theory, but would reject the notion that there is no ambiguity to be found in the truth or falsehood of a given statement of number theory. I think I'm seeing that no one really knows of anyone who holds such a position, which wouldn't surprise me, since, as I've explained, it seems like a difficult position to defend (again: I'm not saying it can't be defended; I'm asking for referral to anyone who has made such a defense. If you're reading my posts as being very close-minded and not worth such a referral, then you're misinterpreting them.). If anyone has any other contributions, I'm certainly all ears. --COVIZAPIBETEFOKY (talk) 19:10, 15 January 2011 (UTC)

I guess I don't know what you mean by "accept the notion of number theory". Nelson is a formalist who doesn't have any problem with the concept of Th(PA) as a set of sentences (although he also thinks it's an inconsistent theory). He just doesn't think PA describes the true natural numbers (i.e. he thinks PA is not merely incomplete, but actually false). 67.122.209.190 (talk) 19:28, 15 January 2011 (UTC)

Stepping back a level, I don't think rejection of PA is really that uncommon a position. Lots of constructivists reject classical logic and would say plenty of PA formulas have no truth value. I think there is a view that various instances of the halting problem (all $\Pi _{1}^{0}$ formulas) have no truth value. 67.122.209.190 (talk) 19:31, 15 January 2011 (UTC)

There are really very few constructivists among mathematicians, though. — Carl (CBM · talk) 22:27, 15 January 2011 (UTC)

Re COVIZAPIBETEFOKY's original question. Each particular number can be described in a finite number of steps. Say that a property of a number is "decidable" if, given a particular number, you can always decide whether the number has that property, in a finite amount of item. Now if we know that there is a number with some decidable property, we can just search for a long time until we find it. However, if we think that there is not any number with a certain decidable property, we cannot test every natural number to be sure. This is where the undecidable problems in number theory arise: they concern statements that require somehow looking at all the numbers. The fact that each particular number can be obtained in a finite number of steps doesn't help when there are infinitely many numbers to look at. — Carl (CBM · talk) 22:27, 15 January 2011 (UTC)

Regarding a later question of COVIZAPIBETEFOKY about ambiguity, the first thing that comes to my mind is the study fragments of arithmetic. For example, in reverse mathematics, people often work with systems much weaker than Peano arithmetic. These people would accept perfectly well the existence of a standard model of arithmetic, but because they are working only with weak axiom systems, various familiar properties of the standard model might be false in an arbitrary model at hand. For example, it is not always the case that if the naturals are split into finitely many pieces then one piece is infinite, if the axiom system is sufficiently weak.

In this setting there is an "ambiguity to be found in the truth or falsehood of a given statement of number theory". The ambiguity arises because the axioms being assumed are too weak to decide the truth of the statement, and so we have to treat its truth as unknown when we are given an arbitrary model. — Carl (CBM · talk) 22:39, 15 January 2011 (UTC)

This is interesting stuff, guys. Thanks a lot. :) --COVIZAPIBETEFOKY (talk) 01:20, 17 January 2011 (UTC)