# Proof NxN is countably infinite?Watch

#1
I am working on this question.

1) Prove that is countably infinite.

Here is what I have done so far, I think I need to show that the cardinality of a bijection from .

So I wrote out the first few terms of like so

It then became clear that if I delete then then then then then then then then and continue in this fashion then I can establish a bijection labeling the first deleted element as the second as 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 to ? 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
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
3 years ago
#3
(Original post by alex2100x)
I am working on this question.

1) Prove that is countably infinite.

Here is what I have done so far, I think I need to show that the cardinality of a bijection from .

So I wrote out the first few terms of like so

It then became clear that if I delete then then then then then then then then and continue in this fashion then I can establish a bijection labeling the first deleted element as the second as 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 to ? 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
X

new posts

Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### University open days

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

### Poll

Join the discussion

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