Talk:Axiom of choice/Archive 3

Archive 1

Archive 2

Archive 3

Archive 4

Archive 5

Archive 6

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"

or

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

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)

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)(\exists y\in x)(True)\rightarrow (\exists f)(\forall x\in X)(f(x)\subseteq x\land 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)

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)

Patrick Suppes

I see that:

"Every set has a choice function."

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)

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

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)

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)

¬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., $\alpha _{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 $\alpha _{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)

Question

Old questions

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.

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$

is

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)

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)

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.

∉ (&notin;) 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)

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^{\omega }$. If X is given the discrete topology and $X^{\omega }$ 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^{\omega }$ 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^{\omega }$, 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^{\omega }$ 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)

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)

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)

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)

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...)

1. Any countable set has Lebesgue measure 0. (No reference, but it follows from every singleton has Lebesgue measure 0 and Lebesgue measure#Properties 2.)
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_{\delta }$ 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, $\sigma$-additivity is implicit in the definition. Maybe it would be better to say "There exist a notrivial measure on (a $\sigma$-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)

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)

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)

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)