Talk:Axiom of choice/Archive 4

Archive 1

Archive 2

Archive 3

Archive 4

Archive 5

Archive 6

GCH implies AC??

I never quite understood this claim. As I understand it, subtly implied in the usual statement of GCH is that every cardinal is one of the Alephs, hence AC, but couldn't one rephrase it to capture the intended meaning without this unintended consequence? It would seem preferable if it were indeed possible. Leberquesgue 19:02, 15 May 2007 (UTC)

The statement is that if for no infinite cardinal $\kappa$ does a cardinal $\kappa <\lambda <2^{\kappa }$ exist, then the axiom of choice holds. The proof is not very simple. The result was proved by A. Lindenbaum and A. Tarski in 1926, but their proof was lost. Sierpinski found a new proof in 1943, and published it in 1947. Kope 06:25, 16 May 2007 (UTC)

Consider $\kappa =\aleph _{\alpha }$. Ordered pairs of ordinals less than kappa can be encoded as ordinals less than kappa. So well-orderings of kappa can be encoded as subsets of kappa. The set of all such subsets of kappa (which can be given an ordering of order type $\aleph _{\alpha +1}$) is a subset of the powerset of kappa. Thus $\kappa <\aleph _{\alpha +1}\leq 2^{\kappa }$. If GCH holds, then it cannot be strictly between them, so we get that $\aleph _{\alpha +1}=2^{\kappa }$. Using transfinite induction, we can show that every infinite cardinal is an aleph. Thus every set can be well-ordered. Thus the axiom of choice holds. JRSpriggs 07:06, 16 May 2007 (UTC) I forgot the equivalence classes of well-orderings. This shows why these things are not so easy without reviewers. JRSpriggs 07:13, 16 May 2007 (UTC)

I would like to add that in Kope's formulation, κ is not necessarily well-orderable, hence not necessarily an aleph. In other words, "cardinal" is meant as "cardinality" (equivalence class of equipotent sets) and not "initial ordinal". --Aleph4 08:47, 16 May 2007 (UTC)

Yes, but in the inductive proof one could assume that all cardinals up to kappa had been shown to be well-orderable. The problem then being to show that its powerset (and thus any subset thereof) is also well-orderable. JRSpriggs 10:43, 16 May 2007 (UTC)

This may be obsolete, due to the line-outs, but that the cardinals are partially-well-ordered by < also requires a form of the axiom of choice, which seems to be the complete transfinite induction you're attempting. (As has been noted, the cardinally being linearly ordered is a form of choice.) — Arthur Rubin | (talk) 15:50, 16 May 2007 (UTC)

I think you mean "well-founded partial order". ZF certainly does not imply that the cardinalities (I prefer this name to "cardinals" in the absence of choice) are well-founded. Indeed, it is consistent with ZF that there is a strictly decreasing ω-sequence of cardinalities. (Start with the cardinality of any infinite Dedekind-finite set.) --Aleph4 17:01, 16 May 2007 (UTC)

PWO is sometimes used for that concept I believe, but you're correct, that's what I meant. Sorry about not checking for the proper notation. — Arthur Rubin | (talk) 18:34, 16 May 2007 (UTC)

JR's induction is almost right, but instead of doing the induction on κ you need to do it on ranks. Suppose that V_α can be wellordered; call its cardinality κ. Then if 2^κ is an aleph, it follows that V_α+1 can be wellordered. I don't see any obvious way of making it work at limit steps (you can't pick a wellordering of V_α for each α<λ) but this would at least get you that every set of rank less than ω×2 can be wellordered. --Trovatore 19:11, 16 May 2007 (UTC)

Trovatore is quite right.

Clearly, I was mistaken in thinking that I could come up with a proof off of the top of my head. JRSpriggs 03:58, 17 May 2007 (UTC)

My mother's book Set Theory for the Mathematician has Sierpinski's proof. Basically, without the axiom of choice, it can be shown that (the symbols m will denote cardinals ≥ ℵ₀, and p will denote arbitrary cardinals, and often confusing sets with their cardinalities), that

(Property P) 2^m-m = 2^m.

(that is, if m + p = 2^m, then p = 2^m, and that, writing ℵ(m) as the least aleph not less than or equal to m, that

$\aleph (\mathbf {m} )\leq 2^{2^{2^{\mathbf {m} }}}$

Then, looking at where $2^{2^{\mathbf {m} }}+\aleph (\mathbf {m} )$, $2^{\mathbf {m} }+\aleph (\mathbf {m} )$, and $\mathbf {m} +\aleph (\mathbf {m} )$ may fall, we end up with $\aleph (\mathbf {m} )$ being a repeated powerset of m, so that m is clearly an aleph, or the contradiction that $\aleph (\mathbf {m} )\leq \mathbf {m}$.

— Arthur Rubin | (talk) 15:13, 17 May 2007 (UTC)

Two small correction's:

Trovatore's proof sketch will not show that GCH implies AC: Rather, it is the beginning of the proof of "If the power set of every well-ordered set (or ordinal) can be well-ordered, then AC holds". (I think this is an exercise in Kunen's book, and may well be due to Sierpinski.) At limit steps, a fixed well-ordering of the power set of "everything so far" has to be used.

Arthur Rubin probably means "infinite cardinals" rather than "cardinals ≥ ℵ₀". These two are not equivalent in ZF.

--Aleph4 14:33, 18 May 2007 (UTC)

Actually, I'm afraid I did mean "cardinals ≥ ℵ₀". Property P may fail if m is Dedekind finite, and certainly if 2^m is (Dedekind finite). On the other hand, the form of GCH as specified in the reference also assumed m ≥ ℵ₀, so that may be the reason. What's needed is the following statement:

GCH implies (p < 2^q implies p ≤ q),

where q is an arbitrary infinite cardinal. On the other hand, the "standard" version of GCH implies there are no infinite Dedekind finite cardinals, as p < p + 1 < 2^p, so the proof can continue normally. Sorry about that. I'm afraid the confusion is due to my mother's choice of notation and definition of GCH. — Arthur Rubin | (talk) 14:49, 18 May 2007 (UTC)

Responding to Aleph4: That of course depends on what you mean by GCH in a non-AC context. Since the weakest version you can come up with actually implies full AC, it's kind of moot, but ignoring that, a reasonable interpretation would be 2^κ=κ⁺ for every wellordered cardinal κ. (I absolutely do take the position that, in the absence of AC, the natural thing to call the continuum hypothesis is $2^{\aleph _{0}}=\aleph _{1}$ -- the weaker claim that there's no intermediate cardinality between $\aleph _{0}$ and $2^{\aleph _{0}}$ should have another name, perhaps "weak CH").

There is an issue I'm not sure how to resolve here. If the powerset of any ordinal can be wellordered, does AC in fact follow (say, in ZF alone)? I don't see how to do the limit case, in the simple induction I proposed. --Trovatore 19:57, 18 May 2007 (UTC)

Yes. I don't have access to my parents' books Equivalents of the Axiom of Choice or my mother's Consequences of the Axiom of Choice at the moment, but Set Theory for the Mathemtician has a proof in NBG that if the power set of any (initial) ordinal can be wellordered, then AC.

The trick is two-fold. (See von Neumann universe for notation.) Fix a V_α which you wish to find a well-ordering of. Fix $\lambda =\{\gamma |\gamma \preccurlyeq V_{\alpha }\}$, and find a well-ordering of $\mathbf {P} (\lambda )$. Then, prove by transfinite recursion, that there is a function F such that, for each β ≤ α, F(β) well-orders V_β.

(The construction used in that book is $V_{\alpha }:=\mathbf {P} \left(\bigcup _{\beta <\alpha }V_{\alpha }\right)$, rather than the one from von Neumann universe, but it's close enough.)

Another try

With the benefit of Arthur Rubin's outline of Sierpinski's proof, I would like to try again. Let S be any set which we want to show is well-orderable. Let $T={\mathcal {P}}({\mathcal {P}}(S\cup \omega ))$, then S can be injected into T by the singleton of the singleton of an element of S. Notice that $\|S\cup \omega \|=\|S\cup \omega \|+1$ and thus $\|{\mathcal {P}}(S\cup \omega )\|=\|{\mathcal {P}}(S\cup \omega )\|\cdot 2$ and thus $\|T\|=\|T\|\cdot \|T\|$. Any powerset of a set with these three properties will also possess them. Let α be the smallest ordinal which cannot be injected into T. Ordered pairs of elements of T can be encoded as elements of T using $\|T\|=\|T\|\cdot \|T\|$. Well orderings of T may be encoded as elements of ${\mathcal {P}}(T)$. Equivalence classes (wrt order isomorphism) of such well orderings can be encoded as elements of ${\mathcal {P}}({\mathcal {P}}(T))$. The elements of α can be mapped injectively to the equivalence classes, so α is injected into ${\mathcal {P}}({\mathcal {P}}(T)).$ ${\mathcal {P}}(T)$ is also injected into ${\mathcal {P}}({\mathcal {P}}(T))$. So using $\|{\mathcal {P}}({\mathcal {P}}(T))\|=\|{\mathcal {P}}({\mathcal {P}}(T))\|+\|{\mathcal {P}}({\mathcal {P}}(T))\|$, we get the disjoint union (sum) of them injected into it. Since this disjoint union is larger or equal to the infinite set ${\mathcal {P}}(T)$ and smaller than or equal to its powerset, we get that it must equal one or the other of them by GCH.

If it equals ${\mathcal {P}}({\mathcal {P}}(T))$, then consider an injective function from ${\mathcal {P}}({\mathcal {P}}(T))\times {\mathcal {P}}({\mathcal {P}}(T))$ through ${\mathcal {P}}({\mathcal {P}}(T))$ to the disjoint union. Using a variation of Cantor's diagonal argument, we can show that there must be a subset of ${\mathcal {P}}(T)$ such that no elements in the column corresponding to it are mapped into ${\mathcal {P}}(T)$ itself. Thus they must all be mapped injectively into the image of α. Thus that column (a copy of ${\mathcal {P}}({\mathcal {P}}(T))$) is equipollent to α. Thus S is injected into a set equivalent to an ordinal and is thus well-orderable.

If it equals ${\mathcal {P}}(T)$ instead, then we combine α with T. Using the fact that α cannot be injected into T and a similar argument to that in the previous paragraph, we get that ${\mathcal {P}}(T)$ can be mapped injectively into α and thus again S is well-orderable. JRSpriggs 05:34, 19 May 2007 (UTC)

Simpler than the proof in my mother's book, at least considering it from "first principles". — Arthur Rubin | (talk) 16:49, 19 May 2007 (UTC)

Thank you for your kind words, Arthur. If anyone has any questions about or criticisms of my proof or would like some part of it expanded in more detail, please speak up. It appears to me now that I did not have to make the image of α and the image of ${\mathcal {P}}(T)$ disjoint, a simple union would have been sufficient. I was thinking of the outline which calls for a sum, but neither GCH nor the variation of Cantor's diagonal argument need that. JRSpriggs 08:16, 21 May 2007 (UTC)

What is (G)CH really?

Perhaps this should really be moved to the CH discussion page?

Responding to Trovatore (above), who says that CH (in the absence of AC) should be $2^{\aleph _{0}}=\aleph _{1}$:

In my opinion, the "natural" definition of CH (over ZF) should be the statement that there is no set of intermediate cardinality between N and R. I can claim that Georg Cantor agrees with me (although I think it was not he who came up with the name "continuum hypothesis"). In his 1878 paper he asks

in how many classes can the linear manifolds [he means: infinite subset of the real line] be divided, if manifolds of the same cardinality are put into the same class...

and later he claims that some kind of induction suggests that there are exactly two such classes. This is exactly the continuum hypothesis. At that time it was still unclear if the real line can be well-ordered, but I think that aleph1 might have been known already.

Aleph4 14:12, 21 May 2007 (UTC)

Probably should be moved to the CH discussion page, and although I've done some work in the field, I'm not really sure whether CH should be

$2^{\aleph _{0}}=\aleph _{1}$

or

$(\not \exists \mathrm {m} )\aleph _{0}<\mathrm {m} <2^{\aleph _{0}}$

They're not the necessarily the same, in the absence of choice. — Arthur Rubin | (talk) 21:38, 21 May 2007 (UTC)

Under ZF

$(\lnot \exists \;\mathrm {m} )\aleph _{0}<\mathrm {m} <\aleph _{1}\leq 2^{\aleph _{0}}$

so certainly the former implies the latter.

CRGreathouse (t | c) 13:51, 23 May 2007 (UTC)

I'm afraid ZF does not imply $\aleph _{1}\leq 2^{\aleph _{0}}$ It implies there is a map from ${\mathcal {P}}(\omega \times \omega )$ onto $\omega _{1}$ (namely, taking any well-ordering to its order type), but chosing representatives requies some form of choice. — Arthur Rubin | (talk) 14:00, 23 May 2007 (UTC)

So what do I have wrong under ZF?

1. Definition of aleph numbers (successor): $(\lnot \exists \;\mathrm {m} )\aleph _{0}<\mathrm {m} <\aleph _{1}$

2. Definition of aleph numbers (order): $\aleph _{0}<\aleph _{1}$

3. Cantor's theorem: $\aleph _{0}<2^{\aleph _{0}}$

Are you saying $\aleph _{1}>2^{\aleph _{0}}$ is consistent under ZF, or just that $\aleph _{1}\not <2^{\aleph _{0}}\wedge \aleph _{1}\neq 2^{\aleph _{0}}\wedge \aleph _{1}\not <2^{\aleph _{0}}$ is?

CRGreathouse (t | c) 14:35, 23 May 2007 (UTC)

The latter. Remember that trichotomy (of < on cardinal numbers) is equivalent to the axiom of choice, as noted back in the article. — Arthur Rubin | (talk) 14:41, 23 May 2007 (UTC)

I do recall that. Does that mean I can say $(\lnot \exists \;\mathrm {m} )\aleph _{0}<\mathrm {m} <\aleph _{1}\not >2^{\aleph _{0}}$ under ZF?

CRGreathouse (t | c) 21:11, 23 May 2007 (UTC)

Yes, ZF implies your statement. But $\not >$ is not a very useful notion.

Comment to Arthur Rubin: In your statement about trichotomy I would suggest the name "cardinal" or even better "cardinality" instead of "cardinal number", because "cardinal number" suggests (to me) an ordinal. --Aleph4 09:20, 24 May 2007 (UTC)

You can say that $\aleph _{1}\leq 2^{2^{\aleph _{0}}}$ even without AC (as in my proof above) by mapping each countable ordinal to the equivalence class of well-orderings of ω which have its order type. Where ordered pairs of natural numbers are encoded as natural numbers in some standard way. JRSpriggs 07:18, 24 May 2007 (UTC)

In a remarkable theorem Shelah proved that if $\aleph _{1}\leq 2^{\aleph _{0}}$ then there is a non-measurable (under the Lebesgue measure) set of reals. So, in every model where all sets are measurable (as Solovay's) $\aleph _{1}\not \leq 2^{\aleph _{0}}$ surely holds. Kope 09:51, 14 June 2007 (UTC)

Implicit usage before 1900

I agree with the motive behind Carl's reversion, but the wording is problematic. Before Zermelo, there was no axiomatic system available to "notice" that it didn't prove certain things if you didn't assume AC. (Well, there was Frege's, but it was wrong, and anyway it was after 1900.) So there are two problems, first, what does the claim even mean? and second, why single out AC, as opposed to, say, replacement or powerset? --Trovatore 07:13, 24 June 2007 (UTC)

I think that one reason to single out AC was that the others were recognized as necessary when the 'complete' axiomatic frameworks were written, but many mathematicians thought they didn't need to assume AC (when in fact they did). CRGreathouse (t | c) 18:40, 24 June 2007 (UTC)

Well, that's a historical point from a period later than the one in question, so I don't see how it's relevant. And it still doesn't address the question of what the claim means. --Trovatore 20:15, 24 June 2007 (UTC)

Perhaps the point which needs to be made is that people are often less conscious of using the axiom of choice than they are of using the other axioms. Even people who overtly deny it often make inferences which cannot be validly formalized with invoking the axiom of choice. JRSpriggs 07:28, 25 June 2007 (UTC)

Ya think? Less conscious than they are of using replacement? No, seriously, I think the existing wording is a problem. That's why I didn't restore it when the anon took it out, even though his edit summary looked like nonsense. --Trovatore 09:36, 25 June 2007 (UTC)

Yes, I think so. In my case I was aware of an axiomatic framework and most of the axioms I was using, but would still use the AoC without realizing that I was. But that's beside the point. I'm really a WP:0RR editor, so I'll leave the article as-is.

CRGreathouse (t | c) 12:56, 26 June 2007 (UTC)

I reverted mainly because the claim is very commonly made and because the edit summary was confusing. One fix would be to give an explicit reference for the claim. I'm away from home for a while, though. — Carl (CBM · talk) 14:15, 26 June 2007 (UTC)

What is the problem?

“ First we might try to proceed as if X were finite. If we try to choose an element from each set, then, because X is infinite, our choice procedure will never come to an end, and consequently, we will never be able to produce a choice function for all of X. ”

The statement claims that human brain can alway choose an element from any given set. It is real function of choice. --Javalenok 18:27, 18 July 2007 (UTC)

“ Next we might try the trick of specifying the least element from each set. But some subsets of the real numbers don't have least elements. For example, the open interval (0,1) does not have a least element. ”

Any non-empty interval (a, b) has a middle element (a+b)/2. The infinite interval (a, +inf) has an (a+1) element. --Javalenok 18:27, 18 July 2007 (UTC)

Yes, we don't need the axiom of choice to pick an element from an open interval of R, we can just use the midpoint. But some sets don't include their midpoints -- or don't even have a well-defined notion of 'midpoint'. That's when we need the axiom of choice.

CRGreathouse (t | c) 19:46, 18 July 2007 (UTC)

For those of us that are advanced at english, and still don't understand...

"exactly one object from each bin can be picked and gathered in another bin".
This seems very poorly worded. What on earth is it talking about.
Imagine a collection/set of bins, each containing at least one object. The theorem states that "...exactly one object, from each bin, can be picked" - what do you mean "picked"? As in "Picked up?" Or as in "Selected?"
So let's assume it means selected.

"...and gathered" - what do you mean "gathered?" Do you mean that ALL of these objects that have been picked are gathered somewhere, like in one big pile or something? Or are we only talking about gathering 1 object, in one place, which is hardly gathering at all. "...in another bin" - do you mean one ultimate bin, where everything has been gathered? Or is it like swapping a bit, where an object is picked, and put into some other random bin, and then another object is picked elsewhere, and put into another completely different bin?

I really wish you could elaborate a bit more. This axiom makes no sense.

Rfwoolf 20:53, 19 August 2007 (UTC)

I suggest changing

"be picked and gathered in another bin"

to

"be selected from and placed into one collecting bin"

--Michael C. Price ^talk 22:14, 19 August 2007 (UTC)

I've never been a fan of physical analogies for AC. It's easy to pick balls out of bins - just reach in and grab one from each bin. AC is about functions that simultaneously select a member from each of a collection of nonempty sets. I can't reach my hand into a set. — Carl (CBM · talk) 22:41, 19 August 2007 (UTC)

simultaneously select? There's nothing in the intuitive description that contradicts this. --Michael C. Price ^talk 23:09, 19 August 2007 (UTC)

Agreed, but I'm not convinced the analogy with bins conveys any useful intuition either. — Carl (CBM · talk) 01:28, 20 August 2007 (UTC)

Hmm, well, it does to me. I'd go so far as to say it makes it clear why AC is true. --Trovatore 03:29, 20 August 2007 (UTC)

What about the specific wording I've suggested? Rfwoolf, does it help? --Michael C. Price ^talk 06:57, 20 August 2007 (UTC)

One other point about thw wording: perhaps we should change

"given a collection "

to

"given any collection "

--Michael C. Price ^talk 07:18, 21 August 2007 (UTC)

I realize that I'm a bit late to the discussion here, but I'll give my two cents worth. I don't have any particular beef with a physical analogy of the axiom of choice, but wouldn't it be more appropriate to begin the article with a mathematical definition? Something like "The axiom of choice is an axiom of set theory stating... Informally, this can be described as..."? It seems more fitting in an entry on a mathematical subject.130.126.63.29 (talk) 05:50, 16 November 2009 (UTC)

Minor change which reverses current sense

I have deleted the word "not" from the April fool's quote about the axiom of choice. Yes, it reverses the sense, but also makes sense out of non-sense. If anyone feels I am out of order, please revert. Kiwi137 (talk) —Preceding comment was added at 14:13, 21 November 2007 (UTC)

I've reverted your edit. It's a direct quote, and should be word-for-word identical with the original: editing direct quotes, even if it improves on their meaning, renders them invalid. -- The Anome (talk) 14:17, 21 November 2007 (UTC)

On New Theorems

The reason people accept some new axioms, like inaccessible cardinals, is that there are new theorems you can prove with inaccessibles that you can't prove without them. The theorems I am talking about are not abstract existence theorems that talk about enormous sets, although some of the theorems you prove with inaccessible cardinals are certainly of this sort. The theorems I am talking about are statements that can be stated in a verifiable way--- they assert that certain computations do not halt. In logic, they are sometimes called "Real Theorems"(standard terminology), to distiguish them from "Fake theorems"(nonstandard terminology), which are abstract assertions that can't be checked by computing anything.

Using inaccessible cardinals, there are computer programs that can be shown not to halt, which cannot be shown not to halt without inaccessibles. The classic example is the program that deduces all consequences of ZFC, looking for a contradiction. This program does not halt if ZFC is consistent, and the weakest inaccessible cardinal axioms prove that ZFC is consistent, and not much else.

The point of strong axioms is that they prove new real theorems, new theorems about computer programs, so generally when people say axiom system A is stronger than axiom system B, or axiom system A proves more theorems than B, they mean this--- there is a program X that B proves not to halt, which A does not.

The question then arises: is the axiom of choice such an axiom? Does it let you prove new theorems about computations, or is it just an assertion about the abstract existence of certain infinite sets? The proof of equiconsistency shows that AC is of the latter type.

If you prove program X does not halt in ZFC and if the program halts, ZFC is inconsistent. But equiconsistency implies then that ZF is inconsistent, which means that there is a proof in ZF that X does not halt.

Equiconsistency is proven in ZF (you can do it in PA), so ZF actually proves the theorem ZFC proves X does not halt implies ZF proves X does not halt. Godel's proof allows this statement to be made into an algorithm--- given a proof that X does not halt in ZFC, there is a textual manipulation of this proof into a proof that X does not halt in ZF. This is proven in Cohen's "Set Theory and the Continuum Hypothesis", for one. It is neither deep nor controversial.

So to say that the axiom of choice proves new theorems, without also saying that it does not prove any new real theorems, is to my mind a gross mischaracterization. It leaves people with the feeling that there are theorems about the outcome of actual computations whose proof is made possible by the axiom of choice, which is just not true. This is why I inserted a balanced discussion contrasting the elegence of the theorems proved with choice, against their essentially unverifiable content.Likebox (talk) 19:43, 15 January 2008 (UTC)

To say that a theorem which doesn't describe computations is "unreal" is — well, I can't think of an appropriate term. If you want to say something about this, in general, under, say equiconsistency, go right ahead. I probably won't even notice. Perhaps it might have one claus, here, but it clearly doesn't deserve a full sentence. As for the rest of your additions, they refer to the opinions of living mathematicians, so require a source. —Preceding unsigned comment added by Arthur Rubin (talk • contribs) 19:52, 15 January 2008 (UTC)

I don't see how the reference to computer programs is particularly relevant to an article about the axiom of choice. There's no good reason I can see for this article to discuss them, since they are not at all an object of study in elementary set theory such as Levy covers in his book Basic Set Theory.

The independence proof is due to Fraenkel (for ZF with urelements) or Cohen (for ZF). Goedel showed that AC is consistent with ZF, but not that it is independent of ZF (and Cohen beat him to that proof). — Carl (CBM · talk) 19:57, 15 January 2008 (UTC)

The point is that it is standard terminology in logic to call theorems "unreal" when they do not assert the halting of computer programs. The reason you mention computer programs is because you want to take into consideration the considerable number of people for whom the computer is the foundational object in mathematics. I did not use controvertial terminology in the edits.Likebox (talk) 20:03, 15 January 2008 (UTC)

For the purposes of proving that "ZFC-> X doesn't halt" implies "ZF-> X doesn't halt", only Godel's proof is enough. Fraenkel's proof doesn't cut it, and Cohen's is not necessary.Likebox (talk) 20:03, 15 January 2008 (UTC)

I have managed to get a PhD in logic without knowing about the standard terminology "unreal theorem". This may indeed be used by some authors (almost every conceivable terminology is used by someone); could you let me know where to look it up? As for independence, I don't think that the point about arithmetical statements is really important enough to emphasize in an introductory article. It is covered (albeit more abstractly) in absoluteness (mathematical logic). — Carl (CBM · talk) 20:07, 15 January 2008 (UTC)

Me too. --Hans Adler (talk) 20:21, 15 January 2008 (UTC)

Actually, my Ph.D. was in universal algebra and generalized recursion theory, both of which are normally considered to be within logic. I'd never heard of it, either. Perhaps he's a constructivist. — Arthur Rubin | (talk) 20:30, 15 January 2008 (UTC)

Ok, maybe I'm wrong about it being standard. I didn't use this terminology in the article, only in the talk page. I heard it from one or two logic professors who casually said "This system proves more real theorems than that system", when they meant more arithmetic theorems. The reason I think it is important to say this in an introductory article is because of my personal experience. The axiom of choice made me stop studying abstract mathematics as an undergraduate, because I felt it was proving lies, and I couldn't keep track of which theorems used it and which ones didn't. I don't want someone else to be driven away from math. If students understand that its a convenience, not a necessity, maybe that will assuage them. Yes, I do have a constructivist bent, so what. So do a lot of other people. The article as written is not biased toward one philosophy or another, in my opinion, since it only states things that everyone pretty much agrees with.Likebox (talk) 20:36, 15 January 2008 (UTC)

I think this point illustrates one of the sources for our communication problems, perhaps even the main one. You are not distinguishing between different modes of speech in mathematics. What you describe is "blackboard language", informal and unprecise language used by mathematicians to convey their ideas. It is only acceptable if it is (ongoing research or) based on much more precise statements. Except in the occasional descriptive paragraph it is not acceptable in normal publications or Wikipedia articles. Mathematics could also work without this restriction, but then it would be much easier to make mistakes. As it is, such definitions are always ad hoc and cannot be carried over from one context to another. You just can't use them undefined and expect others to understand what you mean. --Hans Adler (talk) 22:46, 15 January 2008 (UTC)

I am sorry for any communication gaffes--- I am trying my best to be clear. Perhaps I am not using the best language, but I am saying something precise. The theorem is that (ZFC->X halts) imlies (ZF->X halts).

This can be proved by a textual transformation. If you are given a proof of a theorem (forall integers n F^n(M) doesn't halt) in ZFC, where F is a function that takes a computer one processor step forward in time, and M is an integer that contains the computer's memory, you can translate the theorem to ZF. Replace every set S that occurs in every stage of the theorem with S_L, which just means the same S restricted to the Godel constructible universe. Then for every set which you used a choice function for, the L version has a choice function in ZF, so the proof goes through in L. Once the proof is finished, you end up with the theorem (forall L-integers n (F_L)^(n_L)(M_L) doesn't halt). But the L integers and the L-functions on the integers are the same as the ZF or ZFC integers, and so you've proved the same theorem. That's the translation. It works for any theorem about any absolute notions like integers and ordinals.Likebox (talk) 23:40, 15 January 2008 (UTC)

You are right in principle, but it is very hard to express this idea unambiguously. For example, how about theorems about the number which is 1 if there is a set that cannot be well-ordered, and 0 otherwise? That's not what you had in mind, but mind-reading should not be required to follow a mathematical argument. (Blackboard mathematics excepted, as above. In that case you can ask when you don't understand something.) --Hans Adler (talk) 00:02, 16 January 2008 (UTC)

Yes, I agree, this is a problem. But if the article becomes overly pedantic about points like this then it might become very technical, and too hard for the non-specialists. I am trying to express the precise statement as colloquially as possible, given the constraints of not saying something wrong. This is why I tried "Any statement about the halting or non-halting of a computer program", which I don't think can be misinterpreted. Maybe there's a way to misinterpret that too though.Likebox (talk) 00:17, 16 January 2008 (UTC)

I've deleted your second instance of computation arguments, and placed an {{importance-section}} tag (as we don't have an {{importance-inline}} tag) on the section. I think it's now clear what you're saying (thanks), but the importance is not clear. — Arthur Rubin | (talk) 00:40, 16 January 2008 (UTC)

I think it is important to note that the axiom is not one of those that proves new theorems about the integers--- that's really important. So that the people that cannot accept Banach-Tarski will be able to take it with a grain of salt.Likebox (talk) 00:46, 16 January 2008 (UTC)

I can't restore the tag, because of 3RR. But, if we were to count partial reverts, I would be at 4 and you at 5 already. So, could you please restore the tag while discussion is proceeding. — Arthur Rubin | (talk) 00:49, 16 January 2008 (UTC)

I'm certainly not going to call you on 3RR. Common sense tells me that at no point has this discussion devolved into anything resembling an edit war. I think it has been a reasonable attempt to come to a compromise. But I think that your tag is a little ridiculous--- why not mention that arithmetic theorems can be dechoiced? It will clarify the role of the axiom for constructively minded people.Likebox (talk) 00:59, 16 January 2008 (UTC)

Maybe your objection is to the use of computer programs as the absolute notion. If so, why not just rephrase it so that it says theorems about arithmetic?Likebox (talk) 01:01, 16 January 2008 (UTC)

(←) I tried to implement that suggestion. I used P = NP and the Riemann hypothesis, two famous unsolved problems, to illustrate that there are important problems for which choice is not a real improvement over ZF. — Carl (CBM · talk) 02:02, 16 January 2008 (UTC)

Looks good to me. As a (former, I suppose) professional logician, I sometimes find it difficult to understand the layman's point of view. I apologize to Likebox for that (as he doesn't want me to write to his talk page). — Arthur Rubin | (talk) 02:03, 16 January 2008 (UTC)

It looks good to me too.Likebox (talk) 05:53, 16 January 2008 (UTC)

Brilliant solution. After all this friction the article has definitely been improved. --Hans Adler (talk) 09:31, 16 January 2008 (UTC)

Great work, I'm glad for the friction -- and the good faith on all sides. The article is better now. Would it be too much to ask for a reference, though? CRGreathouse (t | c) 00:30, 17 January 2008 (UTC)

The way I make up my mind whether something is OR or not is by asking myself "Would I be embarassed by triviality to write a paper declaring this result?" In this case, given Godel's construction of L, which is presented in his 194-something monograph, the observation that AC is unnecessary for arithmetic proofs is sort of trivial. But I don't know the literature well enough to know where someone makes this observation explicitly.Likebox (talk) 02:16, 17 January 2008 (UTC)

No, that's not a good test. "Original research" is kind of a WP term of art; it doesn't really mean that it's necessarily particularly original, in the good sense of the word. Certainly something can easily be far too original to be added to WP without attributing it to someone, but not remotely original enough to be published in a research journal. --Trovatore (talk) 02:23, 17 January 2008 (UTC)

(edit conflict) I just vaguely remembered the phrase in Cohen's Set theory and the Continuum Hypothesis: "Godel's proof shows that any proof of a contradiction from ZFC can be textually manipulated into a proof of a contradiction from ZF. Likewise the proof that not-choice is consistent shows that any contradiction from ZF+notC can be textually manipulated into a proof of a contradiction from ZF." or something like that. I think that might be the best reference. Maybe not.Likebox (talk) 02:28, 17 January 2008 (UTC)

I'm not suggesting it's OR, just that a reader might want more details from some mathematical source. The Cohen source sounds good, if it's in there. CRGreathouse (t | c) 13:41, 17 January 2008 (UTC)

Speed up of proofs using AxCh?

The current revision by CBM says "When one attempts to solve problems in this class, it makes no difference whether ZF or ZFC is employed.". Even though one cannot prove more propositions in the language of Peano arithmetic, I think that you can prove some of them more easily (shorter, more direct proofs) if you are allowed to use the axiom of choice. Is this not correct? So this sentence should be changed. JRSpriggs (talk) 01:31, 17 January 2008 (UTC)

Doubtful. I don't have a source, but I don't see it as likely. — Arthur Rubin | (talk) 01:40, 17 January 2008 (UTC)

The essential point is that there is a textual map which takes a proof with AC to a proof without AC of almost exactly the same length. The only thing you need to do is put L subscripts on all the objects you are using and constructing. For example, if at some point you say "Consider the ring of functions on [0,1] under pointwise multiplication with the discrete topology, and the maximal ideal containing Froo and Bat and blah blah blah", you just say "Consider the ring of L-functions on L-R under pointwise multiplication and the L-maximal ideal containing Froo_L and Bat_L and blah blah blah", and then all the choice theorems are true for the L-versions of the objects even in plain ZF, or in ZF + "every subset of R is measurable", or in any other non-choicey extension.

So for example, if you like to thing of the universe as ZF+ "every subset of the real numbers is measurable", you can state, prove, and use the Banach-Tarski theorem in the following form: The set of L points in the unit ball in R^3 can be partitioned into a finite number of pieces, rotated and rearranged to form the L points in two unit balls in R^3. In this model, you have proven that the L-points are measure zero in the unit ball. If you use L-subscripts conscientiously, you lose no theorems by rejecting choice.

The complete lack of speed up is in stark contrast to the axiom of inaccessible cardinals, or any other large cardinal, which will shorten the proofs of certain theorems by such a large amount, that for a general provable theorem the old proof length will be greater than any computable function of the new proof length. This is a great, in my opinion under recognized, theorem of Godel's.Likebox (talk) 01:51, 17 January 2008 (UTC)

To Likebox: Your argument does not show a "complete lack of speed up". It shows that the speed up is merely linear. However, the proportionality may be very large in the formal language of set theory. JRSpriggs (talk) 02:53, 17 January 2008 (UTC)

You're right, the speed up in a formalization is linear, but that's the same speedup as by switching to a somewhat better formal syntax, which allows shorthand "macro" symbols which can be unpacked into more complex symbols. So the usefulness of AC is that of a macro. This is a stark contrast to the axioms of infinity and powerset, which produce speedups which are greater than any computable function. In informal mathematics, which uses shorthands without reservation, the only speed up comes from omitting "I am working in L" at the beginning of the proof.Likebox (talk) 03:15, 17 January 2008 (UTC)

I was just thinking model theoretically. I added another sentence; feel free to edit that further. — Carl (CBM · talk) 04:15, 17 January 2008 (UTC)

While your at it, you might also mention that adding the axiom of "decimal notation" shortens proofs by a linear factor. It allows 34 to be written as 34 instead of (1+1+1)*(1+1+1+1+1+1+1+1+1+1)+1+1+1+1. The point is nobody actually carries out proofs in a first order language without shorthands. If you add a short way of saying "Relativized to L" to the formal proof language, and you prove V=L is a model of ZFC, the proofs are essentially the same length.Likebox (talk) 05:51, 17 January 2008 (UTC)

I don't think there is need for this sort of detail. JRSpriggs was concerned, I think, about the claim that it makes "no difference", and gave an example of a difference it might make. I added a caveat to the sentence that should resolve that concern. — Carl (CBM · talk) 12:39, 17 January 2008 (UTC)

I was just making a point--- I have no complaints with the article.Likebox (talk) 12:46, 17 January 2008 (UTC)

Logical independence

"For example, the generalized continuum hypothesis (GCH) is not only independent of ZF, but also independent of ZF plus the axiom of choice (ZFC). However, ZF plus GCH implies AC, making GCH a strictly stronger claim than AC, even though they are both independent of ZF."

This seems to me to be the opposite of independence. Not(AC) implies Not(GCH), which is Not(logical independence). I'm changing it. --68.161.161.206 (talk) 12:11, 18 April 2008 (UTC)

Never mind. I should read what I'm talking about first. --68.161.161.206 (talk) 12:14, 18 April 2008 (UTC)

4th Paragraph of Usage

In 4th paragraph of Usage, there occurs this line -- "First we might try to proceed as if X were finite. If we try to choose an element from each set, then, because X is infinite, our choice procedure will.."

In this line "try to proceed as if X were finite." and "then, because X is infinite" are contradictory. —Preceding unsigned comment added by Histre (talk • contribs)

The key words are "as if" and the subjunctive "were". — Carl (CBM · talk) 13:04, 19 April 2008 (UTC)

There are two different cases (one is when X is finite, and the other is when X is infinite). In the first case, there is a method by which we can produce a choice function without appealing to this axiom. Unfortunately, that method does not work in the second case. That is all it is saying. There is no contradiction here. JRSpriggs (talk) 05:58, 20 April 2008 (UTC)

2nd paragraph of Usage: it's not induction, is it?

Quote: "(A formal proof for all finite sets would use the principle of mathematical induction.)" -- well, strictly speaking it's not proof by induction because a proof will not use the inductive step, i.e. the k'th step will not depend on the step(s) before. Isn't that right? A proof may just show it for an arbitrary k within the finite range. Or am I missing a point here? Regards, mikl-dk. —Preceding unsigned comment added by 87.60.229.89 (talk • contribs) 21:31, 14 June 2008

Nonconstructive aspects

From another point of view, mathematical constructivists do accept a version of the axiom of choice: If one assumes that every element of the original set is constructively inhabited (which is a stronger property than non-emptiness in constructive mathematics), then a choice function for the set can be constructively realized, and the axiom is not needed. [1]

It is true that any constructive proof of $\forall x\in a\;\exists y\in b\;R(x,y)$ must contain some way of constructing some element of b related by R to any element of a. But this is set theory, not type theory. Sets are supposed to be extensional. There can be many different ways of describing the same set, and no guarantee that this construction will associate extensionally equal elements of b to extensionally equal elements of a. So there won't always be a choice function.

On the other hand, if elements of a have a normal form, such as if a is the set of natural numbers, then of course one can get around this, so the axiom of countable choice is usually acceptable. A whole article could be written on constructive choice principles. --Unzerlegbarkeit (talk) 15:32, 4 July 2008 (UTC)

Hmm, interesting; I hadn't thought of that point (the one in the first paragraph). However I believe the claim that you removed is in fact accurate for some systems (for example, Intuitionistic Type Theory). It's true that ITT is type theory rather than set theory, but that doesn't mean that the relevant theorem is not reasonably understood as a form of AC.

I think there are also set theoretic theories for which the claim is accurate. Maybe this is a difference between CZF and IZF (I never really got straight what the difference is). --Trovatore (talk) 21:39, 4 July 2008 (UTC)

I don't think there is a "set-theoretic" theory for which that is accurate. Not CZF or IZF, anyway. Yes, we can certainly say something about type theory. In fact, I'd like to. And there was certainly truth underlying what I removed, but I think we'll have to do better than that. --Unzerlegbarkeit (talk) 22:25, 4 July 2008 (UTC)

requiring ¬AC?

The name of the section "Results requiring ¬AC" is nonsensical. It gives examples of the form "there is a model of ZF¬C + <statement>". Such a result does not show that anything requires ¬AC, on the contrary, it shows that ¬<statement> requires AC (if provable in ZFC at all). — Emil J. 16:48, 12 January 2009 (UTC)

I would like to see a better section title, though. 1+1=2 is consistent with ZF + ¬AC, but doesn't belong in the section. CRGreathouse (t | c) 17:12, 12 January 2009 (UTC)

Yeah, your change is probably an improvement but the heading is still problematic. The idea really seems to be things that are consistent with ¬AC but inconsistent with AC. That was presumably the original idea of the word requiring but it didn't really come across (especially since ¬AC unadorned buys you basically nothing, since the first failure of AC could come at arbitrarily high rank). --Trovatore (talk) 02:12, 13 January 2009 (UTC)

Clumsy expression?

Under 'Statement' the article reads: An arbitrary Cartesian product of non-empty sets is non-empty. Not sure I understand this. What is an arbitrary Cartesian product of a collection of sets? I hazzard a guess that what's intended is to say that the axiom of choice implies that:

Given any collection of sets, their Cartesian product is a non-empty set. If that's correct, may I suggest an edit in the article?

Cool dude ragnar (talk) 00:54, 14 January 2009 (UTC)

Your rephrasing is correct, and I think it's more clear. Please feel free to edit the article. — Carl (CBM · talk) 01:22, 14 January 2009 (UTC)

I think you mean "Given any collection of non-empty sets, their Cartesian product is a non-empty set.". JRSpriggs (talk) 17:44, 14 January 2009 (UTC)

Exactly?

I have often seen the axiom of choice written as something along the lines of, "Given a collection A of sets it is possible to form a set containing exactly one element from each set in A." While I understand the axiom itself, the word exactly in this form confuses me; does it mean that the resulting set would meet each set in A once, and only once? Obviously, {{x},{y},{x,y}} would contradict this, so what does "exactly" mean? I ask, also, because this is mentioned in the informal part about bins in the lede. Phoenix1177 (talk) 07:18, 16 March 2009 (UTC)

"Exactly" means "exactly", but "collection" and "set" don't mean "set". You really need to start with a family A, and look for a family "containing" exactly one element from each set. By "family" I mean a function from some index set. In your example, the family A would be something like the function f(0)={x}, f(1)={y}, f(2)={x,y}, and from it you would form a family like g(0)=x, g(1)=y, g(2)=x. [corrected a typo 03:22, 17 March 2009 (UTC)]

I agree that this is not very useful, since such formulations assume the mathematical maturity necessary for abusing language in this way and knowing what you are doing. I guess it's probably a historical artefact, dating back to the time when it was necessary to explain the AC to experienced mathematicians. --Hans Adler (talk) 07:55, 16 March 2009 (UTC)

You can also add "pairwise disjoint" to the hypotheses about the original sets. — Carl (CBM · talk) 12:13, 16 March 2009 (UTC)

Carl is correct — see Axiom of choice#Variants. Obviously, {{x},{y},{x,y}} is not a set of pairwise disjoint sets. So it is not a counter-example. I am afraid that Hans Adler's response is not helpful. JRSpriggs (talk) 01:21, 17 March 2009 (UTC)

You are probably right. In Equivalents of the Axiom of Choice II, 19 definitions that are equivalent in a straightforward way are listed. Yours is AC2; mine is AC3, and it's formulated with two functions. --Hans Adler (talk) 03:20, 17 March 2009 (UTC)

Cartesian product of an infinite set

Under the list of "Equivalents" the following appears:

If the set A is infinite, then A and A×A have the same cardinality.

This troubles me. I think it must not be specific enough, because you can prove this without the axiom of choice in the case of the natural numbers -- can't you?

Should it perhaps say something more like "if the set A is of a cardinality greater than aleph-null"? Or am I just confused? 151.199.246.58 (talk) 16:17, 15 May 2009 (UTC)

Whenever you see a conditional statement like that, and no specific set A has been fixed already, there is an implied universal quantifier: for every set A, if the set A is infinite, then A and A×A have the same cardinality. This is a very common convention in mathematical English, and a perennial source of confusion for students. I rephrased the text here, but the sooner you learn the convention the less confusion you will encounter. — Carl (CBM · talk) 16:31, 15 May 2009 (UTC)

So you're saying that the statements "every set A has property P(A)" and "if A is an arbitrary set then A has property P(A)" are equivalent, right? Or did I misunderstand? If I understood you, then the equivalence of the two statements depends on the axiom of choice, as 151.199.246.88 suggested, since this equivalence requires selecting an arbitrary element, A, from a set of such elements.—GraemeMcRae^talk 15:31, 16 May 2009 (UTC)

I am saying that the following English sentences mean the same thing:

1. If the set A is infinite, then A and A×A have the same cardinality.
2. For every set A, if A is infinite, then A and A×A have the same cardinality.

There is a (usually unmentioned) convention in mathematical English that, unless some specific set A has been selected ahead of time, a conditional statement about the set A is intended to be universally quantified. — Carl (CBM · talk) 16:18, 16 May 2009 (UTC)

To GraemeMcRae: Actually you are wrong on two counts: (1) as CBM said, you are misinterpreting how English handles implied quantifiers, and (2) the axiom of choice is not needed to select a single element from a set, that is a normal operation of first order logic. This second point has been discussed before, see Talk:Axiom of choice/Archive 3#Question. JRSpriggs (talk) 19:56, 17 May 2009 (UTC)

Reference for "small number" of constructivists

Why should we say in this article that the community of constructivists is small? Because to do otherwise would give undue weight to the views of a small minority (see WP:NPOV). We do not want a bright high-school senior to read this article and come away with the idea that there are a large number (nor even a substantial minority) of mathematicians who have constructivist objections to the axiom of choice.

I don't believe anyone can seriously argue that the community of mathematical constructivists is not a small minority among practicing mathematicians today. However, I have looked up a reference to Troelstra's paper "History of constructivism in the 20th century" in which Troelstra writes,

"In the the foundational debate in the early part of this century, constructivism played an important role. Nevertheless, at any time only a handful of mathematicians have been actively contributing to constructive mathematics (in the sense discussed here)." ([2] p. 27)

This is particularly telling because Troelstra is an expert on constructive mathematics and is in an exceptional position to gauge the size of the constructivist community.

I don't think this reference needs to go in the article, since it is very tangential. But it does exist; there is not an issue with the verifiability of the claim there are only a small number of constructivists. — Carl (CBM · talk) 17:53, 30 June 2009 (UTC)

Carl, I appreciate your comments, but you're quoting Troelstra very selectively. Right after that part is:

"Much more research has been devoted to intuitionistic logic and the metamathematics of constructive systems. In this area the work has recently somewhat ebbed, but its concepts and techniques play a significant role elsewhere, e.g. in theoretical computer science and artificial intelligence,"

Intuitionistic logic plays a huge role in the semantics of programming languages; indeed, probably a greater role than classical logic.

But all this is beside the point: debates about the correlation between researcher self-identification ("mathematician" vs "computer scientist") and perceived utility of constructive methods is something that belongs in Constructivism (mathematics), not here.

AshtonBenson (talk) 23:16, 6 July 2009 (UTC)

I'm not saying anything about the utility of constructive methods; they are useful, and have nice applications to classical systems. Like I said, my concern is that it would be bad for our article to give the impression that constructivist objections to the axiom of choice have a significant following among mathematicians, when in reality that vast majority of working mathematicians have no objections at all to the axiom of choice. Mentioning the constructivist objections to the axiom of choice here is somewhat like mentioning the objections of people who think Barack Obama is not a U.S. citizen: these people do exist, and should be mentioned, but few people find their arguments convincing. — Carl (CBM · talk) 23:58, 6 July 2009 (UTC)

No -- you're saying something about how the people who find them useful self-identify ("mathematician"), and that is irrelevant. Moreover, "Barack Obama meets the criteria for citizenship in the USA" has a definite truth value; the usefulness of the constructivist viewpoint is a matter of opinion.

Look, the simplest solution is to remove anthropology from the article. I've reworded it to avoid any reference to people or social behavior and have simply stated the facts.

AshtonBenson (talk) 01:20, 7 July 2009 (UTC)

That there are only a small number of constructivists, and that their viewpoint is not considered compelling in the mathematical community, is not irrelevant. This isn't anthropology, it's an accurate representation of the due weight of constructivist views in an article on mainstream mathematics. — Carl (CBM · talk) 01:53, 7 July 2009 (UTC)

I think that Carl's edit was good and I accept his explanation for making it. But I think AshtonBenson's edit is a further improvement by skirting the issue entirely. CRGreathouse (t | c) 06:02, 7 July 2009 (UTC)

I'm largely OK with skirting the issue, but I think what remains is misleading in several ways, not all of them due to AB's changes:

* Saying constructivism is a foundation for mathematics presents constructivism as a unified thing, which really isn't true. Constructivists are in agreement on rejecting nonconstructive existence principles, but they can't agree among themselves on which ones those are.

* Relatedly, the claim that under constructivism all existence proofs are totally explicit is a claim without a clear univocal meaning.

* Finally, singling out the axiom of choice in this context is misleading because it leaves the impression that the rest of ZF is constructive, which I think virtually all constructivists will reject. Granted, there are a couple of links that will clarify the situation for the sufficiently motivated and prepared reader, but it's still a problem. AC is the only axiom of ZFC for which the nonconstructive nature is explicit in its form; it's by no means the only nonconstructive part of the theory. Just as an example, working informally but without using informal equivalents of choice, it's still easy to see there must be undefinable reals.

* Post-finally? (in a different paragraph) I think weakening the claim that most mathematicians accept AC as a "valid" way of proving results, to a "useful" one, is not justified. If you prove a claim using AC, for most mathematicians, that claim is proved. --Trovatore (talk) 09:24, 7 July 2009 (UTC)

I should think that Troelstra is right, although many mathematicians who don't consider themselves constructivists do have reservations about axiomatic set theory, which seems relevant for this article. I'm curious, does Troelstra count predicativism as a form of constructivism? — Charles Stewart (talk) 07:40, 7 July 2009 (UTC)

A deeper issue with the present article is that many of the best-known constructive systems do include the context-appropriate forms of the axiom of choice. For example, intuitionistic type theory and intuitionistic higher order arithmetic are often accompanied by forms of AC that appear very strong classically but are trivialities under the intuitionistic meaning of the AE quantifier. So it is not really the best presentation to simply say that constructivists dislike the axiom of choice, since many of them accept it fully. They have far deeper reservations about classical set theory, and as Trovatore says they would not accept ZF as constructive any more than ZFC. This was already a problem in the article before the latest discussion.

I think it would be more accurate, both from an historical perspective and a contemporary one, to arrange objections section something like this:

• Early objections: mostly due to the odd consequences of AC
• Constructivist objections: went beyond removing AC, proposed replacing set theory with other systems. Weyl, Brouwer, Bishop, etc.
• Category-theoretic objections: importance of canonicity and naturality. We can surely find a MacLane quote for this.

Thoughts about that? — Carl (CBM · talk) 15:52, 7 July 2009 (UTC)

I think that's a great idea. It might be a good idea to include pro-AC viewpoints in the section as well, to transform it from "criticism of AC" to "viewpoints on AC". There's no need to be contentious here! CRGreathouse (t | c) 14:26, 9 July 2009 (UTC)

Notation in Statement and Variants (and possibly later)

Instead of explanation of what is implicitly domain and range of the choice function, why can't we just be explict like in g:P(X)\{}->X when introducing it? Would shorten a bit. YohanN7 (talk) 17:39, 16 July 2009 (UTC)

If you mean the first sentence in the "Statement" section, it actually describes a function $f\colon X\to \bigcup X$. — Emil J. 17:46, 16 July 2009 (UTC)

I actually meant it throughout Statement and Variants. No big deal of course;)

BTW, are we striving for as many examples as possible in "Results requiring AC (or weaker forms) but weaker than it"? Sounds like it. There are definately objects in General Topology, for instance UltraNets and UltraFilters that in a way are very bizarre objects by definition that in my view easily top the Banach-Tarsi Paradox. They can be used to prove one way in the Tychonov Theorem. The proof of Tychonov is really supershort today. YohanN7 (talk) 18:24, 16 July 2009 (UTC)

Oops, I checked out the top section again, and there seem to be enough info already. My intention was that the section "Authors who use this formulation often speak of the choice function on A, but be advised that ..." could be shortened/removed, but if it serves some other purpose ... Too Tired;) YohanN7 (talk) 18:37, 16 July 2009 (UTC)

Bogus References

I have removed the reference to the 1908 paper "A new proof of the possibility of a well-ordering" which is cited in support of the assertion "it is now used without reservation by most mathematicians". The paper is only tangentially related to the assertion, and was published over a century ago -- a century ago cannot reasonably be construed as "now".

Frankly, I don't think this article even ought to be commenting on sociological issues like this, but that's another debate altogether.

Please do not add any more references unless you include the title of the work cited and the year of publication of the original work (not the year of republication in handbook form) in the citation. AshtonBenson (talk) 01:51, 30 August 2009 (UTC)

It appears that you did not look at the reference before you removed it. The text referenced on p. 183 is by van Heijenoort himself, not by Zermelo. One could argue about whether it is a great reference, but it certainly is not "bogus". — Carl (CBM · talk) 03:17, 30 August 2009 (UTC)

Regarding the inclusion of this information in the article, I think it is very germane. Given that there is much misinformation about the axiom of choice floating around, I believe that there will be a reasonable number of people who look to encyclopedias to determine the general opinion of mathematicians on the axiom. This is different than, for example, the principle of mathematical induction, which was never under serious dispute. — Carl (CBM · talk) 03:21, 30 August 2009 (UTC)

Anyway, here is a replacement reference that is much better than the one removed, both in terms of directly supporting the text ehre and in being a good general reference about certain aspects of axiom of choice.

Per Martin-Löf, "100 years of Zermelo's axiom of choice: What was the problem with it?", in Logicism, Intuitionism, and Formalism: What Has Become of Them?, Sten Lindström, Erik Palmgren, Krister Segerberg, and Viggo Stoltenberg-Hansen (2008), p. 210.

"Despite the strength of the initial opposition against it, Zermelo's axoim of choice gradually came to be accepted mainly because it was needed at an early stage in the development of several branches of mathematics, not only set theory, but also topology, algebra, and functional analysis, for example. Towards the end of the thirties, it had become firmly established and was made part of the standard mathematical curriculum in the form of Zorn's lemma."

— Carl (CBM · talk) 03:51, 30 August 2009 (UTC)

Finite analogue section

I think this section should be substantially edited or removed for good. Mainly because of its irrelevance to the general scope of the article, but also because it may lead to confusion regarding which are exactly the cases where AC doesn't need to be used.(Godelian (talk) 23:11, 13 September 2009 (UTC))

I tend to agree. Please inform 82.19.53.31 (talk · contribs · WHOIS) who has been adding it. — Arthur Rubin (talk) 23:28, 13 September 2009 (UTC)

To be fair, we do mention the issue of choice for finite sets in the lede, and so we ought to go into slightly more depth in the article proper. I am not sure that calling it a "finite analogue" is the right way to go, but an explanation why AC is not needed for finite sets would be in order. — Carl (CBM · talk) 00:44, 14 September 2009 (UTC)

Mycielski's anecdote

"Before these results appeared in Fundamenta Mathematicae in 1924, Tarski sent Lebesgue a note showing that (4.3.2) (m=m² for every infinite m) is equivalent to the Axiom, and asked him to submit it to the Comptes Rendus of the Paris Academy of Sciences. Lebesgue returned the note on the grounds that he opposed the Axiom, but suggested sending it to Hadamard. When Tarski did as Lebesgue advised, Hadamard also returned the note—saying that, since the axiom was true, what was the point of proving it from (4.3.2)?"

(G.H.Moore: Zermelo's Axiom of Choice, Springer, 1982, p.215, reference given as "Personal communication from Tarski (10 March 1982).")

Kope (talk) 05:58, 27 September 2009 (UTC)

Antichain principle

Could someone check that. My recollection of Equivalents of the Axiom of Choice (Rubin & Rubin), is that this only implies the axiom of choice in conjunction with "every set can be linearly ordered". My copy of Equivalents is missing, as a result of my layoff from my last employer, so I can't verify it. — Arthur Rubin (talk) 15:04, 20 October 2009 (UTC)

It's part of theorem 2.4 (page 5) in Horst Herrlich (2006), Axiom of Choice, Lecture Notes in Mathematics v. 1876, which is on Google books. It's also form 89 in Howard and Rubin (1998), Consequences of the axiom of choice, also on Google books. About the linear ordering part, I think you're right to some extent; apparently the equivalence requires the axiom of regularity. — Carl (CBM · talk) 16:21, 20 October 2009 (UTC)

Hello Arthur, I have added the equivalence based on Thomas Jech's book "The axiom of choice" (1973) which I have, in chapter 9, theorem 9.1, page 133. Sorry not to mention the reference before. The equivalence requires indeed the axiom of regularity; as done in Jech's book, the antichain principle implies that every linearly ordered set can be well-ordered, this in turn implies that the power set of a well-ordered set can be well-ordered and finally axiom of regularity allows to prove in ZF that this latter implies AC. I couldn't find a reference of this in "Equivalents...", though I only have 1985 edition (with your name on the dedication page:)). I did find there however the first-order logic form that I have also added (although I forgot to login before and thus only my IP is shown). So I think the dispute tag can be removed? Godelian (talk) 03:16, 21 October 2009 (UTC).

My mistake. My recollection was based on the fact that, "a set of sets has a maximal antichain (under inclusion)" does not imply the axiom of choice, as seen in Equivalences. Consequences of the Axiom of Choice (Howard & Rubin) would certainly have the correct details on this form, but my copy of that is missing, as well. — Arthur Rubin (talk) 14:26, 21 October 2009 (UTC)

Not entirely my mistake; it appears to follow in ZF, but not in ZFU. I found my copy of "Consequences"; the online resource reports 89 → 1 as code 6, which reads "known to be independent in ZF⁰ (ZFU, here). — Arthur Rubin (talk) 09:37, 24 October 2009 (UTC)

Indeed. In fact a similar thing happens with the statements mentioned before (every linearly ordered set can be well-ordered and the power set of a well-ordered set can be well-ordered) and also with the axiom of multiple choice. As with the antichain principle, they all follow from AC in ZFU, are equivalent to AC in ZF but AC is independent from each one of them in ZFU. - Godelian (talk) 18:15, 24 October 2009 (UTC)

Logic forms

I have noticed that no logic form has been added in the list of equivalences. To change this I had added the following form: "Every consistent subset of a set of sentences of first-order logic is contained in a maximal consistent subset of sentences". But then it was removed by someone explaining that meta-(first order logic) is not the subject matter of set theory. I wonder, though, if something should still be said about this. There are equivalences on several categories; why not adding a new one? Why wouldn't it be fair? - Godelian (talk) 18:28, 24 October 2009 (UTC)

I also wondered about that, because most of the other things there (topology, algebra, order theory, functional analysis) are also not the subject matter of set theory. On the other hand, we don't want to copy an entire book worth of equivalent statements here. I would suggest removing the antichain principle and the principle about products about uniform spaces. I don't have a strong opinion about the statement from logic. — Carl (CBM · talk) 01:44, 25 October 2009 (UTC)

I tend to think of the section as a way to show the wide variety of areas where AC appears in disguise, by means of a list that without being complete or extensive, is balanced enough as to give an idea of the large spectrum of fields where AC shows unexpectedly. In that sense I would say that I agree to shorten a bit the sublists of equivalences in a particular category, but having, on the other hand, at least one example of each area. Order theory has indeed many examples already, but I feel logic is a missing category and should be mentioned there. - Godelian (talk) 15:30, 25 October 2009 (UTC)

That seems reasonable to me. — Carl (CBM · talk) 15:32, 25 October 2009 (UTC)

Then, unless someone prefers otherwise, I would propose to re-add the mentioned logic form and remove one example from order theory. In this case, though, I would suggest removing the restricted Hausdorff maximal principle first, being a special case of a principle previously stated in the same category (even if its equivalence to AC means something stronger). Antichain principle, it seems to me, is more interesting since it provides a version opposed to it. - Godelian (talk) 17:11, 25 October 2009 (UTC)

The reason I slightly prefer the maximal principle is that I think it is more often stated in texts. For example it is stated (under the name "Kuratowski Lemma") on p. 33 of Kelley's General Topology. Also, for example, Gregory Moore's Zermelo's axiom of choice mentions the maximal principle relatively early (p. 168), but I don't believe it mentions the antichain principle at all. — Carl (CBM · talk) 17:32, 25 October 2009 (UTC)

I do agree with having Hausdorff maximal principle listed as it is now (second on the order theory sublist). What I doubt is having as well the restricted Hausdorff maximal principle, which is now third on the sublist and is a special case of the previous one. Even though its equivalence to AC may seem something slightly stronger, it also sounds somewhat redundant. Kuratowski lemma, as mentioned in Kelley's book, has the more general form instead of the special case. What I propose is just removing the special case, leaving the general maximal principle, and leaving the antichain principle as well to stress the contrast between these two. - Godelian (talk) 18:08, 25 October 2009 (UTC)

To Godelian: My reason for removing it was not that I felt it to be unimportant. Rather I believe that it is not equivalent. Perhaps you could give a proof here and convince me otherwise. JRSpriggs (talk) 20:06, 25 October 2009 (UTC)

That's a good point (I didn't think about the correctness). The Boolean prime ideal theorem (BPI) is enough to get the first-order completion of a theory, as follows: given a theory T, consider the dual of the Lindenbaum algebra for the empty theory in the signature of T, which is ordered so that stronger sentences rank lower in the order. Then the set of logical consequences of T determines an ideal, and any maximal proper ideal extending this ideal will give a completion of the theory.

Maybe a simpler way to see that S = "every consistent theory has a completion" is weaker than AC is to notice that S follows from Gödel's completeness theorem for first-order logic (any consistent theory has a model), which is in turn equivalent to BPI, which is weaker than AC. — Carl (CBM · talk) 21:18, 25 October 2009 (UTC)

Hello, please note the exact content of the equivalence I mentioned and that I'll write again here: "If $A$ is a set of sentences of first order logic and $B$ is a consistent subset, then there exists a maximal consistent subset $C$ that extends $B$". The equivalence is known since 1956 when G. Klimovsky first published it in "Contribuciones científicas" edited by Buenos Aires University. He mentioned there three related equivalent statements proving a chain of imlications between them. It also appears as Theorem 8.4 in "Equivalents of the axiom of choice II" (Rubin & Rubin), p. 165, where a direct proof is given. The proof is simple and follows more or less these lines: AC clearly implies the statement in question since the property of being consistent is a property of finite character. To prove the converse, let $X$ be a set of pairwise disjoint nonempty sets and consider the set of sentences of the following three types: 1) $\exists !x(u*x)$ for each $u\in X$. 2) $a\neq b$ for each $a,b\in \cup X$ such that $a\neq b$. 3) $u*a$ for each $a\in u\in X$. Then, if we consider the subset of all sentences of the first two types, a maximal consistent subset that extends it provides a choice function on X. - Godelian (talk) 22:00, 25 October 2009 (UTC)

I see; apparently I misread the statement too. I made some changes to the article just now to insert that, remove the uniform spaces equivalent, and condense the Hausdorff maximal principle bullets. — Carl (CBM · talk) 22:45, 25 October 2009 (UTC)

When I thought about how to prove that they were not equivalent, I realized that I was implicitly assuming that the set of symbols was countable. So I retract my statement. Sorry. JRSpriggs (talk) 22:48, 25 October 2009 (UTC)