ECS 20 — Lecture 13 — Fall 2013 —7 Nov 2013
Phil Rogaway
Today:
Announcements:
o Dog day next Tuesday! BYOD.
Comparing infinite sets, continued
Review:
|A||B| if there exists an injection f: A B.
|A|=|B| or A~B, if there exists a bijection : AB.
|A||B| if |A|=|B| )
|A|<|B| if |A||B| but |A| |B|: there is an injection but no bijection from A to B.
A set is finite if it is empty or equipotent with {1, ..., n} for some natural number n A set is infinite if it is not finite.
A set is countably infinite if it is equipotent with N.
Write |A| =
That symbol is called a cardinal number.
So the numbers you know about are 0, 1, 2, .... , , c
We showed last time that
Examples:
N~Z
{0,1, ...} ~ {1,2, ...} (hotel with countably many occupied rooms; a new customer arrives)
N ~ {1,2} N (hotel with infinitely many occupied rooms; countably many new customer arrives)
Can also show
N ~ Q : the rationals are countably infinite
N ~ {0,1}* : the strings (over a fixed alphabet, say binary) are countably infinite
But we showed
|N| < |R| : the reals are uncountable
Let’s modify the proof a little to show that
The number of languages (sets of strings over {0,1}) is uncountable
Give the standard diagonalization proof for this.
Important corollary:
Cor: there are languages that no computer program can recognize.
o Comparing the size of infinite sets, cont o Asymptotic notation
The sets are equipotent, equicardinal
1
Theorem [Cantor] |A| < |P(A)| Prove Cantor’s theorem
Proof of Cantor’s theorem, from Wikipedia [Cantor’s Theorem]: To establish Cantor's theorem it is enough to show that, for any given set A, no function f from A into the power set of A, can
be surjective, i.e. to show the existence of at least one subset of A that is not an element of
the image of A under f. Such a subset is given by the following construction:
This means, by definition, that for all x in A, x ∈ B if and only if x ∉ f(x). For all x the
sets B and f(x) cannot be the same because B was constructed from elements ofA whose images (under f) did not include themselves. More specifically, consider any x ∈ A, then
either x ∈ f(x) or x ∉ f(x). In the former case, f(x) cannot equal B because x ∈ f(x) by assumption and x ∉ B by the construction of B. In the latter case, f(x) cannot equal B because x ∉ f(x) by assumption and x ∈ B by the construction of B.
Thus there is no x such that f(x) = B; in other words, B is not in the image of f. Because B is in the power set of A, the power set of A has a greater cardinality than A itself.
Theorem [Cantor-Bernstein-Schroeder] If |A| |B| and |B| |A| then |A| = |B|.
Many proofs, but not simple. I read the one on the Wikipedia page and thought it incoherent. I will
leave this for when you take a set theory class ... except we (UCD) don’t seem to have one.
Leftover
n! – factorial – didn’t mention
Review of properties of logs – lg, log, ln.
Inverse of 2^, 10^, e^ (exp)
y ln(y) (the right notation for how to descript the action of a function. Note the kind of arrow.)
Also -notation: f = x. ln(x) f = x. x2 + 1
log(ab) = log(a) + log(b) loga(b) = logc(b) / logc(a)
Wikipedia: The continuum hypothesis (CH) states that there are no cardinals strictly
between and = / The generalized continuum hypothesis (GCH) states that for every infinite set X, there are no cardinals strictly between | X | and 2| X |. The continuum hypothesis is independent of the usual axioms of set theory, the Zermelo-Fraenkel axioms, together with the axiom of choice (ZFC).
2
sab = (sa)b ax ay = ax+y
Function composition
fg
f:AB, g:BC
then (g f) : A C is defined by (g f)(x) = g(f(x))
Kind of "backwards", but fairly tradition. Some mathematicians (eg, in algebra) will reverse it, (x) (f g) "function operates on the left"
Comparing growth-rates of functions –Asymptotic notation and view
Motivate the notation. Will do big-O and Theta. http://en.wikipedia.org/wiki/Big_O_notation
O(g) = { f: N R: C, N s.t. f(n) C g(n) for all n N}
People often use “is” or “=” for “is a member of” or “is an anonymous element of” .
I myself don’t like this.
Reasons for asymptotic notation:
1. simplicity – makes arithmetic simple, makes analyses easier
2. When applied to running times: Works well, in practice, to get a feel for efficiency
3. When applied to running times: Facilitates greater model-independence
Reasons against:
1. Hidden constants can matter
2. Mail fail to care about things that one should care about
3. Not everything has an “n” value to grow
If f O(n2), g O(n2) the f+g O(n2)
If f O(n2) and g O(n3) then f+g O(n3)
If f O(n log n) and g O(n) then fg O(n2 log n)
etc.
May write O(f) + O(g), and other arithmetic operators
True/False:
If f Θ(n2) then f O(n2) TRUE (Truth: n! = Θ((n/e)n sqrt(n)))
3
Discuss the runtime evaluation of a simple code fragment, eg,
for i= 1 to n do
for j=1 to 10*floor(i/3) do
Constant time statement
Will do many more examples next week.
4