lpetrich
Contributor
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:
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, ...
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.
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, ...