As part of my math homework I need to prove $\lvert \{n_1 \cdot \pi + n_2 \cdot \sqrt{2} \mid n_1, n_2 \in \mathbb{N}\} \rvert = \lvert \mathbb{N} \rvert$, and to be honest I'm quite lost as I can't find a bijective function from one set to the other. I've thought of using the Cantor–Schröder–Bernstein theorem but haven't even been able to find injective functions between the sets.
Any help with proving the equality will be much appreciated. Thanks in advance!
$\begingroup$
$\endgroup$
2
-
$\begingroup$ As long as you are happy with $\Bbb N\times\Bbb N\cong\Bbb N$, the rational (and indeed algebraic) independence of $\pi,\sqrt2$ allow you to think of it in those terms $\endgroup$– FShrikeJul 29, 2022 at 22:54
-
$\begingroup$ Hint: Start by finding a mapping between your set and pairs of natural numbers. This part should be easy. Then use $|ℕ^2| = |ℕ|$. $\endgroup$– DanJul 29, 2022 at 23:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Well, the cardinality is at least $\mid \Bbb N\mid$, because you can just let $n_1=0$.
But, it's also at most $\mid\Bbb N\mid$. "Cantor's pairing function" does the trick. It shows $\mid \Bbb N×\Bbb N\mid=\mid \Bbb N\mid$.
My favorite way makes it utterly trivial. It shows any countable union of countable sets is countable. You put the elements in an (infinite) array. Then you start at the corner and then wind your way back and forth to enumerate them. It's a picture of Cantor's pairing function. 
To use Cantor-Schröder-Bernstein, you just need an injection from $\Bbb N×\Bbb N\hookrightarrow \Bbb N$. Let's write this one down: $$(l,m)\to1/2(l+m)(l+m+1)+m$$.
(It's a theorem (Fueter, Pólya) that this is the only quadratic pairing function. It's an open problem if there are other polynomial pairing functions.)
Another way to get the injection is to take a couple different primes $p,q$, and send $(l,m)$ to $p^lq^m$.
