0
$\begingroup$

I am learning about Axiom of Choice and Well Ordering Principle from Munkres's Topology book, but I can't quite wrap my head around it properly. I have these questions:

  1. [Munkres 0.4.3] If $A = A_1 \times A_2 \times A_3 \times \cdot$, then if $A$ is nonempty then show each $A_i$'s nonempty. Is the converse true ?

I'm having problem seeing why isn't it obvious ? Like can't we use AoC and just pick any element of $A = (a_1, a_2, \cdots )$ with $a_i \in A_i$, then since $a_i \neq \phi$, we have $A_i$ nonempty.

Also isn't the converse false ? If $A_1$ is empty, and say $\{0, 1 \} = A_2 = A_3 = \cdots $, then isn't the element $( \phi, 0,0,0,0, 0, \cdots ) \in A$ and we have $|A| = 2^{\omega}$ ?

  1. So how you can guarantee that a problem must involve choice ? In other words, how are you supposed to solve this exercise from Munkres, Topology:

    [Munkres 0.9.4(d)] Is there a choice function without invoking Axiom of Choice on an uncountable se $X$ ?

I hazard a guess the answer is false but I have no idea how to prove it. I can prove the answer to be "no" however if $X$ is countable.

  1. How to think about well ordering of $\mathbb{R}$/well order in general ? I'm finding them (especially minimal uncountable well ordered set) very very counterintuitive and don't have any mental rough picture of them.

Should I imagine that well ordering makes a set behave like the integers when "zoomed in" in some way ?

Should I imagine a directed graph with the elements of the well ordered set $X$ and an edge from $u$ to $v$ with $u,v \in X$ iff $u <_X v$ ? But then this graph is uncountable and I don't have any idea how to imagine uncountable graphs (I imagine countable graph as a two dimensional lattice points).

  1. How do you imagine transfinite induction ?

In ordinary induction I imagine that there's a set $S$ for which the things ought to be true are proved, and at each step we just increase the size of $S$ so that every integer is eventually added to $S$. This gives a concrete "algorithm" feeling to ordinary induction, but transfinite induction can't be viewed as this process, so I don't have any nice mental model for it.

$\endgroup$
9
  • 10
    $\begingroup$ Suggestion: one question at a time. $\endgroup$ Commented Apr 1, 2019 at 22:13
  • $\begingroup$ Choice isn't needed for 1), but it is for the converse. In fact, Choice is the converse of that statement. $\endgroup$ Commented Apr 1, 2019 at 22:31
  • $\begingroup$ Re (1): $\emptyset \not\in \emptyset$. $\endgroup$ Commented Apr 1, 2019 at 23:14
  • 2
    $\begingroup$ @uniquesolution: Those questions are all intertwined, it makes sense to ask them together, at least to some extent (I agree that the partition into questions could be better). $\endgroup$ Commented Apr 1, 2019 at 23:20
  • 1
    $\begingroup$ @uniquesolution: The axiom of choice, in general, is quite useless without transfinite recursion. As such, questions about intuition related to using the axiom of choice go hand in hand with questions about intuition about transfinite recursion. $\endgroup$ Commented Apr 2, 2019 at 14:47

1 Answer 1

Reset to default
7
$\begingroup$

Your suggested solution is correct. $(a_0,\ldots)$ is an element of $A$, and each $a_i\in A_i$ showing that it is not empty, although the axiom of choice is not used here, since we are only choosing a single element from $A$ (which was guaranteed to be non-empty by a higher power).

However, if $A_0$ is empty, and $A_i=\{0,1\}$ for all $i>0$, it is not true that $(\varnothing,0,0,0,\dots)$ is an element of the product, since $\varnothing\notin\varnothing$.

Indeed, the axiom of choice is equivalent to the statement that the product of non-empty sets is non-empty. To that end, the axiom of choice is an intuitive axiom.

Zermelo treated it as an inference rule, and this much is witnessed by the fact that certain higher-order proof assistants will outright prove the axiom of choice by the same sort of reasoning. One of the most prolific set theorists told me when I was a budding masters student that a good mathematical foundation is one whose axioms are not "in your way", so that you don't interact with them every so often. This is very much true about the axiom of choice, as evident by the common mistakes people make when they claim something doesn't require choice, even when it does.

So. Mental pictures. I suggest that you give up on those. Much like how you only really develop a mental picture of the real numbers after you have worked with them for a while, after you've proved things about them—and with them—for a while, the same is true about well-orders. It is true that an uncountable well-ordering is somehow baffling and counterintuitive, but in fact large countable well-ordering are already just as confusing if you try to imagine them.

The key thing to remember about well-ordering of $\Bbb R$, though, is that it does not agree with the standard ordering of the reals. Much like how a well-ordering of $\Bbb Z$ does not agree with the standard ordering, nor a well-ordering of $\Bbb Q$. Only difference is that for $\Bbb Z$ and $\Bbb Q$ we can actually define such well-ordering.

Transfinite induction is slightly easier. It's the same as "regular induction" mixed with "strong induction". If you knew how to get up to $n$, you should know how to get over $n$. But the same advice as well-orders work here as well.

Well-orders are generally something you want to think of as having successive steps, like a ladder. But then, sometimes you've exhausted the notion of "successive" and you just put "a cap" on top, and continue from there. To that end, thinking about convergent sequences stacked on top of each other is not a bad image. But now let go of however many of those sequences that you've put on top of one another, and just keep the abstract idea of that.

And recursion works on the same principle. Go one step at a time in your current sequence, at limit steps, do something slightly different (e.g. take the limit, in some reasonable sense, like unions sometimes).

Work with the definitions, closely, carefully, and one step at a time. After a lot of hard work, you'll find yourself with a mental image.

(One that you might be struggling to properly explain to others, even if you are very much certain of its correctness.)

Remember. We do not do it because it is easy. We are doing it because it is interesting, and amazing, and it rewards you with knowing that you've accomplished something that only few people have managed to conquer: the transfinite.

$\endgroup$
9
  • $\begingroup$ So. Mental pictures. I suggest that you give up on those. Very true for higher set theory. But, depending on OP's mathematical background, this might be a tricky thing to ask for. Set theory is in some sense unique as it is notoriously difficult to visualise key concepts, something mathematicians from other areas might not be used to. $\endgroup$ Commented Apr 1, 2019 at 23:45
  • $\begingroup$ Thanks a lot for answering my question ! There are a few small things which I don't get yet: (a) I thought i. $\phi$ is an element of every set and ii. The empty set is a set, so putting i and ii don't we get $\phi$ belongs to the empty set, i.e $\phi \in \phi$ ? Anyway I don't know any formal set theory so this may be very wrong. (b) Why you don't need choice to pick an element from, say, $\mathbb{R}$ ? (c) $\endgroup$ Commented Apr 2, 2019 at 5:10
  • 1
    $\begingroup$ @MacRance: Really? What is the visual intuition behind the Goldbach conjecture, or behind Liouveille's theorem, or behind the Rado graph, or the twin prime conjecture? I agree that set theory is different, but it's not it's lack of visualization, that's rather false. I have a very clear mental image, and I'm sure most set theorists do. Set theory is different in that you are told from age 0 that it is different and has no mental picture, so you don't try to develop one unless you become a set theorist. $\endgroup$ Commented Apr 2, 2019 at 6:44
  • 1
    $\begingroup$ @alxchen: Element of is not a subset of, and a subset of is not an element of. Those two notions are independent. $\varnothing$ is a subset of every set, not an element of every set. Indeed, no object is an element of the empty set, that's why we call it "the empty set". As for your second question, we have an inference rule called existential instantiation which lets us move from a non-empty set, to an element of that set. For your last question, not really, there is a robust way of translating results on the natural numbers from ZFC to ZF, but it is a technical reasoning. $\endgroup$ Commented Apr 2, 2019 at 6:46
  • 2
    $\begingroup$ @MacRance: Yes, that is true. Set theory does not have a natural model to impart intuition. This contributes to the myth that there is no visual intuition in set theory. But a physicist or a chemist might tell you the same about analysis in four dimensions. I was had a chat with some engineering students, back when I was an undergraduate, and they were told to imagine a 4D sphere as a "3D sphere moving through time". Would you say that it's the same visual intuition a mathematician has? I wouldn't. Yes, abstraction comes with a price of working harder for visual intuition. Nothing new. $\endgroup$ Commented Apr 2, 2019 at 7:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.