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.
(4) A subset R of An is said to be an n-ary relation. We sometimes write aRb for (a, b) ∈ R.
Definition 2.2.2. Let A1, . . . , An be sets.
(1) The product A1 × A2 × · · · × An = {(a1, . . . , an) : each ai ∈ Ai}.
(2) An = {(a1, . . . , an) : each ai ∈ A}.
Proposition 2.2.3. For any sets A, B, and C,
(1) A × (B ∪ C) = (A × B) ∪ (A × C) and (B ∪ C) × A = (B × A) ∪ (C × A);
(2) A × (B ∩ C) = (A × B) ∩ (A × C) and (B ∩ C) × A = (B × A) ∩ (C × A);
(3) A × (B \ C) = (A × B) \ (A × C) and (A \ B) × C = (A × C) \ (B × C).
Proof. (1) (x, y) ∈ A × (B ∪ C) if and only if x ∈ A ∧ y ∈ B ∪ C, if and only if x ∈ A ∧ (y ∈ B ∨ y ∈ C), if and only if (x ∈ A ∧ y ∈ B) ∨ (x ∈ A ∧ y ∈ C), if and only if (x, y) ∈ A×B ∨ (x, y) ∈ A×C, if and only if (x, y) ∈ (A×B)∪(A×C). The proof of the second statement in (1) is similar.
The proof of parts (2) and (3) are left to the exercises.
Here are some important examples of binary relations that we will return to frequently in what follows.
Example 2.2.4. The standard ordering x ≤ y (as well as the strict order <) on the real numbers is a binary relation, which also applies to the rational numbers, integers, and natural numbers.
Example 2.2.5. The subset relation A ⊆ B on sets, read “A is a subset of B”, or “A is included in B”, is a binary relation.
Example 2.2.6. Let the graph G have vertices (i, j) for integers i, j; this is the lattice of integer points in the plane. Let there be horizontal and vertical edges between adjacent vertices. That is, each (i, j) has four edges, going to (i − 1, j), (i + 1, j), (i, j − 1), and (i, j + 1) which means that, for example, (1, 2)E(1, 3).
Example 2.2.7. The fundamental relation of axiomatic set theory is membership, that is the relation x ∈ y, for sets x and y. Note that when we study higher set theory, we do not distinguish between points and sets.
Example 2.2.8. For any set A, let IA = {(a, a) ∈ A × A : a ∈ A} be the identity relation on A.
Example 2.2.9. The divisibility relation on the set
Here