Proving the Axiom of Choice for countable sets

Question

I am new to the axiom of choice, and currently working my way through some exercises. I am struggling with the following exercise:

Exercise - Prove the Axiom of Choice (every surjective $f: X \to Y$ has a section) in the following two special cases:

1. Y is finite
2. X is countable

(A section has been previously defined as a function $s: Y \to X$ such that $f(s(y)) = y$ for all $y \in Y$)

My confusion - Now from what I understand, in (1) you use surjectivity of $f$ to pick an $x \in X$ such that $f(x) = y_0$ proving the case $|Y| = 1$, and then use induction to proof it for general $|Y| = N$.

I am a bit confused at (2) though. Would it be legal to take the previous argument and take the limit $N \to \infty$? I tried to google it but I got more confused after reading this question and seeing other references to the axiom of countable choice, suggesting that this result cannot be proven.

By the way, I am doing 'naive' set theory here; ZF/ZFC axiom systems and those kind of things have not been discussed in the course.

Answer 1

The countable axiom of choice refers to the case where $Y$ is countable, so it is kind of different.

Let us see how we could do this. Since $X$ is countable there is a bijection $\phi$ with $\mathbb{N}$. Now you have a well defined order on $X$ :

$$x\leq y \text{ by definition if } \phi(x)\leq \phi(y)\text{ in }\mathbb{N} $$

I claim that this order on $Y$ verifies that the property " any non-empty set has a least element" is true (I don't remember right now the name of this property...).

Another way to state this is that in any non-empty $C$ set of $Y$ you can canonically $\textit{ choose }$ an element in $C$ namely $min(C)$. Apply this to construct the section for $f$.

Answer 2

There is a terminological discrepancy here.

The Axiom of Countable Choice refers to the statement "If $S$ is a countable family of non-empty sets, then $S$ admits a choice function".

What you are trying to prove is that if $f\colon X\to Y$ and $X$ is countable, then $f$ admits a section.

This is not the same as choosing from a countable family of non-empty sets. If $\{A_n\mid n\in\Bbb N\}$ is a countable family of non-empty sets then a choice function would be a function from $\Bbb N$ into $\bigcup A_n$, rather than a function from $\Bbb N$ onto the union. The section map, if anything, would map $a\in\bigcup A_n$ to the least $n\in\Bbb N$, such that $a\in A_n$.

But an even more general thing is true. If $X$ can be well-ordered (so it can be uncountable as well), then by fixing a well-ordering of $X$ we can choose for each $y\in Y$ the minimal element of $\{x\in X\mid f(x)=y\}$ (which is non-empty by the surjectivity of $f$).