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