Chapter Summary
Sets
- The Language of Sets, Set Operations
Functions
- Types of Functions, Operations on Functions
Sequences and Summations
- Types of Sequences, Summation Formulae
Matrices
- Matrix Arithmetic
Sets
Introduction
Sets are one of the basic building blocks for the types of objects considered in discrete mathematics.
- Important for counting.
- Programming languages have set operations.
Set theory is an important branch of mathematics.
- Many different systems of axioms have been used to develop set theory
- Here we are not concerned with a formal set of axioms for set theory. Instead, we will use what is called naïve set theory
Definition
A set is an unordered collection of objects.
The notation a ∈ A denotes that a is an element of the set A.
If a is not a member of A, write a ∉ A.
Describing a Set: Roster Method
- S = {a,b,c,d}
Order not important.
- S = {a,b,c,d} = {b,c,a,d}
Each distinct object is either a member or not; listing more than once does not change the set
- S = {a,b,c,d} = {a,b,c,b,c,d}
Ellipses (…) may be used to describe a set without listing all of the members when the pattern is clear.
- S = {a,b,c,d, ……,z }
Some Important Sets
N = natural numbers = {0,1,2,3….}
Z = integers = {…,-3,-2,-1,0,1,2,3,…}
$Z^{+}$ = positive integers = {1,2,3,…..}
R = set of real numbers
$R^{+}$ = set of positive real numbers
C = set of complex numbers
Q = set of rational numbers
Describing a Set: Set-Builder Notation
Specify the property or properties that all members must satisfy :
S = {x | x is a positive integer less than 100}
O = {x | x is an odd positive integer less than 10}
O = {x ∈ Z⁺ | x is odd and x < 10}
A predicate may be used :
S = {x | P(x)}
Interval Notation
[a,b] = {x | a ≤ x ≤ b}
[a,b) = {x | a ≤ x < b}
(a,b] = {x | a < x ≤ b}
(a,b) = {x | a < x < b}
closed interval [a,b]
open interval (a,b)
Universal Set and Empty Set
The universal set U is the set containing everything currently under consideration.
The empty set(null set)is the set with no elements. Symbolized ∅, but {} also used.
Some things to remember
Sets can be elements of sets.
{{1,2,3},a, {b,c}}
{N,Z,Q,R}
The empty set is different from a set containing the empty set.
∅ ≠ { ∅ }
Set Equality
Definition: Two sets are equal if and only if they have the same elements.
Therefore if A and B are sets, then A and B are equal if and only if $ \forall x (x \in A \leftrightarrow x \in B ) $
Venn Diagrams
Sets can be represented graphically using Venn iagrams, named after the English mathematician John Venn, who introduced their use in 1881.
In Venn diagrams the universal set U, which contains all the objects under consideration, is represented by a rectangle.
Subsets
Definition: The set A is a subset of B, if and only if every element of A is also an element of B.
The notation A ⊆ B is used to indicate that A is a subset of the set B.
A ⊆ B holds if and only if $ \forall x (x \in A \rightarrow x \in B) $ is true.
Another look at Equality of Sets
Recall that two sets A and B are equal, denoted by A = B, iff
$$ \forall x (x \in A \leftrightarrow x \in B) $$
Using logical equivalences we have that A = B iff
$$ \forall x [(x \in A \rightarrow x \in B) \wedge (x \in B \rightarrow x \in A)] $$
This is equivalent to
$$ A \subseteq B \ and \ B \subseteq A $$
Proper Subsets
Definition: If A ⊆ B, but A ≠ B, then we say A is a proper subset of B, denoted by A ⊂ B. If A ⊂ B, then
$$ \forall x (x \in A \rightarrow x \in B) \wedge \exist x (x \in B \wedge x \notin A) $$
is ture.
Set Cardinality
Definition : If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is finite. Otherwise it is infinite.
Definition: The cardinality of a finite set A, denoted by |A|, is the number of (distinct) elements of A.
Examples:
- |ø| = 0
- Let S be the letters of the English alphabet. Then |S| = 26
- |{1,2,3}| = 3
- |{ø}| = 1
- The set of integers is infinite.
Power Sets
Definition: The set of all subsets of a set A, denoted $ \mathcal{P} (A) $, is called the power set of A.
Example: If A = {a,b} then
$$ \mathcal{P} (A) = \{ \varnothing, \{ a \}, \{ b \}, \{ a, b \} \} $$
If a set has n elements, then the cardinality of the power set is $ 2^{n} $.
Let’ s look at the same example in another way
Example: If A = {a,b} then $ \mathcal{P} (A) $ = {ø, {a},{b},{a,b}}
Use binary digit 1 to indicate an element is contained in a subset; use binary digit 0 to indicate an element is not contained in a subset.
00 – neither a nor b is contained in a subset. ø
01 – b, not a, is contained in a subset. {b}
10 – a, not b, is contained in a subset. {a}
11 – both a or b is contained in a subset. {a,b}
Ordered n-Tuples
The ordered n-tuple $ (a_{1}, a_{2}, ..., a_{n}) $ is the ordered collection that has $a_{1}$ as its first element and $a_{2}$ as its second element and so on until an as its last element.
2-tuples are called ordered pairs.
The ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.
Cartesian Product
Definition: The Cartesian Product of two sets A and B, denoted by A × B is the set of ordered pairs (a,b) where a ∈ A and b ∈ B .
$$ A \times B = \{(a,b) | a \in A \wedge b \in B\} $$
Example :
A = {a,b} B = {1,2,3}
A × B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}
Definition: The cartesian products of the sets $ A_{1}, A_{2}, …, A_{n} $, denoted by $ A_{1} \times A_{2} \times … \times A_{n} $, is the set of ordered n-tuples $ (a_{1}, a_{2}, …, a_{n}) $ where $a_{i}$ belongs to $A_{i}$ for i = 1, … n.
$$ A_{1} \times A_{2} \times ··· \times A_{n} = \{ (a_{1}, a_{2}, ···， a_{n}) | a_{i} \in A_{i} for \ i = 1, 2, ···, n \} $$
Set Operations
Boolean Algebra
Propositional calculus and set theory are both instances of an algebraic system called a Boolean Algebra.
The operators in set theory are analogous to the corresponding operator in propositional calculus.
As always there must be a universal set U. All sets are assumed to be subsets of U.
Union
Union: ∪ ∨ OR +
Definition: Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set:
$$ \{ x | x \in A \vee x \in B \} $$
Intersection
Intersection: ∩ ∧ AND
Definition: The intersection of sets A and B, denoted by A ∩ B, is
$$ \{ x | x \in A \wedge x \in B \} $$
Note if the intersection is empty, then A and B are said to be disjoint.
Complement
Complement: ¯ ¬ NOT
Definition: If A is a set, then the complement of the A (with respect to U), denoted by Ā is the set U - A
$$ \bar{x} = \{x \in U \ | \ x \notin A\} $$
(The complement of A is sometimes denoted by $A^{c}$.)
Difference
Definition: Let A and B be sets. The difference of A and B, denoted by A – B, is the set containing the elements of A that are not in B. The difference of A and B is also called the complement of B with respect to A.
$$ A - B = \{ x \ | \ x \in A \wedge x \notin B \} = A \cap \bar{B} $$
Example: If U = {1,2,3,4,5} A = {1,2, 4}, and B ={4,5}, what is A – B and B – A ?
Solution:
A – B = {1,2}
B – A = {5}
Review Questions
Example: U = {0,1,2,3,4,5,6,7,8,9,10} A = {1,2,3,4,5} B ={4,5,6,7,8}
$A \cup B$
Solution: {1,2,3,4,5,6,7,8}
$A \cap B$
Solution: {4,5}
$\overline{A}$
Solution: {0,6,7,8,9,10}
$\overline{B}$
Solution: {0,1,2,3,9,10}
A – B
Solution: {1,2,3}
B – A
Solution: {6,7,8}
The Cardinality of the Union of Two Sets
Inclusion-Exclusion
|A ∪ B| = |A| + |B| − |A ∩ B|
Set Identities
- Identity laws
$$ A \cup \varnothing = A \\ A \cap U = A $$
- Domination laws
$$ A \cup U = A \\ A \cap \varnothing = \varnothing $$
- Idempotent laws
$$ A \cup A = A \\ A \cap A = A $$
- Complementation law
$$ \overline{(\overline{A})} = A $$
- Commutative laws
$$ A \cup B = B \cup A \\ A \cap B = B \cap B $$
- Associative laws
$$ A \cup (B \cup C) = (A \cup B) \cup C \\ A \cap (B \cap C) = (A \cap B) \cap C $$
Distributive laws
$$ A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \\ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) $$
De Morgan’s laws
$$ \overline{A \cup B} = \overline{A} \cap \overline{B} \\ \overline{A \cap B} = \overline{A} \cup \overline{B} $$
Absorption laws
$$ A \cup (A \cap B) = A \\ A \cap (A \cup B) = A $$
Complement laws
$$ A \cup \overline{A} = U \\ A \cap \overline{A} = \varnothing $$
Membership Table
Example: Construct a membership table to show that the distributive law holds.
$$ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) $$
Solution:
| A | B | C | $ B \cap C $ | $ A \cup (B \cap C) $ | $ A \cup B $ | $ A \cup C $ | $ (A \cup B) \cap (A \cup C) $ |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Generalized Unions and Intersections
Let $ A_{1}, A_{2}, ..., A_{n} $ be an indexed collection of sets.
We define:
$$ \bigcup_{i = 1}^{n} A_{i} = A_{1} \cup A_{2} \cup ... \cup A_{n} \\ \bigcap_{i = 1}^{n} A_{i} = A_{1} \cap A_{2} \cap ... \cap A_{n} $$
Computer Representation of Sets
First, specify an arbitrary ordering of the elements of U, for instance $a_{1}, a_{2}, ..., a_{n}$. Represent a subset A of U with the bit string of length n, where the ith bit in this string is 1 if ai belongs to A and is 0 if ai does not belong to A.
Example: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order.
What bit strings represent the subset of all odd integers in U?
10 1010 1010
What bit strings represent the subset of all even integers in U?
01 0101 0101
What bit strings represent the subset of integers not exceeding 5 in U?
11 1110 0000
Functions
Definition: Let A and B be nonempty sets. A function $f$ from A to B, denoted $f: A \rightarrow B$ is an assignment of each element of A to exactly one element of B. We write $f(a) = b$ if b is the unique element of B assigned by the function $f$ to the element a of A.
Functions are sometimes called mappings or transformations.
Given a function $f: A \rightarrow B$
We say $f$ maps A to B or $f$ is a mapping from A to B.
A is called the domain of $f$
B is called the codomain of $f$
If $f (a) = b$,
- then b is called the image of a under $f$
- a is called the preimage of b
Two functions are equal when they have the same domain, the same codomain and map each element of the domain to the same element of the codomain.
Questions
$ f (a) = ? $ z
The image of d is ? z
The domain of $f$ is ? A
The codomain of $f$ is ? B
The preimage of y is ? b
$ f (A) = ? $ {y,z}
The preimage(s) of z is (are) ? {a,c,d}
Injections ( one-to-one mapping)
A function that never assigns the same value to two different domain elements is said to be one-to-one.
Definition: A function $f$ is said to be one-to-one, or injective, if and only if $f (a) = f (b)$ implies that a = b for all a and b in the domain of $f$. A function is said to be an injection if it is one-to-one.
Surjections
Definition: A function $f$ from A to B is called onto or surjective, if and only if for every element $b \in B$ there is an element $a \in A$ with $f (a) = b$. A function $f$ is called a surjection if it is onto.
Bijections
Definition: A function $f$ is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto(surjective and injective).
Different Types of Correspondences
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 $$
Composition
Definition: Let $ g: A \rightarrow B $, $ f: B \rightarrow C $. The composition of $f$ with $g$, denoted $ f \circ g $ is the function from A to C defined by
$$ f \circ g(x) = f(g(x)) $$
Note that the composition $f \circ g$ cannot be defined unless the range of $g$ is a subset of the domain of $f$.
Some Important Functions
- The floor function, denoted
$$ f(x) = \lfloor x \rfloor $$
is the largest integer less than or equal to x.
- The ceiling function, denoted
$$ f(x) = \lceil x \rceil $$
is the smallest integer greater than or equal to x.
Examples:
$$ \lfloor 3.5 \rfloor = 3 \;\;\;\; \lceil 3.5 \rceil = 4 \\ \lfloor -1.5 \rfloor = -2 \;\;\;\; \lceil -1.5 \rceil = -1 $$
Sequences and Summations
Introduction
Sequences are ordered lists of elements.
Sequences arise throughout mathematics, computer science, and in many other disciplines, ranging from botany to music.
Definition
A sequence is a function from a subset of the integers A (usually the set {0, 1, 2, 3, 4, …..}) to a set S. The notation $a_{n}$ is used to denote the image of the integer n. We can think of $a_{n}$ as the equivalent of $f(n)$ where $f$ is a function from {0, 1, 2, …} to S. We call $a_{n}$ a term of the sequence.
Geometric Progression
Definition: A geometric progression is a sequence of the form:
$$ a, ar, ar^{2}, ..., ar^{n}, ... $$
where the initial term a and the common ratio r are real numbers.
Arithmetic Progression
Definition: A arithmetic progression is a sequence of the form:
$$ a, a + d, a + 2d , ... a + nd, ... $$
where the initial term a and the common difference d are real numbers.
Strings
Definition: A string is a finite sequence of characters from a finite set (an alphabet).
Sequences of characters or bits are important in computer science.
The empty string is represented by $\lambda$.
The string abcde has length 5.
Recurrence Relations
Definition: A recurrence relation for the sequence {$a_{n}$} is an equation that expresses $a_{n}$ in terms of one or more of the previous terms of the sequence, namely, $a_{0}, a_{1}, …, a_{n-1}$, for all integers n with $n \geq n_{0} $, where $n_{0}$ is a nonnegative integer.
A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.
The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect.
Fibonacci Sequence
Definition: Define the Fibonacci sequence, $f_{0}, f_{1}, f_{2}, …,$ by:
- Initial Conditions: $ f_{0} = 0, \ f_{1} = 1 $
- Recurrence Relation: $ f_{n} = f_{n-1} + f_{n - 2} $
Solving Recurrence Relations
Finding a formula for the nth term of the sequence generated by a recurrence relation is called solving the recurrence relation.
Such a formula is called a closed formula.
Many methods have been developed for solving recurrence relations.
A straightforward method is known as iteration.
An iteration method can be executed using
- Forward substitution (Working upward)
- Backward substitution(Working downward)
Summations
Sum of the terms $a_{m}, a_{m + 1}, ..., a_{n}$ from the sequence {$a_{n}$}
The notation:
$$ \sum_{j = m}^{n} a_{j} \;\;\;\; \textstyle\sum_{j = m}^{n} a_{j} \;\;\;\; \textstyle\sum_{m \leq j \leq n} a_{j} $$
represents $a_{m} + a_{m + 1} + ... + a_{n}$
The variable j is called the index of summation. It runs through all the integers starting with its lower limit m and ending with its upper limit n.
Geometric Series
Sums of terms of geometric progressions:
$$ \sum_{j = 0}^{n} ar^{j} = \left \{ \begin{array}{l} \frac{a(1-r^{n+1})}{1-r} \;\;\;\; r \neq 1 \\ (n+1)a \;\;\;\; r = 1 \end{array} \right. $$
Some useful summation formulae:
| Sum | Closed Form |
|---|---|
| $ \sum_{k=1}^{n} k $ | $ \frac{n(n+1)}{2} $ |
| $ \sum_{k=1}^{n} k^{2} $ | $ \frac{n(n+1)(2n+1)}{6} $ |
| $ \sum_{k=1}^{n} k^{3} $ | $ \frac{n^{2}(n+1)^{2}}{4} $ |
| $ \sum_{k=0}^{\infty} x^{k} $ , IxI < 1 | $ \frac{1}{1-x} $ |
| $ \sum_{k=0}^{\infty} kx^{k-1} $ , IxI < 1 | $ \frac{1}{(1-x)^{2}} $ |
Double Summations
As in the analysis of nested loop in computer program.
$$ \sum_{i=1}^{4} \sum_{j=1}^{3} ij $$
To evaluate the double sum, first expand the inner summation and then continue by computing the outer summation:
$$ \sum_{i=1}^{4} \sum_{j=1}^{3} ij = \sum_{i=1}^{4} (i + 2i + 3i) \\ = \sum_{i=1}^{4} 6i \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 6 +12 +18 +24 \\ = 60 \;\;\;\;\; $$
Matrices
Introduction
Matrices, useful discrete structures, can be used to:
- Describe certain types of functions known as linear transformations.
- Express which vertices of a graph are connected by edge.
Matrices are used to build models of transportation systems and communication networks.
Definition
A matrix is a rectangular array of numbers.
A matrix with m rows and n columns is called an $m \times n$ matrix.
- The plural of matrix is matrices or matrixes.
- A matrix with the same number of rows as columns is called square.
- Two matrices are equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are equal.
Notation
Let m and n be positive integers and let
$$ A = \begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n} \\ a_{21}&a_{22}&\cdots&a_{2n} \\ \vdots&\vdots&&\vdots \\ a_{m1}&a_{m2}&\cdots&a_{mn} \end{bmatrix} $$
The ith row of A is the $1 \times n$ matrix: $[a_{i1}, a_{i2}, …, a_{in}]$.
The jth column of A is the $m \times 1$ matrix: $ \begin{bmatrix} a_{1j} \\ a_{2j} \\ \vdots \\ a_{mj} \end{bmatrix} $.
The (i,j)th element or entry of A is the element $a_{ij}$. We can use $A = [a_{ij}]$ to denote the matrix with its (i,j)th element equal to $a_{ij}$.
Matrix Arithmetic
Addition
Definition: Let $A = [a_{ij}]$ and $B = [b_{ij}]$ be $m \times n$ matrices. The sum of A and B, denoted by A + B, is the $m \times n$ matrix that has $a_{ij} + b_{ij}$ as its (i,j)th element. In other words, $ A + B = [a_{ij} + b_{ij}] $.
Example:
$$ \begin{bmatrix} 1&0&-1 \\ 2&2&-3 \\ 3&4&0 \end{bmatrix} + \begin{bmatrix} 3&4&-1 \\ 1&-3&0 \\ -1&1&2 \end{bmatrix} = \begin{bmatrix} 4&4&-2 \\ 3&-1&-3 \\ 2&5&2 \end{bmatrix} $$
Multiplication
Definition: Let A be an $m \times k$ matrix and B be a $k \times n$ matrix. The product of A and B, denoted by AB, is the $m \times n$ matrix that has its (i,j)th element equal to the sum of the products of the corresponding elements from the ith row of A and the jth column of B. In other words, if $AB = [c_{ij}]$ then $c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + … + a_{ik}b_{kj}$.
Example:
$$ \begin{bmatrix} 1&0&4 \\ 2&1&1 \\ 3&1&0 \\ 0&2&2 \end{bmatrix} \begin{bmatrix} 2&4 \\ 1&1 \\ 3&0 \end{bmatrix} = \begin{bmatrix} 14&4 \\ 8&9 \\ 7&13 \\8&2 \end{bmatrix} $$
The product of two matrices is undefined when the number of columns in the first matrix is not the same as the number of rows in the second.
Identity Matrix and Powers of Matrices
Definition: The identity matrix of order n is the $m \times n$ matrix $I_{n} = [δ_{ij}]$, where $δ_{ij} = 1$ if i = j and $δ_{ij} = 0$ if $i \ne j$.
$$ I_{n} = \begin{bmatrix} 1&0&0&\cdots&0 \\ 0&1&0&\cdots&0 \\ 0&0&1&\cdots&0 \\ \vdots&\vdots&\vdots&&\vdots \\ 0&0&0&\cdots&1 \end{bmatrix} $$
$ AI_{n} = I_{m}A = A $ when A is an $m \times n$ matrix.
Transposes of Matrices
Definition: Let $A = [a_{ij}]$ be an $m \times n$ matrix. The transpose of A, denoted by $A^{t}$ ,is the $n \times m$ matrix obtained by interchanging the rows and columns of A.
Definition: A square matrix A is called symmetric if $A = A^{t}$. Thus $A = [a_{ij}]$ is symmetric if $a_{ij} = a_{ji}$ for i and j with $1 \leq i \leq n$ and $1 \leq j \leq n$.
Zero-One Matrices
Definition: A matrix all of whose entries are either 0 or 1 is called a zero-one matrix.
Algorithms operating on discrete structures represented by zero-one matrices are based on Boolean arithmetic defined by the following Boolean operations:
$$ b_{1} \wedge b_{2} = \left \{ \begin{array}{l} 1 \;\;\;\; if \ b_{1}=b_{2}=1 \\ 0 \;\;\;\; otherwise \end{array} \right. \;\;\;\;\;\;\; \\ b_{1} \vee b_{2} = \left \{ \begin{array}{l} 1 \;\;\;\; if \ b_{1}= 1 \ or \ b_{2}=1 \\ 0 \;\;\;\; otherwise \end{array} \right. $$
Definition: Let $A = [a_{ij}]$ and $B = [b_{ij}]$ be an $m \times n$ zero-one matrices.
- The join of A and B is the zero-one matrix with (i,j)th entry $a_{ij} \vee b_{ij}$. The join of A and B is denoted by $A \vee B$.
- The meet of of A and B is the zero-one matrix with (i,j)th entry $a_{ij} \wedge b_{ij}$. The meet of A and B is denoted by $A \wedge B$.
Boolean Product of Zero-One Matrices
Definition: Let $A = [a_{ij}]$ be an $m \times k$ zero-one matrix and $B = [b_{ij}]$ be a $k \times n$ zero-one matrix. The Boolean product of A and B, denoted by $A \odot B$, is the $m \times n$ zero-one matrix with (i,j)th entry.
$$ c_{ij} = (a_{i1} \wedge b_{1j}) \vee (a_{i2} \wedge b_{2j}) \ \vee ... \vee \ (a_{ik} \wedge b_{kj}) $$
Identity Matrix
Example:
$$ I \times A = A \times I = A $$
Thanks for the learning resource provided by Qi Wang from University at Albany!