Does this construction of total order use axiom of choice?

Question

I will be refering to my previous post, which can be found here: If there is a total order on $A$ and there is surjection $A\rightarrow B$ then can $B$ be totally ordered?

So, I have a sets $A,B$ such that $|A|>|B|$. Suppose $A$ is totally ordered, so I can say something like this: $$A=\{a_1,a_2,\ldots a_i,\ldots\}$$ I wish to construct total order on B. To do so, I construct disjoint 'sections' of A in following way: $$\mathcal{A}=\{A_1,A_2,\ldots,A_j,\ldots\}$$ where $A_k\subset A$ are the sections of $A$. By linear order, each set in $\mathcal{A}$ is linearly ordered. What is really important, that i CAN construct the $\mathcal{A}$ such that $|\mathcal{A}|=|B|$ which implies there is a bijection $\varphi:\mathcal{A}\rightarrow B$. Now, I construct a set $A'\subsetneq A$ such that it contains exactly $1$ element from each set in $\mathcal{A}$. I can say, that i will always choose the minimale element from each $A_i$'s, because, by linear order, they exist. Now, this implies $|A'|=|B|$ and I am able to construct bijection from $A'$ to $B$ and, as discussed in the post linked above, i am able to form a linear order on $B$.

My question is: Am i actually using the AC? AC says there is a function from family of sets such that i can choose exactly $1$ element from each, but when i explicitly define the function, am i still using the AC?

Answer 1

If $(A, <_A)$ is a well-order and $f: A \to B$ is a surjection, then $B$ can be well-ordered by $b_1 <_B b_2$ iff $\min_{<_A} f^{-1}[\{b_1\}] < \min_{<_A} f^{-1}[\{b_2\}]$, where the fibres are non-empty by surjectiveness and the minima exist by well-orderedness. No AC needed.

This of course does not work for linearly ordered sets that are not well-ordered: then we need a choice of representatives for the fibres, or equivalently an injection $g: B \to A$ with $f(g(x)) = x$ for all $x \in B$ (a so-called section of $f$). Either one uses AC. And then the order on $B$ can be defined by $b_1 <_B b_2$ iff $g(b_1) <_A g(b_2)$.

Answer 2

I can say, that i will always choose the minimale element from each $A_i$'s, because, by linear order, they exist.

That's not true. "Linear order" does not imply "every subset has a minimum". In fact, that condition is precisely what it means for linear order to be a well-order.

The theorem of ZF you're looking for is:

If $f: A \to B$ is surjective and you have a total well-ordering of $A$, then you can define a total well-ordering on $B$ by the procedure you describe

Answer 3

Choice is definitely needed to prove that claim.

It is consistent that $\Bbb{R/Q}$ cannot be linearly ordered, e.g. in models where all sets of reals are Lebesgue measurable, but there is a natural surjection from $\Bbb R$ onto $\Bbb{R/Q}$, of course.

On the other hand, requiring that the total order is a well-order lends itself naturally for the order given by choosing the least element of each fiber and comparing those.

Generally, this can work as long as the surjection has an inverse, but "every surjection has an inverse" is equivalent to the axiom of choice itself (note: "every set can be linearly ordered" is much weaker than full choice).

One remark, however, is that $|A|>|B|$ generally means that there is an injection from $B$ into $A$, which means that we can give $B$ a linear ordering using that injection. It is not necessarily the case, however, that the existence of a surjection implies that there is an injection, not without the axiom of choice.