Axiom of Choice not self evident?

[FallenApple]

It seems that it is self evident. After all, a set A consists of things. These things exist as part of the set. Therefore the idea is that I can think about the item of the set without really thinking about the other items in that set. The set is in a sense the totality of the parts. Why is this controversial then? Are the parts not prior to the whole?

It would be quite weird if I think of an item in the set, that suddenly the item just disappears or become undefined. But then, it couldn't have been defined in the first place. If this is the case, then how would the set even exist?

Basically, if I can't pick a item in the set in principle, then are no parts of the whole, which nullifies the idea of a set in the first place.

 

[fresh_42]

It is self-evident to pick an element from a set with countably many elements in it. But how to pick every real number? And one of the consequences of AC is the Banach-Tarski paradox which is all but self-evident.

 

[FallenApple]

It is self-evident to pick an element from a set with countably many elements in it. But how to pick every real number? And one of the consequences of AC is the Banach-Tarski paradox which is all but self-evident.

It may be impractical to find a choice function to pick out of the real numbers. But can I not in principle find one? The set of reals is uncountable. But I can say: let R be the set of real numbers.

let x be in R, regardless of where.

That statement itself automatically locates a number in R, at least its existence in R, though we don't know where. But R is made of numbers. If R has x, then it has x.

It almost seems like the axiom of choice is no different than the definition of a set. We say these things are part of a set. Then AC: one of these things is in the set. Which looks the same.

 

[fresh_42]

I'm probably not the first address to give the devil's advocate because I like my axiom. But "let $x \in \mathbb{R}$" is not picking every real number, just one. How would you pick one of every of $\aleph_1$ many sets? It can't be done in a constructive way, and this is the kernel of the debate about AC. There is no mechanism aka algorithm to do it.

 

[FallenApple]

I'm probably not the first address to give the devil's advocate because I like my axiom. But "let $x \in \mathbb{R}$" is not picking every real number, just one. How would you pick one of every of $\aleph_1$ many sets? It can't be done in a constructive way, and this is the kernel of the debate about AC. There is no mechanism aka algorithm to do it.

Oh I see. So let me see if I have this down.

I could do

let $x_{1} \in \mathbb{R}$
let $x_{2} \in \mathbb{R}$
let $x_{3} \in \mathbb{R}$
.
.
.

Which follows a infinitely countable series of logical existence statements. But the real numbers are not countable. So I have merely listed out an infinitely smaller subset of it. An infinite tuple of logical statements is countable and is hence of cardinality $\aleph_0$

 

[fresh_42]

Yes. And an equivalent formulation is Zorn's Lemma: A partially ordered set, in which each chain has an upper bound, contains a maximal element. Now what is the maximal element in $(0,1)\,$?

 

[FallenApple]

Yes. And an equivalent formulation is Zorn's Lemma: A partially ordered set, in which each chain has an upper bound, contains a maximal element. Now what is the maximal element in $(0,1)\,$?

There is no upper bound in $(0,1)\,$. The supremum exists outside of the set. I can always get close to 1 within the set, but I cannot reach 1. There is no Max.

 

[fresh_42]

There is no upper bound in $(0,1)\,$. The supremum exists outside of the set. I can always get close to 1 within the set, but I cannot reach 1. There is no Max.

$1$ is an upper bound, so according to Zorn's Lemma aka the axiom of choice, there is a maximal element. But it has to be a different ordering than the usual one. However, nobody can tell which. And this is why the axiom of choice isn't self-evident. If it was, then it wouldn't be independent of the other axioms of set theory, which it is. In the end it is a matter of taste and which kind of mathematics one prefers. There is indeed a branch which doesn't use the axiom of choice. Another prominent example is: Every vector space has a basis. So good luck to write down a basis of the vector space of all continuous real functions.

 

[FallenApple]

$1$ is an upper bound, so according to Zorn's Lemma aka the axiom of choice, there is a maximal element. But it has to be a different ordering than the usual one. However, nobody can tell which. And this is why the axiom of choice isn't self-evident. If it was, then it wouldn't be independent of the other axioms of set theory, which it is. In the end it is a matter of taste and which kind of mathematics one prefers. There is indeed a branch which doesn't use the axiom of choice. Another prominent example is: Every vector space has a basis. So good luck to write down a basis of the vector space of all continuous real functions.

So in terms of left to right ordering, there is no sequence that would produce a maximum. Every left to right monotonic sequence would get arbitrarily close to 1. As we zoom in, it is unclear which one is the maximum. So logically, it's just a bunch of infinite logical tuples stacked which is uncountable from the Cantor's diagonal argument. So fundamentally, we can't pinpoint the maximum, as we can always create a tuple of sequences not located in the stack of tuples. Since we can't pinpoint it, we can't know for sure that it exists so we have to make an assumption that it does. Ah that makes sense. In this case, it's not clear that we can a choice because it's not obvious.

For the vector space. We know there are infinite tuples. Each tuple is like a irrational number. Just a infinite sequence of numbers without repeating blocks. Since the set (1,0,0,...), (0,1,0,...)... are countable, we cannot use something that is countable to uniquely determine every single finite tuple can exist? Since defining (1,0,0,...), (0,1,0,...)... is the same as counting. By the same Cantor's diagonal argument?

 

[RockyMarciano]

It may be impractical to find a choice function to pick out of the real numbers. But can I not in principle find one? The set of reals is uncountable. But I can say: let R be the set of real numbers.

let x be in R, regardless of where.

That statement itself automatically locates a number in R, at least its existence in R, though we don't know where. But R is made of numbers. If R has x, then it has x.

It almost seems like the axiom of choice is no different than the definition of a set. We say these things are part of a set. Then AC: one of these things is in the set. Which looks the same.

If as you said the axiom of choice is implicit(at least partially) in the notion of set or of membership ∈, which is a primitive notion in set theory, it clearly makes sense that it cannot be proved in ZF, since primitive notions are starting points, it could only appear as an independent axiom. And it would make more sense to have it as axiom than not having it or denying it for the strength of the axiom system for proofs, which is also what happens.

Being self-evident is an ambiguous concept as it might mean both that it is self-evident that it can be derived from the axioms as a theorem or that it should be a primitive notion or an axiom.

 

[SSequence]

Possibly a somewhat silly question, but one I think might be closely related to discussion at hand. Few questions:
(1) Under what assumptions ℝ can or can't be well-ordered. Now let's assume that ℝ indeed can be well-ordered, which would definitely be true in classical math (as I understand) if CH is true, because then ℝ would have cardinality aleph_1. Can we describe some other set in this case that definitely can't be well-ordered? What would such a description look like?

(2) Is the cardinality of a set also well-defined when it can't be well-ordered? Would a statement such as saying the cardinality of some set A (which, let's assume can't be well-ordered) is aleph_ω² etc. make sense? Possibly we would have to adjust the definition of cardinality?

P.S. I might have posted that as a separate question but it seems that the discussion in this topic is closely related. Kindly mention it in a post below in case I should make a separate thread.

 

[mathman]

It seems that it is self evident. After all, a set A consists of things. These things exist as part of the set. Therefore the idea is that I can think about the item of the set without really thinking about the other items in that set. The set is in a sense the totality of the parts. Why is this controversial then? Are the parts not prior to the whole?

It would be quite weird if I think of an item in the set, that suddenly the item just disappears or become undefined. But then, it couldn't have been defined in the first place. If this is the case, then how would the set even exist?

Basically, if I can't pick a item in the set in principle, then are no parts of the whole, which nullifies the idea of a set in the first place.

You seem to have a misunderstanding of the axiom of choice. It is not about picking an element of a non-empty set. It is about given a collection (infinite - possibly non-countable), of non-empty sets, there exists a set (choice set) which has one element from each set in the collection.

 

[fresh_42]

Possibly a somewhat silly question, but one I think might be closely related to discussion at hand. Few questions:
(1) Under what assumptions ℝ can or can't be well-ordered.

Under the assumption that $\mathbb{R}$ is a set, if one accepts the axiom of choice in first order logic. Otherwise it has to be added as an axiom, e.g. in second order logic. (I haven't checked the second order logic case, so I repeated what can be found on Wikipedia.)

Now let's assume that ℝ indeed can be well-ordered, which would definitely be true in classical math (as I understand) ...

As long as you mean ZFC by classical mathematics.

... if CH is true, because then ℝ would have cardinality aleph_1.

Cardinality or the contínuum hypothesis has nothing to do with the axiom of choice. The C in ZFC (Zermelo-Fraenkel-Choice) stands for choice, not cardinality.

Can we describe some other set in this case that definitely can't be well-ordered? What would such a description look like?

This depends on the restrictions and conditions you set a priori. The axiom of choice in first order logic implies the well-ordering theorem, which states that every set can be well-ordered. The equivalence of the two is shown by transfinite induction IIRC. For a proof of the equivalence of all five statements (Axiom of Choice - Well-ordering Theorem - Zorn's Lemma - Tuckey's Lemma - Hausdorff's maximality principle) see e.g. https://www.amazon.com/dp/0387901388/?tag=pfamazon01-20

(2) Is the cardinality of a set also well-defined when it can't be well-ordered? Would a statement such as saying the cardinality of some set A (which, let's assume can't be well-ordered) is aleph_ω² etc. make sense? Possibly we would have to adjust the definition of cardinality?

See above, cardinality and well-ordering are not in the same division. And all questions here are immediately related to set theoretical axioms and logical deduction systems, so both have to be set beforehand and will influence what might be taken for granted and what does not.

 

[SSequence]

I realize that my previous post was extremely confusing so thanks for replying. Hopefully this is a bit better.

Here is the more precise statement of the question.
(1) Suppose choice is incorrect. Would it be "reasonable" to assume that ℝ can be well-ordered. On the very least, would it be consistent with ZF?
(2) Now if we assume the answer to (1) as positive (that is choice is incorrect but ℝ can be well-ordered). Assuming CH to be true, we must have card(ℝ)=aleph_1 (though I am guessing perhaps CH true or false wouldn't matter for the answer). But in this case, can we describe some other set (obviously can't be ℝ) that definitely can't be well-ordered and what would such a description look like?

See above, cardinality and well-ordering are not in the same division.

Well loosely speaking what I meant was that if some set A can be well-ordered, then we have a standard way of representing cardinality of A as aleph_α (where α is some arbitrary ordinal) ... right?

Now assume that "well-ordering theorem" is incorrect. For a set B that can't be well-ordered, what would be the correct way to describe cardinality of B in symbolic form (and in general sense, not just in basic distinction between countable infinity and uncountable).
Because if we write something like aleph_α for cardinality of B, wouldn't it be nonsensical (contradicting that B can't be well-ordered)? So I am assuming that notation would have to be little different in that case?

 

[fresh_42]

I realize that my previous post was extremely confusing so thanks for replying. Hopefully this is a bit better.

Here is the more precise statement of the question.
(1) Suppose choice is incorrect.

What does this mean? That you can show a set that cannot be well-ordered or that we must not assume the AC as an axiom. These are two completely different things. The first case would be really interesting, as it would imply that the AC contradicts ZF, which isn't the case. The AC is independent of ZF and if you allow AC as an axiom or not is exactly the difference between ZF and ZFC. Your choice.

Would it be "reasonable" to assume that ℝ can be well-ordered. On the very least, would it be consistent with ZF?

In ZFC it is not only reasonable but a given fact, in ZF there is no need to assume it. Whether or not is again a matter of which calculus you want to describe. Again your choice. Assumed ZFC is consistent, ZF + well-ordered-$\mathbb{R}$ will also be consistent. But I do not know whether an assumed well-ordering on only $\mathbb{R}$ already is sufficient for AC in general. Probably not.

(2) Now if we assume the answer to (1) as positive (that is choice is wrong ...

... which would imply a given counterexample, which cannot be given. Therefore every reasoning beyond this point is meaningless ...

... but ℝ can be well-ordered)...

... which is also an assumption as there is no well-ordering known as far as I know, but of course we can assume one, similar as if AC would be accepted.

Assuming CH to be true, we must have card(ℝ)=aleph_1 (though I am guessing perhaps CH true or false wouldn't matter for the answer). But in this case, can we describe some other set (obviously can't be ℝ) that definitely can't be well-ordered and what would such a description look like?

No idea, see previous explanations. When assuming something false, we may conclude whatever we want to. If we had such a counterexample we wouldn't use AC anymore unless in situations, where a well-ordering can be given constructively. ZFC and CH are independent.

Well loosely speaking what I meant was that if some set A can be well-ordered, then we have a standard way of representing cardinality of A as aleph_α (where α is some arbitrary ordinal) ... right?

Now assume that "well-ordering theorem" is incorrect. For a set B that can't be well-ordered, what would be the correct way to describe cardinality of B in symbolic form (and in general sense, not just in basic distinction between countable infinity and uncountable).
Because if we write something like aleph_α for cardinality of B, wouldn't it be nonsensical (contradicting that B can't be well-ordered)?

Maybe this https://ncatlab.org/nlab/show/cardinal+number can shed some light on your question regarding well-ordering and cardinals. As I see it, AC is only needed in case of a special definition of cardinality, simply to make this definition possible. I do not see a closer conceptual connection between the two.

 

[SSequence]

I am confused by your post (and perhaps it might be a serious misunderstanding on an elementary issue on my part).

Let my try one more time. Quoting wikipedia(from this page:https://en.wikipedia.org/wiki/Axiom_of_choice) directly rather than using my own words:

There are important statements that, assuming the axioms of ZF but neither AC nor ¬AC, are equivalent to the axiom of choice.The most important among them are Zorn's lemma and the well-ordering theorem.

Well-Ordering Theorem: Every set can be well-ordered.

Assuming ZF is consistent,...negation of the axiom of choice is not a theorem of ZF...showing that ZFC is consistent.

Assuming ZF is consistent,...axiom of choice itself is not a theorem of ZF...showing that ZF¬C is consistent.

Please correct on any point where there is a mistake (maybe my understanding is "totally" messed up :P):
(1) The first question was that assume ZF¬C. Now given what is written above well-ordering theorem should be wrong. So that there should exist "some" sets that can't be well-ordered. My question was specifically about ℝ in that case.
(i) Is (ZF¬C) + (well-ordered-ℝ) consistent?
(ii) Is (ZF¬C) + ¬(well-ordered-ℝ) consistent?

(2) My second question was that if (ZF¬C)+(well-ordered-ℝ) is consistent then we must give a very precise description of some set A that can't be well-ordered. Because such a set A should exist due to "well-ordering theorem" being false in (ZF¬C) ... right?
And would CH being true or false have any bearing on the description of the set A at all.

=============

Regarding my last question something related is written on the same page as consequence of well-ordering theorem "every cardinal has an initial ordinal." That doesn't answer the important details but gives somewhere to look at.

 

[fresh_42]

The quotations are correct and only say that AC is independent of ZF. You can assume AC or not AC. But you have suggested not AC to be true, which means there is a set that cannot be well-ordered. But as this is independent of ZF, it cannot be proven by ZF. Therefore in this sense not AC is as deliberate as AC is. The other equivalent statements are those I mentioned in post #13.

(1) Yes, you may assume that there is a set which cannot be well-ordered, but nobody has ever seen one for sure, and will not by only the means of ZF. How could we make assumptions about a special case, namely $\mathbb{R}\,$? So in my opinion (I'm no logician) the answers to (i) and (ii) have to be yes. Simply because one cannot draw conclusions from the pure existence of some unknown set with respect to some eventually completely different set $\mathbb{R}$.

(2) Yes for the first part and no for the second part. The latter case has two reasons. Firstly, we have to find a definition of CH which does not use well-ordering, which cuts off the only connection between the two concepts. Thus CH true or false cannot be taken for statements about AC anymore and vice versa. Secondly, the same as under point (1): Without any connection between a still unknown set $A$ and a given example $\mathbb{R}$, which CH refers to, how could one mean anything for the other? Only if we assume $\mathbb{R}$ to be the counterexample, we may draw conclusions. But in this case, the first reason is still in place: what is the definition of cardinality without AC assumed, esp. what is $|\mathbb{R}|$ in this case and what has it to do with any order?

 

[SSequence]

Good answer.

Regarding your answer to (1) I think ℝ should have some special place in the sense of being related to the power-set operation (but I don't know whether it is enough to have an impact on the answers).

... you have suggested not AC to be true, which means there is a set that cannot be well-ordered. But as this is independent of ZF, it cannot be proven by ZF.

Interesting, I didn't think about it while writing the question :p. Upon thinking a bit more, you are completely right that the existence of a set that can't be well-ordered has to be independent of ZF.But assuming (ZF¬C)+(well-ordered-ℝ) is consistent: is there a specific reason why in ZF¬C couldn't provably be able to give the "description" of such a set (that can't be well-ordered)? After all we can prove the "existence" of such a set in ZF¬C.
Maybe it is related to some kind of difference between "existence" and "description"? But I am not sure whether these kind of distinctions can be formalised easily anyway. Admittedly I am a little confused about this (and might be mixing up a few concepts). But anyway you don't have to answer this.Further Edit: Edited a bit further to improve the wording. Added the "(ZF¬C)+(well-ordered-ℝ) is consistent" in beginning of last paragraph as an assumption. Because "if" the assumption is false the direct description of a set that can't be well-ordered can be given as ℝ.

 

[mathman]

The well ordering theorem (as well as Zorn's lemma) is equivalent to the axiom of choice.

https://en.wikipedia.org/wiki/Well-ordering_theorem

 

[SSequence]

...
(1) Yes, you may assume that there is a set which cannot be well-ordered, but nobody has ever seen one for sure, and will not by only the means of ZF. How could we make assumptions about a special case, namely $\mathbb{R}\,$? So in my opinion (I'm no logician) the answers to (i) and (ii) have to be yes. Simply because one cannot draw conclusions from the pure existence of some unknown set with respect to some eventually completely different set $\mathbb{R}$.
...

I can't edit my previous post so I have to make a new one. You are probably completely right, but it might not be a bad idea to confirm it (in case you are interested enough in the question)." I think perhaps (ZF¬C)+(well-ordered-ℝ) "might" be inconsistent. The reason I am saying this is based on this very "rough" idea. Isn't the most powerful way to new generate sets is using power-sets? And ℝ is essentially sort of a power-set thing done to just 1 level. But even the hierarchy of sets generated using power-sets at arbitrary levels are just indexed by ordinals.
So suppose we denote the set at level α as V_α. We also assume ℝ can be well-ordered (which means V_ω+1 can be well-ordered). Given that V_ω+1 can be well-ordered, it doesn't seem entirely implausible that V_α might be well-ordered for any arbitrary α. And if that happens to be the case, it seems that there might be no apparent way to generate sets that can't be well-ordered. "

Of course all of this could be completely wrong. But anyway I am just putting it here for the sake of completeness.

 

[jim mcnamara]

@SSequence - you seem to be making problems for yourself, IMO. Axioms or postulates or assumptions have to be explicitly stated, or you have to assume either ZFC or ZF. Since you seem to like this kind of approach - Goodman's theorem caused debate, and is involved heavily in AC or no AC. Simply stated, it says that no new mathematics is possible by adding the AC. But AFAIK, it cannot be proved if you assume the AC. (This is NOT my area, corrections are welcome) It is interesting, IMO, in the sense of the ancient Chinese curse:

'May you live in interesting times'

Try this: https://projecteuclid.org/download/pdf_1/euclid.pjm/1102784341

Read about shoes, socks, Bertrand Russell, and the AC here:
https://math.vanderbilt.edu/schectex/ccc/choice.html

 

[SSequence]

@SSequence - you seem to be making problems for yourself, IMO. Axioms or postulates or assumptions have to be explicitly stated, or you have to assume either ZFC or ZF. Since you seem to like this kind of approach - Goodman's theorem caused debate, and is involved heavily in AC or no AC. Simply stated, it says that no new mathematics is possible by adding the AC. But AFAIK, it cannot be proved if you assume the AC. (This is NOT my area, corrections are welcome) It is interesting, IMO, in the sense of the ancient Chinese curse:

'May you live in interesting times'

Try this: https://projecteuclid.org/download/pdf_1/euclid.pjm/1102784341

Read about shoes, socks, Bertrand Russell, and the AC here:
https://math.vanderbilt.edu/schectex/ccc/choice.html

Yeah maybe you are right. But the actual question was very simple to state (and I think it might have been lost in so much text). I was simply asking:
" Is (ZF¬C) + (well-ordered-ℝ) consistent? And if so can we give an explicit example of set A that can't be well-ordered (because ℝ already is)."

fresh_42 said he thought that (ZF¬C)+(well-ordered-ℝ) was likely to be consistent. I was just saying that it "may" be possible (in post#20) that it might not be. Obviously while admitting that I don't have a good idea since I don't have good understanding(and neither a good intuition) of these set theory topics.
It also seems that if (ZF¬C)+(well-ordered-ℝ) is consistent then one should also get a set A at some ordinal level α (using power-sets) that can't be well-ordered .

That's the summary of all the discussion! Anyway, good links.

P.S. "well-ordered ℝ" meaning "ℝ can be well-ordered".

 

[stevendaryl]

Yeah maybe you are right. But the actual question was very simple to state (and I think it might have been lost in so much text). I was simply asking:
" Is (ZF¬C) + (well-ordered-ℝ) consistent? And if so can we give an explicit example of set A that can't be well-ordered (because ℝ already is)."

My gut feeling, for what it's worth is that knowing that set $A$ can be well-ordered doesn't imply $\mathcal{P}(A)$ can be well-ordered. ($\mathcal{P}(A)$ meaning the collection of all subsets of $A$). So assuming that R can be well-ordered does not allow you to prove that $\mathcal{P}(R)$ can be well-ordered.

 

[SSequence]

Yes (assuming axioms/principles that allow well-ordering of any set to be false) given the particular fact that P(ℕ) has same cardinality as ℝ, it seems very reasonable to guess that on the very least we shouldn't necessarily assume the well-ordering of P(A) just based upon A.

But the "first case" might perhaps be special in a sense. If P(ℕ) has cardinality equal to something like aleph_α, it seems a bit awkward, for example, that P(P(ℕ)) suddenly can become a set that can't be well-ordered (instead of necessarily having some cardinality aleph_β for example).
But of course it is quite possible that this intuition is not correct (the way classical math works), and the correct way of reasoning is different.