4 ms·

since everyone here is bike shedding about the axiom of choice... I have this axiom of choice book (by Thomas Jech). It includes the following: > if F is a fin

by rtpg 4y ago

since everyone here is bike shedding about the axiom of choice... I have this axiom of choice book (by Thomas Jech). It includes the following: > if F is a finite family of nonempty sets, then there is a choice function (to show this one uses induction on the size of F; naturally a choice function exists for a family which consists of a single nonempty set). could someone lay out how one would "correctly" describe a choice function for a family with a single nonempty set? I feel like I understand theoretically this idea that choosing isn't about providing the value, but some... logical instantiation? What is the piece of the puzzle I'm missing here to understand why the choice function exists "naturally"?

quchen 4y ago
Good question, I’m confused about this as well! Take for example the single-element set containing the set of ℝ→ℝ functions, so { {f | f: ℝ→ℝ} }. The author seems to suggest there’s a natural choice for those functions. To me this sounds as hard as choosing from a larger set-of-sets.
- housecarpenter 4y ago
  I don't think Jech is using "naturally" as in "natural choice"; he's just using it as a synonym for "obviously". If X is non-empty set then there exists an x in X, because that's what it means for X to be non-empty. The choice is arbitrary: if X is the set of all functions from R to R then you could take the exponential function, the x^2 function, etc., whatever you like; the point is that it is certainly possible to make some choice. Doubting the axiom of choice means thinking that when you have infinitely many sets to choose from, it is possible that not only is there is no natural choice function, but there is no choice function at all.
  - rtpg 4y ago
    But why do we need the axiom of choice at all? By this logic I have any family of non-empty sets then I’m good? But surely there’s a distinction here
    - housecarpenter 4y ago
      I'm late replying to this, but---you need the axiom of choice once you have a family of non-empty sets rather than a single non-empty set. At some point you have to go into the formalism to really understand it. It's really about an interchange of quantifiers. If you have a non-empty set X that it is true that [a] (exists x)(x in X) If you have a family F of non-empty sets X then it is true that [b] (forall X in F)(exists x)(x in X) But to say that you have a choice function f for F is to say that [c] (exists f)(forall X in F)(f(X) in X) It turns out that the laws of first-order predicate logic and the axioms of ZF set theory do not allow you to come up with a formal proof that [b] implies [c]. You can try to find one, and you will fail. It's like the parallel postulate in Euclidean geometry. There is actually a proof that the axiom of choice is not provable from the other axioms, but it's a pretty deep result. Historically, there was quite a long time between when the set-theoretical foundations for mathematics were developed at the start of the 20th century, which is when mathematicians realized that the axiom of choice was a principle that needed justification, and when Paul Cohen proved that the axiom of choice wasn't provable from the other axioms, in the 1960s. So if you believe that the implication from [b] to [c] is self-evident, you have to assume [d] (forall X in F)(exists x)(x in X) => (exists f)(forall X in F)(f(X) in X) as an axiom, which is the axiom of choice. I think most people are inclined to agree that [d] is self-evident---that's why it's generally accepted as an axiom, with only a minority of people objecting. However, in the larger context of set theory it makes a lot of sense to minimize the amount of existential assumptions we are making. Historically, set theorists assumed that any set given by a definable formula would exist, but this lead to contradictions (Russell's paradox). So there's some reasonable paranoia about using additional axioms when we don't need to, in case it somehow leads to another inconsistency.
hgsgm 4y ago
Sets are defined by their members. If you have a nonempty set, you must have defined a member when you proved it was nonempty. Take any convenient one. This works for any finite or countable family, because you can repeat the process for each set, any set you can think of will be processed eventually. But for an uncountable set, almost every set will never be processed, and almost every set is impossible to describe in finite time (per set!), unless you just assume that you can do it on one magical oracle bulk selection.
- rtpg 4y ago
  Is the correct way to see this is that logic has to be specified in a finite number of terms? For countable families there’s some sort of meta logic like “for the Nth element I induct to that”? I believe to understand that idea (since it comes up in real analysis to some extent, basically acknowledging there isn’t really infinite sums except as limits of finite sums), but is there a specific sort of text that lays out this idea specifically?

by rtpg 4y ago

quchen 4y ago

Good question, I’m confused about this as well! Take for example the single-element set containing the set of ℝ→ℝ functions, so { {f | f: ℝ→ℝ} }. The author seems to suggest there’s a natural choice for those functions. To me this sounds as hard as choosing from a larger set-of-sets.

housecarpenter 4y ago
I don't think Jech is using "naturally" as in "natural choice"; he's just using it as a synonym for "obviously". If X is non-empty set then there exists an x in X, because that's what it means for X to be non-empty. The choice is arbitrary: if X is the set of all functions from R to R then you could take the exponential function, the x^2 function, etc., whatever you like; the point is that it is certainly possible to make some choice. Doubting the axiom of choice means thinking that when you have infinitely many sets to choose from, it is possible that not only is there is no natural choice function, but there is no choice function at all.
- rtpg 4y ago
  But why do we need the axiom of choice at all? By this logic I have any family of non-empty sets then I’m good? But surely there’s a distinction here
  - housecarpenter 4y ago
    I'm late replying to this, but---you need the axiom of choice once you have a family of non-empty sets rather than a single non-empty set. At some point you have to go into the formalism to really understand it. It's really about an interchange of quantifiers. If you have a non-empty set X that it is true that [a] (exists x)(x in X) If you have a family F of non-empty sets X then it is true that [b] (forall X in F)(exists x)(x in X) But to say that you have a choice function f for F is to say that [c] (exists f)(forall X in F)(f(X) in X) It turns out that the laws of first-order predicate logic and the axioms of ZF set theory do not allow you to come up with a formal proof that [b] implies [c]. You can try to find one, and you will fail. It's like the parallel postulate in Euclidean geometry. There is actually a proof that the axiom of choice is not provable from the other axioms, but it's a pretty deep result. Historically, there was quite a long time between when the set-theoretical foundations for mathematics were developed at the start of the 20th century, which is when mathematicians realized that the axiom of choice was a principle that needed justification, and when Paul Cohen proved that the axiom of choice wasn't provable from the other axioms, in the 1960s. So if you believe that the implication from [b] to [c] is self-evident, you have to assume [d] (forall X in F)(exists x)(x in X) => (exists f)(forall X in F)(f(X) in X) as an axiom, which is the axiom of choice. I think most people are inclined to agree that [d] is self-evident---that's why it's generally accepted as an axiom, with only a minority of people objecting. However, in the larger context of set theory it makes a lot of sense to minimize the amount of existential assumptions we are making. Historically, set theorists assumed that any set given by a definable formula would exist, but this lead to contradictions (Russell's paradox). So there's some reasonable paranoia about using additional axioms when we don't need to, in case it somehow leads to another inconsistency.

hgsgm 4y ago

Sets are defined by their members. If you have a nonempty set, you must have defined a member when you proved it was nonempty. Take any convenient one. This works for any finite or countable family, because you can repeat the process for each set, any set you can think of will be processed eventually. But for an uncountable set, almost every set will never be processed, and almost every set is impossible to describe in finite time (per set!), unless you just assume that you can do it on one magical oracle bulk selection.

rtpg 4y ago
Is the correct way to see this is that logic has to be specified in a finite number of terms? For countable families there’s some sort of meta logic like “for the Nth element I induct to that”? I believe to understand that idea (since it comes up in real analysis to some extent, basically acknowledging there isn’t really infinite sums except as limits of finite sums), but is there a specific sort of text that lays out this idea specifically?