Basic Structures : Sets, Functions, Sequences, Sums, and Matrices
Sets
A set is an unordered collection of distinct objects, called elements or members of the set.
A set is said to contain its elements. We write a A to denote that a is an element of the set A. The notation a A denotes that a is not an element of the set A.
There are several ways to describe a set. One way is to list all the members of a set, when
this is possible. We use a notation where all members of the set are listed between braces. For example, the notation {a, b, c, d} represents the set with the four elements a, b, c, and d. This way of describing a set is known as the roster method.
Another way to describe a set is to use set builder notation. We characterize all those
elements in the set by stating the property or properties they must have to be members. The general form of this notation is {x ∣ x has property P} and is read “the set of all x such that x has property P.”
These sets, each denoted using a boldface letter, play an important role in discrete mathematics:
{0, 1, 2, 3, }, the set of all natural numbers { , −2, −1, 0, 1, 2, }, the set of all integers {1, 2, 3, }, the set of all positive integers {p/q ∣ p Z, q Z, and q 0}, the set of all rational numbers the set of all real numbers the set of all positive real numbers the set of all complex numbers.
Among the sets studied in calculus are intervals, sets of all the real numbers between two numbers a and b, with or without a and b. If a and b are real numbers with a b,
we denote these intervals by
Closed Interval : [a, b] {x | a x b}
Open Interval : (a, b) {x | a x b}.
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 x(x A x B). We write A B if A and B are equal
sets.
THE EMPTY SET:
There is a special set that has no elements. This set is called the empty set, or null set, and is denoted by . The empty set can also be denoted by { } (that is, we represent the empty set with a pair of braces that encloses all the elements in this set).
A set with one element is called a singleton set.
Subsets
The set A is a subset of B, and B is a superset of A, 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.
If, instead, we want to stress that B is a superset of A, we use the equivalent notation B A. (So, A B and B A are equivalent statements.)
We see that A B if and only if the quantification x(x A x B) is true. Note that to show that A is not a subset of B we need only find one element x A with x B. Such an x is a counterexample to the claim that x A implies x B.
Theorem :
For every set S, (i ) S and (ii ) S S.
When we wish to emphasize that a set A is a subset of a set B but that A B, we write A B and say that A is a proper subset of B. For A B to be true, it must be the case that A B and there must exist an element x of B that is not an element of A. That is, A is a proper subset of B if and only if x(x A x B) x(x B x A) is true.
Cardinality
Let S be a set. If there are exactly n distinct elements in S where n is a non-negative 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|.
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 (S).
If a set has n elements, then its power set has 2 elements.
Cartesian Product
The ordered n-tuple (a, a, , a) is the ordered collection that has a as its first element, a as its second element, , and a as its nth element.
In particular, ordered 2-tuples are called ordered pairs.
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}.
Set Operations
Union
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.
An element x belongs to the union of the sets A and B if and only if x belongs to A or x belongs to B. This tells us that A B {x ∣ x A x B}.
Intersection
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.
An element x belongs to the intersection of the sets A and B if and only if x belongs to A and x belongs to B. This tells us that A B {x ∣ x A x B}.
Two sets are called disjoint if their intersection is the empty set.
|A B| |A| + |B| − |A B|
The generalization of this result to unions of an arbitrary number of sets is called the principle of inclusion–exclusion. The principle of inclusion–exclusion is an important technique used in enumeration.
Difference
Let A and B be sets. The difference of A and B, denoted by A − B, is the set containing those
elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A.
An element x belongs to the difference of A and B if and only if x A and x B. This tells us that A − B {x ∣ x A x B}.
Complement
Let U be the universal set. The complement of the set A, denoted by , is the complement of A with respect to U. Therefore, the complement of the set A is U − A.
An element belongs to if and only if x A. This tells us that {x U ∣ x A}.
Set Identities
Identity
Name
A U A A A
Identity Laws
A U U A
Domination laws
A A A A A A
Idempotent laws
A
Complementation law
A B B A A B B A
Commutative laws
A (B C) (A B) C A (B C) (A B) C
Associative laws
A (B C) (A B) (A C) A (B C) (A B) (A C)
Distributive laws
De Morgan’s laws
A (A B) A A (A B) A
Absorption laws
A U A
Complement laws
The union of a collection of sets is the set that contains those elements that are members at least one set in the collection. We use the notation A A A A to denote the union of the sets A, A, , A.
The intersection of a collection of sets is the set that contains those elements that are members of all the sets in the collection. We use the notation A A A A to denote the intersection of the sets A, A, , A.
Multisets
Sometimes the number of times that an element occurs in an unordered collection matters. A multiset (short for multiple-membership set) is an unordered collection of elements where an element can occur as a member more than once. We can use the same notation for a multiset as we do for a set, but each element is listed the number of times it occurs. So, the multiset denoted by {a, a, a, b, b} is the multiset that contains the element a thrice and the element b twice. When we use this notation, it must be clear that we are working with multisets and not ordinary sets. We can avoid this ambiguity by using an alternate notation for multisets. The notation {m ⋅ a, m ⋅ a, , m ⋅ a} denotes the multiset with element a occurring m times, element a occurring m times, and so on.
The numbers m, i 1, 2, , r, are called the multiplicities of the elements a, i 1, 2, , r.
(Elements not in a multiset are assigned 0 as their multiplicity in this set.)
The cardinality of a multiset is defined to be the sum of the multiplicities of its elements. The word multiset was introduced by Nicolaas Govert de Bruijn in the 1970s, but the concept dates back to the 12th century work of the Indian mathematician Bhaskaracharya.
Let P and Q be multisets. The union of the multisets P and Q is the multiset in which the
multiplicity of an element is the maximum of its multiplicities in P and Q.
The intersection of P and Q is the multiset in which the multiplicity of an element is the minimum of its multiplicities in P and Q.
The difference of P and Q is the multiset in which the multiplicity of an element is
the multiplicity of the element in P less its multiplicity in Q unless this difference is negative,
in which case the multiplicity is 0.
The sum of P and Q is the multiset in which the multiplicity of an element is the sum of multiplicities in P and Q.
The union, intersection, and difference of P and Q are denoted by P Q, P Q, and P − Q, respectively . The sum of P and Q is denoted by P + Q.
Functions
Let A and B be nonempty sets. A function from A to B is an assignment of exactly one element of B to each element of A. We write (a) b if b is the unique element of B assigned
by the function to the element a of A. If is a function from A to B, we write : A B.
A function : A B can also be defined in terms of a relation from A to B.
A relation from A to B that contains one, and only one, ordered pair (a, b) for every element
a A, defines a function from A to B. This function is defined by the assignment (a) b, where (a, b) is the unique ordered pair in the relation that has a as its first element.
If is a function from A to B, we say that A is the domain of and B is the codomain of .
If (a) b, we say that b is the image of a and a is a preimage of b. The range, or image, of
is the set of all images of elements of A. Also, if is a function from A to B, we say that maps A to B.
Let and be functions from A to R. Then + and are also functions from A to R
defined for all x A by :
( + )(x) (x) + (x),
()(x) (x)(x).
Let be a function from A to B and let S be a subset of A. The image of S under the function
is the subset of B that consists of the images of the elements of S. We denote the image of S by (S), so (S) {t ∣ s S (t (s))}.
We also use the shorthand {(s) ∣ s S} to denote this set.
One-to-One and Onto Functions
Some functions never assign the same value to two different domain elements. These functions are said to be one-to-one.
A function is said to be one-to-one, or an injection, if and only if (a) (b) implies that
a b for all a and b in the domain of . A function is said to be injective if it is one-to-one.
Note that a function is one-to-one if and only if (a) (b) whenever a b. This way of
expressing that is one-to-one is obtained by taking the contrapositive of the implication in the definition. We can express that is one-to-one using quantifiers as
ab((a) (b) a b) or equivalently ab(a b (a) (b)),
where the universe of discourse is the domain of the function.
A function whose domain and codomain are subsets of the set of real numbers is called
increasing if (x) (y), and strictly increasing if (x) (y), whenever x y and x and y
are in the domain of . Similarly, is called decreasing if (x) (y), and strictly decreasing if (x) (y), whenever x y and x and y are in the domain of .
A function is →
increasing if xy(x y (x) (y)),
strictly increasing if xy(x y (x) (y)),
decreasing if xy(x y (x) (y)), and
strictly decreasing if xy(x y (x) (y)),
where the universe of discourse is the domain of .
A function from A to B is called onto, or a surjection, if and only if for every element
b B there is an element a A with (a) b. A function is called surjective if it is onto.
A function is onto if yx((x) y), where the domain for x is the domain of the function and the domain for y is the codomain of the function.
The function is a one-to-one correspondence, or a bijection, if it is both one-to-one and
onto. We also say that such a function is bijective.
Suppose that : A B :
To show that is injective
Show that if (x) (y) for arbitrary x, y A, then x y.
To show that is not injective
Find particular elements x, y A such that x y and (x) (y).
To show that is surjective
Consider an arbitrary element y B and find an element x A such that (x) y.
To show that is not surjective
Find a particular y B such that (x) y for all x A.
Inverse Functions and Compositions of Functions
Let be a one-to-one correspondence from the set A to the set B. The inverse function of is the function that assigns to an element b belonging to B the unique element a in A such that (a) b. The inverse function of is denoted by . Hence, (b) a when (a) b.
If a function is not a one-to-one correspondence, we cannot define an inverse function of
. When is not a one-to-one correspondence, either it is not one-to-one or it is not onto. If is not one-to-one, some element b in the codomain is the image of more than one element in the domain. If is not onto, for some element b in the codomain, no element a in the domain exists for which (a) b.
Consequently, if is not a one-to-one correspondence, we cannot assign to each element b in the codomain a unique element a in the domain such that (a) b (because for some b there is either more than one such a or no such a).
A one-to-one correspondence is called invertible because we can define an inverse of this
function. A function is not invertible if it is not a one-to-one correspondence, because the
inverse of such a function does not exist.
Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The composition of the functions and , denoted for all a A by ◦ , is the function
from A to C defined by ( ◦ )(a) ((a)).
The Graph of Functions
We can associate a set of pairs in A B to each function from A to B. This set of pairs is called the graph of the function and is often displayed pictorially to aid in understanding the behavior of the function.
Let be a function from the set A to the set B. The graph of the function is the set of ordered pairs {(a, b) ∣ a A and (a) b}.
Important Functions
The floor function assigns to the real number x the largest integer that is less than or equal to x. The value of the floor function at x is denoted by x.
The ceiling function assigns to the real number x the smallest integer that is greater than or equal to x. The value of the ceiling function at x is denoted by x.
x n if and only if n x n + 1
x n if and only if n − 1 x n
x n if and only if x − 1 n x
x n if and only if x n x + 1
x − 1 x x x x + 1
−x −x
−x −x
x + nx + n
x + nx + n
Sequences and Summations
Sequences
A sequence is a discrete structure used to represent an ordered list. The terms of a sequence can be specified by providing a formula for each term of the sequence.
A sequence is a function from a subset of the set of Z to a set S. We use the notation a to denote the image of the integer n. We call an a term of the sequence.
A geometric progression is a sequence of the form a, ar, ar, , ar,
where the initial term a and the common ratio r are real numbers.
An 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.
Recurrence Relations
A recurrence relation for the sequence {a} is an equation that expresses an in terms of
one or more of the previous terms of the sequence, namely, a, a, , a, for all integers n
with n n, where n is a non-negative integer.
A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. (A recurrence relation is said to recursively define a sequence.)
The initial conditions for a recursively defined sequence specify the terms that precede the
first term where the recurrence relation takes effect.
Summations
A large uppercase Greek letter sigma, , is used to denote summation.
a a + a + + a.
The variable i is called index of summation. The index of summation runs through all integers starting with its lower limit m and ending with its upper limit n.
Cardinality of Sets
The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| |B|.
If there is a one-to-one function from A to B, the cardinality of A is less than or the same as the cardinality of B and we write |A| |B|. Moreover, when |A| |B| and A and B have different cardinality, we say that the cardinality of A is less than the cardinality of B and we
write |A| |B|.
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.
When an infinite set S is countable, we denote the cardinality of S by (where is aleph, the first letter of the Hebrew alphabet).
We write |S| and say that S has cardinality “aleph null.”
SCHRÖDER-BERNSTEIN THEOREM :
If A and B are sets with |A| |B| and |B| |A|, then |A| |B|.
In other words, if there are one-to-one functions f from A to B and g from B to A, then there is a one-to-one correspondence between A and B.
THE CONTINUUM HYPOTHESIS
It can be shown that the power set of Z and the set of real numbers R have the same cardinality. In other words, we know that |(Z+)| |R| c, where c denotes the cardinality of the set of real numbers. An important theorem of Cantor states that the cardinality of a set is always less than the cardinality of its power set. Hence, |Z+| |(Z+)|.
We can rewrite this as 2, using the notation 2 to denote the cardinality of the power set of the set S.
Also, note that the relationship |(Z+)| |R| can be expressed as 2.
This leads us to the continuum hypothesis, which asserts that there is no cardinal number X between and .
The continuum hypothesis states that there is no set A such that , the cardinality of the set of positive integers, is less than |A| and |A| is less than , the cardinality of the set of real numbers. It can be shown that the smallest infinite cardinal numbers form an infinite sequence . If we assume that the continuum hypothesis is true, it would follow that , so that 2.
Matrices
A matrix is a rectangular array of numbers. A matrix with m rows and n columns is called an
m n matrix. The plural of matrix is matrices. 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.
Matrix Arithmetic
Let A [a] and B [b] be m n matrices.
The sum of A and B, denoted by A + B, is the m n matrix that has a + b as its (i, j)-th element.
In other words, A + B [a + b].
Let A be an m k matrix and B be a k n matrix.
The product of A and B, denoted by AB, is the m n matrix with its (i, j)-th entry equal to the sum of the products of the corresponding elements from the i-th row of A and the j-th column of B.
In other words, if AB [c], then c ab + ab + + ab.
Transposes and Powers of Matrices
The identity matrix of order n is the n n matrix I [δ], (the Kronecker delta)
where δ 1 if i j and δ 0 if i j.
Hence,
Multiplying a matrix by an appropriately sized identity matrix does not change this matrix.
In other words, when A is an m n matrix, we have AI IA A.
Powers of square matrices can be defined because matrix multiplication is associative. When A is an n n matrix, we have A I, A AAA A. (r times)
Let A [a] be an m n matrix. The transpose of A, denoted by A, is the n m matrix
obtained by interchanging the rows and columns of A.
In other words, if A [b], then b a for i 1, 2, , n and j 1, 2, , m.
A square matrix A is called symmetric if A A .
Thus, A [a] is symmetric if a a for all i and j with 1 i n and 1 j n.
Zero-One Matrices
Let A [a] and B [b] be m n zero–one matrices.
Then the join of A and B is the zero–one matrix with (i, j)-th entry a b.
The join of A and B is denoted by A B.
The meet of A and B is the zero–one matrix with (i, j)th entry a b.
The meet of A and B is denoted by A B.
Let A [a] be an m k zero–one matrix and B [b] be a k n zero–one matrix.
Then the Boolean product of A and B, denoted by A ⊙ B, is the m n matrix with (i, j)-th entry c where c (a b) (a b) (a b).
Let A be a square zero–one matrix and let r be a positive integer. The r-th Boolean power of A is the Boolean product of r factors of A. The r-th Boolean product of A is denoted by A.
Hence, A A ⊙ A ⊙ A ⊙ ⊙ A. (r times). We also define A I.