Discrete Math › Section B · Logic and proofs › Topic B.5
Proofs about sets, functions, and graphs
The proof skeletons of the previous topic work on any mathematical object. Applied to sets, functions, relations and graphs, they produce short, reliable proofs, and writing them is a good way to understand what the definitions really say.
Definitions drive the proof
The previous topic, Direct proof, contrapositive, and contradiction, supplied the logical skeletons. Here the content comes from the discrete structures met in A tour of discrete structures. The method is always the same: write the claim in logical form, usually as an implication, choose a skeleton, then unpack each definition exactly as stated. Many definitions in this area are themselves implications or universal statements, so a careful reading tells you how the proof must start. Abstraction pays off as well: a fact proved once about all sets or all graphs applies to every problem modelled by them.
Subsets as implications
A set A is a subset of B, written \(A \subseteq B\), when every element of A is also an element of B: \(\forall x\,(x \in A \to x \in B)\). It is a proper subset, \(A \subset B\), when also \(A \ne B\). For example, the set \(\{x \in \mathbb{N} : x^2 < 30\}\), which is \(\{0, 1, 2, 3, 4, 5\}\), is a proper subset of \(\{x \in \mathbb{N} : x < 8\}\). Because the definition is a universal implication, a subset proof takes an arbitrary element of A and shows that it lies in B. This is called an element-chasing proof: you follow one element from set to set.
Worked example: an element-chasing proof
Prove: for all sets A, B and C, if \(A \subseteq B\) and \(B \subseteq C\), then \(A \subseteq C\). 1. Skeleton: a direct proof, so assume \(A \subseteq B\) and \(B \subseteq C\). 2. The goal \(A \subseteq C\) is a universal implication, so let x be an arbitrary element of A. 3. Since \(x \in A\) and \(A \subseteq B\), the definition of subset gives \(x \in B\). 4. Since \(x \in B\) and \(B \subseteq C\), it gives \(x \in C\). 5. As x was arbitrary, every element of A is in C, so \(A \subseteq C\). ■
Worked example: proving two sets equal
Two sets are equal when each is a subset of the other, so equality proofs have two halves. Prove: if \(A \subseteq B\), then \(A \cap B = A\). Recall that \(A \cap B\) holds the elements in both A and B. 1. Assume \(A \subseteq B\). 2. First half, \(A \cap B \subseteq A\): if \(x \in A \cap B\), then x is in both sets, so in particular \(x \in A\). 3. Second half, \(A \subseteq A \cap B\): if \(x \in A\), then \(x \in B\) because \(A \subseteq B\), so x is in both sets and \(x \in A \cap B\). 4. Each set is a subset of the other, so they are equal. ■
Injective functions
A function \(f: A \to B\) is injective, or one-to-one, when no two different inputs share an output. As an implication: if \(f(a_1) = f(a_2)\), then \(a_1 = a_2\). That form gives a direct proof. For \(f(n) = 3n + 2\) on the integers, suppose \(3a + 2 = 3b + 2\); subtracting 2 and dividing by 3 gives \(a = b\), so f is injective. To show a function is not injective, one counterexample is enough: \(g(n) = n^2\) on the integers is not injective, because \(g(2) = g(-2) = 4\).
Worked example: the pigeonhole principle
Prove: if A and B are finite sets with \(|A| > |B|\), then no function \(f: A \to B\) is injective. 1. Use the contrapositive: if f is injective, then \(|A| \le |B|\). 2. Assume f is injective, and let \(|B| = m\). 3. Each element of B is the output of at most one element of A. 4. Every element of A has an output in B, so A has at most m elements: \(|A| \le m\). ■ 5. Apply it: map each of 367 people to their birthday, one of 366 possible dates counting 29 February. Since \(367 > 366\), the map is not injective, so two people share a birthday.
Images of sets
For \(f: X \to Y\) and a subset S of X, the image of S is \(f(S) = \{f(s) : s \in S\}\), the set of outputs from inputs in S. With \(f(n) = n^2\) and \(S = \{-2, -1, 0, 1, 2\}\), \(f(S) = \{0, 1, 4\}\). Claim: if \(S \subseteq T\), then \(f(S) \subseteq f(T)\). Proof: let \(y \in f(S)\), so \(y = f(s)\) for some \(s \in S\). Since \(S \subseteq T\), \(s \in T\), so \(y = f(s) \in f(T)\). ■ This is element chasing again, because \(f(S)\) and \(f(T)\) are simply sets.
Relations and transitivity
A relation R on a set is transitive when, for all x, y and z, if x R y and y R z, then x R z. Claim: "divides" is transitive on the positive integers. Proof: assume \(a \mid b\) and \(b \mid c\), so \(b = aj\) and \(c = bk\) for some integers j and k. Then \(c = (aj)k = a(jk)\), so \(a \mid c\). ■ To show a relation is not transitive, find a counterexample that makes the hypothesis true and the conclusion false. "Differ by exactly 1" fails: 1 and 2 differ by 1, as do 2 and 3, but 1 and 3 differ by 2.
Graphs and degrees
A graph has a set of vertices and a set of edges, each edge joining two distinct vertices. The degree of a vertex is the number of edges at it. Take vertices 1 to 5 and edges {1, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}: the degrees are 2, 2, 3, 2 and 1, which add to 10, twice the 5 edges. That is no accident. Each edge has two ends and adds 1 to the degree of each, so in every graph the degrees add up to twice the number of edges. The topic What is a graph? develops this handshake fact further.
Worked example: an impossible party
Can 7 people at a party each shake hands with exactly 5 of the others? 1. Model: people are vertices, handshakes are edges, so we need a graph with 7 vertices of degree 5. 2. The degrees would add to \(7 \times 5 = 35\). 3. But the degree sum is twice the number of edges, so it must be even. 4. 35 is odd, a contradiction, so no such party is possible. 5. The same reasoning proves a general fact: the number of odd-degree vertices is even, because an odd number of odd degrees would make the total odd. In the five-vertex graph above, exactly two vertices, 3 and 5, have odd degree.
Common mistakes to avoid
First, proving \(A \subseteq B\) by checking a few elements instead of an arbitrary one. Second, proving only one half of a set equality. Third, starting an element-chasing proof in the wrong set, B instead of A. Fourth, testing injectivity by checking that every input has an output; every function does that. Fifth, offering a non-transitivity counterexample in which the hypothesis fails. Sixth, forgetting that each edge adds 2 to the degree sum, not 1.
Key takeaways
Write each definition in logical form and let it set the skeleton. \(A \subseteq B\) means every element of A is in B, proved by chasing an arbitrary element; set equality needs both inclusions. A function is injective when equal outputs force equal inputs; if \(|A| > |B|\), no function from A to B is injective, which is the pigeonhole principle. Images respect subsets: \(S \subseteq T\) gives \(f(S) \subseteq f(T)\). Transitivity is an implication, disproved by one counterexample. In any graph the degrees add to twice the number of edges, so the number of odd-degree vertices is even.
Flashcards
Flashcard
Every element of A is in B: ∀x (x ∈ A → x ∈ B)
Test your understanding
Question 1 of 5
To prove A ⊆ B by element chasing, how should the proof begin?
Question 2 of 5
Which function from the integers to the integers is injective?
Question 3 of 5
What is the smallest number of people that guarantees two of them were born on the same day of the week?
Question 4 of 5
On the integers, is the relation "x and y differ by exactly 2" transitive?
Question 5 of 5
Can 9 people at a meeting each shake hands with exactly 3 of the others?
