# Prove that if A is an infinite set and $|A| =|B|$, then $B$ is an infinite set.

Prove that if $A$ is an infinite set and $|A| = |B|$, then B is an infinite set.

Proof:

Suppose $A$ is an infinite set and $|A| =|B|$, and that $B$ is a finite set. Because $B$ is a finite set, $B=\emptyset$ or there's a natural number $k$ such that $B$ is equivalent to $\mathbb{N}_k$ .

If $B=\emptyset$,then $A=\emptyset$, which contradicts that $A$ is infinite, so original statement holds.

If $|B| =|\mathbb{N}_k|$ for some natural number $k$,then $|A| =|\mathbb{N}_k|$, implying $A$ is finite, a contradiction.

Therefore, the original statement holds.

Is the above proof correct? Also, is there another proof of this statement without using contradiction?

• What do you mean by "equivalent"? Do you mean that there is a bijection between sets? Apr 30, 2016 at 16:04
• @Wojowu, Yes. I switched to notation to make it clearer. Apr 30, 2016 at 16:08
• In that case, I think the proof is correct. I don't know whether there is a non-contradiction proof. Apr 30, 2016 at 16:10

Assuming you are only talking about countably infinite sets, you can first say that there exists a bijection between $A$ and $\mathbb N$:

$f: A \to \mathbb N$

Since $|A| = |B|$, we also have a bijection between $A$ and $B$, so write:

$g : B \to A$

Use the fact that the composition of bijective maps is bijective too and you have:

$f\circ g : B \to \mathbb N$

which shows $B$ is countably infinite too.

Well, infinite usually means "not finite" that is "finite $\Rightarrow$ contradiction", so in some sense there cannot be a "contradiction-free" proof.

But, you could cleverly hide the contradiction. A set $A$ is infinite if and only, if there is an injection $\mathbb{N}\to A$. (Though, I think I actually need the axiom of choice for this equivalence).

Then if $A$ is infinite and $|A| = |B|$, there is an injection $m : \mathbb{N} \to A$ and an injection $i : A \to B$ (in fact, there is a bijection $A \to B$), so $i\circ m : \mathbb{N} \to B$ is an injection, hence $B$ is infinite.

Assuming you are using the Kuratowski definition (see this Wikipedia page) of finiteness (i.e. $A$ is infinite iff $A$ is not Kuratowski finite).

So $A$ infinite means there is some Kuratowski inductive subset $K$ of $\mathcal{P}A$ such that $A\notin K$.

We have a bijection $f\colon A\to B$. Define a set $K^\prime\subseteq\mathcal{P}B$ such that $$b\in K^\prime\Leftrightarrow f^{-1}(b)\in K.$$ I claim that this set is Kuratowski inductive and $B\notin K^\prime$, which shows that $B$ is (Kuratowski) infinite. Proof of the claim is below.

• $\emptyset\in K^\prime$ because $f^{-1}(\emptyset)=\emptyset\in K$.
• Suppose $E\in K^\prime$ and $x\in B$. Then consider $f^{-1}(E\cup\{x\})$. By the injectivity of $f$, this is equal to $f^{-1}(E)\cup f^{-1}(\{x\})$, which is a member of $K$ by Kuratowski inductiveness of $K$, since $f^{-1}(\{x\})\in A$.
• $A\notin K$ by assumption, and $f^{-1}(B)=A$, so $B\notin K^\prime$.