elementary-set-theory
Prove that a set A is infinite if and only if $A$ contains a proper subset $B$ that satisfies $|B|=|A|$.
For the first part, I tried the following:
Since $A$ is infinite, it has a countable subset $S=\{a_n\}$ with $n$ in $\mathbb N$. Then we have a function $f:A\to A\setminus \{a_0\}$ such that $f(a_n) = a_{n+1}$ if $a$ is in $A$ and $a=a_n$ and $f(a)=a$ otherwise.
I don't know if this approach is correct, and need help proving part 2.
This actually requires the axiom of choice. Basically, you just do it. Let $a_0$ be any element of $A$. $A\ne\{a_0\}$, since $A$ is infinite, so $A\setminus\{a_0\}\ne\varnothing$. Thus, we can pick some $a_1\in A\setminus\{a_0\}$. $A\ne\{a_0,a_1\}$, since $A$ is infinite, so $A\setminus\{a_0,a_1\}\ne\varnothing$, and we can pick some point $a_2\in A\setminus\{a_0,a_2\}$. In general, at stage $n$ we have distinct points $a_0,\dots,a_{n-1}$. $A\setminus\{a_0,\dots,a_{n-1}\}\ne\varnothing$, since $A$ is infinite, so we can pick $a_n\in A\setminus\{a_0,\dots,a_{n-1}\}$ and continue the construction. When we’re done, we just set $C=\{a_n:n\in\Bbb N\}$.
We want to prove that:
(1) X is equipotent to a proper subset H if and only if (2) X is an infinite set.
Note: X is equipotent to H $\begin{smallmatrix} def \\ \iff \\ \space \end{smallmatrix}$ there is a bijection between X and H $\begin{smallmatrix} def \\ \iff \\ \space \end{smallmatrix}$ |X|=|H| (they have the same cardinality)
H is a proper subset of X $\begin{smallmatrix} def \\ \iff \\ \space \end{smallmatrix}$ H $\subsetneq$ X.
Proof
(1)$\Rightarrow$(2) Assume by contradiction that X is finite. Since there exist a bijection $f:X\rightarrow H$ then by definition of cardinality $|X|=|H|$. But H is a subset of X which is proper so $\forall h \in H : h \in X$ but $\exists x \in X : x \notin H$. Hence H has at least one element less than X, so $|H|<|X|$ - contradiction.
(2)$\Rightarrow$(1) To prove this direction in (ZF) we need the condition "X is a Dedekind-infinite set" instead of just an infinite set. However, we can prove it in (ZF + ACw) applying the axiom of countable choice:
In wikipedia you can find the proof that every infinite set is Dedekind-infinite in (ZF + ACw).
Best Answer
That approach is excellent: you have indeed shown that if $A$ is infinite, it admits a bijection with a proper subset.
Suppose that $f:A\to A$ is a bijection from $A$ to a proper subset of $A$. Pick $a_0\in A\setminus f[A]$. Given $a_n$, let $a_{n+1}=f(a_n)$; now prove that the map $n\mapsto a_n$ is a bijection from $\Bbb N$ into $A$.