Discrete Mathematics and Proof

Proving a set identity

Two descriptions of a set look different. How can anyone show that they pick out exactly the same elements for every choice of sets, and how can anyone show that they do not?

You need

Direct proofGrades 9 to 12 Subsets, proper subsets and equal setsDiscrete Mathematics and Proof

Where you are 15 in Sets

Logic, proof and discrete math6

Sets15

▴ 7 above Union, intersection and complement Infinite sets4

Proving a set identity

Relations and their properties: reflexive, symmetric, antisymmetric, transitive Set identities: distributive and De Morgan laws ▾ Show all 15 (3 more)

When you reach for it

A set identity claims that two expressions name the same set whatever sets are put in. Subsets, proper subsets and equal sets showed what that means, each side a subset of the other, and how to prove a subset with an arbitrary member. Set identities: distributive and De Morgan laws tested identities with membership tables and listed the standard laws. This lesson writes the proof as mathematicians write it: follow one element through the definitions, in sentences. It works for any identity, including ones about sets given by a property or about infinitely many sets, where a table cannot be drawn.

This lesson takes two days. Part 1 is the element-chasing proof, with two new operations, set difference and symmetric difference. Part 2 proves identities by algebra from the standard laws, proves conditional statements about sets, and disproves a proposed identity, including the case where one inclusion holds and the other fails.

The procedure

Part 1: following one element

Two new operations. For sets A and B, the difference A \setminus B is the set of elements of A that are not in B:

A \setminus B = \{x : x \in A \text{ and } x \notin B\}

When A and B lie in a universal set U, this is A \cap B^{c}, since for x \in U, x \notin B means x \in B^{c}. The symmetric difference is what lies in exactly one of the two sets:

A \mathbin{\triangle} B = (A \setminus B) \cup (B \setminus A)

Figure 1 shades both. Membership in A \mathbin{\triangle} B is the exclusive or of membership in A and in B: x \in A \mathbin{\triangle} B exactly when (x \in A) \oplus (x \in B) is true. Order matters in a difference, so A \setminus B and B \setminus A are usually different sets, while A \mathbin{\triangle} B = B \mathbin{\triangle} A by the commutative law for \cup.

Figure 1The difference A \setminus B, the difference B \setminus A, and the symmetric difference A \mathbin{\triangle} B, which is the two of them together.

The shape of the proof. To prove L = R for all sets, prove L \subseteq R and R \subseteq L. Each inclusion is a Direct proof. It opens “Let x \in L”, with x arbitrary, unfolds what membership in L says by the definitions of \cup, \cap, complement and \setminus, and reasons until the facts fold back up into x \in R. Since x was arbitrary, every element of L is in R. Three unfoldings come up again and again. “x \in A \cup B” is used by cases, one for each part. “x \notin A \cap B” says only that x misses at least one of A, B. “x \notin B \setminus C” says x \notin B or x \in C. The proof closes with a sentence naming both inclusions and the conclusion, then \square.

Part 2: algebra, conditions and counterexamples

Proof by algebra. Once the standard identities of Set identities: distributive and De Morgan laws are proved, they can be used like the rules of algebra: rewrite one side a law at a time until it becomes the other. Each \setminus is first replaced by \cap with a complement, so every set must lie in one U. Each equal sign is justified by a named law, and the chain proves both inclusions in one pass.

Conditional statements. A hypothesis “A \subseteq B” is a fact to use inside the chase: whenever x \in A, also x \in B. A claim “... exactly when ...” is an if and only if and needs both directions. One fact is used often: A \setminus B = \varnothing exactly when A \subseteq B, since an element of A \setminus B is precisely an element of A outside B. (Subsets, proper subsets and equal sets proves the same fact written as A \cap B^{c} = \varnothing.)

Disproof. An identity claims every choice of sets, so one choice that breaks it is a Counterexample. Small is best, often a single element placed in some of the sets and not others. When an attempted proof goes through in one direction and stalls in the other, the stalled step shows what the counterexample needs: an element with exactly the property the step could not rule out.

Worked examples

Examples 1 to 3 go with Part 1, and Examples 4 to 7 with Part 2.

Example 1

Differences of two finite sets

Let A be the set of primes less than 20 and B the set of odd positive integers less than 20. Find A \setminus B, B \setminus A and A \mathbin{\triangle} B, and check that A \mathbin{\triangle} B is the part of A \cup B outside A \cap B.

Solution

Here A = \{2, 3, 5, 7, 11, 13, 17, 19\} and B = \{1, 3, 5, 7, 9, 11, 13, 15, 17, 19\}. Removing from A every element of B leaves only the even prime: A \setminus B = \{2\}. Removing the primes from B leaves B \setminus A = \{1, 9, 15\}, since 1 is not prime, 9 = 3 \cdot 3 and 15 = 3 \cdot 5. Their union is A \mathbin{\triangle} B = \{1, 2, 9, 15\}.

For the check, A \cup B = \{1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19\} and A \cap B = \{3, 5, 7, 11, 13, 17, 19\}, the odd primes. Removing the second from the first leaves \{1, 2, 9, 15\} again. One pair of sets agreeing is a check, not a proof; Exercise 10 gives the reason it always happens.

Example 2

A difference inside a difference

Prove that (A \setminus C) \setminus (B \setminus C) = (A \setminus B) \setminus C for all sets A, B and C.

Solution

Proof. Write L for the left side and R for the right.

First, L \subseteq R. Let x \in L. Then x \in A \setminus C and x \notin B \setminus C. The first says x \in A and x \notin C. If x were in B, then together with x \notin C it would be in B \setminus C, which it is not. So x \notin B. Now x \in A and x \notin B give x \in A \setminus B, and with x \notin C this is x \in R.

Next, R \subseteq L. Let x \in R. Then x \in A, x \notin B and x \notin C. From x \in A and x \notin C we get x \in A \setminus C. Every element of B \setminus C lies in B, and x \notin B, so x \notin B \setminus C. Hence x \in L.

Each side is a subset of the other, so L = R. \square

Example 3

An intersection spread over a symmetric difference

Prove that A \cap (B \mathbin{\triangle} C) = (A \cap B) \mathbin{\triangle} (A \cap C) for all sets.

Solution

Proof. Write L and R for the two sides.

L \subseteq R. Let x \in L. Then x \in A, and x is in exactly one of B, C. Suppose first that x \in B and x \notin C. Then x \in A \cap B, and x \notin A \cap C because x \notin C. So x \in (A \cap B) \setminus (A \cap C), which is part of R. If instead x \in C and x \notin B, the same argument with B and C exchanged puts x in (A \cap C) \setminus (A \cap B), the other part of R. Either way, x \in R.

R \subseteq L. Let x \in R. Suppose first that x \in (A \cap B) \setminus (A \cap C). Then x \in A and x \in B. Also x \notin A \cap C, so x misses A or misses C; it is in A, so it misses C. Hence x \in B \setminus C, so x \in B \mathbin{\triangle} C, and with x \in A this gives x \in L. The case x \in (A \cap C) \setminus (A \cap B) is the same with B and C exchanged.

Both inclusions hold, so L = R. \square

The step to watch is “x \notin A \cap C and x \in A, so x \notin C”. Not being in an intersection says only that some part is missed; knowing x \in A is what names the part. Union does not spread over \mathbin{\triangle} in the same way (Exercise 19).

Example 4

Proof by algebra, and the same proof by elements

Let A and B lie in a universal set U. Prove that (A \cup B) \setminus (B \setminus A) = A, first by algebra and then by elements, and compare the two proofs.

Solution

Proof by algebra.

\begin{aligned} (A \cup B) \setminus (B \setminus A) &= (A \cup B) \cap (B \cap A^{c})^{c} \\ &= (A \cup B) \cap (B^{c} \cup A) \\ &= (A \cup B) \cap (A \cup B^{c}) \\ &= A \cup (B \cap B^{c}) \\ &= A \cup \varnothing = A \end{aligned}

The first line writes each difference as an intersection with a complement. The second is De Morgan’s law, (B \cap A^{c})^{c} = B^{c} \cup (A^{c})^{c}, with the double complement law. The third is the commutative law for \cup. The fourth is the second distributive law read right to left, and the last is the complement law B \cap B^{c} = \varnothing followed by the identity law. \square

Proof by elements. Let x \in (A \cup B) \setminus (B \setminus A), so x \in A \cup B and x \notin B \setminus A. If x \notin A, then x \in B, and x \in B with x \notin A says x \in B \setminus A, which is false. So x \in A. Conversely, let x \in A. Then x \in A \cup B, and x \notin B \setminus A because every element of B \setminus A lies outside A. So x is in the left side. Both inclusions hold, and the sets are equal. \square

The algebra has no cases and each line can be checked against the laws, but it needs a universal set and gives no hint of which law comes next. The element chase needs no U and shows why the identity is true: B \setminus A removes from A \cup B only elements outside A.

Example 5

Two conditional statements

(a) Prove that if A \subseteq B, then C \setminus B \subseteq C \setminus A.

(b) Prove that A \setminus B = B \setminus A exactly when A = B.

Solution

(a) Proof. Suppose A \subseteq B, and let x \in C \setminus B, so x \in C and x \notin B. If x were in A, the hypothesis would put it in B. So x \notin A, and x \in C \setminus A. \square Taking away the larger set leaves less, so the inclusion turns around.

(b) Proof. If A = B, both sides are A \setminus A = \varnothing. Conversely, suppose A \setminus B = B \setminus A, and let x \in A. If x \notin B, then x \in A \setminus B = B \setminus A, so x \in B, a contradiction. Hence x \in B, and A \subseteq B. The same argument with A and B exchanged gives B \subseteq A, so A = B. \square

Example 6

One inclusion holds, the other fails

Is (A \setminus B) \cup C = (A \cup C) \setminus B for all sets? If not, say which inclusion holds, and find exactly when the two sides are equal.

Solution

Write L and R for the two sides, and try to prove each inclusion.

R \subseteq L holds. Let x \in R, so x \in A or x \in C, and x \notin B. If x \in A, then x \in A \setminus B. If x \in C, then x is in the union directly. Either way x \in L.

L \subseteq R stalls. Let x \in L. If x \in A \setminus B, then x \in A \cup C and x \notin B, so x \in R. If x \in C, then x \in A \cup C, but nothing says x \notin B. A counterexample needs exactly that: an element of C that is also in B. Take A = \varnothing and B = C = \{1\}:

\begin{aligned} (A \setminus B) \cup C &= \varnothing \cup \{1\} = \{1\} \\ (A \cup C) \setminus B &= \{1\} \setminus \{1\} = \varnothing \end{aligned}

So the equation is not an identity. The stalled step also says when it does hold.

Claim. L = R exactly when B \cap C = \varnothing.

Proof. If B \cap C = \varnothing, the stalled case finishes: x \in C forces x \notin B, so x \in R. Then L \subseteq R, and with R \subseteq L, L = R. Conversely, if L = R, then C \subseteq L = R, so every element of C lies outside B, which says B \cap C = \varnothing. \square

Example 7

Symmetric difference is associative

Prove that (A \mathbin{\triangle} B) \mathbin{\triangle} C and A \mathbin{\triangle} (B \mathbin{\triangle} C) are equal for all sets.

Solution

Both sides can be described by one rule.

Claim. An element x is in (A \mathbin{\triangle} B) \mathbin{\triangle} C exactly when it is in an odd number of the sets A, B, C, that is, in one of them or in all three.

Proof. By definition, x is in (A \mathbin{\triangle} B) \mathbin{\triangle} C exactly when it is in exactly one of A \mathbin{\triangle} B and C. Suppose x \in C. Then x is in the left side exactly when x \notin A \mathbin{\triangle} B, that is, when x is in both A and B or in neither; counting C, that is three of the sets or one. Suppose x \notin C. Then x is in the left side exactly when x \in A \mathbin{\triangle} B, that is, in exactly one of A, B, which with C missed is one of the three. In both cases the condition is “one or three”. \square

Now A \mathbin{\triangle} (B \mathbin{\triangle} C) = (B \mathbin{\triangle} C) \mathbin{\triangle} A by the commutativity of \mathbin{\triangle}, and the claim, applied to the sets B, C, A in that order, says its elements are those in an odd number of B, C, A. That is the same rule, so the two sides have the same elements and are equal. \square

The brackets can therefore be dropped: A \mathbin{\triangle} B \mathbin{\triangle} C is the set of elements in an odd number of the three. It is the set form of the associativity of \oplus in Exclusive or and logic circuits.

Boundaries

Complements need one universal set. An element chase with \cup, \cap and \setminus needs no U. Proof by algebra, and any identity with a complement in it, holds only when every complement is taken in the same U, one that contains all the sets. The rewriting A \setminus B = A \cap B^{c} needs A \subseteq U.

For all sets, not for some. The equation in Example 6 holds whenever B \cap C = \varnothing and is still not an identity: one failing choice of sets settles it.

Difference is neither commutative nor associative. \{1\} \setminus \varnothing = \{1\} while \varnothing \setminus \{1\} = \varnothing, so the order matters. With A = B = C = \{1\}, (A \setminus B) \setminus C = \varnothing while A \setminus (B \setminus C) = \{1\}, so brackets in a chain of differences cannot be dropped. Symmetric difference, by contrast, is both commutative and associative (Example 7).

Where this goes next

The same two inclusions prove identities about power sets, where the elements chased are subsets, and about Cartesian products, where they are ordered pairs. A relation is a set of ordered pairs, so Relations and their properties: reflexive, symmetric, antisymmetric, transitive proves its facts the same way. Counting a difference, \lvert A \setminus B \rvert = \lvert A \rvert - \lvert A \cap B \rvert for finite sets, is a first step toward the Inclusion-exclusion for three or more sets, and derangements.

Exercises

Part 1: computing differences

For Exercises 1 and 2, A = \{1, 2, 3, 4, 5, 6, 7\}, B = \{5, 6, 7, 8, 9\} and C = \{2, 4, 6, 8\}.

Find A \setminus B, B \setminus A and A \mathbin{\triangle} B.
Find (A \cup B) \setminus C and C \setminus (A \cap B).
In the real numbers, let A be the numbers with 0 \le x \le 4 and B those with 2 < x < 6. Find A \setminus B, B \setminus A and A \mathbin{\triangle} B.
In the integers, let A be the even integers and B the multiples of 3. Describe A \setminus B and A \mathbin{\triangle} B by the remainders their elements leave on division by 6.

Part 1: element-chasing proofs

Prove each identity for all sets by showing both inclusions.

A \setminus (B \setminus A) = A
A \cap (B \setminus C) = (A \cap B) \setminus C
(A \cup C) \setminus (B \cup C) = (A \setminus B) \setminus C
A^{c} \mathbin{\triangle} B^{c} = A \mathbin{\triangle} B, for A and B in a universal set U
A \mathbin{\triangle} \varnothing = A and A \mathbin{\triangle} A = \varnothing
A \cup B = (A \mathbin{\triangle} B) \cup (A \cap B), and the two sets on the right have no element in common.

Part 2: proofs from the standard identities

Prove each by algebra, naming the law used at each step. All sets lie in a universal set U.

(A \setminus B) \setminus C = (A \setminus C) \setminus B
(A \setminus B) \setminus (A \setminus C) = (A \cap C) \setminus B
B^{c} \setminus A^{c} = A \setminus B

Part 2: conditional statements

Prove that if A \subseteq B, then A \mathbin{\triangle} B = B \setminus A.
Prove that A \cap B = \varnothing exactly when A \mathbin{\triangle} B = A \cup B.
Prove that A \mathbin{\triangle} B = \varnothing exactly when A = B.
Prove that if A \subseteq B and C \subseteq D, then A \setminus D \subseteq B \setminus C.

Part 2: prove or disprove

Decide whether each equation holds for all sets. If not, give a counterexample and say which inclusion, if either, holds for all sets.

(A \setminus B) \cup B = A
A \cup (B \mathbin{\triangle} C) = (A \cup B) \mathbin{\triangle} (A \cup C)
(A \setminus B) \cup (B \setminus C) = A \setminus C
A \setminus (B \mathbin{\triangle} C) = (A \setminus B) \mathbin{\triangle} (A \setminus C)

Reasoning

Prove that if A \mathbin{\triangle} B = A \mathbin{\triangle} C, then B = C.
For finite sets, prove that \lvert A \mathbin{\triangle} B \rvert equals \lvert A \rvert + \lvert B \rvert - 2\lvert A \cap B \rvert.
Prove A \setminus (B \setminus C) = (A \setminus B) \cup (A \cap C) by algebra inside the universal set U = A \cup B \cup C, and again by elements. Explain why the element proof needed no universal set.
Prove that (A \setminus B) \cup (B \setminus C) \cup (C \setminus A) equals (A \cup B \cup C) \setminus (A \cap B \cap C).

Answers

A \setminus B = \{1, 2, 3, 4\}, B \setminus A = \{8, 9\}, and A \mathbin{\triangle} B = \{1, 2, 3, 4, 8, 9\}.
(A \cup B) \setminus C = \{1, 3, 5, 7, 9\}, since A \cup B = \{1, 2, \dots, 9\}. C \setminus (A \cap B) = \{2, 4, 8\}, since A \cap B = \{5, 6, 7\}.
A \setminus B is 0 \le x \le 2; the number 2 is in it because B starts strictly above 2. B \setminus A is 4 < x < 6. A \mathbin{\triangle} B is the numbers with 0 \le x \le 2 or 4 < x < 6.
A \setminus B is the even integers that are not multiples of 3: remainder 2 or 4. A \mathbin{\triangle} B adds the odd multiples of 3, remainder 3: so remainder 2, 3 or 4.
\subseteq: every element of a difference A \setminus X is in A. \supseteq: let x \in A. Elements of B \setminus A lie outside A, so x \notin B \setminus A, and x is in the left side.
Both sides say x \in A, x \in B, x \notin C. \subseteq: x \in A and x \in B \setminus C give x \in A \cap B and x \notin C. \supseteq: x \in A \cap B and x \notin C give x \in A and x \in B \setminus C.
\subseteq: x \in A \cup C and x \notin B \cup C give x \notin B and x \notin C; then x \in A, since x \notin C. So x \in (A \setminus B) \setminus C. \supseteq: x \in A puts x in A \cup C, and x \notin B, x \notin C give x \notin B \cup C.
For x \in U, x \in A^{c} exactly when x \notin A. So x is in exactly one of A^{c}, B^{c} exactly when it is outside exactly one of A, B, which is being in exactly one of them. Read forward this gives \subseteq, read backward \supseteq.
A \setminus \varnothing = A and \varnothing \setminus A = \varnothing, so A \mathbin{\triangle} \varnothing = A \cup \varnothing = A. Since A \setminus A = \varnothing, A \mathbin{\triangle} A = \varnothing \cup \varnothing = \varnothing.
\subseteq: an element of A \cup B is in exactly one of the sets, so in A \mathbin{\triangle} B, or in both, so in A \cap B. \supseteq: both parts lie inside A \cup B. No common element: elements of A \mathbin{\triangle} B are in one set only, those of A \cap B in both.
By the definition twice and the associative law, (A \setminus B) \setminus C = A \cap B^{c} \cap C^{c} and (A \setminus C) \setminus B = A \cap C^{c} \cap B^{c}. The commutative and associative laws for \cap make these equal.
(A \cap B^{c}) \cap (A \cap C^{c})^{c} = A \cap B^{c} \cap (A^{c} \cup C) by De Morgan and double complement. The distributive law gives (A \cap B^{c} \cap A^{c}) \cup (A \cap B^{c} \cap C). The first part is \varnothing by the complement and domination laws, so by the identity and commutative laws this is (A \cap C) \cap B^{c} = (A \cap C) \setminus B.
B^{c} \setminus A^{c} = B^{c} \cap (A^{c})^{c} = B^{c} \cap A by the definition and double complement, and B^{c} \cap A = A \cap B^{c} = A \setminus B by the commutative law.
Since A \subseteq B, A \setminus B = \varnothing. So A \mathbin{\triangle} B = \varnothing \cup (B \setminus A) = B \setminus A.
A \mathbin{\triangle} B \subseteq A \cup B always. If A \cap B = \varnothing, an element of A \cup B cannot be in both, so it is in exactly one, and A \cup B \subseteq A \mathbin{\triangle} B. Conversely, if the sets are equal and x \in A \cap B, then x \in A \cup B = A \mathbin{\triangle} B, so x is in exactly one set, a contradiction. So A \cap B = \varnothing.
If A = B, then A \mathbin{\triangle} A = \varnothing by Exercise 9. If A \mathbin{\triangle} B = \varnothing, then A \setminus B and B \setminus A are both empty, so A \subseteq B and B \subseteq A.
Let x \in A \setminus D. Then x \in A \subseteq B. If x \in C, then x \in D because C \subseteq D, but x \notin D. So x \notin C, and x \in B \setminus C.
Not an identity: A = \varnothing, B = \{1\} make the left side \{1\} and the right side \varnothing. A \subseteq (A \setminus B) \cup B always, since x \in A is in B or in A \setminus B. In fact the left side is A \cup B, so it equals A exactly when B \subseteq A.
Not an identity: A = B = C = \{1\} give left side \{1\} and right side \{1\} \mathbin{\triangle} \{1\} = \varnothing. Right \subseteq left holds: an element in exactly one of A \cup B, A \cup C cannot be in A, which would put it in both, so it is in exactly one of B, C. Equality holds exactly when A = \varnothing.
Not an identity: A = C = \{1\}, B = \varnothing give left side \{1\} and right side \varnothing. Right \subseteq left holds: for x \in A with x \notin C, either x \in B, so x \in B \setminus C, or x \notin B, so x \in A \setminus B.
Not an identity, and neither inclusion holds. A = \{1\}, B = C = \varnothing give left \{1\}, right \varnothing; A = B = \{1\}, C = \varnothing give left \varnothing, right \{1\}. For x \in A the left side needs x in both or neither of B, C, the right side in exactly one: the two sides share no element and together make up A.
By Example 7, A \mathbin{\triangle} (A \mathbin{\triangle} B) is (A \mathbin{\triangle} A) \mathbin{\triangle} B, which is \varnothing \mathbin{\triangle} B = B by Exercise 9 and commutativity. So taking A \mathbin{\triangle} of both sides of the hypothesis gives B = C.
A \setminus B and B \setminus A have no common element, so \lvert A \mathbin{\triangle} B \rvert = \lvert A \setminus B \rvert + \lvert B \setminus A \rvert. Each element of A is either outside B or in A \cap B, so \lvert A \setminus B \rvert = \lvert A \rvert - \lvert A \cap B \rvert, and likewise for B. Add.
Algebra: A \cap (B \cap C^{c})^{c} = A \cap (B^{c} \cup C) by De Morgan and double complement, and the distributive law makes this (A \cap B^{c}) \cup (A \cap C) = (A \setminus B) \cup (A \cap C). Elements: x \in A and x \notin B \setminus C mean x \notin B or x \in C, which puts x in A \setminus B or in A \cap C. Conversely, an element of either part is in A and is outside B or inside C, so it is not in B \setminus C. The chase used only x \in and x \notin for A, B, C themselves, never a complement, so no U arose.
\subseteq: an element of A \setminus B is in A, so in the union, and misses B, so it is not in all three; the other two parts are alike. \supseteq: let x be in at least one set but not all three. If x \in A: either x \notin B, giving A \setminus B, or x \in B and then x \notin C, giving B \setminus C. If x \notin A: either x \in C, giving C \setminus A, or x \in B and x \notin C, giving B \setminus C.