Talk:Axiom of choice

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B Class

Top Priority

Field: Foundations, logic, and set theory

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
For comment, see below. CMummert 20:08, 6 October 2006 (UTC)

Archives
Aug 2004 – Sep 2004 Sep 2004 – June 2006

1 single members
2 Marxist POV
3 Three element choice, is it equivalent to AC?
4 Not AC: If one counter-example exists, then many exist.
5 Patrick Suppes
6 alternate definition by Suppes
7 model of not choice
8 ¬AC and Transfinite Power Set Cardinality
9 Question
- 9.1 Axiom of Choice does not help your problem
10 Proposed Changes
11 Determinacy
12 Math article rating
13 Ultrafilters
14 Tukey's lemma
15 Countable additivity of Lebesque measure?
16 The axiom of choice
17 Need a little clarification
18 2nd and 3rd paragraphs of "Usage"
19 GCH implies AC??
- 19.1 Another try
20 What is (G)CH really?
21 Implicit usage before 1900
22 What is the problem?
23 For those of us that are advanced at english, and still don't understand...
24 Minor change which reverses current sense
25 On New Theorems
- 25.1 Speed up of proofs using AxCh?
26 Logical independence
27 4th Paragraph of Usage

[edit] single members

The article states that the axiom choice says:

Let X be a set of non-empty sets. Then we can choose a member from each set in X.

Wouldn't it clearer to say a single member? It would make an intuitive description of its negation easier as well. --Michael C Price 18:32, 17 June 2006 (UTC)

I can't see how that would add anything at all, choice let's you choose a member from each set. It can also let you choose two members if you want, there's nothing particularly special about the number of elements. And there's nothing ambiguous about "a member". Can "a member" ever mean anything other than "a single member"? But on the other hand, it also doesn't detract anything to say "a single member" instead of "a member", so if you want to add it, I won't complain. -lethe ^{talk +} 18:50, 17 June 2006 (UTC)

You are grammatically correct, but all I can say is that I wondered if "a member" meant "a single member" until I came across the phrase "exactly one element" -- as opposed to "an element" -- a bit later in the article. I'm sure other casual "lay" readers might wonder the same thing as well. With this emphasized it makes it easier to express ¬AC as corresponding to haveing "sticky fingers", whereby every choice or picking operation pulls out more than one member from each set.--Michael C Price 20:04, 17 June 2006 (UTC)

I've never heard of this "sticky fingers" negation of choice which you describe. It seems to me that the ability to choose any finite number from each set of the collection is equivalent to AC. And obviously we can always "choose all at a time" without any form of choice. There may be weakened forms of choice which allow things like choosing countable subsets but not choosing single elements, though I've never heard of them. But this isn't a negation of choice. -lethe ^{talk +} 20:21, 17 June 2006 (UTC)

But you can't choose any finite number from each set with sticky fingers, because you can't choose just one. OK, I thought it was a good way of describing it to lay people like myself, but perhaps I'm wrong.... --Michael C Price 20:28, 17 June 2006 (UTC)

Suppose you had an axiom that allowed you to choose 3 objects from each of a collection of sets. I think I could prove that this allows also allows the choice of a single element. In other words, finite stickiness makes no difference. The only kind of stickiness that might matter would be an infinite stickiness; if you choose an infinite number from each set, then you may still not be able to also choose a single member. This wouldn't be a negation of choice though, just a weakened form. Anyway, I'm not sure of those theorems, they're just my intuition.

My intuition agrees with yours -- finite stickness makes no difference; no matter how many times you wipe your fingers you still an infinite number stuck -- but I wasn't sure enough to mention this earlier. --Michael C Price 20:47, 17 June 2006 (UTC)

As for finding a layman's description about choice, it's not hard. "Choose a member from each bucket" captures it exactly. What's hard is conveying to the layman why infinitely many choices is a lot less true than one might think. You might not be able to make infinitely many choices, and sticky fingers do not help. -lethe ^{talk +} 20:36, 17 June 2006 (UTC)

I agree it's not hard to find a description of AC -- the article is OK on that. What I was searching for is a balancing lay description of ¬AC, which is obviously harder since most mathematicans seem to think ¬AC is counter-intuitive. --Michael C Price 20:47, 17 June 2006 (UTC)

OK, I see. First of all, I will disagree about "most mathematicans seem to think ¬AC is counter-intuitive". ¬AC is quite weak, it simply says that there is one collection somewhere with no nonconstructive choices. Nonconstructive things are weird. Just because it's convenient to allow for the existence of those nonconstructive choices doesn't mean that mathematicians find their existence intuitive. Explanations of ¬AC are easier to give through equivalents, for example: the reals cannot be well-ordered or Hilbert space doesn't have an algebraic basis. These axioms both imply ¬AC. But the most explicit layman's description is this: there is some collection of buckets which is so infinitely big that, even though I could choose an element from any single bucket, I cannot choose elements one from each bucket all at the same time. -lethe ^{talk +} 21:10, 17 June 2006 (UTC)

Well, the quote section says "most mathematicians find the axiom of choice to be intuitive", and I took this as meaning that they therefore find ¬AC to be counter-intuitive. Your infinite number of buckets is OK as a lay description of ¬AC but that presumably doesn't exclude the "sticky fingers" analogy, which has the advantage that it only requires a finite number of sets / buckets. I guess it's a matter of taste; I find the sticky fingers picture more helpful than the infinite set example, which suggests that we should add both (or none) to the article. --Michael C Price 22:07, 17 June 2006 (UTC)

Your sticky fingers axiom is not a statement of ¬AC, but rather a weaker version of choice. -lethe ^{talk +} 22:16, 17 June 2006 (UTC)

Maybe you want to say this: "there exists a collection of sets such that any choice of members from each set must be sticky enough that for infinitely many of the sets, the choices include infinitely many selections". This may be implied by ¬AC. It would require proof though, and a standard reference, before it could go into the article. On the other hand, the statement that I gave you is just the logical negation of the normal wording for the AC. -lethe ^{talk +} 22:22, 17 June 2006 (UTC)

I don't see why the first use of "infinitely" is required; should it not be replaced with "some"? -- or the number of sets such be specified as infinite. So either:

"there exists an infinite collection of sets such that any choice of members from each set must be sticky enough that for infinitely many of the sets, the choices include infinitely many selections"

"there exists a collection of sets such that any choice of members from each set must be sticky enough that for some of the sets, the choices include infinitely many selections"

I prefer the last wording, if possible. --Michael C Price 22:46, 17 June 2006 (UTC)

If I have a choice which is infinite at only finitely many buckets, then I have a choice which is never infinite (just apply finite AC to those buckets), and then this is not a negation. It seems to me that it has to happen infinitely often that you have to choose infinitely many with your sticky fingers. -lethe ^{talk +} 22:53, 17 June 2006 (UTC)

I confess I don't follow your logic (especially the bit in parenthesis) -- but that doesn't mean you're wrong! I take it that the first wording is acceptable then? --Michael C Price 23:09, 17 June 2006 (UTC)

You can always make a finite number of choices. This follows from ZF (sometimes it's called the finite axiom of choice, though it is no axiom). So if you have a collection of buckets and a choice which picks infinitely many elements at finitely many buckets, then, for those buckets, you can make a new choice function that chooses 1. Splice this back into the collection of all the buckets, and you have a choice function. As for the first formulation, I believe it implies ¬AC. I do even think it's equivalent to ¬AC. -lethe ^{talk +} 23:28, 17 June 2006 (UTC)

OK, so how adding this at the end of the statement section:

The negation of the axiom of choice, ¬AC, implies that there exists an infinite collection of sets such that for any choice of members from each set, and for infinitely many of the sets, the choices return infinitely many members.

No mention of stickiness! --Michael C Price 00:27, 18 June 2006 (UTC)

I'm not especially fond of this formulation mostly for the reason that it is a fairly nonstandard usage of the notion of choice. Usually, choice is a function, which necessarily entails only a single choice. These multivalued choices will have to have different mathematical description. It could be done of course, but I'd feel better if there were an external source for it. Dreaming up our own new equivalents of choice may be a violation of WP:NOR. -lethe ^{talk +} 00:42, 18 June 2006 (UTC)

I hadn't realised choice implies only one, but having looked it up I see it does. My apologies for wasting your time. --Michael C Price 00:52, 18 June 2006 (UTC)

No apologies necessary; it's not a waste of my time. I always enjoy talking about the meaning of choice. -lethe ^{talk +} 09:42, 18 June 2006 (UTC)

OK, I have another query, which I'd better get straight before anything else. The formal definition of AC states:

Let X be a set of non-empty sets. Then there exists a choice function f defined on X. In other words, there exists a function f defined on X, such that for each set s in X, f(s) is in s.

Now I know that mathematicans all realise that this means "For any set X", but shouldn't we be explicit? How about:

For any set of non-empty sets, X, there exists a choice function f defined on X. In other words, there exists a function f defined on X, such that for each set s in X, f(s) is in s.

which permits an even more compact formulation of AC:

Every set has a choice function.

which is also trivially true for the empty set. If this is acceptable then ¬AC is just trivially

There exists a set without any choice function.

--Michael C Price 14:42, 18 June 2006 (UTC)

From what JRSpriggs says we can see that a consequence of one ¬AC set is that an infinite number of ¬AC sets must exist must also exist. Is that right? --Michael C Price 14:47, 18 June 2006 (UTC)

The verbiage "let X be something something. Then do something else, then I assert this about the result" is useful when you're going to do a lengthy manipulation with X. But here, we are simply asserting something about X, so that turn of phrase is needlessly verbose, and I would support the change you suggest. But your third suggestion, "every set has a choice function", is a little bit tricky. Only for sets of nonempty sets does the choice function make sense. Of course, in the familiar models of ZFC, every element of every set is also a set, so it's redundant to say "set of sets". Every set is a set of sets. But of course, they still have to be nonempty. Despite these misgivings, I still use "every set has a choice function" when speaking colloquially, I do think it's useful, as long as everyone knows the provisos. -lethe ^{talk +} 14:53, 18 June 2006 (UTC)

I'm not suggesting that we lose the any of the longer, more formal definitions, just add the more compact one as well. BTW I'll add the non-empty qualifier; whether or not it is required I'm not sure (you seem to suggest it is), but it certainly makes it less confusing for the lay reader. --Michael C Price 16:06, 18 June 2006 (UTC)

[edit] Marxist POV

There's an historical or cultural aspect of the AC that was related to me by a mathematican once that -- if true -- might be worth mentioning in the article. He claimed (and it seemed plausible to me) that the AC was looked upon with disfavor by the Soviet authorities (and many of their mathematicans) because it was judged to be anti-egalitarian. That you couldn't select just one member out of any set made a lot of sense within their dialectic and skewed their focus accordingly. --Michael C Price 20:04, 17 June 2006 (UTC)

If true, it was well disguised, since Soviet functional analysts (Israel Gelfand, Pontryagin, Krein, among many many others) relied on maths drenched in the blood of choice. However, there is an article buy Joseph Dauben (a reputable math historian, author of a book on Cantor for instance) entitled Marx Mao and Mathematics: The politics of infinitesimals, in which he discusses a group of Chinese mathematicians in the 1970's that proposed that nonstandard analysis developed in the 1960s by Abraham Robinson and which is heavily based on choice, was a realization of a program on the foundations of mathematics proposed a century earlier by Karl Marx. The article is an interesting read. I'm sure you can find it by googling. If not, I can email it to you.--CSTAR 21:37, 18 June 2006 (UTC)

Fascinating. Is there more too it than at [1]? --Michael C. Price ^talk 21:55, 18 June 2006 (UTC)

Not unless you have more than a passing interest in nonstandard analysis.--CSTAR 21:59, 18 June 2006 (UTC)

I can't find any evidence for the Soviets' dislike of AC; I guess it was a joke that was taken too seriously. --Michael C. Price ^talk 22:49, 18 June 2006 (UTC)

Though it is possible that such a thing happened, I consider it very unlikely. --CSTAR 23:01, 18 June 2006 (UTC)

[edit] Three element choice, is it equivalent to AC?

In the discussion above, Lethe said "Suppose you had an axiom that allowed you to choose 3 objects from each of a collection of sets. I think I could prove that this allows also allows the choice of a single element.". I do not see how this could be shown. I suspect that it is strictly weaker than the full AC. JRSpriggs 10:26, 18 June 2006 (UTC)

Hmm, actually, I think you're right. I imagined some repeated application of the axiom could pare it down to one, but that make sense at all, does it? So Michael, in light of JR's correction, you could formulate your idea as:

"there exists an infinite collection of sets such that any choice of members from each set must be sticky enough so that for infinitely many of the sets, the choices include more than one selection"

-lethe ^{talk +} 11:12, 18 June 2006 (UTC)

My go-to reference for choice questions, Handbook of Analysis and its Foundations by Eric Schechter, says that MC, the multiple choice axioms, which asserts that it is possible to choose a nonempty subset from each of a collection of nonempty sets, is equivalent to AC (and notes that in particular regularity is necessary). Certainly three element choice implies MC. Thus actually the ability to choose 3 (or any finite number) from every set in a collection is equivalent to AC. Schechter says the proof is too long to include, so I guess it's not obvious, but true. -lethe ^{talk +} 17:23, 22 June 2006 (UTC)

too long to include LOL, shades of Fermat! --Michael C. Price ^talk 17:28, 22 June 2006 (UTC)

MC(infinity, infinity, 3) (for every set of non-empty sets, there is a "choice" function which chooses a subset of from 1 to 3 elements of each set) is mentioned as equivalent in both versions or Equivalents of the Axiom of Choice. That there is a choice function which, for every set of sets of 2 or more elements, chooses a proper subset of each element, appears not to be equivalent to the axiom of choice. I believe it's referred to as KW, the Kinna-Wagner (?) principle, in Consequences of the Axiom of Choice. — Arthur Rubin | (talk) 17:47, 22 June 2006 (UTC)

Er, I assume that MC is the requirement that you can choose a family of proper subsets from each of a collection of nonempty non-singleton sets, or something like that.

Can you check?

The condition you described is trivially true, as you can always choose the family of subsets to be the family of sets you began with; the condition I described isn't implied by three element choice.

In fact, without AC, it's possible to have a family of sets of cardinality three without having a choice function for that family. My somewhat naïve intuition is that you start with a model of ZF-C with such a family, then add sets to satisfy three element choice, but none of them are going to give you a choice function for that family, so AC isn't true ... no idea whether that works :-)

RandomP 17:50, 22 June 2006 (UTC)

(Given Arthur's reference, my intuition was obviously not correct. RandomP 17:52, 22 June 2006 (UTC))

I think I have to go to symbols:

By MC_3, I mean (at least in ZF -- ZFU requires more work):

$(\forall X)((\forall x \in X)(\exist y \in x)(True) \rightarrow (\exists f)(\forall x \in X)(f(x) \subseteq x \and 1 \leq |f(x)| \leq 3))$

KW (the Kinna Wagner principle) is

$(\forall X)((\forall x \in X)(|x| \geq 2) \rightarrow (\exists f)(\forall x \in X)(\emptyset \subsetneq f(x) \subsetneq x))$

If I'm misinterpreting either of the versions of choice stated in English above, I apologize.(As an aside, the second google reference to Kinna Wagner is a paper which I was a co-author on.) Kinna Wagner Selection Principles, Axioms of Choice and Multiple Choice (PDF). — Arthur Rubin | (talk)

[edit] Not AC: If one counter-example exists, then many exist.

If there is one counter-example to the axiom of choice, then there must be many counter-examples. This follows from the fact that there are many ways of encoding the first choice problem as a problem with different sets. For example, if X is the given set of nonempty sets which lacks a choice function, then consider the powerset (minus the singleton of the empty set) of the union of X. If that set had a choice function, then it could be used to well-order the union of X and thus get a choice function for X. Or one could take any other superset of X which has only nonempty members. Or one could form the set of Cartesian products of elements of X with a fixed nonempty set. JRSpriggs 10:35, 18 June 2006 (UTC)

Also, if Y is a subset of X, the set of nonempty sets which lacks a choice function, then either Y or X-Y or both must lack a choice function. JRSpriggs 04:23, 21 June 2006 (UTC)

[edit] Patrick Suppes

I see that:

"Every set has a choice function."^[1]

has been changed to:

"Every set of nonempty sets has a choice function."

Why was it necessary to change it? Wasn't the first one clearer? --Michael C. Price ^talk 22:36, 19 June 2006 (UTC)

^ Patrick Suppes, Axiomatic Set Theory, Dover (1972) pp240, chapter 8, The Axiom of Choice

--Michael C. Price ^talk 22:36, 19 June 2006 (UTC)

Well User:Chinju is correct; only sets of nonempty sets have choice functions. Whether we want to favor pedantic correctness or colloquial compactness is a question I guess. Are you saying that Suppes uses this phrasing without bothering about empty sets? -lethe ^{talk +} 22:53, 19 June 2006 (UTC)

After defining the choice function he says:

Using this definition the axiom of choice may be formulated. Every set has a choice function, although in the formulation given above of the axiom it was not required that the domain of f be restricted to non-empty sub-sets of A. However this is a trivial difference.

His italics, BTW, not mine, in case you wondered.

And why are we talking about sets of sets and not just sets in the most compact form? Doesn't the set of cats admit a choice function? --Michael C. Price ^talk 23:13, 19 June 2006 (UTC)

No. Cats don't have elements, sets do. -lethe ^{talk +} 23:34, 19 June 2006 (UTC)

For example, the set { {1,2} , {4,5} } has a choice function f({1,2}) = 1 and f({4,5}) = 5. What would be a choice function for {snowball, mittens, socks, cleopatra}? -lethe ^{talk +} 23:41, 19 June 2006 (UTC)

Okay, I give up. Why not f({snowball,mittens}) = snowball etc? I'll sleep on it. And read Suppes. --Michael C. Price ^talk 01:02, 20 June 2006 (UTC)

{snowball, mittens} is not an element of the domain, but rather a subset of the domain. Functions act on elements. snowball is an element of the set. What will you choose f(snowball) to be? -lethe ^{talk +} 01:11, 20 June 2006 (UTC)

Hmmm. That seems to contradict Suppes. I have just scanned in the 1st 2 pages of Suppes's chapter on Axiom of Choice. .JPG 401 KB or .TIF 10.3 MB, which do you prefer and how do I send them to you? Then we will be singing from the same hymn sheet.... --Michael C. Price ^talk 10:24, 20 June 2006 (UTC)

I just sent you an email, which you may reply to with an attachment. -lethe ^{talk +} 10:28, 20 June 2006 (UTC)

[edit] alternate definition by Suppes

According to a scan of a page from Suppes's textbook that Michael has provided me, the definition that Suppes uses is this: "For any set A, there is a function such that for every non-empty subset B ⊆ A, f(B) ∈ B". This function acts on all subsets of A, so its domain is the powerset P(A). So Suppes' axiom of choice states in our language "the powerset of every set has a choice function". A priori this looks weaker than the version we have in the article, which states that every set, not just sets which are powersets, has a choice function. Let's see if we can figure out that it's actually equivalent. For finite sets, there are a lot of sets which are not powersets; any set whose cardinality is not a power of 2 certainly cannot be a powerset. Finite sets don't matter when it comes to choice though. For infinite sets, cardinal arithmetic becomes a little simpler. If we assume the generalized continuum hypothesis, then every (infinite) set is equipollent with a powerset, so I think that Suppes's axiom of choice is equivalent to ours. However the GCH is independent of ZFC and many authors prefer not to have it, so Suppes's axiom of choice may be strictly weaker than our axiom of choice. That bothers me quite a bit, though I'm sure Suppes knows what he's doing. I actually have a copy of this book, but I lent it to one of my students. I'd like to see what he's doing with the GCH here.

Anyway, the issue that's concerning you about sets of sets versus sets is not contradicted by Suppes; his function acts on powersets, which are always sets of sets (of cats), never sets of cats. The issue here is that functions take as arguments elements of their domain, not subsets of their domain. That's just part of the set-theoretic definition of a function. Well, Suppes defines the term "choice function" slightly differently. For Suppes, a "choice function on A" is a function whose domain is the powerset of A, while for us, a choice function of a set is the set itself, but the set must also be a set of nonempty sets. So the statement "every set has a choice function" makes sense with Suppes's definition of choice function, but not with ours. -lethe ^{talk +} 10:48, 20 June 2006 (UTC)

Using the above cat example, we may have a function such that f({snowball,mittens}) = snowball and so on. But this is a choice function on the powerset of {snowball, mittens, socks, cleopatra}, not on the set {snowball, mittens, socks, cleopatra} itself. So there is no contradiction with Suppes. I'm still disturbed by the fact that Suppes takes a strictly weaker form of choice though. JRSpriggs, can you check my reasoning above? Is this formulation of choice strictly weaker? -lethe ^{talk +} 10:53, 20 June 2006 (UTC)

I argued above that this axiom is strictly weaker than choice because not every set is a powerset. But actually, every set is less than some powerset (by Cantor), and choice functions on powersets restrict to choice functions on subsets of the powerset. So actually, I think Suppes's definition is equivalent to our version of AC, even in the absence of GCH. Also, I note that GCH implies AC, so this would be a pretty useless axiom in the presence of GCH. Alright, I'm satisfied with Suppes's formulation. Sorry for my tangent, Michael. -lethe ^{talk +} 11:09, 20 June 2006 (UTC)

OK, I've reverted it back to your last version. Does someone need to change choice function as well, or is that OK? --Michael C. Price ^talk 11:38, 20 June 2006 (UTC)

Regarding the revert; Chinju's edit was correct, we do have to only consider collections of nonempty sets. You've reverted to the version that is compatible with Suppes's definition, rather than ours. I won't complain too much though, because if we are seeking the most compact description, then we may understand the nonempty requirement to be implicit.

Regarding choice function: it is OK, it currently defines the function in terms of arbitrary sets of sets, rather than powersets of arbitrary sets. I would not at all mind if we included both definitions though. Wonder what others think about that; including two very similar but slightly different definitions might do more harm then good, cause confusion with the struggling student. -lethe ^{talk +} 11:47, 20 June 2006 (UTC)

Sorry, I misunderstood you. When you said they were equivalent I assumed this meant that Suppes' definition was, er, equivalent. Hmmm. If there is a difference then I think both definitions should be mentioned. If Suppes' def' allows you choose a cat from a set of cats and the other doesn't, then I would opt for Suppes as the more intuitive and the less likely to trip up the struggling student (such as moi). --Michael C. Price ^talk 11:55, 20 June 2006 (UTC)

Right, I meant that the two axioms (in terms of different definitions) were equivalent, not that the definitions were equivalent (they're not). But I think you're right; the Suppes definition is more intuitive. I think the current definition is more standard though, so I would like to have a large consensus before doing something drastic like changing definitions, and mentioning them both side by side seems awkward and liable to confuse because of the similarity. I'm not sure what the right solution is. -lethe ^{talk +} 12:06, 20 June 2006 (UTC)

Actually not only are the two formulations of AC the same, but so are the two formulations of choice. Let X = P({set of all cats}). The choice function is applied to all subsets of X, namely each {set of some cats} and we get f({set of some cats}) = a cat. So the choice function can act on sets of just urelements to select single elements, as you would expect intuitively. This equivalence means that the most compact version of AC, Suppes's that every set has a choice function, is valid ....? --Michael C. Price ^talk 08:09, 22 June 2006 (UTC)

The set of all (nonempty) sets of cats is a set of nonempty sets. With our definition of choice function, it only makes sense for sets of sets, and is only well-defined for sets of nonempty sets. The function you describe is defined on X, the power set of the set of cats. The choice function acts on elements of X (sets of cats), not subsets of X (sets of sets of cats). The domain of f is X (a set of sets of cats), though it can be restricted to subsets of X (any other set of sets of cats; this is why the Suppes formulation is equivalent).-lethe ^{talk +} 09:55, 22 June 2006 (UTC)

Let $A=\prod_{i\in I} A_i, B=\bigsqcup_{i\in I} A_i$ , with all the A_i nonempty. Let f be a Suppes choice function on B. Then $(f (A i)) i$ is an element of A, so A is nonempty, so (AC) holds.

Conversely, if (AC) holds, we can well-order any set X, and define a Suppes choice function f by that, so the two are equivalent.

Is that what you were looking for?

(Hope I didn't screw up)

RandomP 11:18, 20 June 2006 (UTC)

Well I guess I resolved this for myself while you were typing up this reply, but this is also a pretty explanation of why the two are indeed equivalent. Thank you for helping resolve my confusion. -lethe ^{talk +} 11:35, 20 June 2006 (UTC)

Lethe asked whether Suppes's formulation (For any set A, there is a function such that for every non-empty subset B of A, f(B) is in B.(emphasis added)) is strictly weaker than the one we use here (Every set of nonempty sets has a choice function.). For any set X, X is a subset of the powerset of the union of X (assuming that X contains no urelements). Take A to be the union of X. If S is any element of X, then S is a subset of A. Thus Suppes's f(S) is an element of S. So the restriction of Suppes's choice function to X (which is a subset of its domain) is a choice function for X. So you are correct that Suppes's version of AC is equivalent to ours. JRSpriggs 05:20, 21 June 2006 (UTC)

There is another point which I think needs to be clarified. Suppes's statement of AC amounts to saying that for any set A, the powerset of A (minus the empty set) has a choice function. This is NOT the same as saying that A itself has a choice function. A choice function for the powerset is not a choice function for A. Although as I explained above the two formulation are equivalent as universal statements. Michael seems to be confusing the two. JRSpriggs 08:34, 23 June 2006 (UTC)

I am certainly very confused and thanks for trying to clarify things. --Michael C. Price ^talk 08:44, 23 June 2006 (UTC)

Under variants it says:

Suppes has a third version which effectively says:

For any set A, the powerset of A (minus the empty set) has a choice function.

but Suppes also says that this is equivalent to

Every set has a choice function.

so I am still confused. --Michael C. Price ^talk 10:00, 23 June 2006 (UTC)

Suppes is using a different definition of choice function than us.

Granted; his definition of AC is in terms of his definition of choice function (well, it has to, hasn't it?). That's what I meant. The article needs to be clearer on this. --Michael C. Price ^talk 11:04, 23 June 2006 (UTC)

The article currently uses only our definition of choice function, never his. I think that's as clear as it can be, right? Therefore the formulation "every set has a choice function" has no place in the article. Alternate definitions of choice function might be appropriate in that article, but I think here they would confuse more than they would help. -lethe ^{talk +} 11:07, 23 June 2006 (UTC)

I've changed my mind. I added some text to the article. How do you like it? -lethe ^{talk +} 11:15, 23 June 2006 (UTC)

That clears up things for me considerably. :-) I took the liberty of some very minor tweaks on use of pronouns. The real mystery remaining is why this version of choice and AC isn't more popular -- it's so much simpler!. And yes, I think choice function should also reflect the choice in choice functions available. --Michael C. Price ^talk 11:33, 23 June 2006 (UTC)

As I mention below, Schechter uses this as his principle formulation. Perhaps it's more popular than you think! -lethe ^{talk +} 11:42, 23 June 2006 (UTC)

If we say we have a choice function on a set, that means the set is the domain of the function. When Suppes says it, he means the powerset is the domain. In other words, for us, a choice function acts on elements of a given set of sets (of cats), while for him, a choice function acts on subsets of a given set (of cats). -lethe ^{talk +} 10:43, 23 June 2006 (UTC)

For the record, while Schechter spends copious amounts of times with many variant formulations of choice, he uses Suppes's definition as his principle formulation of choice. So that formulation is not unique to Suppes. -lethe ^{talk +} 10:47, 23 June 2006 (UTC)

I appreciate the time everyone's taking to explain these things to me, but I have a further clarification. When you say

Schechter .... uses Suppes's definition as his principle formulation of choice.

do you mean by choice: choice function or axiom of choice or both? --Michael C. Price ^talk 11:56, 23 June 2006 (UTC)

Sorry about a delayed reply. I must have missed this addendum. Anyway, I meant that Schechter uses the formulation of the axiom of choice in terms of subsets of a given set. He doesn't actually take the time to single out the concept of a "choice function". He just says there is a function on all nonempty subsets of a given set such that f(U) ∈ U. He calls that AC1, it coincides with Suppes. Then I think it was AC3 (I don't have it in front of me at the moment) which says that for any collection of sets, there is a function such that f(A) ∈ A, which coincides with that used in this article. I guess if you want to talk about choice functions, then your hand is forced about which definition of choice function you have to use depending on which formulation of AC you want to take. -lethe ^{talk +} 05:48, 11 July 2006 (UTC)

[edit] model of not choice

I would like to read about models of the negation of AC. Are the constructions too elaborate to be described in a paragraph? I had some idea that Goedel's constructible universe at some IC ought to be a model of not choice since it contains only constructible sets, whereas the axiom of choice predicts the existence of sets which are not constructible. However the article on ICs says that L_k is a model of ZFC; it does model choice. That seems contradictory to me. What is wrong with my reasoning? -lethe ^{talk +} 18:13, 22 July 2006 (UTC)

It's complicated. (And this is my field, so please bear with me.) Because the constructible sets are constructed, there is a constructible choice function on the constructible sets. Hence, the inner model L satisfies the axiom of choice.

As for models without choice, it's relatively easy to construct inner models of ZFU (with ur-elements) in which choice fails by looking at the elements preserved by one of a filter of permutations. Probably the simplest technique would be to start with a model M of ZFC and "add" a countable set U of ur-elements to get a model M[U] (or L[U] within M). Any permutation of U can be extended to a permutation of M[U]. Consider the group G of all permuations of U, and the filter F of subgroups of G generated by the subgroups which fix a finite subset of U. The class N of all elements of M[U] which are preserved by all elements of some subgroup in F form a model of ZFU in which choice fails.

To construct models of ZF-C, the concept of forcing or of Boolean-valued models has to be extended to include a filter of permutations of the forcing set or Boolean algebra (respectively), and only allow the new model to include those "sets" which are preserved by a subgroup of the permutation group which lies in the filter.

The Cohen reference in forcing has a few of the simpler constructions for models of ZF-C, as well as ZF-CH.

— Arthur Rubin | (talk) 19:37, 22 July 2006 (UTC)

Im going to take some time to digest your response about the filter of subgroups of permutations of urelements, but thank you. I guess I should also find the Cohen reference? According to the article, there is a more modern treatment of the subject which is easier. Can I find the same material (examples of models of not choice) in newer texts? And about your first paragraph: am I to understand then that L contains constructible Vitali sets, for example? -lethe ^{talk +} 04:52, 23 July 2006 (UTC)

If you read the article on the constructible universe, you will see that L is well-ordered by the order in which the constructible sets are constructed; and this order is itself constructible. There is a subtle difference between a set being constructive and constructible (in the sense of L). When constructing constructible sets one is given free use of the ordinal numbers and also of the hierarchy L_α. The usual notion of constructive would not allow that because there are ordinals which are not the order-type of a recursive well-ordering of the natural numbers. And gathering all the Δ₀ subsets of L_α together to form L_α+1 is not a constructive operation. Yes, there are constructible Vitali subsets within the constructible real numbers. But if there are non-constructible real numbers, then there will not be any constructible Vitali set within the set of all real numbers (including the non-constructible reals). JRSpriggs 11:27, 23 July 2006 (UTC)

To Lethe: You said "the axiom of choice predicts the existence of sets which are not constructible". Not so. The axiom of choice allows one to give a non-constructive proof of the existence of certain sets. That does not preclude the possibility that one might be able to construct those sets by some other method. Indeed, in the case of L, one proves that the axiom of choice holds in L by showing how one could construct such sets. JRSpriggs 03:45, 24 July 2006 (UTC)

[edit] ¬AC and Transfinite Power Set Cardinality

Without assuming the axiom of choice we have

x < 2 x

for all cardinals, x (finite, transfinite or infinite).

But what about

x n < 2 x

where n is any finite cardinal? It's true if x is infinite, false if x is finite, but what about if x is transfinite? --Michael C. Price ^talk 12:52, 23 July 2006 (UTC)

What do you mean by "transfinite"? Usually it is either a synonym for "infinite" or for "finite or infinite". JRSpriggs 03:47, 24 July 2006 (UTC)

But is that because people usually assume AC? Suppes page 155 says "It should be clear from earlier remarks that every known proof that a cardidinal is transfinite if and only if it is infinite depends on the axiom of choice". (See my comments at Talk:Transfinite_number#Definition_of_transfinite) --Michael C. Price ^talk 06:38, 24 July 2006 (UTC)

I doubt that 2^x can be <= x^n, for x infinite and n finite, but it's clear that x^2 <= 2^x provides more structure on x than can be guaranteed without some form of choice. If x is transfinite (i.e., ~~$α 0$~~ $\aleph_0$ <= x) and linearly ordered, than x^n <= 2^x. Otherwise, it's not at all clear. — Arthur Rubin | (talk) 06:07, 24 July 2006 (UTC)

I take it you meant to type $\aleph_0$ rather than

α 0

(otherwise please explain). The issue here seems to be that Michael has some nonstandard understanding of what "transfinite" means; I haven't yet understood exactly what he thinks it means (see talk:transfinite number#Definition of transfinite). Until that point is clarified there's not too much point in trying to answer the original question. --Trovatore 06:15, 24 July 2006 (UTC)

[edit] Question

Does the statement "Given *one* non-empty set, one can choose some element of it" require the axiom of choice?

This is implicitly included in the article, when it discusses choice for finite families of sets. The axiom of choice is not necessary to choose an element of a single nonempty set. The formal reason for this is that there is a deduction rule (sometimes known as existential elimination) which says that if you have proved $\exists x \phi(x)$ then you can take a new (not previously used) constant symbol c and assume $\phi(c)\,$ holds, and this is a sound proof technique. Saying that a set A is nonempty means $\exists x ( x \in A)$ , from which you get $c \in A$ for a new constant c. (This proof technique is even valid in intuitionistic logic assuming you have shown $\exists x (x \in A)$ and not just $\lnot \lnot \exists x (x \in A)$ ). CMummert 18:49, 26 August 2006 (UTC)

Suppose someone holds out a bag and says "This bag may or may not contain some marbles (but not anything else).". If you reach into the bag and try to grasp a marble, what happens? If you get one, then you have chosen a distinguished marble from among those in the bag. If not, then the bag must have been empty. In other words, a set being non-empty MEANS that you can choose an element from it. Consequently, ordinary first-order logic allows you to choose an element from a single non-empty set without having to use the axiom of choice. If you can do this once, then you can repeat it any finite number of times. So you can create a choice function for any finite collection of non-empty sets without using the axiom. Thus the axiom is only needed for infinite collections of non-empty sets; and even then only if no systematic method of choosing is known. Does that make it clear? JRSpriggs 07:12, 27 August 2006 (UTC)

Clear, but I don't believe it. Are you not assuming that we have an operation that can select just one element from the set? Suppose everytime you tried to pick a marble you always got an indefinite handful? See the "sticky fingers" metaphor discused awhile back. --Michael C. Price ^talk 07:23, 27 August 2006 (UTC)

Well, you are not talking about the real world which is what classical logic addresses. In some other universe, perhaps a different kind of logic would be appropriate where such choice was not allowed. But then what does existence mean in that universe? JRSpriggs 08:49, 27 August 2006 (UTC)

At the risk of sounding like a maths crank, surely appealing to the "real world" is a strange way for a mathematican to argue? AC is equivalent to being able to select (I delibrately avoid the word "choose") a single subset from every set. Therefore the negation of AC states that there exists at least one set for which we can't select a single subset. Ergo, unless we assume AC, we can't assume that we can pick an element from a single, arbitrary set; the answer to the opening query would seem "yes". If this isn't true then the article needs to explain this more clearly. --Michael C. Price ^talk 20:10, 27 August 2006 (UTC)

It's not true at all that the AC is required to choose an element from an arbitrary nonempty set. The claim of equivalence in the previous post simply isn't correct. What the AC is required for is to uniformly choose elements from a family of nonempty sets, all at the same time. This is what the second paragraph of the introduction clearly states, and the definition in terms of choice functions makes precise. The article attempts to address this in the section on choice for finite families of nonempty sets; anyone is free to edit that section to make it clearer if they wish. I added the word simultaneously to the definition, which might help resolve this confusion. CMummert 21:27, 27 August 2006 (UTC)

My interpretation was based around Axiom_of_choice#Variants, which uses an intuitive notion of choice as the original query related to, which states:

With this alternate notion of choice function, the axiom of choice can be compactly stated as

Every set has a choice function.^[1]

No notion of uniformity or simultaneity is required. I don't see where my logic fails with this equivalent definition. --Michael C. Price ^talk 03:04, 28 August 2006 (UTC)

In that "variant" the definition of a choice function on a set A is a function that simultaneously chooses an elemenent from every nonempty subset of A. Let's stop talking about this here; the article is correct, and you can get people to explain it at the reference desk if you don't want to read it carefully yourself. Anyone is free to edit the article if they feel it is unclear. CMummert 10:38, 28 August 2006 (UTC)

I think that this discussion is productive and that this is the right place. Understanding what parts of the article may be unclear, especially to those new to the field, can help us rewrite it more clearly. I don't yet have a good idea, so I haven't edited that part of the article, but I may yet. CRGreathouse (t | c) 15:49, 28 August 2006 (UTC)

Yes, this is a productive discussion which CMummert has misunderstood: we are not arguing about whether the article is correct but about its interpretation. Since the notion of choice can be applied to a single set talking about simultaneity is a red herring. Rephrasing the original question slightly:

Given one arbitrary set can we definitely choose one element of it without assuming the axiom of choice?

I would have thought that the answer is obviously no, but absurdo reductum proceeds thus: Assuming the negation of AC, there exists a set from which just one element can not be choosen. Ergo the axiom of choice must be assumed. Clearly the article needs to be explicit about this. --Michael C. Price ^talk 10:12, 29 August 2006 (UTC)

That's not correct. But I don't know where your interpretation error lies. — Arthur Rubin | (talk) 12:51, 29 August 2006 (UTC)

You'll understand, I hope, that I would find an explanation of why I am wrong more satisfying? --Michael C. Price ^talk 12:54, 29 August 2006 (UTC)

Yes, I can understand that. But it's been explained early in this section that the axiom of choice is not needed to select one element from a single non-empty set, and nothing you've said here relates to that argument. In fact, CMummert gave a nearly formal proof. — Arthur Rubin | (talk) 13:51, 29 August 2006 (UTC)

CMummert's "proof" would seem to make the axiom of choice redundant, if it is to be believed. I can see that $\exists x \phi(x) \Rightarrow \phi(c)$ but how does that show that c can be choosen? It seems to beg the question by assuming AC --Michael C. Price ^talk 18:50, 29 August 2006 (UTC)

It's a logical concept, rather than one in set theory. If something exists, it can be explicated (i.e., chosen). This can be extended to a choice function on any finite (as seen from the meta-theory) set (at least in "conventional" logic — as is pointed out in the text, the axiom of choice for sets containing two, not necessarily distinct, elements, implies the law of the excluded middle). Proving, within (conventional) set theory, that any "finite" set has a choice function is more difficult. — Arthur Rubin | (talk) 19:07, 29 August 2006 (UTC)

And leaves open the question of infinite sets, which are the only sets for which AC is required. --Michael C. Price ^talk 19:15, 29 August 2006 (UTC)

The axiom of choice is a mathematical statement; specifically, one that is formulated in the language of set theory. From the mathematical point of view, I don't see what "we" and "definitely" (and also "choose") means. You may be talking about a class version of choice (since you consider arbitrary sets), or you may be talking about introducing an existential quantifier (since you consider one set only). Or (most likely) you mean something entirely different. --Aleph4 11:58, 29 August 2006 (UTC)

Mathematical statements are also capable of expression in English. Replace "definitely" with "always". I don't understand the objection to "we". "Choice" and "choose" are defined in the variants section of the article, as defined by Suppes (and others). --Michael C. Price ^talk 12:41, 29 August 2006 (UTC)

I'm not sure if this is it, but a negation of AC would be more like: there is a set from which we cannot choose one element from every one of its non-empty elements, OR: there is a set from which we cannot choose one element from every one of its non-empty subsets (Suppes), BUT NOT: there is a non-empty set from which we cannot choose one element. This may possibly relate back to the difference between choice function over a set of sets, versus choice function over a power set (and I see that you have gone over that ground here before). If I look in the variants section I see "every set has a choice function", but then if I take "choice function" to be as described in the first "Statements" section, then f(s) is an element of s. Leading to the idea that a choice function is necessary to get an element out of s. The variants section does try to caution against this, but possibly it doesn't spell out what it is as clearly as the Statements section did. Maybe:

Statement

For any set of non-empty sets, X, there exists a function f defined on X such that for every set s in X, f(s) is an element of s.

The function f is called a choice function, blah...

Variants

For any set X, there exists a function f defined on the powerset of X such that for every Y which is a non-empty subset of X, f(Y) is an element of Y.

The function f here is also called a choice function, but there is a slight difference, blah...

Of course, the process of tacking on what exactly is the choice function will go against the whole enterprise of stating the axiom of choice in as few words as possible. In any case I don't claim to know why (or if) it was confusing as it stood, just throwing it out there as a possibility. 192.75.48.150 14:39, 29 August 2006 (UTC)

We can both remove the definition of "choice function" from the definition of AC and make a considerable simplification of the problem by focussing on single sets by adopting Suppes' equivalent definition (see previous discussion on talk page) of the axiom of choice:

For any set A there is a function f such that for any non-empty subset B of A, $f(B)\in B$

Therefore the negation of AC assumes the existence of a subset B that does not satisfy $f(B)\in B$ , i.e. it is not possible to choose a single element of the said subset. Since a subset is automatically a set we have shown that the negation of AC demonstrates the existence of a set from which we cannot select a single element. Ergo AC is required to select a single member from an arbitrary set. Note this problem vanishes for finite sets: AC is not required for them. --Michael C. Price ^talk 19:13, 29 August 2006 (UTC)

Nonsense. The negation of

For any set A there is a function f such that for any non-empty subset B of A, $f(B)\in B$

There is a set A such that for all functions f (on the set of non-empty subsets of A), there is a B such that $f(B) \notin B$ .

Clearly, there must be infinitely many such B, or we could fix that, as you note. — Arthur Rubin | (talk) 19:44, 29 August 2006 (UTC)

(edit conflict) Just about to say that. It looks like you flipped "for all f there is a B" to "there is a B such that for all f", and then concluded that this specific B must be a "sticky set". Is this helping at all? 192.75.48.150 19:50, 29 August 2006 (UTC)

Correction accepted, but doesn't the conclusion still stand? Accepting that ¬AC implies

There is a set A such that for all functions f (on the set of non-empty subsets of A), there is a B such that $f(B) \notin B$

then we have the existence of a subset, B, from which we can't select a single element: i.e. a "sticky" set from which a single element can't be choosen, as the original questioner asked. --Michael C. Price ^talk 20:22, 29 August 2006 (UTC)

No. — Arthur Rubin | (talk) 20:34, 29 August 2006 (UTC)

Expanding on Arthur's answer slightly: For every natural number n, there is a natural number m such that m is greater than n. It doesn't follow that there's a single m that's greater than every n. --Trovatore 20:37, 29 August 2006 (UTC)

Thanks for the expansion :-) , although I wish Arthur would be more explicit (his own wording of ¬AC starts with "there is", so is this really his objection?). But your example does not prove that m does not exist either (although we know for other reasons that it doesn't). --Michael C. Price ^talk 20:58, 29 August 2006 (UTC)

Are we saying the article might lead someone to believe that not-AC implies there is such a sticky set? Or is it that the article doesn't lead someone who already believes in such a sticky set to change his mind? I wouldn't be terribly worried about the second case. 192.75.48.150 21:27, 29 August 2006 (UTC)

When Arthur's "word bag" refills perhaps we'll find out, but I think the confusion/disagrement stems from the existential difference between not adopting AC (which does not require a sticky set) and adopting not-AC (which requires(?) a sticky set). --Michael C. Price ^talk 21:36, 29 August 2006 (UTC)

Okay, we can get back to it later, can I ask you suspend disbelief for a moment and assume that Arthur Rubin knows whereof he speaks, and that adopting not-AC does not require a sticky set? What, in your opinion, is unclear in the article, i.e. what led you to believe there was a sticky set, and how do you think we should fix it (again, please assume for the moment that Arthur is right)? 192.75.48.150 21:52, 29 August 2006 (UTC)

See next section. --Michael C. Price ^talk 22:25, 29 August 2006 (UTC)

One of the criticisms of the Cantor diagonal argument is that there is no "sticky" set which is not in the list, as you can always add a single (or a countable number) of missing sets. The same argument applies here, given a failed choice function f (with either definition) which fails at B, (i.e., $f(B) \notin B$ ), one can find a b ∈ B (using logic, rather than the axiom of choice) and define a function g which is equal to f except at B, but g(B) = b. If g is not a choice function, we can find a second B, etc., etc. — Arthur Rubin | (talk) 23:40, 29 August 2006 (UTC)

But can you complete this patching up process if the original f fails on an infinite number of subsets? If you can then why do we have to assume the axiom of choice at all? --Michael C. Price ^talk 00:30, 30 August 2006 (UTC)

No, you cannot in general patch infinitely many errors in a failed choice function. That's why I have been using the word simultaneous. You can always patch one failure or another, but when choice fails there are situations in which you cannot patch them all at once . CMummert 00:35, 30 August 2006 (UTC)

Okay, I think I get it now. The axiom of choice is only an issue or required when you are presented with an infinite number of fiat choices to make. So we can always pick a marble from a bag of identical marbles: the problems would start if we had an infinite number of bags of marbles and no rule for specifying which one to choose from each bag. The axiom of choice asserts that such a selection procedure always exists, without specifying its details. Is that correct? --Michael C. Price ^talk 03:58, 30 August 2006 (UTC)

I would think that the bags themselves would have to be infinite. Otherwise you could simply lay out the contents of each bag in a row and make the rule be "pick the first marble from each row" for which you don't need AC. —Preceding unsigned comment added by Houseofwealth (talk • contribs) 19:45, 25 October 2007 (UTC)

I'm afraid not. I don't have my references at the moment, but AC₂ (the axiom of choice for sets of 2-element sets) has been shown independent of ZF. You seem to be assuming that there is a global linear ordering of the Universe. — Arthur Rubin | (talk) 19:51, 25 October 2007 (UTC)

You've lost me. Why do you need ZF to order a finite set? And what do you mean by "global linear ordering of the universe" Houseofwealth 17:58, 30 October 2007 (UTC)

The existence of a global linear ordering R of the universe implies ACF (the axiom of choice for sets of finite sets), by merely selecting the R-first element. However, there are models of ZF, in which there is a countable set X of pairs of countable sets of reals, such that X does not have a choice function. (My reference books are at home, or I could give two references that such a model exists.) — Arthur Rubin | (talk) 18:11, 30 October 2007 (UTC)

To Houseofwealth: Suppose we are given a set of finite sets for which we want a choice function. You are right that each finite set can be well-ordered (so that its least element can be selected, but an element could be selected even without ordering). However, if it has n elements (for n ≥ 2), then the number of such well-orderings is n! ≥ 2! = 2. So you have not solved the problem. You have merely pushed it up a level. Now you have to select one of the well-orderings for each of the infinitely many finite sets. You still need the axiom of choice. The point is that what can be done once by logic alone, cannot be done an infinite number of times without something more.

A global linear ordering of the universe would be a formula of set theory with parameters from your model and two free variables x and y which is satisfied by the model when x < y in the linear ordering of all sets. JRSpriggs 02:56, 31 October 2007 (UTC)

One could quibble on the word "procedure", but other than that, yes, you've got it. (The "procedure" is just "take one marble, arbitrarily, from each bag".) --Trovatore 04:55, 30 August 2006 (UTC)

Thanks, although I was a bit surprised that you reverted the lead:

Intuitively speaking, AC says that given an infinite collection of bins, each containing at least one object, and no "rule" for which object to pick from each, then we can still pick exactly one object from each bin and gather them into another bin. AC is not required if either the number of bins is finite or there is such a selection "rule" is available.

back to:

Intuitively speaking, AC says that given a collection of bins, each containing at least one object, then exactly one object from each bin can be picked and gathered in another bin - even if there are infinitely many bins, and there is no "rule" for which object to pick from each. AC is not required if the number of bins is finite or if such a selection "rule" is available.

I find the 2nd (and now current) statement confusing, especially the phrase "even if", which can be read to suggest that the infinite condition is not so important. You might argue that the phrase does not imply this, but even so, it implies that AC has an application to the finite case which, as this discussion has shown, is definitely not the case. --Michael C. Price ^talk 06:58, 2 September 2006 (UTC)

Hm? It certainly can be applied to the finite case. It just isn't necessary in that case. There is no requirement that you avoid an axiom when it isn't necessary. The intuition in the finite and infinite cases is the same. --Trovatore 07:02, 2 September 2006 (UTC)

Okay. I guess the 2nd sentence is clear enough. --Michael C. Price ^talk 11:44, 2 September 2006 (UTC)

[edit] Axiom of Choice does not help your problem

If "Every set of nonempty sets has a choice function.", then by König's theorem (set theory) there will (usually) be many choice functions. How do you choose a choice function to make your choices for you, if you cannot choose anything without the axiom of choice? JRSpriggs 05:19, 30 August 2006 (UTC)

König's theorem would give you one set containing infinitely many choice functions; you don't need AC to pick an element from a single set, as per the above discussion. If you had an uncountable collection of families of sets and you wanted a choice function for each family, you'd need to use AC twice: once to ensure existance of choice functions for each family of sets; then again to pick one choice funtion for each family in the collection. —The preceding unsigned comment was added by 210.54.148.98 (talk • contribs).

Yes, I know. I was trying to point out the absurdity of the attempt to use the axiom of choice for picking one element from a non-empty set rather than relying on logic. JRSpriggs 07:33, 5 October 2006 (UTC)

[edit] Proposed Changes

Switch the variants of AC in the article so that Suppes' more intuitive but equivalent definition of AC is given primacy, so that we have

AC:For any set A there is a function f such that for any non-empty subset B of A, $f(B)\in B$

This is much clearer than the current definition. If it is truely equivalent (as the previous discussion a couple of months ago concluded) then only minor tweaks to other sections are required.

Also include:

¬AC:There is a set A such that for all functions f (on the set of non-empty subsets of A), there is a B such that $f(B) \notin B$ .

Pending resolution of the "sticky set" question, include it as a consequence of ¬AC. --Michael C. Price ^talk 22:25, 29 August 2006 (UTC)

I don't know what a sticky set is, but it seems like original research to me. To be clear about what you mean, please give a description of a model of ZF and a description of particular set in that model that you would call sticky. Lacking that, it is unclear to me (and probably everyone else) exactly what you are describing. Merely hypothesizing that some particular set might exist, without producing a model of ZF in which the set actually does exist, is not convincing. CMummert 22:59, 29 August 2006 (UTC)

The term sticky set came up as a metaphor a couple of months back and is OR, but there should be a statement about whether AC is required to choose a single element from any set, as the original questioner posed. Or not, pending outcome of debate. --Michael C. Price ^talk 23:16, 29 August 2006 (UTC)

I don't see why the final version AC (expanding "choice function") in the existing first section is more complicated than what we have here; in fact, in restricted versions of set theory (without full power set), that version might be undefined.

AC: For any set X of non-empty sets, there is a function f on X such that for any x ∈ X, f(x) ∈ x.

¬AC: There is a set X of non-empty sets, such that, for any function f on X, there is an x ∈ X such that f(x) ∉ x.

∉ (∉) is not in my current character set, but you know what I mean. — Arthur Rubin | (talk) 23:25, 29 August 2006 (UTC)

Well, this is probably a matter of taste and clarity, but Suppes' version is a statement about sets, as opposed to a statement about sets of sets. --Michael C. Price ^talk 00:24, 30 August 2006 (UTC)

Once you remove the difference in terminology, Suppes's version is a statement about sets that are powersets of other sets, rather than a statement about arbitrary sets of sets. CMummert 02:19, 30 August 2006 (UTC)

I have inserted the above formulations of AC and ¬AC in the variants section, and added a rider in the lead that AC not required for any finite number of choices. I think this will help other non-mathematicans. --Michael C. Price ^talk 10:19, 30 August 2006 (UTC)

[edit] Determinacy

The article states that determinacy for open or closed sets follows from AC, but is weaker than AC.

I think it is pretty obvious (and I think I have seen this somewhere, but don't remember where) that closed determinacy for games on arbitrary sets, already for games of length 2, implies the axiom of choice:

Let (A(j): j in J) be a family of nonempty sets. Now consider the following game: Player I plays a k in J (otherwise loses immediately). Now player II plays an x in the union of all A(j). Player II wins if x is in A(k).

This game is clopen, and clearly player I does not have a winning strategy. But a strategy for player II is just a choice function.

Aleph4 09:28, 5 October 2006 (UTC)

Please explain your assertion that the game is "clopen". In other words, what topology is appropriate on $J \times \bigcup_{j \in J} A_j$ ? (Especially since we know that full determinancy is incompatible with the axiom of choice.) — Arthur Rubin | (talk) 19:12, 5 October 2006 (UTC)

I didn't write the original post, but it makes sense to me. The basic setup is the same as Martin's proof of Borel determinacy, where you have a set X and you play a game on

X ω

. If X is given the discrete topology and

X ω

the product topology from this, and $Z \subseteq X^\omega$ is Borel in with this topology, Martin showed the game with winning set Z is determined.

In the situation at hand, $X = J \cup \bigcup_j A_j$ , and

Z

is the set of all sequences z such that $z(0) \in J \land z(1) \not \in A_{z(0)}$ . This is a clopen set in

Z = X ω

because it and its complement are unions of basic open sets (for any $x,x' \in X$ the set of sequences starting

(x, x')

is basic open in the product topology.) Player I has no winning strategy, because she must play $z(0) \in J$ but then player II is free to pick some $z(1) \in A_{z(0)}$ and win.

What Aleph4's proof shows is that this sort of general determinacy is equivalent to choice. AD is not about arbitrary games though; it is about games on

2 ω

, and so AD does not imply this strong form of determinacy.

I think that what Aleph4 was complaining about is the an inaccurate section heading Important theorems requiring AC (or weaker forms) but weaker than it . As a benefit of the doubt, the notation G(T,X) is not defined in the article; it would be possible to just change the statement to the determinacy of Borel games on

2 ω

which is provable in ZFC but is also a consequence of AD and thus does not imply choice (this assumes that Borel determinacy is not provable in ZF, a fact I don't know). CMummert 20:33, 5 October 2006 (UTC)

It is not the section header which is the problem (if any). I do not know enough about games or determinacy to make a judgment on Aleph4's claim. But IF there is a problem, it is that "Every infinite game G(T,X) where X is either open or closed is determined." is in the weaker than AC section rather than in the equivalent to AC section. JRSpriggs 07:14, 6 October 2006 (UTC)

Thank you, CMummert. This is exactly what I meant.
Borel determinacy cannot be proved in ZF, because it would show that the countable union of countable set of reals is countable, and I think (again I do not remember the reference) that it is even consistent with ZF that the reals can be covered with a countable union of countable sets.
To show that the union of countably many set A(0), A(1), ... is countable (from ZF + Borel determinacy), consider the following game: Player I chooses n, and then player II has to enumerate the set A(n). Again player I does not have a winning strategy. (And again this is not "my" proof.)
Aleph4 11:12, 6 October 2006 (UTC)

Thanks. I changed the statement in question to Borel determinacy for games in Baire space. CMummert 12:53, 6 October 2006 (UTC)

Apparently I was wrong, it should have been in either the wrongly-worded-result section or the does-not-follow-from-AC section. :-( JRSpriggs 06:30, 7 October 2006 (UTC)

I think you were correct that the original statement could go in the section on equivalents of AC. But the notation

G (T, X)

isn't defined in this article or in the determinacy article, and I'm not familiar with that particular notation myself, so rather than leave it undefined I thought it was better to replace it with something that I understand until a more knowledgable editor comes along. CMummert 12:53, 7 October 2006 (UTC)

The G(T,X) notation refers to a tree T on some set Z (that is, a set of finite tuples from Z closed under subsequence), and a winning condition X which is a subset of the branches through T. The players cooperatively construct a branch, and I wins if the branch is in X. You have to make some arbitrary decision about what happens if you get to a leaf (usually the last player loses). It's one of the things that still needs to be added to the determinacy article (there's a subsection, determinacy#Games played on trees). --Trovatore 17:34, 7 October 2006 (UTC)

[edit] Math article rating

I gave this article a B rating on the WP 1.0 rating scale. But the article is actually better than that sounds; the rating system is not granular enough. With a little work, this could be a B+ or A quality article. Here are some places the article could be improved. I will improve some of them myself over time.

The concept of a model of set theory is delicate and difficult for many people, so defining them and explaining what independence means in terms of models of set theory would be helpful.
The paragraph on nonconstructivity coud be phrased more clearly.
The paragraph on category theory could be expanded.
In the references section, the only textbook is Suppes. I'm not looking for inline citations for everything (not by far), but right now the references really are quite modest.
The section on the law of the excluded middle could use more explanation on what these constructive set theories are and why this proof is interesting. The section is just a proof right now.

CMummert 20:08, 6 October 2006 (UTC)

[edit] Ultrafilters

Zorn's Lemma is used to construct nonprincipal ultrafilters. Can we prove some form of AC from their existence? Andy D. —The preceding unsigned comment was added by Andy drucker (talk • contribs) 23:34, 2 January 2007 (UTC).

The form you have in mind is the Boolean prime ideal theorem, which is weaker than AC. Also, it is consistent with ZF and DC that there is no nonprincipal ultrafilter on the natural numbers (see this article [2] to get started if you want to dig references). CMummert 01:01, 3 January 2007 (UTC)

[edit] Tukey's lemma

Tukey's lemma states, "Each nonempty family of finite character has a maximal element". This lemma is equivalent to the axiom of choice. See [3]. DFH 19:27, 23 February 2007 (UTC)

[edit] Countable additivity of Lebesque measure?

Ben Standeven (talk · contribs) added "The Lebesgue measure of a countable disjoint union of measurable sets is equal to the sum of the measures of the individual sets." to the list of important theorems requiring a weak form of the axiom of choice. I would like to see some justification for the claim that this requires choice. I thought it was a matter of definition. JRSpriggs 11:41, 25 March 2007 (UTC)

It's consistent that the real line is a countable union of countable sets; in that case some property of the Lebesgue measure must fail. Maybe Ben Standeven can point out a reference. CMummert · talk 12:02, 25 March 2007 (UTC)

huh? "if the real line is a countable union of countable sets...some property of the Lebesgue measure must fail?" would you mind rephrase/elaborate? Mct mht 06:04, 26 March 2007 (UTC)

(No reference, but...)

Any countable set has Lebesgue measure 0. (No reference, but it follows from every singleton has Lebesgue measure 0 and Lebesgue measure#Properties 2.)
Lebesgue measure is countably additive. (Again, Lebesgue measure#Properties 2.)

Therefore, any countable union of countable sets has Lebesgue measure 0.

If, then, the reals are a countable union of countables, then the reals have Lebesgue measure 0, contradiction Lebesgue measure#Properties 1.

— Arthur Rubin | (talk) 06:18, 26 March 2007 (UTC)

aha, thanks. misread slightly CMummert's statement there. Mct mht 06:22, 26 March 2007 (UTC)

Re property 1, every countable set is contained in a G-delta set of measure 0, which is relevant here because it shows that countable sets have measure 0 without requiring countable additivity of the measure. The G_delta cover can be constructed without choice; so it seems to me that it is property 2 that must fail. CMummert · talk 11:58, 26 March 2007 (UTC)

Can you tell me how you can construct such

G δ

cover and show that its measure is 0 without using countable additivity of the measure? Slawekk 20:35, 26 September 2007 (UTC)

I haven't written it down carefully, but it seems to just depend on additivity for sequences of disjoint basic open sets. To compute the measure of the intersection of the G_δ cover only requires monotonicity of the measure. Is there something I'm missing? — Carl (CBM · talk) 21:39, 26 September 2007 (UTC)

Probably not, I just thought that you meant that the proof does not use countable additivity of the "measure". It seems you still use it, but applied only to disjoint open intervals.

Coming back to the issue I don't think "The Lebesgue measure of a countable disjoint union of measurable sets is equal to the sum of the measures of the individual sets" is a good formulation of what we want to say. Once you call something a measure,

σ

-additivity is implicit in the definition. Maybe it would be better to say "There exist a notrivial measure on (a

σ

-algebra of subsets of) $\mathbb{R}$ that assigns zero to all one-element sets". Where exactly the construction of the Lebesgue measure breaks without AC is an interesting question that I would be happy to know the answer to. Slawekk 17:29, 27 September 2007 (UTC)

[edit] The axiom of choice

In any given language, the set of definable numbers is countable. Therefore, if we substract the set of definable numbers from any uncountable set, such as real or complex numbers in any given range, we come up with a set of numbers which cannot be defined in this language. Therefore, any choice of a number from such a set cannot be expressed in this language (although, there exist languages in which it can be expressed). We can conclude that numbers from such a set cannot be chosen, since there is no way to express such a choice (in the specific language). The only way to express such a choice (in the given language) is with infinite information, such as a number with infinite number of digits. Uri Even-Chen 00:24, 18 April 2007 (UTC)

So, what do you conclude from that? Are you proposing to change the article? My impression is that conventional analysis is willing to accept half a dozen paradoxes like that before breakfast. It doesn't bother them. And AC only says that an element can be chosen. I believe that it doesn't say how. EdJohnston 01:44, 18 April 2007 (UTC)

AC has nothing to do with the discussion above. You never need AC to choose a single element of a nonempty set, no matter how undefinable. You do sometimes need it to argue that the set you're interested in is nonempty. --Trovatore 02:11, 18 April 2007 (UTC)

My view is similar to the constructivists view. It is true that if we are not able to select any number from a given set, the set can be considered empty. This leads to a conclusion that we are unable to define sets which are uncountable. The set of real numbers is not uncountable. If one wants to claim that it is uncountable, one needs to prove that it includes numbers which can't be defined in our language. If they can't be defined, then in what sense they exist? We can conclude that the axiom of choice is valid only if there are no uncountable sets. Uri Even-Chen 15:09, 19 April 2007 (UTC)

This is interesting, but conversations should be relevant to improving the article. Do you have a change to suggest? There are also a number of articles on constructivism, and you are welcome to contribute to those, if you know the material. See Category:Mathematical constructivism. EdJohnston 16:52, 19 April 2007 (UTC)

[edit] Need a little clarification

I am a little confused. If the axiom of choice implies the law of the excluded middle, then doesn't it obviously contradict Godel's first theorem of incompleteness? This seems particularly bizarre to me since Godel himself worked on the axiom of choice after proving the two incompleteness theorems. Or are we talking only about (expressively) limited axiomatic systems where incompleteness does not apply? If someone could help me understand this, I'd be grateful. Right now it seems to me like the axiom of choice is plain wrong which of course it can't be. Panayk 20:33, 22 April 2007 (UTC)

It is perfectly normal for a theory to prove "A or not A" without either proving A or proving not A. Every classical theory does this, even when A is the Godel sentence for the theory. CMummert · talk 22:09, 22 April 2007 (UTC)

Gödel's incompleteness theorems are not inconsistent with the law of excluded middle. The former has to do with provability. The latter has to do with truth. JRSpriggs 09:10, 23 April 2007 (UTC)

@CMummert: Understood (I think), thanks. @JRSpriggs: I am probably completely off the mark, but if you have time, consider this:

(1) Suppose the law of the excluded middle for a suitably powerful theory T.

(2) Consider the Gödel sentence G for T: "G is not provable".

(3) Suppose G is false: Then G is provable, hence true. Contradiction.

(4) Therefore G cannot be false and, by the law of the excluded middle, it is true.

(5) Doesn't the above (2-4) constitute a proof of G in T using reductio ad absurdum?

(6) But this a contradiction!. Hence the law of the excluded middle does not hold, nor do any axioms that imply it.

I suppose the problem is with (3) or (5). But why? Panayk 17:03, 23 April 2007 (UTC)

Step 3: That if G is provable, then G is true only follows in T + Consis(T). — Arthur Rubin | (talk) 17:40, 23 April 2007 (UTC)

Step (3) isn't right, because there are nonstandard models. G being false in a model means that there is a "natural number" in the model which encodes a "proof" of G. It is only if this "proof" is coded by a standard natural number that it can be converted into an proof of G (which, by definition, must be finite).

As A. Rubin alludes, there are models of PA in which G is false. However, if G is false in the standard model then your point (3) does go through - this is how one proves by contradiction that G is, in fact, true in the standard model.

Another way of looking at it: the Godel sentence does not actually say "G is not provable", it says "there is no element in the domain of the model which satisfies a certain property that would also be satisfied by the Godel number of a proof of G". If you limit yourself to the standard model, these two statements turn out to be equivalent, because in that case you can pass between proofs and their Godel numbers freely, but in general they are not equivalent. CMummert · talk 17:47, 23 April 2007 (UTC)

Note that step (3) is actually two steps. If G is false (false simpliciter is the same as "false in the standard model"), then G is provable from T; that part is correct. It's the second part -- "hence true" -- that fails: In this situation T must be inconsistent, and therefore it proves false statements (for example, G) as well as true ones. --Trovatore 19:55, 23 April 2007 (UTC)

[edit] 2nd and 3rd paragraphs of "Usage"

Maybe I'm just being dense, but it seems that the second paragraph under the "Usage" heading doesn't adequately explain why we don't need the AC for finite sets X. Without any instructions for how to choose a particular member from even a single set, is it really guaranteed possible? Similarly, the third paragraph ought to explicitly state what property it is of the natural numbers that makes the AC unnecessary (something like being well-ordered?)141.140.6.188 01:27, 24 April 2007 (UTC)

Re "choosing" an element of a nonempty set, please see the section titled Question higher on this talk page. Someone else asked the same question. The third paragraph does state the property the natural numbers have - every nonempty set of natural numbers has a least element. CMummert · talk 11:28, 24 April 2007 (UTC)

[edit] 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 $κ$ does a cardinal $κ < λ < 2 κ$ 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

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

Then, looking at where $2^{2^{\mathbf m}} + \alefsym(\mathbf m)$ , $2^{\mathbf m} + \alefsym(\mathbf m)$ , and $\mathbf m + \alefsym(\mathbf m)$ may fall, we end up with $\alefsym(\mathbf m)$ being a repeated powerset of m, so that m is clearly an aleph, or the contradiction that $\alefsym(\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.)

[edit] 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)

[edit] 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$

$(\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 \le 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 \le 2^{\aleph_0}$ It implies there is a map from $\mathcal P (\omega \times \omega)$ onto

ω 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 \ne 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 \le 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)

[edit] 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)

[edit] 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)

[edit] 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"

"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 "

"given any collection "

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

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)