intermediate logic: Cantor

Cantor's Result, Cantor's Paradox, Russell's Paradox, and the semantic
paradoxes


1) Cantor's Result: The cardinality of a set is the number of members it
has. A general concept of "A has the same cardinality as B," which can be
applied to infinite sets, is that there is a one-to-one mapping of items
from A to items in B. For infinite sets, this 1-1 mapping is given by an
algorithm, a rule for constructing the next item in the sequence. For every
item in one set there is an item in the other set, and vice versa. Various
infinite sets, for instance the set of integers and the set of rational
numbers (fractions) have the same number of members.

Here is an example of an enumeration (mapping onto the natural numbers) of
the rational numbers (i.e. the fractions):

1/1 2/1 3/1 4/1 5/1…….

1/2 2/2 3/2 4/2 5/2…..

1/3 2/3 3/3 4/3 5/3……

1/4 2/4 3/4 4/4 5/4 …….

1/5 2/5 3/5 4/5 5/5…….
:
The enumeration proceeds by mapping 1 onto 1/1, 2 onto 2/1, 3 onto 1/ 2, 4
onto 1/3, 5 onto 2/2, 6 onto 3/1, 7 onto 4/1, 8 onto 3/2, and so on. You
follow the zig-zag path indicated by the lines in the diagram above,
working your way through the rational numbers one by one. You eventually
get to each fraction. To get a 1-1 mapping, you need to eliminate
duplication as you go. That is, ignore 2/2, 3/3, 4/4, and so on, since you
already have that rational number in the form 1/1. One procedure would be
to check back through the rational numbers enumerated so far before you
assign a natural number to the new number on the grid. If the number is
already on the enumeration, ignore it and check the next number. (All this
is obviously algorithmically doable.) Another procedure is to check each
fraction to determine whether the numerator and denominator are relatively
prime, i.e. that neither is a factor of the other. If a fraction is not
relatively prime, another fraction is, and that will be the correlate to
the integer. So, in the above grid, 2/2, 3/3, 4/4, 5/5, 2/4, and 4/2 will
be kicked out of the 1-1 mapping.
So, the 1-1 mapping will be 1 to 1/1, 2 to 2/1, 3 to ½ 4 to 1/3, to 3/1, 6
to 4/1, 7 to 3/2. 8 to 2/3, 9 to ¼, 10 to 1/5, 11 to 5/1, and so on.

If you follow the ignoring procedure, there is a unique natural number
corresponding to each rational number. So, there are exactly as many
fractions as there are natural numbers. (A surprising result, since between
1 and 2 there are an infinity of rational numbers. This feature of
infinity, that an infinite set has proper subsets (S1 is a proper subset of
S2 just in case every member of S1 is also a member of S2, but there are
members of S2 that are not members of S1. For finite sets, that would mean
that there are more members of S2. A definition of the concept "infinite
set" is that an infinite set S2 has a proper subset S1 with the same
cardinality.)

Now consider an attempted enumeration of the subsets of the natural
numbers. For finite sets, the cardinality of the set of subsets of a given
set is 2n, where n is the number of items in the set. So, for instance, the
set {1,2,3} has the subsets {1,2,3}, {1,2}, {1,3}, {2,3}. {1}, {2}, {3},
and Ø. (You might wonder why the null set is a subset of every set. By the
definition of "subset" "A is a subset of B if every member of A is a member
of B," a set with no members meets the definition: All of its members are
members of the other set.)
The idea will be to have a horizontal infinite list of the natural numbers,
and to enumerate the subsets by sequences of 1's and 0's, depending on
whether the number is or is not in the subset. The vertical list will be
the enumeration of the subsets. So the array will look like this:
Numbers that are or are not in the subset are across the top, the
enumeration of subsets is at the far left.


1 2 3 4 5 6……
1 0 1 1 0 0 1……..
2 1 0 0 1 0 0 …….
3 1 0 1 0 0 1…….
4 0 1 1 0 1 1…….
5 0 0 1 0 1 0…….:
6 1 1 1 1 0 0
.
.
The complete infinite vertical list of infinite sequences of 0's and 1's
will be the alleged enumeration (= 1-1 mapping) of the subsets of the
natural numbers onto the natural numbers. The second line on the list,
for instance, is one of the subsets that contain 1 and 4. If the rest
of the entries in line 2 are 0's, then the subset is {1,4}. This is an
infinite array of subsets.

Supposing that the dots to the left are all 0's, the subsets enumerated as
the first 5 are {2,3,6}, {1,4}, {1,3}, {2,3,5,6}, {3,5}and {1,2,3,4}.
The subset along the diagonal is {3,5}.

As we showed above, there are mappings of the rational numbers between 0
and 1 with the rationals between 0 and 1,000,000. Surprising results.
There are exactly as many fractions between 0 and 1 as there are
between 0 and 1,000,000.

Now construct the following subset L for "left out", on the basis of the
beginning of the enumeration above: 1 is a member of L, 2 is, 3 is not 4
is, and so on. The set L differs from the first set by including 1 if and
only if the first set does not include 1, from the second set by including
2 iff the second set does not include 2, from the billionth set by
including 1 billion only if the billionth set does not include 1 billion,
and so on. Set L differs from every set S in the enumeration by differing
from S in at least one place. So, set L cannot be in the enumeration. It is
different from every element in the enumeration.
The portion of subset L given by the above diagram is {1,2,4,6}. This is a
set that is not on the list so far. It cannot be on the list, since it is
defined so that it differs from each element on the list in at least one
place. That continues forever. So, that subset is not on the enumeration.
Given any alleged enumeration of the subsets, the diagonal set L is a
subset that is not included in the enumeration. By the definition of "has
more members than," there are therefore MORE subsets of natural numbers
than there are natural numbers, even though there are an infinity of both.
Some infinities have a greater cardinality than others.
This proof procedure is called diagonalization, a very productive
proof-method. Briefly, you show that given any mapping of elements of a set
with elements of its power set, some element of the power set can be
constructed which must be left out of the one-to-one matching. The most
familiar application of diagonalization shows that the set of real numbers
is larger than the set of rational numbers.

You might think that this is just a kind of oddity, and that there
really are not that many numbers that are not rational numbers. One way to
see that there are lots more real numbers than rational numbers is to
realize that for every integer, there are an infinity of roots. That is,
there is the mth root of n for every m and n ( m n). We can prove that such
roots are either integers or irrational numbers, using the theorem that
every number decomposes into a product of primes in exactly one way.[1]
This does not prove that there are more real numbers than rational numbers,
but it may make the proof above, that given any enumeration, we can
construct a real number left out of the enumeration, is not a trick.

The power set of a set is the set of subsets of a set. For finite
sets, the cardinality of the power set is 2n, where n is the cardinality of
the set. Repeat: There are 8 (= 23) subsets
of a 3-membered set {1,2,3): {1}{2}{3}(1,2}{2.3}{1,3}{1,2,3}and Ø. There
is of course no one-one mapping of that 3-membered set onto its subsets.
There are strictly more subsets than members.
Infinite sets have proper subsets of the same cardinality. That's what
the 1-1 mapping of the rationals onto the natural numbers showed. The
natural numbers are a proper subset of the rationals, since there are lots
of rationals that are not natural numbers. Intuitively, since between any
two natural numbers there are an infinity of rationals, you would suppose
that there are in some sense more rationals than naturals. Not so. For
infinite sets, the cardinality of a proper subset can have the same
cardinality as the set. (Zeno of Elea took this feature of infinity to be
contradictory/paradoxical and to show the impossibility of physical
existence.)

Cantor proved that the cardinality of the power set of a set is greater
than the cardinality of the set itself even for infinite sets. So, there
are different levels of infinity. Cantor labeled the lowest level of
infinity aleph-null. The cardinality of the subsets of the natural numbers
is 2aleph 0. This is also referred to as the cardinality of the continuum,
the real numbers (=the rationals plus the irrationals). There are more real
numbers than there are rational numbers, unlike other infinities in
relation to their proper subsets.

Why is this relevant to 2nd –order logic?
Second-order logic allows you to say things like, "For all sets F, if a is
a member of F if and only if b is a member of F, then a=b" (\/F((Fa Fb)
->a=b) as a definition of identity. A proof-procedure for 2nd-order logic,
though, could have an infinite path that remained open forever even though
there were instantiations that would make the path close. You would just
never get to the counterexample. Another principle that requires second-
order logic, but which can be captured by special rules, is the
mathematical induction principle, which says that any property which holds
of 0 and holds of n+1 if it holds of n, holds of every number. Since this
refers to all properties of numbers, and properties of numbers have subsets
of numbers as extensions, there are more properties of natural numbers than
there are natural numbers.

2) Cantor's Paradox
What's the paradox? Consider the set of all sets. This would seem to be the
largest set. But its power set would be larger than it. (And the power set
of the power set….) Note that this set of all sets includes itself as a
member. So, what do you say about the expression "the set of all sets"? It
seems that it ought to describe a set, but it cannot. If it did, there
would be the set of subsets of the set of all sets, which would be larger
than the set of all sets, and not included in the set of all sets, but it
would be ONE of the sets of all sets. .So, gosh.

3) Russell's paradox: The set of frogs is not a frog. So the set of frogs
is not a member of itself. But the set of sets with more than two members
has more than two members, and so is a member of itself. Now, there ought
to be a set of sets which are members of themselves, as well as a set of
sets which are not. But consider the set of sets which are not members of
themselves. It must either be a member of itself or not, since every item
is either within a set or not. If it is a member of itself, then it is not.
If it is not, then it is.
This paradox transformed set-theory, which had become the basis of
mathematics in the nineteenth century. Briefly and crudely, two approaches
to set-theory were proposed to avoid the paradox: Zermelo-Fraenkel set
theory proposes an axiom system which specifies which sets exist. It does
not generate the paradoxical sets. This is the set-theory accepted and used
by mathematicians and logicians today.
Russell's type-theory establishes a hierarchy of sets, such that a set
of level n can only have objects of level < n as member. Russell's idea was
that level 1 consists of objects that are not sets. Level 2 consists of
sets of objects and objects that are not sets. Level 3 consists of sets of
sets of objects, sets of objects, and sets of objects that are not sets.
Any legitimate set has a level. The paradoxical set has no level, and so is
not a legitimate set. It would have to be at two levels at once.

There are semantical paradoxes which are closely akin to the set-theoretic
paradoxes. The Liar Paradox can be illustrated by the sentence "The quoted
sentence in this line is false." If this is true, then it is false. If it
is false, it is true. The most well-known people in the UCONN Philosophy
department have fashioned entire careers dealing with this paradox.

Another paradox about "true of:" Some words apply to themselves. "Short"
is short, but "gorilla" is not a gorilla. "English" is English but "French"
is not French (that would be "francais.")
Call the words that are true of themselves "autological." Call the words
that are not true of themselves "heterological." Now, consider the word
"heterological:" Is it heterological or autological? With either choice, if
it is, it is not.
Even for naming, paradoxes arise: Consider the description, "the smallest
number not specifiable in fewer than six words." This specification has ten
words.
-----------------------
[1] Suppose ( m4PQ^dfg D ¹ "M_h Œ?±Õäì


"

&

2

:

<

D

H

J

T

Z

b

d

f

ñåñÔÆÔ¸Ô¸ÔªœªÔœÔœ¸ª¸ª¸Ž€¸ŽrdŽdŽ¸r€¸ª¸r€hµeðCJOJQJ^JaJh"
CJOJQJ^JaJhDzCJOJQJ^JaJh

ÔCJOJQJ^JaJhógCJOJQJ^JaJh²v¾CJOJQJ^JaJhØ)ïCJOJQJ^JaJhtlCJOJQJ^JaJ n) =
a/b, where a and b are integers, so that a/b is a rational number. Put that
rational number in lowest terms, i.e. so that the numerator and denominator
are relatively prime. Then n= (a/b)m= am/bm. Then n x bm= am. Since a and b
have no common factors, the only way this could be the case is if b=1. That
is, any integral root of any integer is either an integer or an irrational
number.

Whatever the prime factors of b are, the prime factorization of n x b will
be those prime factors raised to the mth power multiplied by the prime
factors of n. Since a and b are relatively prime (have no common divisors)
there is no way this could happen unless b=1. If b=1, the root is an
integer.