Proof NxN is countably infinite? Watch

alex2100x
Badges: 2
Rep:
?
#1
Report Thread starter 3 years ago
#1
I am working on this question.

1) Prove that \displaystyle \mathbb{N} \times \mathbb{N} is countably infinite.

Here is what I have done so far, I think I need to show that the cardinality of \displaystyle \mathbb{N} \times \mathbb{N} = \aleph_0 \displaystyle \iff \exists a bijection from \displaystyle \mathbb{N}\rightarrow\mathbb{N} \times \mathbb{N}.

So I wrote out the first few terms of \displaystyle \mathbb{N}\times\mathbb{N} like so

\displaystyle \begin{matrix}(1,1) & (1,2) & (1,3) & ... \\ 

(2,1) & (2,2) & (2,3) & ... \\ 

(3,1) & (3,2) & (3,3) & ... \\ 

\vdots & \vdots & \vdots & \ddots\\    

\end{matrix}

It then became clear that if I delete \displaystyle (1,1) then \displaystyle (2,1) then \displaystyle (2,2) then \displaystyle (1,2) then \displaystyle (1,3) then \displaystyle (2,3) then \displaystyle (3,3) then \displaystyle (3,2) then \displaystyle (3,1)\displaystyle ... and continue in this fashion then I can establish a bijection \displaystyle \mathbb{N}\rightarrow\mathbb{N} \times \mathbb{N} labeling the first deleted element as \displaystyle 1 the second as \displaystyle 2 and so on. Thus showing that it is countably infinite.

My question is, is there a better way to show how you would assign the elements in \displaystyle \mathbb{N}\times\mathbb{N} to \displaystyle \mathbb{N} ? Is this a good approach and is it acceptable in a mathematical sense? It is my first time doing a question like this and I was wondering.

Thanks!
0
quote
reply
poorform
Badges: 9
Rep:
?
#2
Report 3 years ago
#2
I am far far far from being an expert in this but it looks okay to me, I'm not really sure whether there is a better way to set it out but the reasoning behind the cancelling makes sense to me but perhaps someone who is better on here will tell you any mistakes, I will be interested to see them.
0
quote
reply
DFranklin
Badges: 18
Rep:
?
#3
Report 3 years ago
#3
(Original post by alex2100x)
I am working on this question.

1) Prove that \displaystyle \mathbb{N} \times \mathbb{N} is countably infinite.

Here is what I have done so far, I think I need to show that the cardinality of \displaystyle \mathbb{N} \times \mathbb{N} = \aleph_0 \displaystyle \iff \exists a bijection from \displaystyle \mathbb{N}\rightarrow\mathbb{N} \times \mathbb{N}.

So I wrote out the first few terms of \displaystyle \mathbb{N}\times\mathbb{N} like so

\displaystyle \begin{matrix}(1,1) & (1,2) & (1,3) & ... \\ 

(2,1) & (2,2) & (2,3) & ... \\ 

(3,1) & (3,2) & (3,3) & ... \\ 

\vdots & \vdots & \vdots & \ddots\\    

\end{matrix}

It then became clear that if I delete \displaystyle (1,1) then \displaystyle (2,1) then \displaystyle (2,2) then \displaystyle (1,2) then \displaystyle (1,3) then \displaystyle (2,3) then \displaystyle (3,3) then \displaystyle (3,2) then \displaystyle (3,1)\displaystyle ... and continue in this fashion then I can establish a bijection \displaystyle \mathbb{N}\rightarrow\mathbb{N} \times \mathbb{N} labeling the first deleted element as \displaystyle 1 the second as \displaystyle 2 and so on. Thus showing that it is countably infinite.
It's not immediately clear what "and so on" means here (I expect it would be clearer if you did a hand drawn diagram).

My question is, is there a better way to show how you would assign the elements in \displaystyle \mathbb{N}\times\mathbb{N} to \displaystyle \mathbb{N} ? Is this a good approach and is it acceptable in a mathematical sense? It is my first time doing a question like this and I was wondering.[
For many of these questions, the "quick way" is to show there's an injection into N; this immediately establishes countability (and that N x N is infinite is obvious).

Finding an injection is easy; e.g. (a, b) -> 2^a 3^b is an injection due to uniqueness of prime factorization.

Thanks![/QUOTE]
0
quote
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of Lincoln
    Mini Open Day at the Brayford Campus Undergraduate
    Wed, 19 Dec '18
  • University of East Anglia
    UEA Mini Open Day Undergraduate
    Fri, 4 Jan '19
  • Bournemouth University
    Undergraduate Mini Open Day Undergraduate
    Wed, 9 Jan '19

Were you ever put in isolation at school?

Yes (281)
27.52%
No (740)
72.48%

Watched Threads

View All