446256948-Discrete-Mathematics-and-its-Application-Chapter-2-ppt.ppt

discrete math and application

1. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Sixth Edition, Mc Graw-Hill, 2011© by Kenneth H. Rosen, Discrete Mathematics & its Applications, Sifth Edition, Mc Graw-Hill, 2007
Chapter 2:Chapter 2:
Basic Structures: Sets, Functions, Basic Structures: Sets, Functions,
Sequences and SumsSequences and Sums
• Sets (Section 2.1)
• Set Operations (Section 2.2)
• Functions (Section 2.3)
• Sequences and Summations (Section 2.4)

2. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
2
Sets (2.1)Sets (2.1)
•A set is a collection or group of objects or
elements or members. (Cantor 1895)
–A set is said to contain its elements.
–There must be an underlying universal set U,
either specifically stated or understood.

3. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
3
Sets (2.1) (cont.)Sets (2.1) (cont.)
–Notation:
•list the elements between braces:
S = {a, b, c, d}={b, c, a, d, d}
(Note: listing an object more than once does not change the
set. Ordering means nothing.)
•specification by predicates:
S= {x| P(x)},
S contains all the elements from U which make the
predicate P true.
•brace notation with ellipses:
S = { . . . , -3, -2, -1},
the negative integers.

4. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
4
Sets (2.1) (cont.)Sets (2.1) (cont.)
•Common Universal Sets
–R = reals
–N = natural numbers = {0,1, 2, 3, . . . }, the counting
numbers
–Z = all integers = {. . , -3, -2, -1, 0, 1, 2, 3, 4, . .}
–Z
+
is the set of positive integers
•Notation:
x is a member of S or x is an element of S:
x  S.
x is not an element of S:
x  S.

5. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
5
Sets (2.1) (cont.)Sets (2.1) (cont.)
•Subsets
–Definition: The set A is a subset of the set B, denoted
A  B, iff
x [x  A  x  B]
–Definition: The void set, the null set, the empty set,
denoted , is the set with no members.
Note: the assertion x   is always false. Hence
x [x    x  B]
is always true(vacuously). Therefore,  is a subset of every set.
Note: A set B is always a subset of itself.

6. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
6
Sets (2.1) (cont.)Sets (2.1) (cont.)
–Definition: If A  B but A  B the we say A is a
proper subset of B, denoted A  B (in some texts).
–Definition: The set of all subset of a set A, denoted
P(A), is called the power set of A.
–Example: If A = {a, b} then
P(A) = {, {a}, {b}, {a,b}}

7. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
7
Sets (2.1) (cont.)Sets (2.1) (cont.)
–Definition: The number of (distinct) elements in
A, denoted |A|, is called the cardinality of A.
If the cardinality is a natural number (in N), then the
set is called finite, else infinite.
–Example: A = {a, b},
|{a, b}| = 2,
|P({a, b})| = 4.
A is finite and so is P(A).
Useful Fact: |A|=n implies |P(A)| = 2
n

8. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
8
Sets (2.1) (cont.)Sets (2.1) (cont.)
–N is infinite since |N| is not a natural number. It is called a
transfinite cardinal number.
–Note: Sets can be both members and subsets of other sets.
–Example:
A = {,{}}.
A has two elements and hence four subsets:
, {}, {{}}. {,{}}
Note that  is both a member of A and a subset of A!
–Russell's paradox: Let S be the set of all sets which are not
members of themselves. Is S a member of itself?
–Another paradox: Henry is a barber who shaves all people who
do not shave themselves. Does Henry shave himself?

9. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
9
Sets (2.1) (cont.)Sets (2.1) (cont.)
•Definition: The Cartesian product of A with B, denoted
A x B, is the set of ordered pairs {<a, b> | a  A  b  B}
Notation:
Note: The Cartesian product of anything with  is . (why?)
–Example:
A = {a,b}, B = {1, 2, 3}
AxB = {<a, 1>, <a, 2>, <a, 3>, <b, 1>, <b, 2>, <b, 3>}
What is BxA? AxBxA?
–If |A| = m and |B| = n, what is |AxB|?
 
iin21i
n
1i
Aaa,...,a,aA 


10. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
10
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
•Propositional calculus and set theory are
both instances of an algebraic system called
a
Boolean Algebra.
The operators in set theory are defined in terms of
the corresponding operator in propositional
calculus
As always there must be a universe U. All sets are
assumed to be subsets of U

11. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
11
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
•Definition:
Two sets A and B are equal, denoted A = B,
iff
x [x  A  x  B].
–Note: By a previous logical equivalence we have
A = B iff x [(x  A  x  B)  (x  B  x  A)]
or
A = B iff A  B and B  A

12. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
12
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
•Definitions:
–The union of A and B, denoted A U B, is the set {x | x  A  x  B}
–The intersection of A and B, denoted A  B, is the set
{x | x  A  x  B}
Note: If the intersection is void, A and B are said to be disjoint.
–The complement of A, denoted , is the set {x | (x  A)}
Note: Alternative notation is A
c
, and {x|x  A}.
–The difference of A and B, or the complement of B relative to A, denoted A - B, is the set A 
Note: The (absolute) complement of A is U - A.
–The symmetric difference of A and B, denoted A  B, is the set
(A - B) U (B - A)
A
B

13. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
13
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
–Examples:
U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A= {1, 2, 3, 4, 5},
B = {4, 5, 6, 7, 8}. Then
•AB = {1, 2, 3, 4, 5, 6, 7, 8}
•A  B = {4, 5}
• = {0, 6, 7, 8, 9, 10}
• = {0, 1, 2, 3, 9, 10}
•A - B = {1, 2, 3}
•B - A = {6, 7, 8}
•AB = {1, 2, 3, 6, 7, 8}
A
B

14. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
14
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
•Venn Diagrams
–A useful geometric visualization tool (for 3 or less sets)
–The Universe U is the rectangular box
–Each set is represented by a circle and its interior
–All possible combinations of the sets must be represented
–Shade the appropriate region to represent the given set operation.
U U
A
A
B
C
B
For 2 sets For 3 sets

15. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
15
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
•Set Identities
–Set identities correspond to the logical equivalences.
–Example:
The complement of the union is the intersection of the
complements:
= 
Proof: To show:
x [x   x   ]
To show two sets are equal we show for all x that x is a
member of one set if and only if it is a member of the
other.
AB
AB
BA
BA

16. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
16
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
–We now apply an important rule of inference
(defined later) called
Universal Instantiation
In a proof we can eliminate the universal
quantifier which binds a variable if we do not
assume anything about the variable other than it
is an arbitrary member of the Universe. We can
then treat the resulting predicate as a proposition.

17. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
17
–We say
'Let x be arbitrary.'
Then we can treat the predicates as propositions:

18. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
18
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
Hence
x   x  
is a tautology.
Since
• x was arbitrary
• we have used only logically equivalent
assertions and definitions
BA AB

19. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
19
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
we can apply another rule of inference called
Universal Generalization
We can apply a universal quantifier to bind a variable if
we have shown the predicate to be true for all values of
the variable in the Universe.
and claim the assertion is true for all x, i.e.,
x [x   x   ]
Q. E. D. (Latin phrase “Quod Erat Demonstrandum”)
BA AB

20. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
20
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
–Note: As an alternative which might be easier in some cases, use the identity
A = B  [A  B and B  A]
–Example:
Show A  (B - A) = 
The void set is a subset of every set. Hence,
A  (B - A)  
Therefore, it suffices to show
A  (B - A)   or x [xA  (B - A)  x  ]
So as before we say 'let x be arbitrary’.

21. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
21
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
–Example (cont.)
Show xA  (B - A)  x  is a tautology.
But the consequent is always false.
Therefore, the antecedent better always be false
also.
Apply the definitions:

22. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
22
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
–Example (cont.)
Hence, because P  P is always false, the implication
is a tautology.
The result follows by Universal Generalization.
Q. E. D.

23. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
23
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
•Union and Intersection of Indexed
Collections
–Let A
1,A
2 ,..., A
n be an indexed collection of
sets.
–Union and intersection are associative
(because 'and' and 'or' are) we have:
n21i
n
1i
n21i
n
1i
A...AAA
and
A...AAA





24. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
24
Set Operations (2.2) (cont.)Set Operations (2.2) (cont.)
–Examples
Let
),n[A
),1[A
i1),,i[A
i
n
1i
i
n
1i
i





),n[A
),1[A
i1),,i[A
i
n
1i
i
n
1i
i






25. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
25
Functions (2.3)Functions (2.3)
•Definition:
Let A and B be sets. A function (mapping,
map) f from A to B, denoted f :AB, is a
subset of A*B such that
x [x  A  y [y  B  < x, y > f ]]
and
[< x, y
1 > f  < x, y
2 >  f ]  y
1 = y
2

26. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
26
Functions (2.3) (cont.)Functions (2.3) (cont.)
•Note: f associates with each x in A one and only one y in B.
A is called the domain and
B is called the codomain.
If f(x) = y
y is called the image of x under f
x is called a preimage of y
(note there may be more than one preimage of y but
there
is only one image of x).
The range of f is the set of all images of points in A
under
f. We denote it by f(A).

27. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
27
Functions (2.3) (cont.)Functions (2.3) (cont.)
If S is a subset of A then
f(S) = {f(s) | s in S}.
Example:
• f(a) = Z
• the image of d is Z
• the domain of f is A = {a, b, c, d}
• the codomain is B = {X, Y, Z}
• f(A) = {Y, Z}
• the preimage of Y is b
• the preimages of Z are a, c and d
• f({c,d}) = {Z}
A B
a
b
c
d
X
Y
Z

28. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
28
Functions (2.3) (cont.)Functions (2.3) (cont.)
•Injections, Surjections and Bijections
–Let f be a function from A to B.
–Definition: f is one-to-one (denoted 1-1) or injective if preimages
are unique.
Note: this means that if a  b then f(a)  f(b).
–Definition: f is onto or surjective if every y in B has a preimage.
Note: this means that for every y in B there must be an x in A
such that f(x) = y.
–Definition: f is bijective if it is surjective and injective (one-to-one
and onto).

29. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
29
Functions (2.3) (cont.)Functions (2.3) (cont.)
–Examples:
The previous Example function is neither an
injection nor a surjection. Hence it is not a
bijection.A B
a
b
c
d
X
Y
Z
Surjection but not an injectionSurjection but not an injection

30. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
30
Functions (2.3) (cont.)Functions (2.3) (cont.)
A B
a
b
c
d
X
Y
Z
W
V
A B
a
b
c
d
X
Y
W
V
Injection but not a surjectionInjection but not a surjection
Injection & a surjection, Injection & a surjection,
hence a bijectionhence a bijection

31. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
31
Functions (2.3) (cont.)Functions (2.3) (cont.)
–Note: Whenever there is a bijection from A to
B, the two sets must have the same number
of elements
or the same cardinality.
–That will become our definition, especially for
infinite sets.

32. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
32
Functions (2.3) (cont.)Functions (2.3) (cont.)
–Examples:
Let A = B = R, the reals. Determine which are
injections, surjections, bijections:
• f(x) = x,
• f(x) = x
2
,
• f(x) = x
3
,
• f(x) = x + sin(x),
• f(x) = | x |

33. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
33
Functions (2.3) (cont.)Functions (2.3) (cont.)
–Let E be the set of even integers {0, 2, 4,
6, . . . .}.
Then there is a bijection f from N to E , the even
nonnegative integers, defined by
f(x) = 2x.
Hence, the set of even integers has the same
cardinality as the set of natural numbers.
OH, NO! IT CAN’T BE....E IS ONLY HALF AS BIG!!!
Sorry! It gets worse before it gets better.

34. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
34
Functions (2.3) (cont.)Functions (2.3) (cont.)
•Inverse Functions
–Definition:
Let f be a bijection from A to B. Then the
inverse of f, denoted f
-1
, is the function from
B to A defined as
f
-1
(y) = x iff f(x) = y

35. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
35
Functions (2.3) (cont.)Functions (2.3) (cont.)
–Example: Let f be defined by the diagram:
A B
a
b
c
d
X
Y
W
V
f A B
a
b
c
d
X
Y
W
V
f
-1
Note: No inverse exists Note: No inverse exists
unless f is a bijectionunless f is a bijection

36. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
36
Functions (2.3) (cont.)Functions (2.3) (cont.)
–Definition: Let S be a subset of B. Then
f-1(S) = {x | f(x)  S}
Note: f need not be a bijection for this
definition to hold.
–Example: Let f be the following function:
ff
-1-1
({Z}) = {c, d}({Z}) = {c, d}
ff
-1-1
({X, Y}) = {a, b}({X, Y}) = {a, b}
A B
a
b
c
d
X
Y
Z

37. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
37
Functions (2.3) (cont.)Functions (2.3) (cont.)
•Composition
–Definition:
Let f: B C, g: A B. The composition of f
with g, denoted fg, is the function from A to
C defined by
f  g(x) = f(g(x))

38. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
38
–Examples:
A B
a
b
c
d
X
Y
W
V
g
j
i
h
Cf
A
a
b
c
d
j
i
h
Cfg

39. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
39
Functions (2.3) (cont.)Functions (2.3) (cont.)
–If f(x) = x
2
and g(x) = 2x + 1, then f(g(x)) = (2x+1)
2

and g(f(x)) = 2x
2
+ 1
–Definition:
•The floor function, denoted f ( x) = x or
f(x) = floor(x), is the largest integer less than or equal to x.
•The ceiling function, denoted f ( x) = x or f(x) = ceiling(x),
is the smallest integer greater than or equal to x.

40. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
40
Functions (2.3) (cont.)Functions (2.3) (cont.)
–Examples: 3.5 = 3, 3.5 = 4.
Note: the floor function is equivalent to truncation for positive numbers.
–Example:
Suppose f: B  C, g: A  B and f  g is injective.
What can we say about f and g?
• We know that if a  b then f(g(a))  f(g(b)) since the composition is
injective.
• Since f is a function, it cannot be the case that g(a) = g(b) since
then f would have two different images for the same point.
• Hence, g(a)  g(b)
It follows that g must be an injection.
However, f need not be an injection (you show).

41. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
41
Sequences and Summations (2.4)Sequences and Summations (2.4)
•Definition: A sequence is a function from a subset of
the natural numbers (usually of the form {0, 1, 2, . . . }
to a set S.
Note: the sets
{0, 1, 2, 3, . . . , k} and {1, 2, 3, 4, . . . , k}
are called initial segments of N.
Notation: if f is a function from {0, 1, 2, . . .} to S we
usually denote f(i) by a
i
and we write
where k is the upper limit (usually ).
 
k
0i
k
0ii210
aa,...a,a,a 


42. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
42
Sequences and Summations (2.4) (cont.)Sequences and Summations (2.4) (cont.)
Examples:
Using zero-origin indexing, if f(i) = 1/(i + 1). then the
Sequence
f = {1, 1/'2,1/3,1/4, . . . } = {a
0, a
1, a
2, a
3, . . }
Using one-origin indexing the sequence f becomes
{1/2, 1/3, . . .} = {a
1, a
2, a
3, . . .}

43. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
43
Sequences and Summations (2.4) (cont.)Sequences and Summations (2.4) (cont.)
•Summation Notation
Given a sequence we can add
together a subset of the sequence by using
the summation and function notation
or more generally

Sj
j
a




n
mj
)j(g)n(g)1m(g)m(g
aa...aa

k
0i
a

44. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
44
Sequences and Summations (2.4) (cont.)Sequences and Summations (2.4) (cont.)
Examples:












Sj
10752j
n
mj
j2)n(2)1m(2m2
1
n
0
jn210
aaaaa then {2,5,7,10}S if
aa...aa
i
1
...
4
1
3
1
2
1
1
rr...rrr
Similarity for theSimilarity for the product product notation: notation:



n
mj
n1mmj
a...aaa

45. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
45
Sequences and Summations (2.4) (cont.)Sequences and Summations (2.4) (cont.)
Definition:

A geometric progression is a sequence of the form
a, ar, ar
2
, ar
3
, ar
4
, . . . .
Your book has a proof that
(you can figure out what it is if r = 1).
You should also be able to determine the sum
• if the index starts at k vs. 0
• if the index ends at something other than n
(e.g., n-1, n+1, etc.).
1r if
1r
1r
r
n
0i
1n
i







46. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
46
Sequences and Summations (2.4) (cont.)Sequences and Summations (2.4) (cont.)
•Cardinality
–Definition:
The cardinality of a set A is equal to the cardinality
of a set B, denoted
| A | = | B |,
if there exists a bijection from A to B.

47. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
47
Sequences and Summations (2.4)Sequences and Summations (2.4)
–Definition:
If a set has the same cardinality as a subset of
the natural numbers N, then the set is called
countable.
If |A| = |N|, the set A is countably infinite.
The (transfinite) cardinal number of the set N is
aleph null = 
0.
If a set is not countable we say it is uncountable.

48. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
48
Sequences and Summations (2.4)Sequences and Summations (2.4)
–Examples:
The following sets are uncountable (we show later)
•The real numbers in [0, 1]
•P(N), the power set of N
–Note: With infinite sets proper subsets can have the
same cardinality. This cannot happen with finite sets.
Countability carries with it the implication that there is
a listing of the elements of the set.

49. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
49
Sequences and Summations (2.4)Sequences and Summations (2.4)
–Definition: | A |  | B | if there is an injection from A to B.
Note: as you would hope,
–Theorem:
If | A |  | B | and | B |  | A | then | A | = | B |.
This implies
•if there is an injection from A to B
•if there is an injection from B to A
then
•there must be a bijection from A to B
–This is difficult to prove but is an example of demonstrating existence
without construction.
–It is often easier to build the injections and then conclude the bijection
exists.

50. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
50
Sequences and Summations (2.4)Sequences and Summations (2.4)
–Example:
Theorem: If A is a subset of B then | A |  | B |.
Proof: the function f(x) = x is an injection from A to B.
–Example: {0, 2, 5}|  
0
The injection f: {0, 2, 5}  N defined by f(x) = x is
shown below:
0 1 2 3 4 5 6 …0 1 2 3 4 5 6 …
0 2 50 2 5

51. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
51
Sequences and Summations (2.4)Sequences and Summations (2.4)
•Some Countably Infinite Sets
–The set of even integers E ( 0 is considered even) is
countably infinite. Note that E is a proper subset of N,
Proof: Let f(x) = 2x. Then f is a bijection from N to E
–Z
+
, the set of positive integers is countably infinite.
0 1 2 3 4 5 6 …0 1 2 3 4 5 6 …
0 2 4 6 8 10 12 …0 2 4 6 8 10 12 …

52. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
52
Sequences and Summations (2.4)Sequences and Summations (2.4)
–The set of positive rational numbers Q
+
is
countably infinite.
Proof: Z
+
is a subset of Q
+
so |Z
+
| = 
0  |Q
+
|.
Now we have to show that |Q
+
|  
0.
To do this we show that the positive rational
numbers with repetitions, Q
R, is countably infinite.
Then, since Q
+
is a subset of Q
R, it follows that
|Q
+
|  
0
and hence |Q
+
| = 
0
.

53. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
53
Sequences and Summations (2.4)Sequences and Summations (2.4)

54. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
54
Sequences and Summations (2.4)Sequences and Summations (2.4)
–The position on the path (listing) indicates the
image of the bijective function f from N to Q
R:
f(0) = 1/1, f(1) = 1/2, f(2) = 2/1, f(3) = 3/1, and so forth.
Every rational number appears on the list at least once,
some many times (repetitions).
Hence, |N| = |Q
R| = 
0. Q. E. D
–The set of all rational numbers Q, positive and
negative, is countably infinite.

55. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
55
Sequences and Summations (2.4)Sequences and Summations (2.4)
–The set of (finite length) strings S over a finite alphabet A is
countably infinite.
To show this we assume that
•A is nonvoid
•There is an “alphabetical” ordering of the symbols in A
Proof: List the strings in lexicographic order:
•all the strings of zero length,
•then all the strings of length 1 in alphabetical order,
•then all the strings of length 2 in alphabetical order,
etc.
This implies a bijection from N to the list of strings and hence it is a
countably infinite set.

56. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
56
Sequences and Summations (2.4)Sequences and Summations (2.4)
–For example:
Let A = {a, b, c}.
Then the lexicographic ordering of A is
{ , a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa,
aab,
aac, aba, ....} = {f(0), f(1), f(2), f(3), f(4), . . . .}

57. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
57
Sequences and Summations (2.4)Sequences and Summations (2.4)
–The set of all C programs is countable.
Proof: Let S be the set of legitimate characters which can appear in a
C program.
•A C compiler will determine if an input program is a syntactically correct C
program (the program doesn't have to do anything useful).
•Use the lexicographic ordering of S and feed the strings into the compiler.
–If the compiler says YES, this is a syntactically correct C program, we add the
program to the list.
–Else we move on to the next string.
–In this way we construct a list or an implied bijection from N to the set
of C programs.
–Hence, the set of C programs is countable. Q. E. D.

58. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
58
Sequences and Summations (2.4)Sequences and Summations (2.4)
•Cantor Diagonalization
–An important technique used to construct an object which is not a
member of a countable set of objects with (possibly) infinite
descriptions
Theorem: The set of real numbers between 0 and 1 is uncountable.
Proof: We assume that it is countable and derive a contradiction.
If it is countable we can list them (i.e., there is a bijection from a
subset of N to the set).
We show that no matter what list you produce we can construct a
real number between 0 and 1 which is not in the list.
Hence, there cannot exist a list and therefore the set is not countable

59. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
59
Sequences and Summations (2.4)Sequences and Summations (2.4)
It's actually much bigger than countable. It is said to
have the cardinality of the continuum, c.
Represent each real number in the list using its
decimal expansion.
e.g., 1/3 = .3333333........
1/2 = .5000000........
= .4999999........
If there is more than one expansion for a number, it
doesn't matter as long as our construction takes
this into account.

60. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
60
Sequences and Summations (2.4)Sequences and Summations (2.4)
–THE LIST....
r
1 = .d
11d
12d
13d
14d
15d
16. . . . .
r
2
= .d
21
d
22
d
23
d
24
d
25
d
26
. . . .
r
3 = .d
31d
32d
33d
34d
35d
36 . . . .
...
Now construct the number x = .x
1x
2x
3x
4x
5x
6x
7. . . .
x
i = 3 if d
ii  3
x
i = 4 if d
ii = 3
(Note: choosing 0 and 9 is not a good idea because of the non uniqueness of
decimal expansions.)
Then x is not equal to any number in the list.
Hence, no such list can exist and hence the interval (0,1) is uncountable.
Q. E. D.

61. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
61
Sequences and Summations (2.4)Sequences and Summations (2.4)
–An extra goody:
Definition: a number x between 0 and 1 is
computable if there is a C program which when given
the input i, will produce the ith digit in the decimal
expansion of x.
–Example:
The number 1/3 is computable.
The C program which always outputs the digit 3,
regardless if the input, computes the number.

62. © by Kenneth H. Rosen, Discrete Mathematics & its Applications, Seventh Edition, Mc Graw-Hill, 2011
CSE 504, Ch.1 (part 3): The foundations:
Logic & Proof, Sets, and Functions
62
Sequences and Summations (2.4)Sequences and Summations (2.4)
Theorem: There is exists a number x between 0 and 1
which is not computable.
There does not exist a C program (or a program in any
other language) which will compute it!
Why? Because there are more numbers between 0 and
1 than there are C programs to compute them.
(in fact there are c such numbers!)
Our second example of the nonexistence of programs
to compute things!