Page 207 - Discrete Mathematics and Its Applications

186 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

A − B (the difference of A and B): the set containing those n i = 1 a i : the sum a 1 + a 2 + ··· + a n
n
elements that are in A but not in B
i = 1 a i : the product a 1 a 2 ··· a n
A (the complement of A): the set of elements in the universal cardinality: two sets A and B have the same cardinality if
set that are not in A there is a one-to-one correspondence from A to B
A ⊕ B (the symmetric difference of A and B): the set con- countable set: a set that either is finite or can be placed in
taining those elements in exactly one of A and B one-to-one correspondence with the set of positive integers
membership table: a table displaying the membership of ele-
ments in sets uncountable set: a set that is not countable
function from A to B : an assignment of exactly one element ℵ 0 (aleph null): the cardinality of a countable set
of B to each element of A c: the cardinality of the set of real numbers
domain of f : the set A, where f is a function from A to B Cantor diagonalization argument: a proof technique used to
codomain of f : the set B, where f is a function from A to B show that the set of real numbers is uncountable
b is the image of a under f : b = f(a) computable function: a function for which there is a com-
a is a pre-image of b under f : f(a) = b puter program in some programming language that finds its
range of f : the set of images of f values
onto function, surjection: a function from A to B such that uncomputable function: a function for which no computer
every element of B is the image of some element in A program in a programming language exists that finds its
one-to-one function, injection: a function such that the im- values
ages of elements in its domain are distinct continuum hypothesis: the statement there no set A exists
one-to-one correspondence, bijection: a function that is both such that ℵ 0 < |A| < c
one-to-one and onto matrix: a rectangular array of numbers
inverse of f : the function that reverses the correspondence matrix addition: see page 178
given by f (when f is a bijection) matrix multiplication: see page 179
f ◦ g (composition of f and g): the function that assigns I n (identity matrix of order n): the n × n matrix that has
f(g(x)) to x entries equal to 1 on its diagonal and 0s elsewhere
t

x (floor function): the largest integer not exceeding x A (transpose ofA): the matrix obtained fromA by interchang-
x
(ceiling function): the smallest integer greater than or ing the rows and columns
equal to x symmetric matrix: a matrix is symmetric if it equals its trans-
partial function: an assignment to each element in a subset of pose
the domain a unique element in the codomain zero–one matrix: a matrix with each entry equal to either 0 or
sequence: a function with domain that is a subset of the set of 1
integers A ∨ B (the join of A and B): see page 181
2
geometric progression: a sequence of the form a, ar, ar ,... , A ∧ B (the meet of A and B): see page 181
where a and r are real numbers A B (the Boolean product of A and B): see page 182
arithmetic progression: a sequence of the form a, a + d,
a + 2d,... , where a and d are real numbers RESULTS
string: a finite sequence
empty string: a string of length zero
recurrence relation: a equation that expresses the nth term a n The set identities given in Table 1 in Section 2.2
of a sequence in terms of one or more of the previous terms The summation formulae in Table 2 in Section 2.4
of the sequence for all integers n greater than a particular The set of rational numbers is countable.
integer The set of real numbers is uncountable.

Review Questions

1. Explain what it means for one set to be a subset of another 5. a) Define the union, intersection, difference, and sym-
set. How do you prove that one set is a subset of another metric difference of two sets.
set?
b) What are the union, intersection, difference, and sym-
2. What is the empty set? Show that the empty set is a subset metric difference of the set of positive integers and the
of every set. set of odd integers?
3. a) Define |S|, the cardinality of the set S.
6. a) Explain what it means for two sets to be equal.
b) Give a formula for |A ∪ B|, where A and B are sets.
4. a) Define the power set of a set S. b) Describe as many of the ways as you can to show that
two sets are equal.
b) When is the empty set in the power set of a set S?
c) How many elements does the power set of a set S with c) Show in at least two different ways that the sets
n elements have? A − (B ∩ C) and (A − B) ∪ (A − C) are equal.