The size of sets and infinities

[Mentallic]

The set of integers is smaller than the set of real numbers. This I understand through logic.
I've also heard that the set of irrationals is larger than the set of rationals. How is this so?
And so I'm guessing the set of reals is larger than both the set of rationals and irrationals since it's both those sets combined.

Here's where I'm even more confused. I've heard that the set of complex numbers is the same size as the set of real numbers. Now logic kicks in again and tells me that for every real number there are infinite complex numbers to go with it. So in a sense, whatever sized infinite the set of real numbers is, the complex numbers should be this size squared. This can be seen geometrically as well.

 

[Werg22]

You're touching upon a property of infinite sets: they are as large as some of their proper subsets. You have to be careful what it means for a set to be large than another: A is larger than B is there is a surjective map from A to B, but not one from B to A. A and B have the same cardinality if there is both a surjective map from A to B and one from B to A. A finite set is always larger than any of its proper subsets, but with infinite ones this fails. For example, the set of natural numbers is of the same size as the set of even numbers, or as you pointed out, the set of real numbers is of the same size as the set of complex numbers. For more info, read on set theory.

 

[CRGreathouse]

You can search for more information on this (paradoxical?) topic with the term "Dedekind-infinite".

 

[Gib Z]

Werg22, I think the condition is stronger, there must be a bijective map from A to B to conclude they are the same cardinality.

 

[Tac-Tics]

With finite sets, it's easy to count how many elements there are. Start with 0 as your running total. Identify an element, add one to your running total, and then remove that element. Repeat this until you reach the empty set. The size of your set is the final value of your running total.

With infinite sets, that procedure doesn't work. Take the integers. You can remove as many elements as you want, and your running total can grow as large as you want it to, and you'll still never remove all the elements. That's the definition of infinite!

So then we ask, are all infinite sets created equal?

This all depends on your choice of definitions, but the classic definition for the size (or "cardinality") of a set is given by Cantor. His definition tells you when two sets are equal in cardinality and when one is less than.

According to Cantor's definition:

Two sets have equal cardinality whenever there is a bijection between them. (A bijection is a one-to-one onto function). Another way of putting this is that you can "assign" (or "name" or "label") every object from one set with a unique object from the other.

For finite sets, this is the same as our intuitive notion of size. {1, 2, 3} has the same size as {"one", "two", "three"}, because we can define the bijection f(1) = "one; f(2) = "two"; f(3) = "three".

This definition also works for infinite sets, though. Take an infinitely large theater with an infinite number of seats with an infinite number of patrons. As long as the box office is well organized, they can assign a seat to each person and a person to each seat. The cardinality of seats and patrons is equal.

A concrete example of this is between Z and Z+. It would seem that Z contains "half" as many elements as Z+, because Z is a superset of Z+. But use your definitions! We can find a bijection like this:

f(0) = 1
f(1) = 2
f(-1) = 3
f(2) = 4
f(-2) = 5
...
f(n) = 2n when n > 0
f(n) = -2n+1 when n < 0

This is a bijection (hint: find the inverse of f to prove it).

So the cardinality of Z and Z+ is the same.

Shaving off a finite number of elements doesn't change a set's cardinality. So Z has the same cardinality as Z\{0} has the same cardinality as Z\{0, 1}, etc, etc. It's only when you take away an infinite number of elements that it's possible to change an infinite set's cardinality... and even then it isn't guaranteed (for example, there are infinite primes, but the set of composite numbers is still the same as that of all integers).

That's just the tip of the iceberg. You can show all sorts of weird things with this definition. R^1 has the same cardinality as R^2 has the same cardinality as R^n (for any integer n). We can show that the rationals and the integers are equal in size. We can show the reals are larger than both. We can show that functions from reals to reals outnumber all of them. We can build a "tower" of cardinalities, each one bigger than the rest.

Some help with intuition. It's weird at first, but most things we study in math have the same cardinality as either the integers or the reals. The set of all finite sequences of a kind of object has the same cardinality as the object. So there are just as many PAIRS of integers as there are integers. This is why there are as many rationals as integers -- because a rational is just a pair of integers. Similarly, that's why there are just as many points in R^2 as R^3.

Bottom line: "bigger than" is a bad word to use. It's not that hard to intuit a lot of properties of cardinalities, but you can't think of one set as bigger than another just because it has elements the other doesn't.

 

[Werg22]

Werg22, I think the condition is stronger, there must be a bijective map from A to B to conclude they are the same cardinality.

Right, although with AC, it's equivalent.