Prove that .

I know of a fact that . The problem here is how I can go about establishing the bijective function non-trivially.

Thanks in advance.

Printable View

- Sep 8th 2011, 09:30 PMMarkeurCardinality Problem (2)
Prove that .

I know of a fact that . The problem here is how I can go about establishing the bijective function non-trivially.

Thanks in advance. - Sep 8th 2011, 10:55 PMDrexel28Re: Cardinality Problem (2)
If you know basic cardinal arithmetic you can say that , but this is really just what you're asking, isn't it? If you know there exists a bijection define by taking to the function given by . To see this is a bijection you must merely note that if then there exists some for which check then that . I leave it to you to show that this is a surjection.

Note, this extends to show that . - Sep 9th 2011, 08:11 AMMoeBleeRe: Cardinality Problem (2)
This is just an instance of the more general theorem:

If S and T are 1-1, then B^S and B^T are 1-1.

I would just prove that more general result.

Or are you asking how to prove that N and NxN are 1-1?

Do you have the fundamental theorem of arithmetic at your disposal? If so, it's easy to get an injection form NxN into N. If not, then there are other ways too.