Question from a Texan Textbook

Deary, deary me...

Discuss the language of the universe.

Moderators: Calilasseia, ADParker

Re: Question from a Texan Textbook

#121  Postby VazScep » Apr 23, 2016 6:07 pm

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?
Here we go again. First, we discover recursion.
VazScep
 
Posts: 4590

United Kingdom (uk)
Print view this post

Ads by Google


Re: Question from a Texan Textbook

#122  Postby scott1328 » Apr 23, 2016 7:48 pm

The following URL gives several examples of a bijective function that given any natural number N produces a rational number Q, or given any rational number Q produces a natural number N. This therefore demonstrates that the Rationals have the same cardinality as the Natural Numbers.

http://math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturals
User avatar
scott1328
 
Name: Some call me... Tim
Posts: 8695
Male

United States (us)
Print view this post

Re: Question from a Texan Textbook

#123  Postby VazScep » Apr 23, 2016 8:19 pm

That's cool, but it doesn't really help when someone comes along saying "I don't know much maffs: but I've got a bunch of ideas about infinity and stuff and I've got some notations to prove it!"
Here we go again. First, we discover recursion.
VazScep
 
Posts: 4590

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#124  Postby crank » Apr 23, 2016 9:10 pm

This isn't about this thread, just a comment in general. Sometimes these extreme DunningKruger types make me cringe a bit, feeling sorry for them, they can be so earnest, and have put a great deal of thought and effort into something, and it's like: eh, no. There is such a vast gulf evident between what they're thinking and even an elementary understanding of what they're trying to deal with, even a vague notion of an inkling of how vast the gulf is is way beyond their kin. I strive pretty hard to get at least an idea of how stupid and ignorant I am, it's an important skill to have. And I still fail to even get that right way too often.
“When you're born into this world, you're given a ticket to the freak show. If you're born in America you get a front row seat.”
-George Carlin, who died 2008. Ha, now we have human centipedes running the place
User avatar
crank
RS Donator
 
Name: Sick & Tired
Posts: 10413
Age: 5
Male

Country: 2nd miasma on the left
Pitcairn (pn)
Print view this post

Re: Question from a Texan Textbook

#125  Postby VazScep » Apr 24, 2016 6:06 am

Yeah, I'm mostly just bemused by it, and I sometimes wonder whether I'm spoiling posters' fun if they're all largely ignorant but still having an intense discussion in wibble.

It's different when we're being educated formally. There we mostly shut up and pay attention. There are going to be tests at the end, and the people running the course are the ones who best know how to pass them.
Here we go again. First, we discover recursion.
VazScep
 
Posts: 4590

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#126  Postby LjSpike » Apr 24, 2016 3:18 pm

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?


Thats all fine (and I've used that type of expression before in computer code here and there. It allows you to translate a flow diagram or over-length code into a nice compressed, yet still readable format as you don't need 3 or more statements).
However
integers < rationals
rationals !< integers
(! = not).

Hopefully fractions work here too.
[tex]\frac{i1*x =< y =< x*i2}{1 < x < infinity}[/tex]
where i1 (lower-end integer) and i2 (upper-end integers) are the edges of the range.

The pattern is linear, it does not change as it doesn't involve any powers (its simply counting up the sets of integers and rationals infinitely), so no matter how many integers you choose to check between, that function will portray each of the rationals in the range. (AKA, this pattern could (theoretically, though you need to represent infinities clearly) be represented as a simple nth term, without any powers)

To calculate the number of rationals in the range I reckon you'd do
[tex]((x*i2)-(x*i1))*infinity = n[/tex]
where n is the number of rationals in that range. Its still incredibly tricky to represent clearly, as it is a different infinity to the infinity of the rationals. I'd suggest representing it as whatever the first part of the equation ((x*i2)-(x*i1)) resulted in, in front of the infinity.

Then to extrapolate for infinite integers, you have the fact its a linear pattern, so you can multiply n by infinity.
Now if you chose to just represent n as infinity, you can easily represent this new ratio as infinity^2.

So even if n = total number of integers, n^2 must be larger, as the total number of integers isn't 0.

As far as going 'wibble' to others solutions goes. I'd say that the proof of the 1:1 relationship as its a infinity:infinity relationship is the biggest wibble in the thread, as the infinities are not equal. (If you have a solid explanation using terms which have a concrete value, to prove the infinities as equal, I'll give in).
LjSpike
 
Posts: 89
Age: 20
Male

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#127  Postby scott1328 » Apr 24, 2016 3:28 pm

To LjSpike: how do you judge whether two finite sets are the same size?
User avatar
scott1328
 
Name: Some call me... Tim
Posts: 8695
Male

United States (us)
Print view this post

Ads by Google


Re: Question from a Texan Textbook

#128  Postby VazScep » Apr 24, 2016 4:19 pm

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).
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.

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.
Last edited by VazScep on Apr 24, 2016 9:49 pm, edited 1 time in total.
Here we go again. First, we discover recursion.
VazScep
 
Posts: 4590

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#129  Postby scott1328 » Apr 24, 2016 4:33 pm

VazScep wrote:
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).
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.

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?
User avatar
scott1328
 
Name: Some call me... Tim
Posts: 8695
Male

United States (us)
Print view this post

Re: Question from a Texan Textbook

#130  Postby VazScep » Apr 24, 2016 9:50 pm

scott1328 wrote:
VazScep wrote:
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).
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.

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?
Shit. Yes. And I probably should avoid "in one-one correspondence" when I hadn't really defined that particular phrase.
Here we go again. First, we discover recursion.
VazScep
 
Posts: 4590

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#131  Postby BWE » Apr 25, 2016 12:59 am

There is a funny relationship between abstracted quantification and the number line.
User avatar
BWE
 
Posts: 2498

Print view this post

Re: Question from a Texan Textbook

#132  Postby LjSpike » Apr 25, 2016 4:21 pm

VazScep wrote:
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).
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.

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.


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 :D).
LjSpike
 
Posts: 89
Age: 20
Male

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#133  Postby crank » Apr 25, 2016 4:28 pm

It's not at all a ratio. It's this, basically. ou have two piles of stuff. There is some rule that takes an object in one pile and matches it with one and only one in the other pile. This goes for every object in each pile, it's symmetric.
“When you're born into this world, you're given a ticket to the freak show. If you're born in America you get a front row seat.”
-George Carlin, who died 2008. Ha, now we have human centipedes running the place
User avatar
crank
RS Donator
 
Name: Sick & Tired
Posts: 10413
Age: 5
Male

Country: 2nd miasma on the left
Pitcairn (pn)
Print view this post

Re: Question from a Texan Textbook

#134  Postby VazScep » Apr 25, 2016 6:41 pm

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 :D).
Awesome :thumbup:

See, I moaned in some other thread about this sort of issue. On the face of it, it would seem to be cool if we could use intuitive sounding words for maths concepts. But then, people can be misled if they just go with their intuitive understanding and don't check that understanding against a formal definition. So I think it might be better to always use big scary, technical names for maths concepts, to remind readers to chuck their intuition and always stick to the formal definition. If I were following my advice here, I would insist on never saying "one-one correspondence", which you found misleading, and instead saying "bijection", which is probably completely opaque to you and forces you to ask "what the fuck is that?"

It's not a problem for experienced mathematicians, because we all know to check the formal definitions no matter how intuitive something sounds, and honestly, I'd rather be speaking in English than some pretentious Latinate technobabble. But that's the tension.

I kinda defined "one-one correspondence" above. To get an intuition (warning: don't rely on intuition), think about the functions you graph. For some of them, if you draw a horizontal line anywhere on the graph, you'll find that it hits the curve exactly once. Those graphs are graphs of functions we call bijections (or one-one correspondences). But functions are much more general than the stuff you can graph.

Defining a "function" isn't easy for me, since it's a foundational concept in maths. In some cases, the notion of a function is just this primitive axiomatic thing. The rough intuitive idea is that it's a black box machine that you feed an input and it spits out an output, but that intuition really doesn't tell you much about the way mathematicians use functions day-to-day. That's something you internalise as you learn more and higher mathematics, and by the time you've done so, you realise you've thrown intuition out the window and are now working in a completely new and weird conceptual space.

You'll find this out soon enough if you keep up your enthusiasm for the subject! There's several of us on this forum who are eternally in love with the subject and would happily try to indoctrinate you into the cult.
Here we go again. First, we discover recursion.
VazScep
 
Posts: 4590

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#135  Postby Newmark » Apr 26, 2016 1:01 pm

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 :D).


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

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...
User avatar
Newmark
 
Posts: 365
Age: 41
Male

Sweden (se)
Print view this post

Ads by Google


Re: Question from a Texan Textbook

#136  Postby VazScep » Apr 26, 2016 2:54 pm

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". Your notation is a bit borked throughout:

E.g. y=f(2*x) is injective, so it has the inverse function x=g(y/2).
The function implied by y=2*x has inverse implied by y=x/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.
Here we go again. First, we discover recursion.
VazScep
 
Posts: 4590

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#137  Postby LjSpike » Apr 26, 2016 5:01 pm

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 :D).


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

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...


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!

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.
LjSpike
 
Posts: 89
Age: 20
Male

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#138  Postby crank » Apr 26, 2016 5:05 pm

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 ...]
“When you're born into this world, you're given a ticket to the freak show. If you're born in America you get a front row seat.”
-George Carlin, who died 2008. Ha, now we have human centipedes running the place
User avatar
crank
RS Donator
 
Name: Sick & Tired
Posts: 10413
Age: 5
Male

Country: 2nd miasma on the left
Pitcairn (pn)
Print view this post

Re: Question from a Texan Textbook

#139  Postby LjSpike » Apr 26, 2016 5:09 pm

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 ...]

Thanks! :D
LjSpike
 
Posts: 89
Age: 20
Male

United Kingdom (uk)
Print view this post

Re: Question from a Texan Textbook

#140  Postby Newmark » Apr 27, 2016 9:36 am

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...

Your notation is a bit borked throughout:

E.g. y=f(2*x) is injective, so it has the inverse function x=g(y/2).
The function implied by y=2*x has inverse implied by y=x/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.


That is indeed the correct way to write the inverse function, yes. As for the sloppiness, it might indeed be what they teach these days, but I should know better. Thanks for clarifying it! :thumbup:
User avatar
Newmark
 
Posts: 365
Age: 41
Male

Sweden (se)
Print view this post

PreviousNext

Return to Mathematics

Who is online

Users viewing this topic: No registered users and 1 guest