0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ with $\min_{<A} f^{-1}[\{b_1\}]$ you mean the minimum from the set where $b_1$ is contained? $\endgroup$ – Michal Dvořák Aug 18 '18 at 11:09
  • 1
    $\begingroup$ @MichalDvořák Yes, the minimum of the fibre of $b_1$, which is the set of all $x \in A$ with $f(x) = b_1$. $\endgroup$ – Henno Brandsma Aug 18 '18 at 11:17
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Oh, I see. I'm just curious, can you give an example of totally ordered set which is NOT well ordered? $\endgroup$ – Michal Dvořák Aug 18 '18 at 10:48
  • $\begingroup$ Actually, $A$ is a set of strings, which are ordered 1. lexicographically (I work with a finite alphabet) and 2. by length (which is natural number). So the $A$ is well odered, isn't it? $\endgroup$ – Michal Dvořák Aug 18 '18 at 10:54
  • 2
    $\begingroup$ @MichalDvořák the reals or the rationals in their usual ordering are not well-ordered. $\endgroup$ – Henno Brandsma Aug 18 '18 at 10:58
  • 1
    $\begingroup$ @MichalDvořák see my answer.. $\endgroup$ – Henno Brandsma Aug 18 '18 at 11:05
  • 1
    $\begingroup$ @MichalDvořák Not; as I said, the theorem I stated is a theorem of ZF. $\endgroup$ – Hurkyl Aug 18 '18 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.