Show that any two infinite subsets of $\mathbb{Z}$ have the same cardinality.

Question

Hi, I was wondering if this is sound enough. I am trying to self teach so I would appreciate the critique.

Show that any two infinite subsets of $\mathbb{Z}$ have the same cardinality.

To achieve this, let A and B be infinite sets and $A, B\subset \mathbb{Z}$, meaning $|A|\leq|\mathbb{Z}|$ and $|B|\leq|\mathbb{Z}|$ where $\mathbb{Z}$ is countably infinite i.e. $|\mathbb{Z}|=|\mathbb{N}|$ (as proven in 1.1). By definition $|A|\leq|\mathbb{Z}|$ if there is an injection between A to $\mathbb{Z}$, and $|B|\leq|\mathbb{Z}|$ if there is an injection between B to $\mathbb{Z}$, thus A and B are countable as $|A|\leq|\mathbb{N}|$ and $|B|\leq|\mathbb{N}|$. Because $\mathbb{Z}$ is countably infinite as well as A and B are also countable and infinite as we have proven separately, we conclude our proof by stating $|A|=|B|=|\mathbb{N}|=|\mathbb{Z}|$.$\blacksquare$

Answer 1

For one thing, you should not write "by definition" except when you have in mind a specific definition that you are applying in a logically immediate way.

Next, I wouldn't rely on facts about comparison of cardinalities except when citing (at least implicitly, but in this case you should be explicit) a particular theorem. In this case, perhaps the Schröder–Bernstein theorem could be used.

However, all other things being equal, it's better to keep things as simple as they really are. In this case exhibiting an actual bijection can be done quickly.

Remember that by definition, and I do mean definition, two sets have the same cardinality if and only if there is a bijection between them.

Suppose $A$ is an infinite subset of $\mathbb Z.$ Let the first member of a sequence be the nonnegative member of $A$ (if any) of smallest absolute value. Let the next member of the sequence be the negative member of $A$ (if any) of smallest absolute value. Let the next be the nonnegative member of smallest absolute value among those not already in the sequence. Let the next be the negative number (if any) of smallest absolute value among those not already in the sequence. And so on.

This gives you a bijection between $A$ and $\{1,2,3,\ldots\}.$ Similarly create a bijection between $B$ and $\{1,2,3,\ldots\}.$ By composition, then, you have a bijection between $A$ and $B.$

Answer 2

I'm happy enough with that.

My own answer would go: it is enough to show that any two infinite subsets of $\mathbb{N}$ have the same cardinality, since $\mathbb{N}$ and $\mathbb{Z}$ are in bijection. So let $A, B \subseteq \mathbb{N}$ be infinite. Then we construct a bijection between them, as follows: let $A = \{a_1, a_2, \dots\}$ where $a_1 < a_2 < \dots$, and let $B = \{b_1, b_2, \dots \}$ where $b_1 < b_2 < \dots$. Then the bijection is $a_n \mapsto b_n$.

You can do this even more explicitly, using the idea which my lecturer called "attempts": building an object piece by piece until you've built the whole thing. Let $l(X)$ be the least element of set $X$, and define $A_1 = \{l(A)\}$. Then define $A_{n} := A_{n-1} \cup \{l(A \setminus A_{n-1})\}$, and $B_n$ similarly (so $A_n$ is the $n$ smallest elements of $A$); and finally define $f_n : A_n \to B_n$ given by $f_n = f_{n-1}$ on $A_{n-1}$, and $f(l(A \setminus A_{n-1})) = l(B \setminus B_{n-1})$. Then the union of the $f_n$ is a bijection $A \to B$.

Answer 3

Lemma: If $A \subset \mathbb N$ is infinite, then $A$ is countably infinite.
Proof
We define a recursive sequence $(A_n)$ of subsets of $\mathbb N$ as follows:

$\quad A_0 = A \text{ and } A_n = A_{n-1} \setminus \{\text{LeastElement}(A_{n-1})\}$

The function that maps $m \in \mathbb N$ to $\text{LeastElement}(A_m)$ is a bijective mapping between $\mathbb N$ and $A$.
$\blacksquare$