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

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$

• It is ok. You are using Schroder-Bernstein's theorem, maybe it is good to mention it and be clear that it is being used. – user539964 Mar 13 '18 at 20:50
• It is sufficient to note that $|\mathbb{Z}| = |\mathbb{N}| \le |A| \le |\mathbb{Z}|$. Same applies to $B$. – copper.hat Mar 13 '18 at 20:51
• I cannot understand this proof. If you are using specific lemmas about cardinality, you should cite them explicitly. Otherwise, you need to use the definition of cardinality and give a bijection from $A$ to $B$. – Jair Taylor Mar 13 '18 at 20:53

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

• I would mark the OP's answer higher than yours. His argument is complete, yours is missing proving that your map from $\mathbb{N}$ to $A$ is surjective. – user539964 Mar 13 '18 at 21:05

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

• Oh wow that is pretty explicit, a bit beyond my level but am I seeing schroder-bernstein? – C. Ekinci Mar 13 '18 at 20:53
• @YoloSatoshi No Schröder-Bernstein here: just a good old "voilà, a bijection". – Patrick Stevens Mar 13 '18 at 20:54
• @MichaelHardy But so is your answer. – user539964 Mar 13 '18 at 21:06

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$

• Not familiar with least element, do you mean min? – C. Ekinci Apr 13 '18 at 1:37
• Yes. In mathematics, a well-order (or well-ordering or well-order relation) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. see en.wikipedia.org/wiki/Well-order – CopyPasteIt Apr 13 '18 at 1:53