Talk:Axiom of choice/Archive 1

This is an archive of past discussions about Axiom of choice. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Archive 2

Archive 3

→

Archive 5

Originally from User talk:CSTAR, later moved to talk:axiom of choice, then archived

Thanks. That helps quite a bit. Sorry to keep bugging you, but you seem like a person who really knows his (or for all I know her) stuff. Are you by chance familiar with the axiom of choice? It's been a recurring thought of mine over the past year, and I just can't seem to get why there's such a fuss over it.

According to mathworld, the axiom of choice states: "...given any set of mutually exclusive nonempty sets there exists at least one set that contains exactly one element in common with each of the nonempty sets."

It seems to me that's equivalent to "Given any set of mutually exclusive nonempty sets, $S=\{S_{\alpha }\}_{\alpha \in A}$ , there exists a function $\phi :A\to \cup S$ such that $\phi \left(\alpha \right)\in S_{\alpha }$ . After all, the image of $\phi$ would be the set required.

But that seems like it would be easy to do. Let $U=\cup S$ and let $M:A\to U$ . Further, let $M_{\alpha }:U\to S_{\alpha }$ . Then wouldn't $\phi \left(\alpha \right)\equiv M_{\alpha }\circ M\left(\alpha \right)$ be just the map desired? It sure seems that way to me. Where have I gone wrong? –Floorsheim 20:34, 20 Aug 2004 (UTC)

(Butting in) No, unless the U are disjoint, you haven't defined a function. But really these are kind of entry-level questions. Non-separable Hilbert spaces can be shown to exist by cardinality arguments (separable spaces can't be larger than the cardinality of the reals). If you had an uncountable orthonormal basis, that would be an inseparable Hilbert space. But probably one can't apply this in physics in a reasonable way. Charles Matthews 20:51, 20 Aug 2004 (UTC)

As I mentioned previously, most spaces which occur in Analysis are separable. However, in some sense, non-separable ones are unnavoidable. For insatnce, the the algebra of all operators on a separable infinite dimensional space has naturally occurring irreducible representations on non-separable spaces.CSTAR 21:01, 20 Aug 2004 (UTC)

Somehow the transmission got lost. I was satisfied (for now anyway) by the previous response to the separability question although it's nice to have another example. My new question is about the axiom of choice. And, yes, the $S_{\alpha }$ are assumed to be disjoint (as in mutually exclusive). –Floorsheim 22:25, 20 Aug 2004 (UTC)

How do show the family

M_{\alpha }:U\rightarrow S_{\alpha }

exists which satisfies your conditions? It boils down to the same question.CSTAR 22:29, 20 Aug 2004 (UTC)

I see your point. Why is it, then, that there is so much hesitation concerning the axiom of choice? Going back to the original statement from mathworld of it, "...given any set of mutually exclusive nonempty sets there exists at least one set that contains exactly one element in common with each of the nonempty sets." Such elements do exist, so a multiplicity consisting of them exists. Why are people so hesitant to put that multiplicity into a set? –Floorsheim 17:20, 21 Aug 2004 (UTC)

(Butting in) the issue with the axiom of choice that many "unpleasant" constructions in mathematics require it, most notably that of non measureable sets. If you don't assume the axiom of choice, then you can construct a model in which all sets are measureable which seems, apriori, like a nice boon, you don't have to think about measurability problems etc. It also implies that any construction of a non measureable set would have to use something like the simple construction, transfinite induction, or something of the sort.

I am not really a fan of this, though. Removing the axiom of choice wrecks havoc on cardinal arithmetic, renders the Hahn-Banach theorem wrong in non-separable spaces etc. Overall I think the mathematics is better off with the axiom of choice. Gadykozma 18:05, 29 Aug 2004 (UTC)

Gadykozma: I generally agree with you, but it would be foolhardy I think to adopt too cavalier an attitude towards this. Yes, the axiom of choice makes life easier but that can be a risky road to take -- If it's easy proofs you want, why not assume 1=2? I know this is not what your saying, but a in dialectical discussion, this challenge has to be confronted somehow.CSTAR 23:02, 29 Aug 2004 (UTC)

I am not sure what you mean here when you say "challange". I think there are some separate issues here:

Is the axiom of choice true?
Is the research of what depends on the axiom of choice important?
Is mathematics better off assuming or not assuming the axiom of choice?

For the first, I have no clue. This requires physical or metamathematical arguments, and I have niether. For the second, I say obviously yes, since this shows that a given part of the argument (say the use of Zorn's lemma in Hahn-Banach) is important. Knowing which parts of a proof are important and why is what mathematics is all about, in my opinion. As for the third, I think the version of mathematics with the axiom of choice richer, and this is the test to take. On the other hand, mathematics assuming 1=2 would be much poorer than current mathematics ;-) Gadykozma 04:49, 30 Aug 2004 (UTC)

Some issues, Gadykozma. First off, if the axiom of choice is a priori false, then assuming it to be true would be a contradiction. In that case, anything that follows from 1=2 also follows from the axiom of choice—since any statement follows from a contradiction. Second of all, although I can't say for certain seeing as I'm not a mathematician, I presume that, for the most part, mathematicians are concerned with discovering what is true or coming as close as they can to doing so—not with putting together an interesting or rich story. That being the case, the truth of the axiom of choice is crucial to whether mathematics is better off with or without it. –Floorsheim 17:37, 30 Aug 2004 (UTC)

Floorsheim, I will first answer your general question "what mathematicians want" and then specifically about the axiom of choice

What is mathematics? The formalist view, which is probably the majority view among mathematicians, is that mathematics is about inferring theorems from axioms. No matter how unrelated to real life the axioms are, as long as the formal deduction is good, it's good mathematics. So when you say "what is true", I say that the claim "axioms A,B and C lead to theorem D" is a true claim. For example, the claim "The Zermelo-Frenkel axioms + the 0=1 axiom lead to the result that all the greek have blue eyes" is a good mathematical claim (I guess you heard this before but thought it was a joke). This "everything goes" approach means that you need something external to judge a given mathematical theory. This can be its applicability, but it can also be its interest value.
Now for the truthness of the axiom of choice, which is really a question in epistemology. There is a proof that the axiom of choice is independent from the rest of ZL axioms (there are some caveats, I think). So you cannot construct a proof that its either true or false unless you make extraneous assumptions. How would such assumptions look like? Practice has shown that practically any obvious claim is provable by ZF. In fact almost all of mathematics follows from the ZF axioms, and other axioms that have been propsed (say the continuum hypothesis) are far more dubious than the axiom of choice. So the current state of things is that there is no obvious approach from within mathematics to attack this problem. That's why I say it's a problem in epistemology: it is not clear whether determining if it's true or not is within human grasp at all, nor is it clear that the question is meaningful (physically speaking). Gadykozma 19:38, 30 Aug 2004 (UTC)

I see the appeal of your view; it makes things nice and tidy to say that mathematics is nothing more than the study of formal deductions from given assumptions. However, I don't think it is completely accurate. I agree that most mathematicians concern themselves with proving things within previously defined axiomatic systems. But there are also those who define the axioms in the first place. This latter job, while still a mathematical one, does not fit your description--especially when you note that, in many cases, axioms are specifically set up to mimic something that the mathematician already knows about. For example, most of us—mathematicians included—know about natural numbers and facts concerning them before we are ever exposed to an axiomatic version of them. If a given axiomatic version of the natural numbers leads to statements that are obviously false concerning the natural numbers we have this prior knowledge of (perhaps that there exists a largest natural number), then we would say that that system of axioms does not correspond to the natural numbers. I think a more inclusive description of mathematics is that it is the study of certain types of systems—for which axiomatization is an extremely useful and widely-applied tool.

ZFC is supposed to be an axiomatized version of general mathematical deduction. Its job is to, when combined with first-order logic, derive all mathematical reasoning that may take place. Mathematical reasoning, like natural numbers, is something we already know a little about. The job of ZFC is to be a list of statements from which all and only valid mathematical deductions (of the sort we are already aware of) follow, using first-order logic. If it does not do this job, then it is inadequate. Now it is either the case that there is no system to which the axiom of choice does not apply or it is the case that there is at least one system to which the axiom of choice does not apply. In the event of the latter, then ZFC is no good and should only be viewed as a restrictive set of axioms that apply only to certain systems. Again, the pertinent question concerning ZFC is not whether or not it is interesting but whether or not it is an accurate, fully general model of mathematical reasoning.

It seems to be your view that this is undecidable, at least for a mathematician. Perhaps this is the case. But it also may not be the case. Suppose, for instance, that the negation of the axiom of choice contains a hidden contradiction. Or suppose that ~~the statement "The axiom of choice applies to all systems"~~ [the axiom of choice] contains a contradiction. Either scenario would decide things clearly. –Floorsheim 03:06, 1 Sep 2004 (UTC)

Floorsheim, it is known that the axiom of choice is independent. In other words, the axiom of choice does not contain a hidden contradiction, nor does its negation. I don't understand you last points and specifically I don't understand what you mean when you say "system". Do you mean a model of set theory? Gadykozma 19:46, 1 Sep 2004 (UTC)

I could be wrong, seeing as I've never actually looked at them, but I'm pretty sure those independence proofs presume that there are no internal contradictions in either of the target propositions. I've read multiple times that the verdict is still out as to whether ZF contains hidden contradictions. By your reasoning, it shouldn't be.

As far as my use of the word "system," please disregard it. The axiom of choice is stated as something that is true for any and all families of sets; it is redundant to try to generalize further. I only used the phrase in the first place to make my point more clear. If it doesn't do this, forget I mentioned it. –Floorsheim 01:04, 2 Sep 2004 (UTC)

What these proofs assume (and I am definitely stepping out of my knowledge here. Consider everything below as rumors) is that ZF is consistant. If so, then it has a model (by Gödel's theorem?) Given this model you can construct a second model that will also satisfy the axiom of choice (prehaps V?). You can construct a third model (presumably by forcing) that will not satisfy the axiom of choice. In both cases, the existence of a model implies that the set of axioms is consistant (again, I think this is Gödel).

So, the upshot of all this is: if ZF is consistant, so will be ZF+choice and ZF+not choice. Any "hidden contradiction" must lie inside ZF. Adding the axiom of choice (or its negation) cannot create a contradiction if none existed before. This is proved, not assumed.

There could be contradictions in the extra propositions brought in during forcing. –Floorsheim 21:37, 4 Sep 2004 (UTC)

CSTAR, do you want us to move this discussion elsewhere? Gadykozma 13:38, 2 Sep 2004 (UTC)

Yes , it probably would be easier to follow.CSTAR 14:45, 2 Sep 2004 (UTC)

Anybody against moving all this text to Talk:Axiom of choice? Gadykozma 16:42, 2 Sep 2004 (UTC)

not me –Floorsheim 18:05, 2 Sep 2004 (UTC)

BTW, just to make it clear, I do use the axiom of choice with what seems like shameless abandon. However, worrying about it is legitimate.CSTAR 17:54, 30 Aug 2004 (UTC)

The two parts of your sentence correspond to my points 3 & 2 above respectively, so it seems we agree completely :-) Gadykozma 19:38, 30 Aug 2004 (UTC)

This is quite an overstatement. CSTAR clearly thinks there is more to the issue than you do and nothing he says here is in firm agreement with your second and third bullets. –Floorsheim 03:06, 1 Sep 2004 (UTC)

More on the axiom of choice

Hmmm, yes Gadykozma that is stretching what I said. Using the axiom of choice is a little like profiting from an activity or living under a government about which one has some misgivings. You could argue that such complicity is implicit moral approval. It is legitimate to hold accomplices of an activity responsible in some way. It does not follow that they have no intellectual legitimacy (or basis) to question activities to which they contribute.

Yes I use the axiom of choice, but the entire enterprise of scientific activity requires continual examination of all aspects of research. In fact I am not sure I agree with 2 or 3; indeed if it turned out that the axiom of choice leads to a contradiction, then we might be worse off having used it and the research it justified may have little value. My view is that the axiom of choice is valid in some empirical sense and its formulation in set theory is a formal model of empirical facts about sets. So I almost accept your principle (1), i.e. the axiom of choice is true as best we can determine empirically.

This view itself has a gaping goal -- Do we know of any way of falsifying the axiom of choice? I suppose that if it lead to a contradiction then in some sense that would be a falsification. But I have to confess, I am out of my depth here.CSTAR 03:41, 1 Sep 2004 (UTC)

I have nothing against the examination of the validity of the axiom of choice. When I said that it belongs to epistemology and meta-mathematics I did not mean it in a pejorative way! I think the philosophical foundations of mathematics (and vice-versa, what mathematics has to offer to philosophy) are very important.

BTW, there is a theorem in number theory (I think the existance of infinitely many twists in the prime mod 4 competition) which has two proofs, one assuming Riemann's conjecture and the other assuming its negation. Would the second one become redundant when its finally proved? I don't think so. Even after Riemann's conjecture is proved, the fact that some theorem has a proof not using it is important (I am a little less sure about the value of http://www.cse.iitk.ac.in/primality.pdf, though). So, even if some kind of physical experiment shows that the axiom of choice holds (or not), I still think there is lots of value in knowing which results require it. Gadykozma 20:36, 1 Sep 2004 (UTC)

"Even after Riemann's conjecture is proved, the fact that some theorem has a proof not using it is important" I disagree. If the Riemann hypothesis is true, assuming its negation is a contradiction; and anything follows from a contradiction. Also, if Riemann's conjecture is true, assuming it to be true is a tautology; and anything that follows from a tautology is, itself, a tautology. It would definitely be interesting, though, to see a proof of the theorem you referenced that didn't go along the lines of A٨¬A → {A, ¬A} → {A٧B, ¬A} → B, but it wouldn't establish anything unknown. –Floorsheim 21:37, 4 Sep 2004 (UTC)

"A proof not using the Riemann hypothesis" is not at all the same thing as "a proof using the negation of the Riemann hypothesis". Suppose A has a short simple proof using the Riemann hypothesis, and a short simple proof not using the Riemann hypothesis. If the Riemann hypothesis is hard to be (as appears to be the case), then wouldn't the short simple proof of A not using the Riemann hypothesis make the proof of A accessible to those who haven't worked through the proof of the Riemann hypothesis? And might it not be important for that reason? Michael Hardy 17:19, 8 Sep 2004 (UTC)

I agree with Mr. Hardy here. It seems to me that a proof of a theorem not using the Riemann hypothesis (were such a proof possible) would be a better representation of *why* the theorem is true than a proof that circumnavigated through it and would, in that sense, be important. Perhaps the quote I should have referenced is "BTW, there is a theorem in number theory (I think the existance of infinitely many twists in the prime mod 4 competition) which has two proofs, one assuming Riemann's conjecture and the other assuming its negation." –Floorsheim 11:00, 9 Sep 2004 (UTC)

Floorsheim, it seems we switched sides: now you are the formalist and me the intuitionist... mathematical practice is just not like that. Most mathematicians I know prefer not to use heavy theorems if they can. One of them went so far as to claim that "the classification of finite simple groups ruined group theory". By that he meant that people prove theorems by reducing them to the simple case and then checking all possibilities (alas, I have a paper like that too...) and the field lost any intuition it ever had. Another person remarked to me that (paraphrasing) "Carleson's theorem is a black box and everything you prove with it becomes a black box proof that you cannot understand". Gadykozma 17:56, 5 Sep 2004 (UTC)