so that x ∈ A ∩ B. Thus A ⊆ A ∩ B. Next suppose that x ∈ A∩B. Then x ∈ A ∧ x ∈ B, so certainly x ∈ A. Thus A ∩ B ⊆ A. It follows that A ∩ B = A, as desired.
(2)
We will sometimes write A \ B for A ∩ B∁. The proof of the following is left as an exercise.
Proposition 2.1.9. The following conditions are equivalent:
(1) A ⊆ B;
(2) B∁ ⊆ A∁;
(3) A \ B =
There are some interactions between the inclusion relation and the Boolean operations, in the same way that inequality for numbers interacts with the addition and multiplication operations.
Proposition 2.1.10. For any sets A, B, and C, we have the following properties:
(1) If B ⊆ A and C ⊆ A, then B ∪ C ⊆ A.
(2) If A ⊆ B and A ⊆ C, then A ⊆ B ∩ C.
Proof. (1) Assume that B ⊆ A and C ⊆ A. Let x be arbitrary and suppose that x ∈ B ∪ C. This means that x ∈ B ∨ x ∈ C. There are two cases. Suppose first that x ∈ B. Since B ⊆ A, it follows that x ∈ A. Suppose next that x ∈ C. Since C ⊆ A, it follows again that x ∈ A. Hence x ∈ B ∪ C → x ∈ A. Since x was arbitrary, we have B ∪ C ⊆ A, as desired.
The proof of part (2) is left to the exercises.
Exercises for Section 2.1
Exercise 2.1.1. Prove the Commutative Law for intersection, that is, for any sets A and B, A ∩ B = B ∩ A.
Exercise 2.1.2. Prove the Associative Law for union, that is, for any sets A, B, and C, A ∪ (B ∪ C) = (A ∪ B) ∪ C.
Exercise 2.1.3. Prove the Distributive Laws, that is, for any sets A, B, and C, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Exercise 2.1.4. Show that, for any set A,
Exercise 2.1.5. Show that, for any set A, (A∁)∁ = A.
Exercise 2.1.6. Show that, for any set A, A ∪
Exercise 2.1.7. Show that, for any set A, A ∩
Exercise 2.1.8. Complete the argument that the relation ⊆ is a partial ordering by showing that it is transitive, that is, if A ⊆ B and B ⊆ C then A ⊆ C.
Exercise 2.1.9. Show that, for any sets A and B, A ⊆ B if and only if A ∪ B = B.
Exercise 2.1.10. Show that the following conditions are equivalent:
(1) A ⊆ B;
(2) B∁ ⊆ A∁;
(3) A \ B =
Exercise 2.1.11. Show that, for any sets A, B, and C, A ⊆ B and A ⊆ C imply that A ⊆ B ∩ C.
2.2. Relations
Relations play a fundamental role in mathematics. Of particular interest are orderings, equivalence relations, and graphs. The notion of a graph is quite general. That is, a graph G = (V, E) is simply a set V of vertices and a binary relation E. In a directed graph, a pair (u, v) is said to be an edge from u to v.
A key notion here is that of an ordered pair. Given two elements a1, a2 from our universe U, the ordered pair (a1, a2) is defined so that for any two pairs of elements (a1, b1) and (b1, b2), (a1, a2) = (b1, b2)
Definition 2.2.1. Let A and B be sets.
(1) The product of A and B is defined to be
(2) An = {(a1, . . . , an) : each ai ∈ A}. Here (a1, . . . , an) is called an n-tuple.
(3) A subset R of A×B is called a relation, specifically a binary relation.
