Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Axiom of Choice not self evident?

  1. Sep 10, 2017 #1
    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.
     
  2. jcsd
  3. Sep 10, 2017 #2

    fresh_42

    Staff: Mentor

    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.
     
  4. Sep 10, 2017 #3
    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.
     
  5. Sep 10, 2017 #4

    fresh_42

    Staff: Mentor

    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.
     
  6. Sep 10, 2017 #5
    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##
     
  7. Sep 10, 2017 #6

    fresh_42

    Staff: Mentor

    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)\,##?
     
  8. Sep 10, 2017 #7
    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.
     
  9. Sep 10, 2017 #8

    fresh_42

    Staff: Mentor

    ##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.
     
  10. Sep 10, 2017 #9
    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?
     
  11. Sep 11, 2017 #10
    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.
     
  12. Sep 11, 2017 #11
    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_ω2 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.
     
  13. Sep 11, 2017 #12

    mathman

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  14. Sep 13, 2017 at 8:51 AM #13

    fresh_42

    Staff: Mentor

    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.)
    As long as you mean ZFC by classical mathematics.
    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.
    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/Abstract-Analysis-Graduate-Texts-Mathematics/dp/0387901388
    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.
     
  15. Sep 13, 2017 at 9:59 AM #14
    I realise 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?

    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?
     
    Last edited: Sep 13, 2017 at 12:06 PM
  16. Sep 13, 2017 at 11:14 AM #15

    fresh_42

    Staff: Mentor

    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.
    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.
    ... which would imply a given counterexample, which cannot be given. Therefore every reasoning beyond this point is meaningless ...
    ... 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.
    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.
    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.
     
  17. Sep 13, 2017 at 11:52 AM #16
    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:

    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.
     
    Last edited: Sep 13, 2017 at 1:29 PM
  18. Sep 13, 2017 at 1:34 PM #17

    fresh_42

    Staff: Mentor

    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?
     
  19. Sep 13, 2017 at 2:03 PM #18
    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).

    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 ℝ.
     
    Last edited: Sep 13, 2017 at 3:51 PM
  20. Sep 13, 2017 at 7:00 PM #19

    mathman

    User Avatar
    Science Advisor
    Gold Member

  21. Sep 13, 2017 at 8:18 PM #20
    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.
     
    Last edited: Sep 13, 2017 at 9:15 PM
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Axiom of Choice not self evident?
  1. The Axiom of Choice (Replies: 9)

  2. Axiom of choice (Replies: 3)

  3. Axiom of Choice (Replies: 17)

  4. The Axiom of Choice? (Replies: 11)

  5. The Axiom of Choice (Replies: 8)

Loading...