On bijection of NxN to N

I still remember in my final exam of Discrete Mathematics I in Fasilkom. I have never come to teaching-assistant session at that time, so problems are problems. The lecture was also not so clear about the function (did he even teach that?)

So it comes to me that I have to prove that \mathbb{N} \times \mathbb{N} has the same cardinality. Because I really like writing with my hand, I wrote the answer as clearly as possible. I listed them diagonally, which honestly, I have to say this, was inspired from listing s-p-d-f in Chemistry (thank you Chemistry, but I still hate your high-school syllabus and presentation). I didn’t know about Cantor’s stuff back then. So, then I was not satisfied? How can I convince that it’s actually bijection (aside from taking diagonal lines to “hit” the numbers). I am interested in the formula to blast, so I found the formula:

f(m,n) = {m+n-1 \choose 2 }+m

which can be derived from simple counting arguments. But that’s only a formula! How then I know about the proof that it’s bijective? Should I prove it? Yes. I proved it in the exam (I almost cried now). Well, it’s not that hard because you know what to prove (strictly increasing, everyone hit) as you see the “diagonal-list”. Damn. What an overkill. But I’m satisfied even though I didn’t have time checking my answers on other problems.

I feel stupid now. Yes, first because I cared too much about the rigority (which is actually not needed). But, it’s interesting to know that there’s another beautiful bijection formula. What is that? Well, here’s the guy:

f(m,n)=2^{m-1}(2n-1).

Oh God, it’s beautiful right, that shiny little monster? I know you don’t even know what to say just because of it’s just too simple to be explained. Nah, eat that.

(Indeed, every positive integer can be represented with 2 to the something-non-negative times a positive odd number)

I also still remember I protested another lecturer how unfair the exam is. Such tedious problem is only worth of 10 marks.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s