Axiom talk:Axiom of Choice

From ProofWiki
Jump to navigation Jump to search

Actually, the Axiom of Choice is also necessary for countable sets! For example, the proof that the countable union of countable sets is countable relies on the Axiom of Choice. I've heard some people call the statement "A choice function exists for all countable sets" the "Axiom of countable Choice."

Finite sets, on the other hand, can be dealt with using induction.

Shouldn't this (the first formulation):
$\forall x \in a: \exists P \left({x, y}\right) \implies \exists y: \forall x \in a: P \left({x, y \left({x}\right)}\right)$
be replaced by, say (where $b^a$ denotes the set of functions from $b$ to $a$ (it can be demonstrated to exist)):
$\forall x \in a: \exists y \in b: P \left({x, y}\right) \implies \exists f \in b^a: \forall x \in a: P \left({x, f \left({x}\right) }\right)$
I have a source here which practically defines AC as 'A surjection has a section' (i.e., a right-inverse); that's not what either of the above say.
At the moment, the statement of AC in its first form appears very incoherent to me. I'd say it needs restatement (or explanation, at the very least). Maybe it's just me. --Lord_Farin 06:09, 1 February 2012 (EST)
"A surjection has a section" seems very similar to Relation Contains Mapping is Equivalent to AoC‎, which is another way of looking at it.
The "existence of choice function" seems to be the way it is mainly reported, which is the "incoherent" way LF refers to. The "element of Cartesian product" is Halmos's definition, and he then goes on to show his definition implies the "choice function" definition. Other contributors are now coming out and saying that AoC is defined in various other ways - but beyond the demonstration that all these definitions are equivalent, there is no intrinsic reason for choosing one over another - except that the very name "Axiom of Choice" naturally contains in its name a hint as to its (usual) definition - i.e. the "choice function" one. This is probably due to historical reasons, i.e. this was how it was first formulated (and it may be this is the most convenient method of reporting it in the limited axiomatic language of ZF(C) itself). I confess I haven't made an exhaustive study of the literature. --prime mover 14:09, 1 February 2012 (EST)
I don't proclaim that the definition you hallow shouldn't be the primary one. It is just that quantifying over function symbols isn't first-order logic, while AC is expressible in first-order terms. That's why I think the precise statement should be changed. Again, if the first thing posted above isn't the same as the second one, explain the first one please. I can't make 'there exists a choice function' out of it; most notably as $y$ is treated as a set (when quantifying), while moments later it is used as a function symbol. Rigour is everything. AC should be in first-order language if we want to talk about ZFC. --Lord_Farin 16:50, 1 February 2012 (EST)
I don't "hallow it", it's just that's the only statements of the axiom I've found. The first thing and the second thing are shown to be equivalent in Equivalence of Versions of Axiom of Choice. Fuxk it, I'm bored with the entire topic. Let someone who knows more about the subject than what they've picked up off internet chatrooms get on with it ... --prime mover 18:11, 1 February 2012 (EST)

I am more determined to get it correct; at the moment, I even doubt that the current statement (obtained from MathWorld) says what is in the line above.

An attempt devised by myself, assuming that one can talk about functions (which is possible by the formal definition of ordered pair, axiom of powers and maybe some more); let $\mathcal P \left({a}\right)$ be the power set of $a$:

$\forall a: \exists f: f \in a^{\mathcal P \left({a}\right)} \land \left({ \forall b: \left({ b \in \mathcal P \left({a}\right) \land \exists x: x \in b }\right) \implies f \left({b}\right) \in b }\right)$

where $a^b$ is notation for the set of functions from $b$ to $a$; it too can be demonstrated to exist. Does that calm your mind, pm? --Lord_Farin 09:17, 2 February 2012 (EST)

I confess I don't really care, as long as it's not up to me to look after it. I'm too far out of my depth to be able to make any sense of it all.
We need to put something in place that defines zeroth order, first order, second order etc. I have trouble focusing on it.
Feel free to take it on, because I'm seriously not going to be much use here. --prime mover 16:23, 2 February 2012 (EST)
Another dot added to my long-term list. I will continue parsing Conway's Functional analysis book first. --Lord_Farin 17:41, 2 February 2012 (EST)


The first statement doesn't appear to make sense. What is $a$? What is $P$? I can't make head or tail of that thing. There are also different forms that are all called "axiom of choice". Existence of choice functions, existence of sets with one element from each of a set of disjoint sets, etc. --Dfeuer (talk) 06:09, 21 February 2013 (UTC)

Are you really unable to "make head or tail of that thing" or are you just expressing in your usual rhetorical style that you believe the context of which it is couched needs to be explained? If the first, I suggest you take up knitting instead or something. If the latter then feel free to add the appropriate explanatory language. And I would reiterate my plea to direct more of your energy towards accurate and helpful specification towards the changes you believe to be necessary. --prime mover (talk) 06:18, 21 February 2013 (UTC)
You seem to have a lot of trouble differentiating between the things you hold in your head while writing something and the things that are actually written out. There was not enough actually in the statement to give much of a clue about what it was intended to mean. If you want to pull it out of the history and give it some kind of internal and/or external context, feel free. I recommend you start by explaining what $a$ and $P$ are supposed to represent. --Dfeuer (talk) 06:51, 21 February 2013 (UTC)
Bit late now, it's gone. --prime mover (talk) 06:55, 21 February 2013 (UTC)

Equivalent forms

I can't remember where this discussion was held now, but IIRC a decision was made to put all statements equivalent to AoC into a category rather than list them on the page. In that way the page does not become unwieldy and does not require one to go back and edit this page as soon as someone digs out yet another equivalence. This approach fits in better with ProofWiki philosophy. --prime mover (talk) 07:48, 21 February 2013 (UTC)

The three formulations given here are the most important ones. Some would argue that Formulation 2 is not actually a statement of AC but an equivalent statement, but I've seen AC defined that way. And I know that I should be writing AoC — meh. In general I agree, but I think the page currently does that pretty well. --Lord_Farin (talk) 08:56, 21 February 2013 (UTC)
In practice, Zorn's Lemma and Tukey's Lemma are just as important, while the basis theorem and Tychonoffs theorem are quite important in their own fields, and there are surely key ones I don't know about yet. We have a category for things that depend on AoC, but not one for things that are actually equivalent to it. --Dfeuer (talk) 15:01, 21 February 2013 (UTC)
There is Category:Equivalents of the Axiom of Choice (which indeed needs to be renamed according to paradigm). I know that it's almost empty. --Lord_Farin (talk) 15:11, 21 February 2013 (UTC)
Ah! I'd have seen that if it were linked from this page... --Dfeuer (talk) 15:30, 21 February 2013 (UTC)