How can be proved that: A = {n + m√2 | n,m € N} is (or is not) a countable set? - N is the set of the natural numbers. - n and m are natural numbers.Thanks in advance for your answers.  

Expert Answers
degeneratecircle eNotes educator| Certified Educator

Yes, the mapping `n+msqrt(2)->(n,m)` is one to one and onto `NNxxNN`. One thing I didn't explicitly mention is that the map is well-defined, that is, there is only one choice for each input. It's well-defined because of the irrationality of `sqrt(2)`. If `n+msqrt(2)=a+bsqrt(2)`, then solving for `sqrt(2)` shows that `m=b` and `n=a` (because otherwise `sqrt(2)` would be rational).

This is probably clearer if you consider a case where the map wouldn't be well-defined. If our set was `{n+msqrt(2) | n,m in RR}` and we want to map to `RRxxRR` using the same type of mapping, then would `0+1sqrt(2)` map to (0,1), or would it map to `(sqrt(2),0)` , since `0+1sqrt(2)=sqrt(2)+0sqrt(2)`? That wouldn't be a well-defined operation.

degeneratecircle eNotes educator| Certified Educator

It is countable and the proof depends on what you're allowed to assume. Can you use the fact that the Cartesian product of finitely many countable sets is countable? Because then any number of the form `n+msqrt(2)` where `n,m in NN` can obviously be represented by the ordered pair `(n,m) in NNxxNN`, which, being the Cartesian product of `NN` with itself, is countable by the theorem mentioned.

Or, you could show how to write the elements of your set in a list as follows (I'll say `0 in NN` here) :

`(0,0), (1,0), (0,1), (2,0), (1,1,), (0,2), (3,0), (2,1), (1,2), (0,3)`, etc. Do you see the pattern? First list all pairs with `n+m=0` , then `n+m=1` , and so on.

mmora50 | Student

Great explanation!!! Thanks a lot!!!

mmora50 | Student

Thanks a lot for your response.


I think the property you mention about the Cartesian product can be used. So, a bijection can be established between the value and (n,m), right? Please, confirm that is right. Having that bijection is a proof that A is countable.