1
$\begingroup$

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?

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

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .