Infinite Sets

[lpetrich]

Our understanding of the mathematics of infinite sets owes a lot to Georg Cantor's work in the late 19th century. But it was controversial back then and into the early 20th century, though it is not very controversial now. It was controversial because some mathematicians argued that some arguments involved infinite-set proofs are illegitimate, and even that there is no such thing as an infinite set. Mathematicians like Leopold Kronecker, a contemporary of Georg Cantor.

But that aside, I will get to the issue of cardinalities or sizes of sets. That is the count of how many elements a set has, and for set A, it is |A| or card(A). Two sets have the same cardinality / size / element count if there exists a bijection between them. A bijection? For set A to set B, a mapping gets these names if it gets these properties:

• Injection (one-to-one): different elements of A map onto different elements of B
• Surjection (onto): every element of B has at least one element of A that maps onto it
• Bijection (one-to-one correspondence): both injection and surjection. Every element of B gets one and only one element of A mapped onto it.

For a finite set A, |A| is a nonnegative integer, and for the empty set {}, |{}| = 0.

Size equality satisfies the axioms of equality: reflexivity: x = x, symmetry: x = y gives y = x, and transitivity: x = y and y = z give x = z.


Let's do some arithmetic on cardinalities, and do it with set theory. If A is a subset of B, A <= B, then |A| <= |B|. If A is a proper subset of B, then |A| < |B| is always true only for finite sets. For infinite sets, one can choose a proper subset A where |A| = |B|. That may even be interpreted as a defining property of infinite sets.

Addition: if A and B are disjoint (A intersect B = {}), then |A union B| = |A| + |B|

Multiplication: |all ordered pairs (a,b) where a is in A and b in B| = |A| * |B|

One can get Peano's axioms out of set theory. To get those axioms' representations of numbers, one defines "0" as the empty set, {}, and the successor operation S(A) = A union {A}. Repeating the successor operation gives a unary or base-1 representation of the nonnegative integers, and applying it to this "0" gives
{}, {{}}, {{},{{}}}, {{},{{}},{{},{{}}}}, ...


One can easily show that these set-theory nonnegative integers and their operations have all the properties that one would expect -- commutative, associative, distributive, identities, ...

 

[GenesisNemesis]

I've read that Cantor proved that one infinity can be bigger than another infinity. Is that true?

 

[lpetrich]

One can also define exponentiation with set theory. To do that, we start with finding the square of some cardinality / set size:

|(a,b) for all a,b in A| = |A| * |A| = |A|^2
Likewise, for larger tuples,
|(a,b,c) for all a,b,c in A| = |A|^3
|(a,b,c,d) for all a,b,c,d in A| = |A|^4

In general,
|(a1,a2,...,a) for all a1,a2,...,a in A| = |A|^n
for nonnegative integer n. I say nonnegative, because for n = 0, one gets the empty tuple (), and the set of it has size 1.

Let us see if we can generalize it. A tuple (a1,a2,...,a) can be interpreted as a function f that reduces some component for some index value: f(1) = a1, f(2) = a2, ..., f(i) = a(i), ..., f = a. This function accepts 1,2 , ..., n, and we can generalize that to arbitrary sets. Thus,

|all functions f(B) -> A| = |A|^|B|

where f(B) -> A is shorthand for f(b) = a for all b in B and some a in A.


Let us consider an interesting case: the power set of a set, the set of all that set's subsets. Each subset can be interpreted as a function that takes that set's elements and returns true or false, depending on whether that element is in the subset or not. Thus, for a two-element set {a,b}, the subsets have functions
{} -- f(a) = false, f(b) = false
{a} -- f(a) = true, f(b) = false
{b} -- f(a) = false, f(b) = true
[a,b} -- f(a) = true, f(b) = true

Since |{false,true}| = 2, |PowerSet(A)| = 2^|A|


Let us consider |PowerSet(A)| and whether it is equal to |A|. We try to find a bijection between elements of A and subsets of A. Let us consider a set of "normal" subsets N, "normal" meaning that its elements x are not contained in their associated subsets X. Mapped onto it is an element of A, which I will call n. If n is in N, then by the definition of N, n must not be in N, while if n is not in N, then N must contain the element that is mapped onto N, that is, n. This contradiction proves that no bijection exists between A and PowerSet(A).

Since all a in A have a bijection with the {a} in PowerSet(A), we have |A| <= |PowerSet(A)|. But the previous result shows that |A| != |PowerSet(A)|. This means that |A| < |PowerSet(A)|.

Thus, for every set, one can construct a larger set from it.


A similar sort of set is the set of all permutations of a sequence, equivalent to the set of all self-bijections of a set. For {a,b}:
{a->a,b->b} and {a->b,b->a}

For set A, this set, Permut(A) satisfies |Permut(A)| = |A| ! for finite A. Meaning that |Permut(A)| > |A| for |A| > 2. In fact, |Permut(A)| > 2^|A| for |A| > 3.

elementary set theory - What is the largest set for which its set of self bijections is countable? - Mathematics Stack Exchange states that, for infinite sets,

2^|A| <= |Permut(A)| <= |A|^|A|

One would prove it by using proper subsets, but I haven't been very successful in that.

 

[lpetrich]

I've read that Cantor proved that one infinity can be bigger than another infinity. Is that true?

That is indeed correct.

That follows from the size of a set always being smaller than the size of its power set, the set of all subsets of that set. Meaning that for every set, there a larger one. That holds for infinite sets as well as for finite sets, so some infinities will be bigger than other infinities.

 

[Kharakov]

No he didn't. It's just an interesting troll by mathematicians.

The power set of a set doesn't have a bijection with the set in most cases, this doesn't mean that the power set has more elements- it just means mapping them one to one is not possible.

Infinite elements= infinite elements. They don't have a set size.

 

[lpetrich]

Infinite elements= infinite elements. They don't have a set size.

So are you claiming that there is no such thing as an infinite set? That the only sets are finite ones?

What makes a difference here?

 

[Derec]

I've read that Cantor proved that one infinity can be bigger than another infinity. Is that true?

Yes. Think of the set of all natural numbers and then a set of all even numbers. Both are infinite, but for every even number, there are two natural numbers.

There is an old math puzzle (it's Hilbert's Grand Hotel Paradox actually, and it is from 1924) about a hotel with infinitely many rooms which is full. A customer arrives. How do you get him a room? Simple. You move everybody from room n to room n+1 and give the new guy the room 1.
Then an infinite bus comes along. What does the poor guy at the front desk do? Simple! Just move every existing guest from room n to 2n and fit the new guests into the infinite number of odd-numbered rooms that are now vacant.

Btw. that hotel's infinity pool is less deceptively named than regular infinity pools ...

 

[lpetrich]

Now for what sizes of infinite sets there are. The smallest one is aleph-null (A-0), the size of the set of all positive integers. Sets with that size are called countably infinite or just plain countable. Sets with larger infinities as their sizes are called uncountable.

Aleph Null- smallest infinity? : askmath has a proof that there is no smaller one:

In order for there to exist an infinite cardinal number less than aleph null, there must exist an infinite subset of the natural numbers that is strictly smaller than the set of natural numbers. To prove this, we would need to show that no bijection exists between the natural numbers and its carefully chosen infinite subset. A properly of natural numbers to consider is their countability and ordering. This property extends to all subsets of the natural numbers. The nth element of the natural numbers can be paired with the nth element of its infinite subset.

Let's see what sets have size A-0. Starting with the positive integers, N+:
1 2 3 4 5 ...

The nonnegative integers, N:
0 1 2 3 4 ...

The integers, Z:
0 1 -1 2 -2 3 -3 4 -4 ...

For the rational numbers, Q, one needs to zigzag through them, but one can get a rational number for every positive integer. I'll do it for the positive rational numbers to avoid clutter:
1/1 . 2/1 1/2 . 3/1 2/2 1/3 . 4/1 3/2 2/3 1/4 ...

Since there are some duplicates, |Q| <= (A-0). But the rational numbers include the positive integers, so (A-0) <= |Q|. Thus, |Q| = (A-0).

The real algebraic numbers A require similar zigzagging, with coefficient values 0, +-1 for linear, 0, +-1, +2 for quadratic, 0, +-1, +-2, +-3 for cubic, ... allowing degeneration into lower-order equations as one goes. Each nth-order equation has n solutions, and we must also include each of them in our zigzagging. One gets both duplication and complex solutions, and it is evident that |A| <= (A-0), and also that (A-0) <= |A|. Thus, |A| = (A-0).

The computable numbers T require zigzagging through Turing-machine configurations that can calculate these numbers to arbitrary precision. These numbers include all the algebraic numbers, and also all the transcendental numbers that we use, numbers like e and pi. Here also, (A-0) <= |T| <= (A-0), thus giving |T| = (A-0).

The definable numbers D are those that can be defined with some finite-sized definition, and one zigzags through them also. These numbers include the computable numbers and such uncomputable numbers as Chaitin's constant. Here also, (A-0) <= |D| <= (A-0), giving |D| = (A-0).

One gets a hierarchy of subset inclusion:
N+ < N < Z < Q < A < T < D < R

All but the last one is countable, and Georg Cantor discovered that the real numbers R are uncountable. He showed that with his diagonal trick. Consider the real numbers between 0 and 1 inclusive. Suppose that they are countable. Make a list of them. Then change the first digit of the first one, the second digit of the second one, etc. That gives a number that was not in the list. This proves that the real numbers between 0 and 1 are uncountable, and thus that the real numbers in general are uncountable, since one can map from (0,1) to the entire real line with f(x) = (2x-1)/(x*(1-x)). There are the same number of numbers for a closed or semi-closed interval as for an open one, since one can push in an interval endpoint and cause an infinite chain reaction of smaller and smaller pushes. 1 -> 1/2, 1/2 -> 1/4, 1/4 -> 1/8, 1/8 ->1/16, etc.

The cardinality or size of the real numbers is called C for continuum, and this diagonal argument works for any number base B. Thus,
C = B^(A-0).

B can be 2, and by mapping 0 and 1 onto false and true, one shows that the real numbers between 0 and 1 match onto subsets of N+, the set of all the digit indices. Thus, C = |PowerSet(N+)|.

 

[Artemus]

I've read that Cantor proved that one infinity can be bigger than another infinity. Is that true?

Yes. Think of the set of all natural numbers and then a set of all even numbers. Both are infinite, but for every even number, there are two natural numbers.

These sets are actually same size since you can write a one-to-one mapping of the elements:

1 <--> 2
2 <--> 4
3 <--> 6
etc.

The natural numbers and rational numbers are also the same cardinality for the same reason. The set of irrational numbers is larger than the set of natural numbers, though.

 

[steve_bank]

Countable in this context sounds like a reassignment of meaning.

the set of all reals from 1 to 2 is bounded but infinite. I can add the set of 1..2 to 4..5. Operations can be derived on infinite sets.

But assigning an integer count to an infinite set appears mutually exclusive.

1,2,3.... can be called an infinite set, but that is a limitation of verbal language. Infinite and countable are mutually exclusive.
k = 1,2,3...

count = 1
k = 1
while forever{
k = k + 1
count = count + 1
?

Will the term count ever stop at a finite value?

 

[Kharakov]

The power set of a set doesn't have a bijection with the set in most cases, this doesn't mean that the power set has more elements- it just means mapping them one to one is not possible.

Infinite elements= infinite elements. They don't have a set size.

So are you claiming that there is no such thing as an infinite set? That the only sets are finite ones?

What makes a difference here?

Whether or not a power set has more elements than its root set, Mr. infinity to the infinitieth power.

It's like equating \(\lim_{x\to+\infty} \,\, x \, < \,x^2\) with \({+\infty}<\,{+\infty}^2\)...

 

[lpetrich]

Georg Cantor thus concluded that there is a series of infinite cardinalities or set sizes. He called the series aleph-0, aleph-1, aleph-2, ... or A-0, A-1, A-2, ...

He tried to prove that C = (A-1), the  Continuum hypothesis, but he failed. Later mathematicians proved that it is independent of a common axiomatic formulation of set theory, the Zermelo-Fraenkel axioms with the Axiom of Choice (ZFC). Both its truth and its falsehood are consistent with those axioms.


There is a sequence of infinite cardinals that can be constructed using power sets, however, the beth numbers, after the next letter in the Hebrew alphabet. Take a countable set, and then take power sets:
beth-0 = aleph-0
beth-(n+1) = 2^(beth-n)
beth-1 = C, the set size of the real numbers
beth-2 is the set of all functions of real numbers that give real numbers
Mathematicians have not been able to find any straightforward interpretation of beth-3 or any higher ones.

-

beth-0 = aleph-0
Countably infinite sets:
Positive integers N+, nonnegative integers N0, integers Z, rational numbers Q, real algebraic numbers A, computable numbers T, definable numbers D
"Natural numbers" N are variously defined as N+ (starting at 1) and N0 (starting at 0).

All n-tuples of positive integers (n finite) -- do zigzagging for pairs (2-tuples) and mathematical induction for the rest -- (A-0)^n = (A-0)
This means that all complex integers, complex rational numbers, complex algebraic numbers, complex computable numbers, and complex definable numbers have set size aleph-0, since they are pairs of their prototype numbers.

All finite sets of positive integers -- for each n, there are 2^n sets that may contain positive integers <= n.

All finite multisets of positive integers -- a multiset is like a set, but with some elements repeated. One can zigzag over maximum element and maximum multiplicity.

-

beth-1 = 2^(A-0) = C
The continuum cardinality:
Real numbers R, continuous intervals in the real numbers like R(0,1) -- can be closed, semiopen, and open. For n > 1, n^(A-0) = C
Irrational numbers, transcendental numbers, uncomputable numbers, undefinable numbers

All n-tuples of real numbers (n finite) -- one can prove that by mapping onto R(0,1) and then interleaving the numbers' trailing digits -- C^n = C.
All complex numbers, since they are pairs of real numbers.

All finite subsets of real numbers.

All sequences of positive integers (or rational numbers or other elements of countable sets) -- (A-0)^(A-0) = C
All sequences of real numbers -- C^(A-0) = C

All real analytic functions and real continuous functions of real numbers
All complex analytic functions of complex numbers

Continuous functions have f(x) = limit of n->oo for f(x) where limit of n->oo for x = x itself. Since every real number is the limit of some Cauchy sequence of rational numbers, and since there are C of such sequences, that means that there are C of such functions.

-

beth-2 = 2^C
All functions from real numbers to real numbers: C^C

 

[lpetrich]

Now for some explicit bijections.

 Galileo's paradox -- there are as many squares of positive integers as there are positive integers themselves: n <-> n^2.

Positive and nonnegative integers. For x in N+ (starting at 1) and y in N0 (starting at 0), x = y + 1 and y = x - 1.

Nonnegative integers and integers in general. For x in N+: if x is even, then one gets x/2, while if x is odd, then one gets -(x-1)/2-1.

Ordered pairs of positive integers: do zigzagging:
(1,1) . (2,1) (1,2) . (3,1) (2,2) (1,3) . (4,1) (3,2) (2,3) (1,4) ...
For (x,y), find z = x + y - 1, and then n = (1/2)z*(z+1) + (y-1)
One can then find x and y from any positive integer n.

N-tuples of positive integers in general (ordered sets of n of them). Use mathematical induction:
Tuple (x,y, ..., z) = ((x,y, ...), z).
If there is a bijection between (n-1)-tuples of N+ and N+ itself, then an n-tuple over N+ reduces to a pair over N+, and that has a bijection with N+.
So every n-tuple over N+ has a bijection with N+, and (A-0)^n = (A-0).


Taking on (A-0)^(A-0), that can be interpreted as all infinite sequences of rational numbers. That includes all the Cauchy sequences of rational numbers, and there is a surjection of these sequences into the real numbers, since a real number may be represented by more than one Cauchy sequence. Thus,
C <= |functions of N+ to Q| = |functions of countable set to countable set|

I don't know how to get the opposite inequality.


For a pair of real numbers, one maps them onto R(0,1) and finds a place-system decomposition:
a = 0.a1a2a3...
b = 0.b1b2b3...
One then constructs an interleaved number:
0.a1b1a2b2a3b3...

For an n-tuple, one repeats this operation for all the numbers, making a sequence of the numbers' first digits, then their second digits, etc. Thus, C^n = C.

For an infinite sequence of real numbers, one maps them onto R(0,1) and then recognizes that each number has a countable number of digits:
x(1): 0.x(1,1)x(1,2)x(1,3)...
x(2): 0.x(2,1)x(2,2)x(2,3)...
x(3): 0.x(3,1)x(3,2)x(3,3)...
So one constructs an interleaved number:
0.x(1,1)x(2,1)x(1,2)x(3,1)x(2,2)x(1,3)...
using the zigzagging for pairs of positive integers.

Thus, there is a bijection between the infinite sequences of real numbers and the real numbers themselves, and C^(A-0) = C.

For continuous function s, their continuity is
f(limit of x(k) for k to infinity) = limit of f(x(k)) for k to infinity

Thus, f(real value) = limit of f(rational values) where the rational values form a Cauchy sequence. Thus, one can find every continuous function by finding its values for the rational numbers. There are thus at most C^(A-0) of these functions, and thus at most C of them. Since there are at least C of such functions, since there are C of the constant-valued ones, there are thus exactly C of them.


I'm stumped by beth-2 and functions of real numbers to real numbers.

 

[lpetrich]

Now a bijection between finite subsets of N0 and N0 itself.

For each element of N0, do a binary-system decomposition, and then turn the 1's into trues and the 0's into falses. Apply this to which elements of N0 are present: k is present if bit k is 1, and absent if bit k is 0. Since the elements of N0 are finite, they have a finite number of 1's, and thus map onto finite subsets of N0.

One can add a count over the 1's:
1: 0, 2: 1, 3: 0 1, 4: 2, 5: 0 2, 6: 1 2, 7: 0 1 2, 8: 3, ...
and one gets countability there also.

Thus, all the finite subsets of the real numbers contain a countable number of real numbers, and that set's size is thus C.

 

[lpetrich]

The operation of finding all functions from one set to another may be given the shorthand name of exponentiation of sets:
A^B = {all functions f from B to A}

Ordinary exponentiation to power n is using B = {1, 2, 3, ..., n}. If A is the empty set, then A^B is also the empty set. If B is the empty set, then A^B has one element, an element that may be called the empty function.

Set exponentiation has some familiar properties: (A*B)^C = (A^C)*(B^C) and (A^B)^C = A^(B*C)
Also inequalities:
A1 < A2 -> A1^B < A2^B ... |A1| < |A2| -> |A1|^|B| <= |A2|^|B| for nonempty B
B1 < B2 -> A^B1 < A^B2 ... |B1| < |B2| -> |A|^|B1| <= |A|^|B2| for nonempty A

For finite n >= 2,

A-0 = beth-0

2^(A-0) = n^(A-0) = (A-0)^(A-0) = C = beth-1
(A-0)^2 = (A-0)^n = A-0

2^C = n^C= (A-0)^C = C^C = beth-2
C^2 = C^n = C^(A-0) = C

 

[lpetrich]

Mathematicians recognize three different kinds of infinity:

• Cardinal numbers, the sizes of sets.
• Ordinal numbers, numbers in sequence.
• Limits of arbitrarily large finite numbers.

There is a theory of infinite ordinal numbers, and it is very different from the theory of infinite cardinal numbers. That is unlike the finite case, where cardinals and ordinals match.


The continuum hypothesis may be stated as beth-1 = aleph-1. There is a generalization of that: beth-n = aleph-n for all ordinals n.