1. ## Infinite Sets

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, ...  Reply With Quote

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

3. 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(n)) for all a1,a2,...,a(n) 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(n)) 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(n) = a(n). 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.  Reply With Quote

4. Originally Posted by GenesisNemesis 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.  Reply With Quote

5. 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.   Reply With Quote

6. Originally Posted by Kharakov 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?  Reply With Quote

7. Originally Posted by GenesisNemesis 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 ...   Reply With Quote

8. 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+)|.  Reply With Quote

9. Originally Posted by Derec  Originally Posted by GenesisNemesis 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.  Reply With Quote

10. 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?  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•