I posted a very similar problem just yesterday, and yet I'm still struggling understanding these kinds of problems, so if anyone could suggest some kind of material I could read/watch to understand this better, I would be very grateful, I've been trying to solve this very simple problem since yesterday after posting my last question, watching youtube videos on functions, reading the material in my book I'm studying, reading material on the internet...

Youtube videos unfortunately cover very basic functions, I don't think I specifically struggle with functions, more than I'm struggling how to "construct" a function, and the material in my book only covers the basics as always with very few simple examples.

Anyways, here's the problem, like the title says, I need to determine the cardinality of $M$

$M = \{(x,y) \in \mathbb{R} \times \mathbb{R} \mid 2x + y \in \mathbb{N}$ and $x - 2y \in \mathbb{N} \}$

Now, I have a tip at the bottom of the problem (which means I must solve this problem using this tip), that goes like this :

Let's assume that $2x + y = m$ and $x-2y = n$ and "solve" a simple equation, which confused me even more. Also, I'm not allowed to use the Cantor-Bernstein-Schröder theorem.

Now, I think it's pretty obvious that the cardinality of $M$ is $\aleph_{0}$, because it "depends" on $\mathbb{N}$, and the set "ends", whenever $\mathbb{N}$ "ends".(Obviously they never really end), or at least that's what I intuitively think.

Now, I've seen this topic : What is the cardinality of $A=\{(a,b)\in \mathbb{R}\times \mathbb{R}\mid 2a+b\in \mathbb{N}\text{ and }a-2b\in \mathbb{N}\}$

But still can't quite grasp the idea, which is why I'm askin for material to read.

Any help would be appreciated.


  • 2
    $\begingroup$ To save on countless retags efforts. If you feel that both set theory tags fit your question, then only [elementary-set-theory] should be used. $\endgroup$ – Asaf Karagila Dec 27 '14 at 13:26
  • $\begingroup$ Got it, thanks. $\endgroup$ – PainKiller Dec 27 '14 at 13:27

Your intuition is accurate.

Following the hint, let $m=2x+y$ and $n=x-2y$. We know that $m$ and $n$ are natural numbers, and we’d like to use this information to say something about the possible values of $x$ and $y$. That’s reminiscent of a more familiar situation: if we actually had specific values for $m$ and $n$, we could solve those two equations for $x$ and $y$. We don’t have specific values for $m$ and $n$, but we do at least have some information about them, so it might be useful to solve for $x$ and $y$ anyway.

Subtracting twice the second equation from the first, we find that $m-2n=5y$. Adding twice the first to the second, we find that $2m+n=5x$. Thus, we have the solution

$$\left\{\begin{align*} x&=\frac15(2m+n)\\\\ y&=\frac15(m-2n)\;. \end{align*}\right.\tag{1}$$

We know that $m$ and $n$ are integers, so $2m+n$ and $m-2n$ are integers. Thus,

$$M\subseteq\left\{\left\langle\frac{k}5,\frac{\ell}5\right\rangle:\langle k,\ell\rangle\in\Bbb Z\times\Bbb Z\right\}\;.\tag{2}$$

I expect that you can show that the cardinality of the righthand set in $(2)$ is $\aleph_0$, so either $M$ is finite, or $|M|=\aleph_0$. And it’s not hard to show that $M$ is infinite, so $|M|=\aleph_0$.

That last step uses either the Cantor-Schröder-Bernstein theorem or the result that an infinite subset of a countable set must have cardinality $\aleph_0$. If you already have the latter result, then this argument works fine. If not, you’ll need a slightly different approach, but this at least confirms your intuition.

With a little more work we can see that $(1)$ defines a bijection between $M$ and $\Bbb N\times\Bbb N$. Let $\langle m,n\rangle\in\Bbb N\times\Bbb N$; we know that $m$ and $n$ determine a member $\langle x,y\rangle$ of $m$ by $(1)$, and we know that every member of $(1)$ can be produced in this way, so $(1)$ defines a surjection from $\Bbb N\times\Bbb N$ to $M$. Now suppose that $\langle m',n'\rangle\in\Bbb N\times\Bbb N$ as well, and that $x'=\frac15(2m'+n')$ and $y'=\frac15(m'-2n')$. It’s not hard to show that if $\langle x,y\rangle=\langle x',y'\rangle$, then $\langle m,n\rangle=\langle m',n'\rangle$: $$m'=2x'+y'=2x+y=m\;,$$ and similarly $$n'=x'-2y'=x-2y=n\;.$$ Thus, $(1)$ does indeed define a bijection between $\Bbb N\times\Bbb N$ and $M$.

  • $\begingroup$ A very detailed explanation, thanks a lot! $\endgroup$ – PainKiller Dec 28 '14 at 10:26
  • $\begingroup$ @PainKiller: You're very welcome! $\endgroup$ – Brian M. Scott Dec 28 '14 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.