Proving a set is infinite

Question

Question:

Let $B$ be a proper subset of a set $ A$, and let $f$ be a bijection from $A$ to $B$. Prove that $A$ is an infinite set.

My attempt:

Proof by contradiction:

Assume $A$ is an finite set. Then $ B$ is a finite set. Since $B$ is a proper subset of $A$, we have $ |A|>|B|$. This is a contradiction since $ f : A\to B$ is a bijection and |A| = |B|.

Answer 1

you can choose $x_1\in A\setminus B$ and define $f_1:=f\setminus(x_1,f(x_1))$. But you still have that $B\setminus\{f(x_1)\}$ is proper subset of $A\setminus\{x_1\}$, so you can repeat the process. If it stop in a finite many steps, then $A=B$, a contradiction. so $A$ is infinite.

Answer 2

Suppose $A$ is a finite set. Then there exists a bijection $g:A\to \{1,2,\cdots,n\}$ for some positive integer $n$. Now $ g\circ f^{-1}:B\to \{1,2,\cdots,n\}$ is a bijection which is a contradiction (why?).

Answer 3

Take $x\in A$ \ $B.$ Let $f:A\to B$ be a bijection.

Let $g(0)=x$ and let $g(n)=f(g(n-1))$ for $n\in \mathbb N.$

Claim: $g:(\;\{0\}\cup \mathbb N\;)\to A$ is injective.

Proof: Suppose by contradiction that there exist $m,n$ with $0\leq m<n$ and $g(m)=g(n).$ Then let $m_0$ be the $least$ $m$ such that $g(m)=g(n)$ for some $n>m$, and let $n_0>m_0$ with $g(m_0)=g(n_0).$

Now we cannot have $m_0=0,$ else $g(m_0)=g(0)=x\not \in B$ and $g(n_0)=f(g(n_0-1))\in B.$

But if $m_0>0$ then $f(g(m_0-1)=g(m_0)=g(n_0)=f(g(n_0-1),$ and $f$ is bijective, so $ g(m_0-1)=g(n_0-1).$ But this contradicts the def'n of $m_0.$

Remark: Being a bijective image of $\{j\in \mathbb N: j<n\}$ for some $n\in \mathbb N$ is equivalent to the property called Tarski-finite. A set with a bijection to a proper subset of itself is called Dedekind-infinite. Without the Axiom of Choice it is consistent that there exists a set which is not Tarski-finite and is also not Dedekind-infinite.