ZFC and the Axiom of Choice.

axiom-of-choiceelementary-set-theoryproof-writingset-theorysolution-verification

I've been given the following problems in set theory, specifically, ZFC:

  1. Every infinite set has a countable infinite subset. Conclude that every Dedekind finite is also finite.

  2. Every infinite set is the union of two infinite disjoint sets.

  3. Every infinite set is the countable union of infinite sets.

  4. If there exists a surjection from the set $A$ to the set $B$. Then, there exists an injection from $B$ to $A$.

  5. If $A$ is infinite, $B \subseteq A$ and $|B| < |A|$. Then, $\left|A \setminus B\right| = |A|$.

My thoughts and questions;

  1. This proof was taken from https://proofwiki.org/wiki/Infinite_Set_has_Countably_Infinite_Subset#:~:text=Now%2C%20suppose%20that%20that%20there,countably%20infinite%20subset%20of%20S, the third proof, and left me with some questions. Let $S$ be a infinite set. By the axiom of choice, there exists a choice function $f: \mathcal{P}(S)\setminus\{\emptyset\}\to S$ such that
    $$\forall s \in \mathcal{P}(S)\setminus\{\emptyset\}:f(s)\in s$$
    Let $C = \left\{X \subset S\;\vert\; X \mbox{ is finite } \right\}$, which is a set by the theorem of separation. If $A\in C$, it follows by assumption that $S\setminus A \neq \emptyset$, then, $S\setminus A \in \mbox{Dom}(f)$. Define $g:C \to C$ by
    $$g(A) = A\cup f(S \setminus A)$$
    Define $h:\omega \to C$ (here in the proof, it is said that $h$ is a recursion on $g$, is this necessary? Can't we just define $C$ and then $h$?) by
    $$h(x)= \left\{ \begin{array}{rcl}
    \emptyset & \mbox{if}
    & x=0 \\
    h(x)\cup f\left(S \setminus h(n)\right) & \mbox{if} & x = n^{+}
    \end{array}\right.$$
    Consider now the function $j: \omega \to S$ given by
    $$\forall n \in \omega: j(n)=f\left(S \setminus h(n) \right)$$
    which has the properties

(1) $\forall n \in \omega: j(n)\notin h(n)$

(2) $\forall n \in \omega : j(n) \in h(n^{+})$

(3) $(\forall n,m \in \omega)(n\leq m) \Rightarrow h(n) \subseteq h(m)$

(4) $(\forall n,m \in \omega)(n <m) \Rightarrow j(n) \neq j(m)$. Since $j(n) \in h(m)$ but $j(m) \notin h(m)$.

From (4), it follows that $j$ is an injection, if $\mbox{Img}(j) = B \subset S$, then, $j: \omega \to B$ is a bijection. Thus, the set $\mbox{Img}(j) \subset S$ is countably infinite.

In ZFC, every infinite set is also Dedekind infinite. Thus, if a set $X$ is Dedekind finite, $X$ is itself finite.

  1. Let $S$ be infinite. Take $a_0 \in S$ and let $A_0 = \{a_0\}$ and take $b_0 \in S\setminus A_0$, then $B_0 = \{b_0\}$. Take $a_1 \in S\setminus A_0 \cup B_0$, then $A_1 = A_0\cup\{a_1\}$ , take $b_1 \in S \setminus A_1 \cup B_0$, then $B_1 = B_0 \cup\{b_0\}$. With this, we can construct
    \begin{align*}
    A &= \bigcup_i A_i \\
    B &= \bigcup_j B_j
    \end{align*}

This process can't be carried indefinitely, and thus we need the axiom of choice. However, I can't think of how to precisely build this, any help would be appreciated. I'm having quite some trouble in solving problems which require the use of the axiom of choice, any tip on how to develop a better problem-solving technique for those specific cases?

  1. I'm not sure, but I believe this would follow similarly from the previous problem. If not, where does the idea breaks down and how to solve it?

  2. Taken from If there is a surjection $A\to B $ and another $B\to A$ then $A $ and $B$ are in bijection. Let $A$ and $B$ be sets and let $f: A \to B$ be a surjection. For each $b \in B$, we can (by the axiom of choice), take an element $a\in f^{-1}(b)$. Thus, we have an injection $g: B \to A$ by defining
    $$g(a) = b$$
    for every $b$. How can this be written more rigorously using a choice function?

  3. Not sure it this counts as a duplicate of Let $A, B$ be some sets such that $A\setminus B$ is infinite while $B$ countable or finite. Prove that $A\setminus B\sim A$. Let $A$ be infinite, $B \subseteq A$ and $|B|<|A|$. If $B$ is finite, it is trivial that $|A \setminus B| = |A|$. If $B$ is infinite, I can see how to relate the axiom of choice to this problem.

Again, any help is extremely appreciated. I'm really struggling to construct proofs using choice functions and the axiom of choice.

Best Answer

I know I should have split this question, but since I have my solutions which were accepted by my teacher (less rigorously), I will end posting this as the full answer to the 5 questions.

  1. Let $S$ be infinite. If $S \approx \omega$, we can split $S$ into the even and odd mappins in the naturals. If $S$ is not countable, let $a_1 \in S$ and take $A_1 = \{a_1\}$. Let $a_2 \in S\setminus A_1$ and take $A_2 = A_1 \cup \{a_2\}$, and so forth. By the axiom of choice, there is a choice function which does this selection. Thus, $$A = \bigcup_{i \;\in\, \omega\setminus\{0\}} A_i$$ is countable.

  2. Let $S$ be infinite. If $S$ is countable, we can do the same as the first case of $1.$. If $S$ is uncountable, take $A$ as the countable subset of $S$ and $B = S\setminus A$, then $A \cap B = \emptyset$ by construction. Thus $$S = A \cup B$$ as desired.

  3. Let $S$ be infinite. If $S$ is countable, this is trivial. If $S$ is uncountable, take the same construction from 2., taht is $$S = A \cup B$$ where $B = S\setminus A$ is uncountable, thus it has a countable subset $C$, that is $$S = A \cup C \cup B\setminus C$$ we can keep aplying 2. to this, thus, by recurrsion $$S = \bigcup_{i\;\in \,\omega} A_i$$ where $A_0 = A$, $A_1 = B$, $A_3 = C$ and so forth.

  4. Let $f:A \to B$ be surjective. Take $C = \left\{f^{-1}(b) = a\;\vert\; b \in B \right\}$, by the axiom of choice, there is a choice function $g$ on $C$. Thus, $h: B \to A$ definied by $$h(b) = g(a)$$ is an injection.

  5. Let $A$ be inifinite, $B \subset A$ and $|B|<|A|$. If $A$ is countable, $B$ has to be finite and thus $|A\setminus B| = |A|$ is trivial. If $A$ is uncountable and $B$ infinite ($B$ finite is trivial), $A\setminus B$ has a countable subset $C$, that is $A\setminus B = \left((A\setminus B)\setminus C\right)\cup C$ and then $A = \left((A\setminus B)\setminus C \cup B \right) \cup \left(C \cup B \right) = \left(A\setminus C \right) \cup \left(C \cup B \right)$. Define $f: A\setminus B \to A$ by $$f(x_i) = \left\{\begin{array}{lcr} x_i & \mbox{if } x_i \in \left(A \setminus B \right)\setminus C \\ y_i\in B \cup C & \mbox{if } x_i \in C \end{array}\right.$$ which can be shown to be bijective. Thus $|A\setminus B| = |A|$.

Related Question