Question from a Texan Textbook

Deary, deary me...

Discuss the language of the universe.

Moderators: Calilasseia, ADParker

Re: Question from a Texan Textbook

#141  Postby Newmark » Apr 27, 2016 9:37 am

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! :grin:

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! :cheers:
User avatar
Posts: 365
Age: 41

Sweden (se)
Print view this post

Ads by Google

Re: Question from a Texan Textbook

#142  Postby VazScep » Apr 27, 2016 10:14 am

Newmark wrote:
VazScep wrote:
Newmark wrote:Given your experiences with functions as outlined above, I'd say that the most basic illustration of a one-to-one correspondence is y = f(x).
You mean "y = x".

Well, yes, that would be more correct. I used the notation from LjSpike's post as I got lost in trying to explain other things. Had I stopped to think for a bit, I would have described the function below as f(n)=2*n and used f to describe the relationship between x and y by saying that y=f(x). As currently written, y=f(2*x), it almost looks a bit like I'm trying to do lambda calculus...
No shame in that, given that Church only invented lambda calculus as a foundation for maths where functions were the privileged concept. Lambda calculus notation is basically used in ordinary maths, but instead of \lambda x. ..., you write x \mapsto ....

Typical convention in maths is to say: let f be a function in R \rightarrow R such that f(x) = x^2. You then avoid all mention of xs and ys, save that you might say {(x,y) : y = f(x)} is the graph of f.

I wish this was the way it was taught from day 1. Kids learn about functions early on now in computer science and they should be shown the connection. That way, they won't get into the sloppy notions of dependent versus independent variables and equations versus identities, but instead learn that all variables must be bound, whether universally, existentially, by function abstraction, by set comprehension (or list comprehension for programmers), by a differential operator or an integral sign (don't get me started on that latter source of endless abuse).

There is no such thing as a dependent variable. Dependent values are JUST functions.

This is not stuff I wanted to get across to LjSpike lest it sow confusion. But it seems you did a bang up job anyway despite my nitpicking.
Here we go again. First, we discover recursion.
Posts: 4590

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#143  Postby Evolving » Apr 27, 2016 10:29 am

VazScep wrote:... the sloppy notions of dependent versus independent variables and equations versus identities...

...There is no such thing as a dependent variable...


la la la I can't hear you
How extremely stupid not to have thought of that - T.H. Huxley
User avatar
Name: Serafina Pekkala
Posts: 11993

Country: Luxembourg
Luxembourg (lu)
Print view this post

Re: Question from a Texan Textbook

#144  Postby Veida » Apr 27, 2016 11:39 am

It might be that you need to skip some of the coordinates in the cantor pairing process, for example if you're matching naturals and fractions. Then, 1/2 is equal to 2/4, so you need to skip the pair (2,4) when you get to it. Otherwise the same fraction gets mapped to several different naturals.
Posts: 852

Sweden (se)
Print view this post


Return to Mathematics

Who is online

Users viewing this topic: No registered users and 1 guest