# Proof Check: The cardinality of all monotonically increasing series of natural numbers.

Given an infinite series, $a_1a_2a_3\ldots$ define $F$, $F(a_1a_2a_3\ldots) = a_1\bmod(2)a_2\bmod(2)a_3\bmod(2)\ldots$

It's trivial to show that $F$ is onto the set of all infinite binary series, which has a cardinality of $\aleph_1$.

So the cardinality of the aforementioned set $\ge \aleph_1$.

Then again the set of all infinite binary sets is a subset of the set of all infinite series of natural numbers, therefore yielding a cardinality of $\le\aleph_1$.

All in all we get a cardinality of $\aleph_1$ by the Cantor–Bernstein–Schroeder theorem.

I feel like I might've made a mistake with $F$, but I'm not sure. Can anyone verify? Thanks for your time!

• You seem to be assuming the continuum hypothesis.
– Jay
Commented Jan 31, 2014 at 23:50
• I think you proved that the cardinality is $\geq 2^{\aleph_0}$ twice, although the set of all the infinite binary sequences is not a subset of the monotonically increasing sequences of natural numbers. Commented Jan 31, 2014 at 23:51
• @Jay : I wouldn't leap to the conclusion that he's assuming the continuum hypothesis: some otherwise respectable mathematicians labor under the impression that $\aleph_1$ is defined to be $2^{\aleph_0}$, the cardinality of the continuum. Commented Feb 1, 2014 at 0:02
• @Michael: That's like saying that not knowing that theft is illegal means that you can take whatever you want from wherever you want. Commented Feb 1, 2014 at 0:03
• PS: For the record: The fact that there are no cardinalities between $\aleph_0$ and $\aleph_1$ is provable without the axiom of choice and without the continuum hypothesis. The relation $\aleph_1\le 2^{\aleph_0}$ is not provable in ZF but is provable in ZFC, i.e. ZF plus the axiom of choice. The continuum hypothesis says there are no cardinalities between $\aleph_0$ and $2^{\aleph_0}$. In ZFC, that is equivalent to $\aleph_1=2^{\aleph_0}$. In ZF, it is possible that $\aleph_1$ and $2^{\aleph_0}$ are incomparable even if the continuum hypothesis is true. Commented Feb 1, 2014 at 0:12

Your gravest mistake is that $\aleph_1$ is NOT the cardinality of the continuum (well, at least not in general). We define $\aleph_1$ to be the least uncountable cardinal, whereas $2^{\aleph_0}$ is just uncountable. It is consistent with the axioms of set theory that they are equal, and it is consistent that they are not.

The $F$ that you define is fine, and it is indeed a surjection from the set of monotonically increasing sequences onto the set of binary sequences. This establishes, as you point out that the cardinality of the set that you are interested in is at least $2^{\aleph_0}$.

However the second part is not well-written. You provide a second argument as to why the cardinality is at least $2^{\aleph_0}$ rather than providing an argument that it is at most $2^{\aleph_0}$ (which will then imply equality).

HINT: Every sequence of natural numbers is in fact a function $f\colon\Bbb{N\to N}$. Note that such function $f$ is a subset of $\Bbb{N\times N}$. How many subsets does this product have?

• Thanks for this, your hint really clears things up. If I change every aleph1 in my proof to C, the cardinaltiy of R, will my proof be correct? Commented Jan 31, 2014 at 23:59
• Why do I need a second argument that the cardinality is at least C? Commented Feb 1, 2014 at 0:00
• You don't need a second one, you have a second one. You proved the same direction in two different ways. One of them is quite sketchy as it is. Commented Feb 1, 2014 at 0:00
• Ahh, I've made a few mistakes. This:" Then again the set of all infinite binary sets is a subset of the set of all infinite series of natural numbers, therefore yielding a cardinality of ≤ℵ1. " Should've been: "Then again the set of all infinite monotonically increasing series of natural numbers is a subset of the set of all infinite series of natural numbers, therefore yielding a cardinality of ≤ℵ1." Commented Feb 1, 2014 at 0:04
• I also misread your answer. Is this revised version correct? Commented Feb 1, 2014 at 0:05