Deary, deary me...
Moderators: Calilasseia, ADParker
VazScep wrote:I'll rephrase one of my earlier posts:
The enumerability of the rationals is easy to discover. The hard part is establishing that enumerability and its generalisation as one-one correspondences is a really big deal. Until then, you're wibbling.
Simple check: without the Cantor-Schroeder-Bernstein Theorem, would we have cared what Cantor had to say?
First, you should realise that these correspondences have nothing to do with ratios, or proportions, and that none of it generalises the sort of stuff you do in algebra with real numbers. This is discrete mathematics, a completely different branch of the subject, and set theory in particular. The theory was laid down towards the backend of the 19th century, and is now part of the basic vocabulary that mathematicians use to talk about an axiomatic notion called sets.LjSpike wrote:(If you have a solid explanation using terms which have a concrete value, to prove the infinities as equal, I'll give in).
VazScep wrote:First, you should realise that these correspondences have nothing to do with ratios, or proportions, and that none of it generalises the sort of stuff you do in algebra with real numbers. This is discrete mathematics, a completely different branch of the subject, and set theory in particular. The theory was laid down towards the backend of the 19th century, and is now part of the basic vocabulary that mathematicians use to talk about an axiomatic notion called sets.LjSpike wrote:(If you have a solid explanation using terms which have a concrete value, to prove the infinities as equal, I'll give in).
I suspect you haven't properly done functions yet at school, and knowing exactly what counts as a function is pretty important for getting into the subtleties of this stuff. But the basic idea is that a function is a rule which tells you how to go from one set of objects to another. It's like a function in programming, except all you're allowed to do is take an input and compute an output.
Some functions send two different inputs to the same output. Some functions send any two inputs to two different outputs. The latter are called "injective." Some functions can produce any output in the output set for a suitable input. Such functions are called "surjective." Functions which are both are called "bijective", or "one-one correspondences."
On these definitions, we say that the natural numbers are in one-one correspondence with the reals.
Why one-one correspondences are of interest is something you learn by studying set theory.
Shit. Yes. And I probably should avoid "in one-one correspondence" when I hadn't really defined that particular phrase.scott1328 wrote:VazScep wrote:First, you should realise that these correspondences have nothing to do with ratios, or proportions, and that none of it generalises the sort of stuff you do in algebra with real numbers. This is discrete mathematics, a completely different branch of the subject, and set theory in particular. The theory was laid down towards the backend of the 19th century, and is now part of the basic vocabulary that mathematicians use to talk about an axiomatic notion called sets.LjSpike wrote:(If you have a solid explanation using terms which have a concrete value, to prove the infinities as equal, I'll give in).
I suspect you haven't properly done functions yet at school, and knowing exactly what counts as a function is pretty important for getting into the subtleties of this stuff. But the basic idea is that a function is a rule which tells you how to go from one set of objects to another. It's like a function in programming, except all you're allowed to do is take an input and compute an output.
Some functions send two different inputs to the same output. Some functions send any two inputs to two different outputs. The latter are called "injective." Some functions can produce any output in the output set for a suitable input. Such functions are called "surjective." Functions which are both are called "bijective", or "one-one correspondences."
On these definitions, we say that the natural numbers are in one-one correspondence with the reals.
Why one-one correspondences are of interest is something you learn by studying set theory.
You meant to say rationals?
VazScep wrote:First, you should realise that these correspondences have nothing to do with ratios, or proportions, and that none of it generalises the sort of stuff you do in algebra with real numbers. This is discrete mathematics, a completely different branch of the subject, and set theory in particular. The theory was laid down towards the backend of the 19th century, and is now part of the basic vocabulary that mathematicians use to talk about an axiomatic notion called sets.LjSpike wrote:(If you have a solid explanation using terms which have a concrete value, to prove the infinities as equal, I'll give in).
I suspect you haven't properly done functions yet at school, and knowing exactly what counts as a function is pretty important for getting into the subtleties of this stuff. But the basic idea is that a function is a rule which tells you how to go from one set of objects to another. It's like a function in programming, except all you're allowed to do is take an input and compute an output.
Some functions send two different inputs to the same output. Some functions send any two inputs to two different outputs. The latter are called "injective." Some functions can produce any output in the output set for a suitable input. Such functions are called "surjective." Functions which are both are called "bijective", or "one-one correspondences."
On these definitions, we say that there is a one-one correspondence from the naturals to the rationals.
Why one-one correspondences are of interest is something you learn by studying set theory.
AwesomeLjSpike wrote:Your right to say we haven't done much on functions. The extent of functions is where we have a graph and we change y = f(x) to say y = 2f(x+1). Then as well, we have done f(x) = (lets just say) x^3, work out what f(x-2) is...
It'd be nice if you define one-to-one correspondence then, because It sounded like it was just being used as an alternative term to ratio (and I'd love to know if my ratio was correct ).
LjSpike wrote:Your right to say we haven't done much on functions. The extent of functions is where we have a graph and we change y = f(x) to say y = 2f(x+1). Then as well, we have done f(x) = (lets just say) x^3, work out what f(x-2) is...
It'd be nice if you define one-to-one correspondence then, because It sounded like it was just being used as an alternative term to ratio (and I'd love to know if my ratio was correct ).
You mean "y = x". Your notation is a bit borked throughout: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).
The function implied by y=2*x has inverse implied by y=x/2.E.g. y=f(2*x) is injective, so it has the inverse function x=g(y/2).
Newmark wrote:LjSpike wrote:Your right to say we haven't done much on functions. The extent of functions is where we have a graph and we change y = f(x) to say y = 2f(x+1). Then as well, we have done f(x) = (lets just say) x^3, work out what f(x-2) is...
It'd be nice if you define one-to-one correspondence then, because It sounded like it was just being used as an alternative term to ratio (and I'd love to know if my ratio was correct ).
(Note: You seem to be quite passionate about math, and I hate to stifle that, so please do protest if I come across as condescending. It's not my intention to be so now, but I know I can be arrogant at times...)
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). When you model it in a graph, you would draw it as a straight diagonal line, mapping each value on the X-axis to the corresponding value on the Y-axis. To clarify a few terms, the X-axis represents the domain of the function, i.e. the set of elements we use as "inputs" to the function. In a similar manner, the Y-axis represents the codomain of the function, i.e. the set of elements that are "outputs".
As you may know, a function can by definition only yield one output per input1. We can also reasonably conclude that the function y=f(x) is well-defined, i.e. that each element in its domain actually has a corresponding element in its codomain, since no elements are excluded by how we defined our function. This gives us the first piece of the one-to-one correspondence puzzle, as we now know that each and every element in the domain is mapped to one (and only one) element in the codomain. In the graph, this is illustrated by the fact that for each point on the X-axis, there is a corresponding point on our plotted line straight above, below, or on it.
So let's tackle the codomain. First of all, our function is injective, i.e. each element in its domain corresponds to a unique element in its codomain. One example of a function that isn't injective is y=f(x^2), since both x=1 and x=-1 yields y=1. You might have noticed that this property closely mirrors one of the fundamental definitions of a function that I outlined above; in fact, by being injective (and only if it is injective) a function also has exactly one inverse function2. We also have something that mirrors a function being well-defined: a function is surjective if each element in its codomain corresponds to (at least) one element in its domain. For example, the function y=f(x^2) isn't surjective if we use all the real numbers as its codomain; the negative numbers don't correspond to anything3. However, if we define our codomain as the positive reals (and 0), the function becomes surjective. A function that is both injective and surjective is bijective; a bijective function has an inverse function (due to being injective) that is well-defined (due to being surjective). In graph terms, this means that for each point on the Y-axis, we have one (and only one) point on our plotted line straight right of, left of, or on it. To return to y=f(x): it is clearly bijective as all y's have a corresponding x, and no y is the result of two different x's as input.
And this is our definition of "one-to-one correspondence": that there exists a bijective function between sets. Each element in the domain corresponds to exactly one element in the codomain, and each element in the codomain corresponds to exactly one element in the domain. By this, we can see that two sets are equinumerous, i.e. that they contain the same number of elements. This "size" of a set is called its cardinality, which will be important when we discuss infinities later.
But for now, let's leave the reals as they are somewhat cumbersome, and dive into set theory. I don't know how familiar you are with sets, but a short recap: a set is a collection of unique elements4. For example, we can have a set S with each integer from 1 to 3, which we could write as S={1, 2, 3}, i.e. a collection containing the elements "1", "2", and "3". Those elements are called the members of S. Now, if we define a set T={2, 3, 4}, we can see that it is a distinct set from S as they both contain elements the other does not. However, we can construct a function y=f(x+1) that has S as its domain and T as its codomain. If we examine f, we can see that its bijective; each element in each set is mapped to exactly one unique element in the other set. This one-to-one correspondence makes it impossible for one set to contain more elements than the other set, thus they have the same cardinality. In this case (since we are dealing with finite sets), we can simply count the number of elements in one set (its cardinality is 3) and conclude that is also the size of the other set.
Another useful definition is "subset": a subset S' of a set S is a set where each element in S' is a member of S. Furthermore, S' is a proper subset of S iff there exits an element of S that is not a member of S'.
Now consider the set of natural numbers, N, consisting of all positive integers5 (N={1, 2, 3, ...}). Since we can't count to infinity, the cardinality of this set has been defined as aleph-null. Let's compare it to another set M consisting of every integer larger than 1 (M={2, 3, 4, ...}) by defining a function y=f(x+1), where x is a member of N and y is a member of M. We can see that this function is a bijection by a simple proof of contradiction: is there any element in N that doesn't yield exactly one result when we input it into this function, and is there any element in M that doesn't correspond to exactly one element in N? By this, we can conclude that M is equinumerous to N, and thus have a cardinality of aleph-null. This answers the first "problem" with Hilbert's Grand Hotel: you can always move your guests to a room with a number one higher than the one they are currently residing in, and the room "1" will be free. Please note that this "paradox" is only something that is counter-intuitive rather than counter-factual; this is how we have defined our math to work.
Let's take another set L containing all non-negative even integers, L={0, 2, 4, ...}. We compare it to N by the function y=f(2*x) in the same manner as before. Yet again, we have a bijection, and N and L both have a cardinality of aleph-null. This is Hilbert's second problem, when a bus with an infinite number of new guest arrive at you full hotel with an infinite number of rooms. Move each current guest to the room with the double of their current number, and you've got an infinite amount of free rooms. Infinity times two is still... infinity. By (roughly) the same method, we can also conclude that there are as many integers (I={..., -2, -1, 0, 1, 2, ...}) as there are natural numbers...
Now things gets more tricky: an infinite number of buses each carrying an infinite number of passengers arrives and demand rooms. This corresponds to the relation between the natural numbers (N) and the rational numbers (Q). First, we can easily see that there can't be more natural numbers than rational numbers, since N is a (proper) subset of Q. Second, we can construct any6 rational number by taking an ordered pair of natural numbers to represent the numerator and the denominator. This scheme will yield several numbers that are the same (e.g. 1/1, 2/2, 3/3, etc.), but at least we know that all rationals will be present. However, using the Cantor pairing function, we can map a natural number to each of these ordered pairs, and thus we know that the rationals can be represented by a subset of the set of ordered pairs that we now know are of cardinality aleph-null. Thus, there cannot be more naturals than rationals, and there cannot be more rationals than naturals, so they must be equinumerous. It turns out that infinity times infinity is still infinity...
But one thing that you did get right is that infinity comes in different sizes7, just not that N and Q have cardinalities corresponding to different infinities. One example is the real numbers, which are of a provable larger infinity. Personally, I had quite a bit of problem with these things when I first encountered them at university, so I know from personal experience how wrong they can sound...
This is not to say that your concept of ratios (as far as I think I've understood them) is necessarily wrong or without merit, merely that you have extrapolated a few things about infinities without proper support. The closest thing to your "ratio" that I can think of is the field of computational complexity (computer science is what I studied), which concerns growth rates of functions and is used to estimate how effective an algorithm is with regard to e.g. memory and processor cycle usage. If you're into programming, I think you'd enjoy it!
1Therefore, any operation that yields more than one answer cannot be a function. E.g. the square root of 1 is both 1 and -1, thus the square root isn't usable as a proper function in and of itself.
2E.g. y=f(2*x) is injective, so it has the inverse function x=g(y/2).
3Well, they do correspond to imaginary numbers, but since they aren't part of our domain, we can ignore them.
4Also order doesn't matter, and a few other things, but those aren't important right now.
5It can be argued that 0 should be included too, but this definition is usable for now.
6positive. We should include the negative rationals too, but that can be done in an analogous fashion to the negative integers.
7About an infinity of them...
crank wrote:Happy B'Day kid. And it's a big one. [fucking youngster, he doesn't know how lucky he is. Back in the day, why, we ...]
Your notation is a bit borked throughout:The function implied by y=2*x has inverse implied by y=x/2.E.g. y=f(2*x) is injective, so it has the inverse function x=g(y/2).
The y =...x... way of talking about functions is all a bit sloppy, but I don't think they teach anything else at school.
Users viewing this topic: No registered users and 1 guest