16 2. Background
they have the same elements; if they have no elements in common
they are called disjoint. The set A is a subset of a set B if all of the
elements of A are also elements of B; this is denoted A B. If we
know that A is not equal to B, we may write A B or (to emphasize
the non-equality) A B. The collection of all subsets of A is denoted
P(A) and called the power set of A.
We may write a set using an explicit list of its elements, such as
{red, blue, green} or {5, 10, 15,...}. When writing down sets, order
does not matter and repetitions do not count, so {1, 2, 3}, {2, 3, 1},
and {1, 1, 2, 2, 3, 3} are all representations of the same set. We may
also use notation that may be familiar to you from calculus:
A = {x :
(∃y)(y2
= x)}.
This is the set of all values we can fill in for x that make the logical
predicate
(∃y)(y2
= x) true. The syntax of set definitions is often
looser than in logical formulas generally, using commas to mean “and”
and condensing clauses. For example, {(x, y) : x,
y2
Q, x y}
abbreviates {(x, y) : x Q &
y2
Q & x y}.
We are always working within some fixed universe, a set which
contains all of our sets. The domain of quantification is all elements
of the universe, and hence the contents of the set A above will vary
depending on what our universe is. If we are living in the integers it
is the set of perfect squares; if we are living in the real numbers it is
the set of all non-negative numbers.
Given two sets, we may obtain a third from them in several ways.
First there is union: A B is the set containing all elements that
appear in at least one of A and B. Next intersection: A B is
the set containing all elements that appear in both A and B. We
can subtract: A B contains all elements of A that are not also
elements of B. You will often see A \ B for set subtraction, but
we will use ordinary minus because the slanted minus is sometimes
given a different meaning in computability theory. Finally, we can
take their Cartesian product: A × B consists of all ordered pairs that
have their first entry an element of A and their second an element of
B. We may take the product of more than two sets to get ordered
triples, quadruples, quintuples, and in general n-tuples. If we take
Previous Page Next Page