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.  

4 Answers | Add Yours

degeneratecircle's profile pic

degeneratecircle | High School Teacher | (Level 2) Associate Educator

Posted on

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.

Sources:
degeneratecircle's profile pic

degeneratecircle | High School Teacher | (Level 2) Associate Educator

Posted on

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.

Sources:
mmora50's profile pic

mmora50 | Student, Undergraduate | (Level 2) eNoter

Posted on

Great explanation!!! Thanks a lot!!!

mmora50's profile pic

mmora50 | Student, Undergraduate | (Level 2) eNoter

Posted on

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.

 

We’ve answered 318,963 questions. We can answer yours, too.

Ask a question