LjSpike wrote:Thats one really brilliant explanation of the concepts. I probably still couldn't answer the question, but I do know what sets, cardinality and correspondences (and to a greater extent functions) are now!

Glad to have been of help!

I however how 1 final question. Do you think you could explain a bit on how the cantor pairing process works. I looked through (some) of the wikipedia page, and although wikipedia is brilliant, it can sometimes give slightly baffling explanations.

I can try.

First, let's look at the actual function:

π(k1, k2) = ½(k1 + k2)(k1 + k2 + 1) + k2

We also define our domain to be the natural numbers N, so both k1 and k2 belong to {0, 1, 2, ...}

Now let's look at the picture from wiki:

You may notice that the pairings proceed along diagonal lines, from the X-axis up to the Y-axis. Each of these lines can be described as going through all coordinates that has the same sum. E.g. the third line goes through (2, 0), (1, 1), and (0, 2), all of which has a sum of two. This sum (or line number, if you wish) is what the (k1 + k2) part of the function represents. If we define w=(k1 + k2), we can simplify our function a bit more:

π(k1, k2) = ½w(w + 1) + k2

Another thing to notice is that each such diagonal goes through one more coordinate than the preceding diagonal, e.g. the third diagonal goes through the three points I wrote above, while the fourth diagonal goes through four. We can view this as a equilateral triangle: we've gone four steps each on the X- and Y-axis, and we have a diagonal that also goes four steps. Now, the total number of points we passed through in our diagonals can easily be summed up using the triangular number of any of the sides of the triangle. The triangle number t of n is t=½n(n+1), which hopefully seems familiar. Using this sum in our function lets us simplify it further:

π(k1, k2) = t + k2

This only leaves the last k2, which tells us how far along our current diagonal we have traversed. Together, this gives us a unique natural number that corresponds to each pair.

I hope this illuminates things a bit more. And have happy birthday!