|
DENUMERABLE SETS
Equivalent
sets
Definition: Set A is equivalent to set B, i. e. they have equal number
of elements, denoted by A ~ B if exists a bijection f : A  B.
Non-empty set A is finite if
and only if there is such an element n  N, that is A ~ {1, 2, ...,n}, where N is set of
natural numbers.
Each injection from the finite set A into A is
bijection.
It is obvious that N is the inifinite set.
If function
from set A into set B is bijection, then it is said that they have the
same power or cardinal number.
Definition: A set is infinite if it is
equivalent to a proper subset of itself. Contrary a set is finite.
Theorem: The relation in sets defined by A ~ B, is an equivalence
relation.
Note that A ~ A for any set A, if A ~ B, then B ~ A, if A ~
B and B ~ C, then A ~ C.
If two finite sets A, B are equivalent, then they have
the same number of elements. If the set A has k different elements, then
k(A) denotes cardinal number of the set A.
Back to top
Denumerable
sets
Let take a look at the set of all odd numbers. The elements of the set
{2, 4, 6, 8, …} can be assigned to the set of natural numbers {1, 2, 3,
4,…}, respectively. This mapping is one-one and onto. So, we can express
these numbers as a series, for example a1, a2,
a3, …, where
numbering is denoted by indexes.
Definition: The set A is called denumerable set, if A is finite or A
~N. Contrary we say that A is non-denumerable. For denumerable and
inifinite set is said to have cardinality  0 (aleph
zero).
The following theorem concerns
denumerable sets.
Theorem: Set of all rational numbers Q is
denumerable.
Every infinite set contains a subset, which is
denumerable.
A subset of a denumerable set is either finite or
denumerable.
A subset of a countable set is countable.
Let
A1, A2, A3,… be a denumerable family of
pairwise disjoint sets, each of which is denumerable. Then the union of
the sets  i
N Ai is
denumerable.
Let {Ai}iI be a countable family of
countable sets. Then iI Ai is countable.
Back to
top
The Continuum
For the set, which has the same cardinal number as the
set of all real numbers R, we say that it has power of continuum or
cardinal number 20= c
Not every infinite
set is denumerable.
Theorem: The unit interval [0,1] is not denumerable.
Proof: As we
are dealing with a set of real numbers we can take an adventage of this
property: Al least one real number y exists in each closed interval
I1=[a1,b1],
I2=[a2,b2],… for which I1 I2…. Let's start from the
contradiction. Then, A={x1,x2,…}. Consider three
closed sub-intervals of [0,1], which have length 1/3: [0,1/3], [1/3,2/3],
[2/3,1] It is obvious that x1 cannot belong to all three
intervals. If x1 = 1/3 then x1 belongs to the first
and to the second interval. If x1=2/3 then x1
belongs to the second and to the third interval. Let
I1=[a1,b1] be one of the proposed
intervals such that x1 I1. We can devide I1 in three closed sub-intervals
with length 1/9. [a1,a1+1/9], [a1+1/9,
a1+2/9], [a1+2/9, b1] Analogously, there
is such an interval I2 with the property that x2
does not belong to I2. Continuing this procedure we reach a
sequence of closed intervals I1I2… such that xnInfor every n N. There exists a real number y [0,1] such that y belongs to
every interval I1I2….
But y A =
{x1,x2,…} implies y=xkfor some k N. Then y=xkIk, which
contradicts the fact that y belongs to every interval in I1
I2… . So we reach the contradiction. Therefore
our assumtion is wrong. We have proved that A is non-denumerable.
Back to
top
Cardinal numbers
A number used to designate the size of a
set--i.e.,to answer the question, "How
many?"--is used cardinally. Any use that depends on the position of the
number in the prescribed sequence is the ordinal use of the number. The
number found at the top or bottom of a page in a book is an example of the
ordinal use of the number. Definition: Let A be any set and let  denote the family of sets which
are equivalent to A. Then
is called a cardinal number and is denoted by =k(A).
Definition: The cardinal number of each of the sets  , {1}, {1,2}, {1,2,3},… is denoted by
0,1,2,3…, respectively, and is called a finite cardinal.
Definition: The cardinal numbers of N, the set of natural numbers, and
the unit interval [0,1] are denoted by k(N) = 0, k([0,1])=c if A
Cardinal
arithmetic
Definition: Let A and B be two non-empty, disjoint sets with cardinal
numbers and  such that =
k(A), = k(B).
Then +
=
k(A B) and = k(A ´ B)
Theorem: The definitions of +
and * do not depend upon the particular sets A and B.
In other words, if A ~ A’, B ~B’, A  B = , A’ B’ = then k(A B) = k(A’ B’) and k(A×B)= k(A’× B’). < /FONT>
By the assumption that the sets A and B are disjoint
and the fact that the sets A × {1} and B × {2} are always
disjoint, (while it does not matter how A and B look
like), it can be said:
Let = k(a) and =
k(b), then + = k(A×{1}) B × {2})
and = k(A × B)
Theorem: The operations of addition and multiplication of cardinal
numbers is associative and commutative; and addition distributes over
multiplication, i.e. for any cardinal numbers ,
and  ,
( + ) + = + ( +
)
, ( ) =
(
) ,
+
=
+ ,
=
, (
+ )= + . if A Consider a, b, c N, then a + b= a + c implies b= c
and ab= ac implies b= c. < BR > For k(N) = follows:
+ =
, 1 + = does not imply =
1
= , 1 =
does not imply =1
the cancellation law is not true for the operations of
addition and multiplication of cardinal numbers.
Inequalities
Definition of an inequality relation for the cardinal numbers:
if A
Let =k(A) and = k(B). Then, let A be equivalent to a
subset of B. This means there exists an one-one function f : A B. Then we write A  B which reads “ A precedes B”.
and which reads “ is
less then or equal to ” and
A ~ B’  B f : A B’, k(A) k(B)
Theorem: The relation in the cardinal numbers defined by is reflexive
and transitive.
CANTOR’S THEOREM
For any set A, A < 2A and,
therefore, for any cardinal number k(A) < k(2A) Note that
if =k(A) then 2 = k(2A),
the cardinal number of the family of subsets of A.
Proof: The function g : A 2Awhich sends each element a A into the set consisting of a
alone, i.e. which is defined by g(a) = {a}, is one-one; hence A 2A.
If we
now show that A is not equivalent to 2A, then the theorem will
follow. Suppose the contrary, i.e. let there exist a function f : a 2Awhich is
one-one and onto. Let a A
be called a “bad” element if a is not a member of the set which is its
image, i.e. a f(a), and
let B be the set of “bad” elements. Specifically, B={x | x A, x f(x)}
Note B is a subset of A, that B 2A. Hence, since f
: A 2Ais
onto, there exists an element b A with the property that f(b)=B. Is b “bad” or “good”? If b B then, by definition of B, b
f(b) = B, which is
impossible. Likewise, if b B, then b f(b) =
B which is also impossible. Thus the original assumption, that A ~
2A , has led
to a contradiction.
SCHRÖDER-BERNSTEIN
THEOREM
For any par of sets A and B, at least one of the following must be
true:
A is equivalent to B, i.e., k(A) = (B)
A is not equivalent
to B but A is equivalent to a subset of B, k(A) < (B) (or k(B) <
k(A)) < BR > A is equivalent to a subset of B and B is equivalent to
a subset of A, i.e., k(A) k(B) and k(B) k(A)
A is not equivalent to a subset of B and B is not
equivalent to a subset of A, i.e., k(A) <  k(B), k(A) (B) and k(A) > k(B)
Schröder-Bernstein theorem: If A B and B A; therefore for any cardinal
numbers and , and implies = .
Equivalent for ofSchröder-Bernstein theorem
is the following:
Let X Y
X1 and X ~ X1; then X ~ Y.
Proof: Equivalence
of X and X1 i.e. X ~ X1,implies the existance
of a function f : X
X1which is one-one and onto. While X Y, the restriction of f to
Y, denoted by f, is also one-one; therefore Y is equivalent to a
subset of X1, i.e. Y ~ Y1where X Y X1 Y1and f : Y Y1 is one-one and onto. But
X1 Y. fOn
the same way, X1 ~ X2where X Y X1
Y1
X2 andf : X1 X2 is one-one and onto. Therefore, there exist
equivalent sets X1, X2, X3, … and
equivalent sets Y, Y1, Y2, … such that X Y X1 Y1 X2 Y2 …
Suppose B = X Y X1
Y1
X2
Y2…
Then X =(X-Y)
(Y-X1)
(X1-Y1) … B
Y = (Y-X1) (X1-Y1) (Y1-X2) … B
Then (X-Y) ~
(X1-Y1) ~ (X2-Y2) ~ …
The
function f : (Xn – Yn) (Xn+1 –Yn+1) is one-one
and onto.
Assume that the function g : X Y is defined as:
f(x),= if x Xi - Yior x
X - Y g(x) = { = x,
= if x Yi -
Xior x B
Then g is one-one
and onto. Therefore X ~ Y. This was the proof.
Theorem (Law of Trichotomy): For any pair of cardinal numbers and , either < , = or > .
CONTINUUM
HYPOTHESIS
People have tried
to understand space, time, motion, and the meaning of "continuum" for
thousands of years.
In 1874 Georg
Cantor discovered that there is more than one level of infinity. The
lowest level is called "countable infinity" and higher levels are called
"uncountable infinities." The natural numbers are an example of a
countably infinite set and the real numbers are an example of an
uncountably infinite set. In 1877 Cantor hypothesized that the number of
real numbers is the higher level of infinity above countable infinity.
Since the real numbers are used to represent a linear continuum, this
hypothesis is called "the Continuum Hypothesis".
The power set of the natural numbers, P(N), can also be represented by the set
of all countably infinite sequences of 0's and 1's. Each sequence
represents a subset of N by interpreting a 0 in position n to
mean that the number n is not in the subset and a 1 in position n to mean
the number n is in the subset. This way of specifying asetis called the
"characteristic function" of the set.
One way to represent all countably infinite sequences of 0's and 1's is
to useCartesian product notation{0, 1}0Since in set theory {0, 1} = 2, we can also
write this as:20 So we now
have:0 c= k(R) = k((0,1)) = k(P(N)) = 20
Theorem: 2 =c.
Continuum Hypothesis (Cantor): There exists
no cardinal number such
that < <
c.
There is no cardinal number which lies
“between” and c.
Back to
top |
