Page 1 of 2 [ 26 posts ]  Go to page 1, 2  Next

MCalavera
Veteran
Veteran

User avatar

Joined: 15 Dec 2010
Gender: Male
Posts: 5,442

08 Feb 2011, 5:50 am

How is that possible?

I thought that if something's infinite, then it has no limits and, thus, no defined size. Yet, in mathematics, this is such a thing as one infinite set being greater than another infinite set. But I don't get it. If one set has an infinite number of elements, the any other set with an infinite number of elements should have an equal cardinality to the first set.

So where am I going wrong here?



Biokinetica
Toucan
Toucan

User avatar

Joined: 8 Dec 2010
Age: 32
Gender: Male
Posts: 266
Location: Vulcan

08 Feb 2011, 6:05 am

Don't know exactly how this was explained to you, but the only way this can be "possible" is if you sample each at the same point in time where the iterator for one is older than the other. The biggest thing to take away from infinity is that it's a description of the way something else increases (or decreases), not an actual number.



Tsela
Yellow-bellied Woodpecker
Yellow-bellied Woodpecker

User avatar

Joined: 3 Jan 2011
Age: 44
Gender: Male
Posts: 70

08 Feb 2011, 6:46 am

It's actually quite simple. "Infinite" is not a simple thing, and indeed an infinite set may not have the same cardinality as another infinite set. How we compare sets is by trying to find a bijection, i.e. a one-to-one correspondence between their elements. If we can find one, the sets have the same amount of elements, and thus the same cardinality. If we can't, then they don't. And as it happens, this definition is valid for infinite sets as well.

Let's start simply with N, the set of natural integers (including 0), and Z, the set of negative and positive integers, including 0. Is there a bijection that connects each element of N to each element of Z? Well, there is. Take the following correspondences:
0 of Z -> 0 of N
negative number of Z -> 2 times absolute value of that number
positive number of Z -> 2 times that number - 1
This is a bijection between Z and N, i.e. it connects 1 element of Z to 1 element of N and vice-versa, and it connects all elements of Z to all elements of N, without missing a single one (it doesn't matter that they are infinite sets, as long as it's a bijection we know it's true). Because of this, and only because of this, we can say that Z has the same cardinality as N (we call Z a countable infinite set).
We can do that with Q, the infinite set of rational numbers (fractions of integers) as well. It's also a countable infinite set.

However, this breaks down when we try to create a correspondence between the elements of N and the elements of R, the real numbers. Whatever we try, there just doesn't exist a bijection between N and R. That's because between any two elements of R, there is always an infinite amount of elements of R, while between any two elements of N there is only a finite amount of elements of N. Because of this property, it's just impossible to find a one-to-one correspondence between all the elements of N and all the elements of R. You'll always miss elements of R.
So N and R are both infinite sets, but R definitely has more elements than N (you can connect all the elements of N to elements of R, but not do the opposite, so R has to have more elements), and thus a greater cardinality. R is called an uncountable infinite set.

The notion of correspondences, or more exactly bijections, is vital to understand the notion of the cardinality of infinite sets. Common sense like "two sets are infinite so they must have the same number of elements" is just plain wrong: there are more than one kind of infinity.

Note that there are also more than two kinds of infinity. The set of functions from R to R, for instance, has been proven to be of an even higher cardinality than R itself, i.e. there are more functions from R to R than there are real numbers.



ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 84
Gender: Male
Posts: 31,502
Location: New Jersey

08 Feb 2011, 7:18 am

MCalavera wrote:
How is that possible?

I thought that if something's infinite, then it has no limits and, thus, no defined size. Yet, in mathematics, this is such a thing as one infinite set being greater than another infinite set. But I don't get it. If one set has an infinite number of elements, the any other set with an infinite number of elements should have an equal cardinality to the first set.

So where am I going wrong here?



Look up Theory of Transfinite Numbers based on G. Cantor's Set Theory There is an infinite hierarchy of infinite cardinalities and ordinalities. For starters, the set of integers (which is an infinite set) is a lesser infinity than the set of real numbers.

See http://en.wikipedia.org/wiki/Transfinite_number

ruveyn



naturalplastic
Veteran
Veteran

User avatar

Joined: 26 Aug 2010
Age: 66
Gender: Male
Posts: 25,362
Location: temperate zone

08 Feb 2011, 12:09 pm

One simple example than even I can understand is this difference between a "countable infinity" and an "uncountable infinity".

The number of all integers is infinite, but atleast you make a start at counting them ( 1,2,3,4,...).

The infinite number of all odd numbers is the same infinity as the infinity all integers despite the fact the odd numbers are a subset of all integers ( you might think there are more integers than odd integers but no they are the same size infinity).

But the number of ALL real numbers ( not just integers) is an UNcountable infinity.
This is because you cant count 'em. What is the first number after zero? One? One half? One over one billion? There is always a smaller fraction so it is impossible to determine what the first number after zero is. So they cant be counted in an ordinal way as integers are. So the number of all numbers is a bigger infinity than the infinity of all integers because it is an uncountable infinity.
Similarly the number of all possible points on a line is also an uncountable infinity.

Back in the fourties when George Gamow wrote the book I read in the sixties as a child called "one, two, three,..Inifinity" mathematicians had decreed that there was also a third, even bigger infinity than the two above.

An example of this third kind of infinity is the number of all possible of curves that a line can make. Thats bigger than both the infinity of all integers, and the infinity of all points on a line ( or the infinity of all numbers), but why its considered bigger Ive forgotten.



ryan93
Veteran
Veteran

User avatar

Joined: 15 Apr 2009
Age: 28
Gender: Male
Posts: 2,315
Location: Galway, Ireland

08 Feb 2011, 4:31 pm

Is the way that I visualize it correct?

If there is an n x n plane, and in each 1 x 1 sample of the plane there is one A and two B. If n is infinite, then there is a larger infinite of B to A.


_________________
The scientist only imposes two things, namely truth and sincerity, imposes them upon himself and upon other scientists - Erwin Schrodinger

Member of the WP Strident Atheists


Tollorin
Veteran
Veteran

User avatar

Joined: 14 Jun 2009
Age: 39
Gender: Male
Posts: 3,178
Location: Sherbrooke, Québec, Canada

08 Feb 2011, 5:28 pm

Imagine that the Universe is infinite... (It may be.) In any lenghty portion of the Universe there is more stars than galaxy (A galaxy count billions of stars after all.). Same thing in a infinte Universe, even though the number of stars and galaxys is then both infinte, there is still more stars than galaxy; A bigger infinite.



ryan93
Veteran
Veteran

User avatar

Joined: 15 Apr 2009
Age: 28
Gender: Male
Posts: 2,315
Location: Galway, Ireland

08 Feb 2011, 5:37 pm

If that is true, then the notation is strange. Why not let 2 x ∞ = 2∞? It would reflect that infinities can be in ratios.


_________________
The scientist only imposes two things, namely truth and sincerity, imposes them upon himself and upon other scientists - Erwin Schrodinger

Member of the WP Strident Atheists


Orwell
Veteran
Veteran

User avatar

Joined: 8 Aug 2007
Age: 31
Gender: Male
Posts: 12,518
Location: Room 101

08 Feb 2011, 5:57 pm

ryan93 wrote:
Is the way that I visualize it correct?

If there is an n x n plane, and in each 1 x 1 sample of the plane there is one A and two B. If n is infinite, then there is a larger infinite of B to A.

No, that is not correct. Both of those are still countably infinite.

The number of positive integers (1, 2, 3, ...) is exactly the same as the number of rational numbers (p/q where p, q are integers, either positive or negative). It is also the same as the number of ordered pairs of integers (eg points in the n x n plane).


_________________
WAR IS PEACE
FREEDOM IS SLAVERY
IGNORANCE IS STRENGTH


ryan93
Veteran
Veteran

User avatar

Joined: 15 Apr 2009
Age: 28
Gender: Male
Posts: 2,315
Location: Galway, Ireland

08 Feb 2011, 6:31 pm

Quote:
No, that is not correct. Both of those are still countably infinite.

The number of positive integers (1, 2, 3, ...) is exactly the same as the number of rational numbers (p/q where p, q are integers, either positive or negative). It is also the same as the number of ordered pairs of integers (eg points in the n x n plane).


Makes sense, I have "God Created the Integers" sitting on my shelf, so I'll see if I can make it past Boole and move of to Cantor.


_________________
The scientist only imposes two things, namely truth and sincerity, imposes them upon himself and upon other scientists - Erwin Schrodinger

Member of the WP Strident Atheists


soulecho
Blue Jay
Blue Jay

User avatar

Joined: 27 Jul 2010
Age: 44
Gender: Female
Posts: 78
Location: Niagara Falls

08 Feb 2011, 6:49 pm

And to make it even more confusing, the set of numbers on the interval [0,1] has the exact same cardinality as R. :twisted:



ryan93
Veteran
Veteran

User avatar

Joined: 15 Apr 2009
Age: 28
Gender: Male
Posts: 2,315
Location: Galway, Ireland

08 Feb 2011, 7:41 pm

well, in light of what Orwell said that makes sense :)


_________________
The scientist only imposes two things, namely truth and sincerity, imposes them upon himself and upon other scientists - Erwin Schrodinger

Member of the WP Strident Atheists


Orwell
Veteran
Veteran

User avatar

Joined: 8 Aug 2007
Age: 31
Gender: Male
Posts: 12,518
Location: Room 101

08 Feb 2011, 8:20 pm

ryan93 wrote:
Makes sense, I have "God Created the Integers" sitting on my shelf, so I'll see if I can make it past Boole and move of to Cantor.

I have not read that book, but I instinctively distrust anything which attempts to popularize a detailed and technical subject. You would likely be better educated (but far worse entertained) by a textbook. Topology by Munkres has a pretty decent treatment of these concepts.

soulecho wrote:
And to make it even more confusing, the set of numbers on the interval [0,1] has the exact same cardinality as R.

And the set of numbers which lie on the unit circle (x^2+y^2=1) has greater cardinality than the entire real line.


_________________
WAR IS PEACE
FREEDOM IS SLAVERY
IGNORANCE IS STRENGTH


Tsela
Yellow-bellied Woodpecker
Yellow-bellied Woodpecker

User avatar

Joined: 3 Jan 2011
Age: 44
Gender: Male
Posts: 70

09 Feb 2011, 3:32 am

naturalplastic wrote:
One simple example than even I can understand is this difference between a "countable infinity" and an "uncountable infinity".

The number of all integers is infinite, but atleast you make a start at counting them ( 1,2,3,4,...).

The infinite number of all odd numbers is the same infinity as the infinity all integers despite the fact the odd numbers are a subset of all integers ( you might think there are more integers than odd integers but no they are the same size infinity).

But the number of ALL real numbers ( not just integers) is an UNcountable infinity.
This is because you cant count 'em. What is the first number after zero? One? One half? One over one billion? There is always a smaller fraction so it is impossible to determine what the first number after zero is. So they cant be counted in an ordinal way as integers are. So the number of all numbers is a bigger infinity than the infinity of all integers because it is an uncountable infinity.
Similarly the number of all possible points on a line is also an uncountable infinity.

Back in the fourties when George Gamow wrote the book I read in the sixties as a child called "one, two, three,..Inifinity" mathematicians had decreed that there was also a third, even bigger infinity than the two above.

An example of this third kind of infinity is the number of all possible of curves that a line can make. Thats bigger than both the infinity of all integers, and the infinity of all points on a line ( or the infinity of all numbers), but why its considered bigger Ive forgotten.


Because you can't create a bijection between R (the set of real numbers) and R^R (the set of functions from R to R, what you call "all possible curves that a line can make"). You can trivially make a mapping (also called injective function) between R and R^R, i.e. you can prove that for each element of R, you can associate an element of R^R (take for instance the function that takes a value a of R and returns the function f(x)=a). But you can't do the opposite, i.e. associate every element of R^R to one (and only one) element of R. In other words, R^R has more elements than R, and thus is a bigger infinity.

The only mathematically correct way to talk about cardinality of sets (including that of infinite sets) is through bijections (counting elements is just a special case that is usable only for finite sets). If there is a bijection between two sets, they have the same cardinality. If not, they don't, and that is true of infinite sets too. And you can talk about which set is bigger than the other through the use of injections. If there exists an injective function from one set to the other, then the first set is smaller than the second set. And that is true of infinite sets as well.

See Cardinal Number on Wikipedia for more info. Check the links as well!



Tsela
Yellow-bellied Woodpecker
Yellow-bellied Woodpecker

User avatar

Joined: 3 Jan 2011
Age: 44
Gender: Male
Posts: 70

09 Feb 2011, 3:37 am

soulecho wrote:
And to make it even more confusing, the set of numbers on the interval [0,1] has the exact same cardinality as R. :twisted:


Even more confusing: the set of numbers on any interval of R, whatever its size, has the exact same cardinality as R itself! It's true however small that interval may be!
That's because R is continuous, i.e. between two elements of R there is always at least one other element of R that is strictly smaller than one and strictly bigger than the other.

R goes on infinitely not only with bigger and bigger numbers, but also with smaller and smaller ones. That's the main difference with N and Z.



ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 84
Gender: Male
Posts: 31,502
Location: New Jersey

09 Feb 2011, 6:44 am

Tsela wrote:
soulecho wrote:
And to make it even more confusing, the set of numbers on the interval [0,1] has the exact same cardinality as R. :twisted:


Even more confusing: the set of numbers on any interval of R, whatever its size, has the exact same cardinality as R itself! It's true however small that interval may be!
That's because R is continuous, i.e. between two elements of R there is always at least one other element of R that is strictly smaller than one and strictly bigger than the other.

R goes on infinitely not only with bigger and bigger numbers, but also with smaller and smaller ones. That's the main difference with N and Z.


The essence of an infinite set is that it can be put into one to one correspondence with a proper subset of itself. By the way the property of R you stated is not continuity but density. A linearly ordered set is dense if and only between two distinct points of the set a third point can be found between them. The set of rational numbers is dense but not compact. That is there are Cauchy sequences of rationals that do not converge to a rational and the rational numbers do not possess the Heine-Borel property (look it up on wiki). That property is called compactness -- what you called continuous.

ruveyn