CS 441 Discrete Mathematics for CS
                                                         Lecture 11
                                           Countable and uncountable sets.        
                                                          Matrices. 
                               Milos Hauskrecht
                               milos@cs.pitt.edu
                               5329 Sennott Square
                                                     CS 441 Discrete mathematics for CS    M. Hauskrecht
                                                    Arithmetic series
                               Definition: The sum of the terms of the arithmetic progression
                                  a, a+d,a+2d, …, a+nd is called an arithmetic series. 
                               Theorem:The sum of the terms of the arithmetic progression
                                  a, a+d,a+2d, …, a+nd is
                                           n                  n           n(n1)
                                       S    (a jd)  nad     j  na  d
                                          
                                                                             2
                                           j11j
                                                     CS 441 Discrete mathematics for CS    M. Hauskrecht
                                                                                                                          1
                                                                                        Geometric series
                                                     Definition: The sum of the terms of a geometric progression a, ar, 
                                                          ar2, ..., ark is called a geometric series.
                                                     Theorem:The sum of the terms of a geometric progression a, ar, 
                                                          ar2, ..., arn is
                                                                                 n                  n           rn1 1
                                                                         S          (arj)       a      r j    a
                                                                                                          
                                                                               
                                                                                                                 r1 
                                                                                j00j
                                                                                                                            
                                                                                          CS 441 Discrete mathematics for CS                               M. Hauskrecht
                                                                               Infinite geometric series
                                                     •    Infinite geometric series can be computed in the closed form 
                                                          for x<1
                                                     •    How?
                                                                                         k                           xk1 1                  1             1
                                                          xn lim                      xn lim                                                    
                                                                                k                           k        x 1                x 1         1x
                                                          n0                           n0
                                                     •    Thus:
                                                                                                     1
                                                                                xn 
                                                                               n  0              1  x
                                                                                          CS 441 Discrete mathematics for CS                               M. Hauskrecht
                                                                                                                                                                                                                2
                                                           Cardinality
                                 Recall: The cardinality of a finite set is defined by the number of 
                                    elements in the set. 
                                 Definition: The sets A and B have the same cardinality if there is 
                                    a one-to-one correspondence between elements in A and B. In 
                                    other words if there is a bijection from A to B. Recall bijection is 
                                    one-to-one and onto.
                                 Example:  Assume A = {a,b,c} and B = {α,β,γ}
                                    and function f defined as: 
                                         •a α
                                         •b β
                                         •c γ
                                 F defines a bijection. Therefore A and B have the same cardinality, 
                                    i.e. | A | = | B | = 3.
                                                        CS 441 Discrete mathematics for CS       M. Hauskrecht
                                                           Cardinality
                                 Definition: A set that is either finite or has the same cardinality as 
                                                                   +
                                    the set of positive integers Z   is called countable. A set that is 
                                    not countable is called uncountable.
                                 Why these are called countable? 
                                 •  The elements of the set can be enumerated and listed.
                                                        CS 441 Discrete mathematics for CS       M. Hauskrecht
                                                                                                                                 3
                                                         Countable sets
                                 Example:
                                 •  Assume A = {0, 2, 4, 6, ... } set of even numbers. Is it 
                                    countable? 
                                                        CS 441 Discrete mathematics for CS       M. Hauskrecht
                                                         Countable sets
                                 Example:
                                 •  Assume A = {0, 2, 4, 6, ... } set of even numbers. Is it 
                                    countable? 
                                                                                             +
                                 •  Using the definition: Is there a bijective function f: Z  A 
                                 Z+ = {1, 2, 3, 4, …}
                                                        CS 441 Discrete mathematics for CS       M. Hauskrecht
                                                                                                                                 4