mathtres
Thu 04/26/07
therefore onto.
example . N x N is denumerable.
define f: N x N -> N
f(m,n)= 2^(n-1) * (2n-1)
we've proved this is 1-1 and onto.
qed.
Are there any uncountable sets? If there more than one order of infinity? Yes.
Background.
Look at intevol (0,1).
Look at decminals in normalized form.
If a in (0,1), then a= .a[1] a[2] a[3] ..
where 0 ≤ a[i] ≤9 .. and integers.
.4999999999 = .5
two numbers in normalized decimal form are equal iff they have identical digits in each decimal location.
Theorem 5.13 The interval (0,1) is uncountable.
"there are more numbers between zero and 1 than in all the natural numbers"
Proof. Georg Canter.
Show not finite or denumerable.
not finite. {1/2, 1/3, 1/4 1/5} is subset of (0,1) so it has an ∞ subset so its ∞
show its not denumerable.
Suppose it is.
Therefore there exists f: N -> (0,1) that's 1-1 onto.
Show not onto.
Write the images of f in normalized form
f(1) = 0.a[1][1]a[1][2]a[1][3] ..
f(2) = 0.a[2][1]a[2][2]a[2][3] ..
f(n) = 0.a[n][1]a[n][2]a[n][3] ..
then every element in the interval of zero to one is in the list some place.
Define b by 0.b[1]b[2]b[3],
where b[i] is 3. where a[i][i] ≠ 3
b[i] = 7 where a[i] =3.
..
b differs from f(n) in the nth digit.
therefore b is not an element of the range of f.
therefore f is not onto.
the cardinal number of (0,1) is c .. and that stands for continuom.
Theorem 5.14
Let a,b in R, a<b.
cardinal number of (a,b) = c.
theorem 5.15
cardinal number for the set of all R = c.
proof -- tan function.
Mon 04/30/07
2 - 1-1, ONTO
6- indirection
12 - inductin
indirect
235
denumerable - show that its in a 1-1 correspondence with natural numbers
show 1-1 onto N -> other set.
if its obvious that its a function, dont prove thht its a function
7500+6800
=
7500+6800=
3 tf
5 cardinal numbers
---
natural numbers are denumerable;
reals are not - we proved it.
what about the rationals -- are they denumerable?
N is a subset of rationals is a subset of the reals.
does the cardinal number of Q = cardinal of N or of reals?
aloph null or c?
theorem 5.16 (cantor)
the set Q+ of positive rational numbers is denumerable.
proof.
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/1 then 2/1 then 1/2 3/1, skip 2/2, 1/3, 4/1, 3/2
this list contains all of them .. so they're denumerable.
the set of all positive rational numbers is denumerable.
theorum 5.17
If A is denumerable, then A u {x} is denumerable.
Proof. If x in A, then A union {x} = A, therefore denumerable.
x not in A.
there exists an f : N->A that's 1-1 and onto.
f(1) .. f(2) .. f(3) ..
we could put
x f(1) f(2) .. and so on.
Define g: N -> A u {x} by
g(n) = { x for n=1, (n-1) for n≠1 }
so cardinal number alloph null plus 1 = alloph null.
transfinite arithmetic.
5.18 If A is denumerable and B is finite, then A u B is denumerable.
alloph null plus n = alloph null
can be proved by induction
Theorem 5.19 If A and B are disjoint denumerable sets, then A u B is denumerable.
Proof. Similar to proof for Z.
alloph null plus alloph null = allph null.
Theorem 5.20. The set Q of all rationals is denumerable.
Proof Q = Q+ u {0} u Q-.
Q- is denumerable because its equivalent to Q+
1,2, .... alloph null .. c.
is there an infinite cardinal number inbetween alloph null and c ..
the assumptin taht there's nothing inbetween .. the continum hypothesis.
homework due wed at 2.
Thu 05/03/07
problem 7.
show it works for 1
then show that if it works for some integer n, then it works for n+1
then it works for all integers.
ladder. if you can get to the first step and on any step you can climb another, then you can climb the ladder.
i) show n=1.
Suppose A1 is finite
Let n=1 .. U i=1 to 1 of A[i] = A[1], which is finite. that takes care of the 1 case.
ii) suppose that if A[1] .. A[n] are finite.
then U i=1 to n of A[i] is finite.
Let A[1] .. A[n+1] be finite sets.
show that union i=1 to n+1 of A[i] is finite.
union i=1 to n+1 of A[i] = U i=1 to n of A[i] U A[n+1] // by the associative law for union.
U i=1 to n of A[i] is finite by IH
A[n+1] is finite by given.
Therefore U i=1 to n of A[i] U A[n+1] is finite by Theorem 5.7b.
induction refresher.
The ordering of the cardinal numbers.
A-bar-bar
what's bigger, 2 or 3?
3.
if we have three cookies, you can eat two and still have one left.
1-1 function going one way .. but not the other.
so that's going to be our definition of less than.
Def. 5.4
a) cardinal number of A = Cardinal number of B iff they are equivalent.
b) cardinal number of A is ≤ B-bar-bar
iff exists f : A->B that's 1-1
c) A-bar-bar < B-bar-bar iff A-bar-bar ≤ B-bar-bar and A-bar-bar ≠ B-bar-bar
Theorem 5.21
For all sets A, B, C
a) reflexivity: A-bar-bar ≤ A-bar-bar
b) transitivity of =
if A-bar-bar = B-bar-bar and B-bar-bar = C-bar-bar
then A-bar-bar = C-bar-bar
c) Transitivity of ≤ if A-bar-bar ≤ B-bar-bar and B-bar-bar ≤ C-bar-bar then A-bar-bar ≤ C-bar-bar.
d) A-bar-bar ≤ B-bar-bar iff A-bar-bar ≤ B-bar-bar or A-bar-bar = B-bar-bar
e) if A subset of B, then A-bar-bar ≤ B-bar-bar
f) A-bar-bar ≤ B-bar-bar iff exists w subset of B such that A-bar-bar = W-bar-bar.
Proof (a).
I[A]: A -> A is 1-1 QED.
Proof (b). Theorem 5.1
Proof (c). Suppose A-bar-bar ≤ B-bar-bar and A-bar-bar ≤ C-bar-bar
exists f: A->B 1-1
exists g: B->C 1-1
therefore g o f : A->C is 1-1 .. we proved it. some theorem or other.
part d.
=>
Suppose A-bar-bar ≤ B-bar-bar
Suppose ~ A--bar-bar = B-bar-bar.
Therefore A-bar-bar ≤ B-bar-bar .. by definition of <
<= Suppose less than or equal to.
cases
case 1. Suppose A-bar-bar < B-bar-bar.
Therefore A-bar-bar ≤ B-bar-bar, by definition.
case 2. A-bar-bar = B-bar-bar
Then exists f: A->B 1-1 onto.
therefore f is 1-1
therefore A-bar-bar ≤ B-bar-bar.
Part e)
i : A -> B is 1-1
inclusion function
Theorem 5.23 - Canter's great theorem.
For every set A, the cardinal number of A is stricktly less than the cardinal number of the POwer set of A.
Works for any set of A.
Show its ≤ and ≠
1. Show A-bar-bar ≤ Power(A)-bar-bar.
Define F: A-> POwer(A) by
F(x) = {x}
QED part 1
show A-bar-bar ≠ POwer(A)-bar-bar.
IP - Suppose A-bar-bar = POwer(A)-bar-bar.
therefore A ~~ POwer(A)
Therefore exists g: A-> POwer(A) that's 1-1 and onto.
Let B = { y in A : y not in G(y) }
Suppose A = {1,2}
g(1) = {2}
g(2) = {1,2}
in our example, B = {1} .. everything that's not in its image.
B is a subset of A.
Therefore, B in POwer(A).
since g is onto, B in Rng(g).
therefore exists z in A st g(z) = B.
therefore z in B or z not in B.
If z in B, therefore z not in g(z).
therefore z not in B.
-> <-
If z not in B, then z in g(z). then z in B by definition of g(z) -><-
since everything leads to a contradiction, g is not onto .. contradiction.
Why is this so exciting?
we know taht alloph null is less than c
and that's less than the cardinal number of the Power(R) and that's less than Power((Power(R))
.. you get an infinite string of larger and larger orders of infinities.
we have infinitely many different sizes of infinity.
infinite number of new axiums, each of which is indepedent of the axium of set theory.
Fri 05/04/07
partition -
collectiin of sets
antisymetric
aRb bRa => a = b.
function
0 - subset of A x B
1 - Dom(f) = A
2 - if they hhve the same first element, then they have the same 2nd element
equivalent -
exists a 1-1 onto functin from one set to the other.
cardinal number
9-12, 1-3 .. office hours for thursday.
roughly the same hours wed.