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:
[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}$ ?
- 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.
- 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).
- 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.
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.