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