Discrete Mathematics – Chap.

Discrete Mathematics – Chap. 2

Basic Structures : Sets, Functions, Sequences, Sums, and Matrices

University of Seoul
Department of Mathematics
Jaechul Sung
(jcsung@[Link])

Dept. of Mathematics, Jaechul Sung

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices

Contents of this chapter

2.1 Sets
2.2 Set operations
2.3 Functions
2.4 Sequences and summations
2.5 Cardinality of sets
2.6 Matrices

Dept. of Mathematics, Jaechul Sung 2

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.1 Sets

2.1 Sets
[Def.] A set is unordered collection of objects.
[Def.] The object in a set are called the elements or members,
of the set. A set is said to contain its elements.
 N ={1, 2, . . . } : the set of natural numbers.
 Z ={. . . ,-2, -1, 0, 1, 2, . . . } : the set of integers.
 Z+ ={1, 2, . . . } : the set of positive integers.
 Q ={ p/q | pZ, q Z, q≠0} : the set of rational numbers.
 R : the set of real numbers.
[Def.] Two sets are equal if and only if they have the same
elements.
Dept. of Mathematics, Jaechul Sung 3
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.1 Sets

Empty set / Singleton set / Subset

 Empty set (null set) : a set that has no elements
- a set that has no elements
- denoted by { } or Ø
 Singleton set : a set with one element
 The set A is said to be a subset of B if and only if every
element of A is also an element of B. We use the notation
A  B to indicate that A is a subset of the set B.
- x (x  A  x  B) is true.
- A is proper subset of B if A is a subset of B but A ≠ B.

[Theorem] For any set S, (i) Ø  S, (ii) S  S.

Dept. of Mathematics, Jaechul Sung 4
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.1 Sets

Finite set / Infinite set / Power set

[Def.] Let S be a set. If there are exactly n distinct elements
in S where n is a nonnegative integer, we say that S is a
finite set and that n is the cardinality of S. The cardinality
of S is denoted by |S|.
[Def.] A set is said to be infinite if it is not finite.
[Def.] Given a set S, the power set of S is the set of all
subsets of the set S. The power set of S is denoted by P(S).
[Ex.11 (p.82)] What is the power set of the set {0,1,2} ?
Sol.) P({0,1,2}) = {Ø,{0},{1},{2},{0.1},{1,2},{2,3},{1,2,3}}

Dept. of Mathematics, Jaechul Sung 5

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.1 Sets

Cartesian products
[Def.] Let ordered n-tuple (a1, a2, . . . , an) is the ordered
collection that has a1 as its first element, a2 as its second
element, . . ., and an as its nth element.
[Def.] Let A and B be sets. The Cartesian product of A and B,
denoted by A  B, is the set of all ordered pairs (a, b) where
a  A and b  B. Hence,
A  B = {(a, b) | a  A  b  B}.
[Def.] The Cartesian product of A1, A2,. . ., An, denoted by A1 
A2  ꞏ ꞏ ꞏ  An, is the set of ordered n-tuples (a1, a2, . . ., an),
where ai  Ai for i = 1, 2, …, n. In other words
A1A2 ꞏ ꞏ ꞏ An = {(a1,a2, . . . ,an) | ai  Ai for i = 1, 2, …, n}.
Dept. of Mathematics, Jaechul Sung 6
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.2 Set operations

2.2 Set operations

[Def.] Let A and B be sets. The union of the sets A and B,
denoted by A  B, is the set that contains those elements
that are either in A or in B, or in both.
 Examples
- {1, 3, 5}  {1, 2, 3} = {1, 2, 3, 5}
- {a, b}  Ø = {a, b}

[Def.] Let A and B be sets. The intersection of the sets A

and B, denoted by A  B, is the set containing those
elements in both A and B.
 Examples
- {1, 3, 5}  {1, 2, 3} = {1, 3}
- {a, b}  Ø = Ø
Dept. of Mathematics, Jaechul Sung 7
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.2 Set operations

Venn diagram
 In a generic Venn diagram for a subset
U
S of a fixed universal set U, the
universal set is represented by a
S
rectangular region in the plane and the
set S is represented by a subregion.

 Venn diagram of A  B and A  B

U U

A B A B

☞ Two sets are called disjoint if their intersection is the empty set.
Dept. of Mathematics, Jaechul Sung 8
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.2 Set operations

Difference / Complement
[Def.] Let A and B be sets. The difference of the sets A and
B, denoted by A  B, is the set containing those elements
that are in A but not in B. The difference A and B is also
called the complement of B with respect to A.
 Example
- {1, 3, 5}  {1, 2, 3} = {5} , {a, b} - Ø = {a, b}

[Def.] Let U be the universal set. The complement of the A,

denoted by A, is the complement of A with respect to U.
In other words, the complement of the set A is U  A.
 Example
- U = {1, 2, 3, 4, 5, 6}, {1, 3, 5} = {2, 4, 6}, Ø = U
Dept. of Mathematics, Jaechul Sung 9
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.2 Set operations

Set identity rules

Name Identity Name Identity

Identity A Ø=A Associative A(BC) = (AB)C

laws A U=A laws A(BC) = (AB)C

Domination A U=U Distributive A(BC)=(AB)(AC)

laws A Ø= Ø laws A(BC)=(AB)(AC)

Idempotent AA=A De Morgan’s A  B = A  B

laws AA=A laws A B=AB
Complementation Absorption A  (A  B) = A
laws (A) = A
laws A  (A  B) = A
Commutative A B= B A Complement AA= U
laws A B= B A laws AA= Ø
Dept. of Mathematics, Jaechul Sung 10
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.2 Set operations

Generalized unions and intersections

 The unions and intersection of A, B, and C
U U
A B A B

C C

[Def.] The union of a collection of sets is the set that contains

those elements that are members ofn at least one set in the
collection. A1  A2  ꞏ ꞏ ꞏ  An =  Ai
i =1
[Def.] The intersection of a collection of sets is the set that
contains those elements that are membersn
of all the set in
the collection. A1  A2  ꞏ ꞏ ꞏ  An =i =1
 Ai
Dept. of Mathematics, Jaechul Sung 11
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.2 Set operations

Computer representation of sets

 Assume that the universal set U ={a1,a2, . . . ,an} is finite.
Represent a subset A of U with the bit string of length n,
where the i-th bit in this string is 1 if ai belongs to A and
0 if ai does not belong to A.

 Examples
- U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} , ai = i
- A = { 1, 3, 5, 7, 9} 1010101010
- B = { 1, 2, 3, 4, 9} 1111000010

Dept. of Mathematics, Jaechul Sung 12

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.3 Functions

2.3 Functions
[Def.] Let A and B be sets. A function f from A to B is an assignment
of exactly one element of B to each element of A. We write f(a) = b
if b is the unique element of B assigned by the function f to the
element a of A. If f is a function from A to B, we write f : A  B.
- We say that f : A  B a mapping from domain A to codomain B.
- We say that f(a) is called the image of the element of a, and the element a is
called a preimage of f(a). The word range is commonly used the image.

f A B
• •
f • •
a• • • y
b •
•
• •
x
Dept. of Mathematics, Jaechul Sung 13
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.3 Functions

One-to-one and onto functions

[Def.] A function f : A  B is said to be one-to-one (or
injective) if for every b  B, there is at most one a  A
such that f(a) = b.
[Def.] A function f : A  B is said to be onto (or surjective)
if for every b  B, there is at least onc a  A such that
f(a) = b.
[Def.] A function f : A  B is said to be one-to-one
correspondence (or bijection) if it is both one-to-one and
onto.

Dept. of Mathematics, Jaechul Sung 14

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.3 Functions

Examples of different types of correspondences

(a) one-to-one, (b) onto, (c) one-to-one,
not onto not one-to-one and onto
1 a a 1
a 1
2 b b 2
b 2
3 c c 3
c 3
4 d d 4

(d) Neither one-to-one, (e) Not a function

nor onto
a 1 1
a
b 2 2
b
c 3 3
c
d 4 4

Dept. of Mathematics, Jaechul Sung 15

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.3 Functions

Inverse functions
[Def.] Let f : A  B be a bijection. The inverse function
f 1 : B  A is the rule that assign to each b  B the
unique element a  A such that f(a) = b.

f 1(b)

a = f 1(b) b = f (a)
f (a)

f 1
A B

f
Dept. of Mathematics, Jaechul Sung 16
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.3 Functions

Composition functions
[Def.] Let g: A  B and f : B  C be functions. The
composition function f ◦ g : A  C is defined by
(f ◦ g) (a) = f (g(a)) .
(f ◦ g) (a)

g (a) f (g(a))

a a a

g f
A B C

f◦g

Dept. of Mathematics, Jaechul Sung 17

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.3 Functions

Some functions – floor and ceiling fts

[Def.] The floor function ꞏ:R→Z,
where x (“floor of x”) means the 3
2 .1.6=2
largest (most positive) integer  x. 1.6 .
1 .
I.e., x :≡ max ( { i  Z | i ≤ x } ). 1.6=1

0
[Def.] The ceiling function ꞏ :R→Z, 1.4= 1
.
1 1.4.
where x (“ceiling of x”) means the .
smallest (most negative) integer  x. 2 1.4= 2
3. . .
I.e., x :≡ min ( { i  Z | i ≥ x } ). 3 3=3= 3

☞ If x  Z, x   x & x   x .

If x  Z, x = x = x.
Dept. of Mathematics, Jaechul Sung 18
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.3 Functions

Useful properties of the floor and ceiling fts

No Useful properties of the floor and ceiling functions
(1a) x = n if and only if n ≤ x < n + 1
(1b) x = n if and only if n  1 < x ≤ n
(1c) x = n if and only if x  1 < n ≤ x
(1d) x = n if and only if x ≤ n < x + 1
(2) x  1 < x ≤ x ≤ x < x + 1
(3a)  x =  x
(3b)  x =  x
(4a)  x + n  = x + n
(4b)  x + n  = x + n

Dept. of Mathematics, Jaechul Sung 19

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.3 Functions

An example of ceiling functions

[Ex.24 (p.107)] Prove that if x is a real number, then
2x = x + x + ½ 
Sol.)
Let x = n + є , where n is a positive integer and 0 ≤ є < 1. Then
there are two cases to consider depending whether є is less than ½.
CASE 1 : 0 ≤ є < ½
In this case, 2x = 2n + 2є and 2x = 2n.
Similarly, x + x + ½  = n + n = 2n.
CASE 2 : ½ ≤ є < 1
In this case, 2x = 2n + 2є and 2x = 2n + 1.
Similarly, x + x + ½  = n + (n +1) = 2n + 1.
Dept. of Mathematics, Jaechul Sung 20
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.4 Seq. & summations

2.4 Sequences and summations

[Def.] A sequence is a function from a subset of the set of
integers (usually {0, 1, 2, . . .}, {1, 2, 3, . . . }) to a set S.
We use the notation an to denote the image of the integer n.
We call an an term of the sequence,

 Geometric progression : a, ar, ar2, . . . , arn

 Arithmetic progression : a, a + r, a + 2r, , . . . , a + nr

 A string is a sequence in an alphabet (a1a2 ꞏ ꞏ ꞏ an).

- The empty string, denoted by λ, is the string that has no terms.

Dept. of Mathematics, Jaechul Sung 21

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.4 Seq. & summations

Special integer sequences

 Given some initial terms a1 , a2 , ꞏ ꞏ ꞏ , ak of a sequence,
try to construct a rule that is consistent with those terms.
 There are two rules for calculating a generic term ak.
- Recursion for an : a function whose arguments are earlier
terms in the sequence.
- Closed form for an : a formula whose argument is the
subscript n.

 Example : 1, 3, 5, 7, 9, 11, . . .
- recursion : a1 = 1, an+1 = an + 2 for n ≥ 1.
- closed form : an = 2n − 1.

Dept. of Mathematics, Jaechul Sung 22

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.4 Seq. & summations

Some useful sequences

nth term First 10 terms

n2 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, . . .

n3 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, . . .

n4 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000, . . .

2n 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, . . .

3n 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59047, . . .

n! 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, . . .

Dept. of Mathematics, Jaechul Sung 23

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.4 Seq. & summations

Summations
[Def.] Given a series {an}, an integer lower limit j  0, and
an integer upper limit k  j, then the summation of {an}
from j to k is written and defined as follows:
k

 a : a
i j
i j  a j 1  ...  ak

 Here, i is called the index of summation.

[Theorem] If a and r are real numbers and r ≠ 0, then

n

 
ar j

j 0
(arn+1 – a) / (r – 1) if r ≠ 1

(n+1)a if r = 1.
Dept. of Mathematics, Jaechul Sung 24
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.5 Cardinality of Sets

2.5 Cardinality of Sets

[Def.] The sets A and B have the same cardinality if and
only if there is a one-to-one correspondence from A to B.

[Def.] A set that is either finite or has the same cardinality

as the set of positive integers is called countable. A set
that is not countable is called uncountable.

 The cardinality of N is ω(omega) or 0(aleph null).

 0 is the smallest infinite cardinality (N, Z, Q).
 1 is the cardinality of real numbers (R).

Dept. of Mathematics, Jaechul Sung 25

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.5 Cardinality of Sets

Rational numbers is countable

[Theorem] The set of positive rational numbers is countable.
Proof :

1/1 1/2 1/3 1/4 1/5 . . .

2/1 2/2 2/3 2/4 2/5 . . .

3/1 3/2 3/3 3/4 3/5 . . .

4/1 4/2 4/3 4/4 4/5 . . .

5/1 5/2 5/3 5/4 5/5 . . .

Dept. of Mathematics, Jaechul Sung 26

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.5 Cardinality of Sets

Uncountable set
[Theorem] The set of real numbers is uncountable.
Proof :
Suppose that the set of real numbers is countable.
Then, the subset of all real numbers that fall between 0 and 1 would
also be countable. The real numbers in [0, 1) can be listed in some
order, say r1, r2, r3, . . . . Let the decimal representation of these real
numbers be the following ;
r1 = 0.d1,1 d1,2 d1,3 d1,4 d1,5 d1,6 d1,7 d1,8…
r2 = 0.d2,1 d2,2 d2,3 d2,4 d2,5 d2,6 d2,7 d2,8…
r3 = 0.d3,1 d3,2 d3,3 d3,4 d3,5 d3,6 d3,7 d3,8…
r4 = 0.d4,1 d4,2 d4,3 d4,4 d4,5 d4,6 d4,7 d4,8…
Consider a real number r generated by taking all the digits di,i that lie
along the diagonal in this figure and replacing them with different
digits. The number r is not in r1, r2, r3, . . . , which is contradiction.
Dept. of Mathematics, Jaechul Sung 27
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.6 Matrices

2.6 Matrices
 For A matrix is a rectangular array
of objects (usually numbers).
 An m  n (“m by n”) matrix has
exactly m horizontal rows, and n
vertical columns.
 An n  n matrix is called a square
matrix, whose order or rank is n.
 Application of matrix
- Solving systems of linear equations
- Computer Graphics, Image Processing
- Quantum Mechanics, Quantum Computing
- and so on.

Dept. of Mathematics, Jaechul Sung 28

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.6 Matrices

Matrix arithmatic
 Matrix notation  a1,1 a1, 2  a1,n 
a a2 , 2  a2,n 
A  [ai , j ]  
2 ,1

     
 
am,1 am , 2  am , n 
 Matrix addition : already known

A + B = [ai,j+bi,j]

 Matrix multiplication : already known

k 
AB  C  [ci , j ]   ai , b , j 
  1 

Dept. of Mathematics, Jaechul Sung 29

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.6 Matrices

Matrix transposes and powers of matrices

 If A=[aij] is an mn matrix, the transpose of A (often
written At or AT) is the nm matrix given by At = B = [bij]
= [aji] (1in,1jm)

 A is symmetric if A = At

 If A is an nn square matrix and p0, then:

Ap : AAAꞏꞏꞏA (and A0 : In)

Dept. of Mathematics, Jaechul Sung 30

Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.6 Matrices

Zero-One matrices
 Useful for representing other structures.
- E.g., relations, directed graphs (later in this course)

 All elements of a zero-one matrix are either 0 or 1

- Representing False & True respectively.

 The join of A, B (both mn zero-one matrices):

- AB : [aijbij] The 1’s in A join the 1’s in
B to make up the 1’s in C.
 The meet of A, B:
Where the 1’s in A meet the
- AB : [aijbij] = [aij bij]
1’s in B, we find 1’s in C.
Dept. of Mathematics, Jaechul Sung 31
Discrete Mathematics – Chap.2 Basic Structures : Sets, Functions, Sequences, Sums, and Matrices - 2.6 Matrices

Boolean product of zero-one matrices

 A = [aij] : an mk zero-one matrix.
B = [bij] : a kn zero-one matrix.
 The boolean product of A and B is like normal matrix , but using
 instead of + in the row-column “vector dot product”:

A⊙B  C  [ cij ] 
 k

  1
( ai b )
j 


 Example
(1  1)  (0  0) (1  1)  (0  1) (1  0)  (0  1)
A⊙B = (0  1)  (1  0) (0  1)  (1  1) (0  0)  (1  1)
 
1 0
(1  1)  (0  0) (1  1)  (0  1) (1  0)  (0  1)
1 1 0
A   0 1  B  
 0 1 1
 1 0  1 1 0 
0 1 1 
=  
1 1 0

Dept. of Mathematics, Jaechul Sung 32