Lecture 18 — Proving Properties of Sets and Intro to Functions

lecture
discrete-math
set-theory
proof
functions

Pre-work: Video 023 (Properties of sets) and Video 024 (Functions defined on general sets). See proving-set-properties for the three proof methods and the set identities, and functions-on-general-sets for the function material in the second half.

Learning goals

  1. Be comfortable with notation for sets including \(x \in A\), \(A \subseteq B\), \(A \subset B\), \(A \cap B\), \(A \cup B\), \(A - B\), \(A^{c}\), \(\mathcal{P}(A)\), \(A \times B\).
  2. Be able to use the element method to prove set properties.
  3. Be able to use the laws of logical equivalence to prove that two sets are equal.
  4. Be able to use set identities to prove that two sets are equal.
  5. Understand what a function is, and associated concepts and definitions.

Goal 1 carries over from 2026-09-03-set-theory-definitions. For goal 2, the element method, the operational point is that \(A = B\) means \((A \subseteq B\) and \(B \subseteq A)\) — the shape every equality proof below takes.

Common questions

Q1 and Q3 from video 23, and Q1 and Q2 from video 24, are all worked below.

What is the difference between co-domain and range, and how do you distinguish between them? The co-domain is declared, the range is computed. See the functions section.

Worked: Q1 from video 23 — a proper subset

Let \(S = \{x \in \mathbb{Z} \mid x \equiv 2 \;(\mathrm{mod}\; 3)\}\) and let \(T = \{x \in \mathbb{Z} \mid x \equiv 5 \;(\mathrm{mod}\; 6)\}\).

\[S = \{\dots, -7, -4, -1, 2, 5, 8, 11, \dots\} \qquad T = \{\dots, -7, -1, 5, 11, \dots\}\]

Prove that \(T \subset S\). The proof splits into the two things \(\subset\) demands, (i) and (ii):

(i) \(T \subseteq S\). Suppose \(t \in T\). Then \(t = 6k + 5\) for some integer \(k\). Thus \(t = 3(2k+1) + 2\), and since \(2k + 1 \in \mathbb{Z}\), we have \(t \in S\). Therefore \(T \subseteq S\).

(ii) \(T \neq S\) and \(\exists s \in S - T\). Furthermore, \(2 \in S\) but \(2 \notin T\), so \(T \subset S\). \(\blacksquare\)

Part (i) is the general argument — “suppose \(t \in T\)”, nothing assumed beyond membership. Part (ii) is a single witness. A universal claim needs a general argument; an existential claim needs one example, and mixing up which is which is the usual way this proof goes wrong.

Worked: Q3 from video 23 — a Venn diagram is not a proof

For all sets \(A\), \(B\), \(C\): \(\;(A - B) \cap (B - A) = \emptyset\). True.

Three Venn diagrams — \(A\) and \(B\); then \(A - B\) shaded; then \(B - A\) shaded — show the result, but they are not a proof. The figure is in proving-set-properties.

Worth taking seriously, because the diagrams are so convincing. A Venn diagram shows one configuration; the claim is about all sets, including the cases the picture does not draw — \(A = B\), either set empty, one contained in the other. And the regions are drawn non-empty when the statement has to survive them being empty.

The proof takes two lines: suppose \(x \in (A-B) \cap (B-A)\); then \(x \in A\) and \(x \notin B\), and also \(x \in B\) and \(x \notin A\); so \(x \in B\) and \(x \notin B\), a contradiction. Hence no such \(x\), and the intersection is empty. \(\blacksquare\)

Diagrams to find the answer; the element method to justify it.

The element method of proof

To prove that \(S \subseteq T\), you consider an arbitrary element \(x \in S\) and show that \(x \in T\).

To prove that \(S \subset T\), you prove that \(S \subseteq T\) and then prove \(\exists\, t \in T\) such that \(t \notin S\).

To prove that \(S = T\), you prove that \(S \subseteq T\) and also prove that \(T \subseteq S\).

Worked: complementation reverses containment

Prove that for all sets \(A\) and \(B\) in some universe \(U\), if \(A \subseteq B\) then \(B^{c} \subseteq A^{c}\).

Proof. Let \(x \in B^{c}\). Then \(x \in U - B\) (by definition of complement). Thus \(x \in U\) and \(x \notin B\) (by definition of set difference).

Since \(A \subseteq B\) we have: every element in \(A\) is also an element of \(B\). Taking the contrapositive, \[x \notin B \;\longrightarrow\; x \notin A\] Since \(x \in U\) and \(x \notin A\), then by the definition of complement, \(x \in A^{c}\). \(\blacksquare\)

The step to notice is the contrapositive. \(A \subseteq B\) gives you “\(x \in A \rightarrow x \in B\)”, which is the wrong way round for what you have; flipping it to “\(x \notin B \rightarrow x \notin A\)” is what makes the hypothesis usable. See proof-techniques for why that flip is free.

Figure 1: The universe as a rectangle, A inside B, and B-complement hatched in red. The shading of the ring B − A is what makes the result readable off the picture: A-complement is the hatched region plus the ring, so it contains B-complement. A picture like this is a check on the answer, not a substitute for the element proof above.

The result itself is worth remembering as a fact: complementation reverses containment. The smaller set has the bigger complement.

Methods of proof for properties of sets

Three methods, and when each is useful:

Method Useful for Note
The element method a variety of results about sets the only one that can prove a containment, not just an equality
Laws of logical equivalence proving two sets are equal quicker
Set identities proving two sets are equal quicker

The element method has three sub-forms, the second of which does not mention a second set at all:

  1. To prove \(S \subseteq T\), suppose \(x \in S\) and then prove that \(x \in T\).
  2. To prove that all elements in a set \(S\) have property \(P\), suppose \(x \in S\), and then prove that \(x\) has property \(P\).
  3. To prove that \(S = T\), first prove that \(S \subseteq T\), and then prove that \(T \subseteq S\).

The laws of logical equivalence method

Example. Prove that for all sets \(A\) and \(B\), \(\;A - (A - B) = A \cap B\).

\[\begin{aligned} x \in A - (A - B) &\equiv (x \in A) \land \big(x \notin (A-B)\big) && \text{by definition of set difference} \\ &\equiv (x \in A) \land \sim\!\big(x \in (A-B)\big) && \text{by definition of } \notin \\ &\equiv (x \in A) \land \sim\!\big((x \in A) \land (x \notin B)\big) && \text{by definition of set difference} \\ &\equiv (x \in A) \land \big(\sim\!(x \in A) \lor \sim\!(x \notin B)\big) && \text{by De Morgan's law} \\ &\equiv (x \in A) \land \big((x \notin A) \lor (x \in B)\big) && \text{by definition of } \in \text{ and } \notin \\ &\equiv \big((x \in A) \land (x \notin A)\big) \lor \big((x \in A) \land (x \in B)\big) && \text{by the distributive law} \\ &\equiv \mathbf{c} \lor \big((x \in A) \land (x \in B)\big) && \text{by the negation law} \\ &\equiv (x \in A) \land (x \in B) && \text{by the identity law} \\ &\equiv x \in A \cap B && \text{by the definition of } \cap \end{aligned}\]

The justifications are of two kinds, and the grouping is the lesson. Four of the nine lines are laws of logical equivalence doing the actual work — De Morgan, distributive, negation, identity. The other five are definitions of set symbols, translating in and out of logic: the three at the top, the last one, and — easy to miss — the “\(\in\) and \(\notin\)” line sitting in the middle of the chain, so the two kinds do not fall into neat blocks. Every line is named; the naming is where the marks are.

Because the chain is all \(\equiv\), this proves the equality in one pass rather than the element method’s two containments.

Set identities

The full table is in proving-set-properties and appears on the exam formula page (see formula-sheet). The ones used below:

3(b) Distributive \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
4(a) Identity \(A \cup \emptyset = A\)
5(b) Complement \(A \cap A^{c} = \emptyset\)
6 Double Complement \((A^{c})^{c} = A\)
9(b) De Morgan’s \((A \cap B)^{c} = A^{c} \cup B^{c}\)
12 Set Difference \(A - B = A \cap B^{c}\)

Worked: the same equality by set identities

Using the set identities, prove that for all sets \(A\) and \(B\), \(\;A - (A - B) = A \cap B\).

The same result as the worked example, by the third method:

\[\begin{aligned} A - (A - B) &= A - (A \cap B^{c}) && \text{by the set difference law (12)} \\ &= A \cap (A \cap B^{c})^{c} && \text{by the set difference law (12)} \\ &= A \cap \big(A^{c} \cup (B^{c})^{c}\big) && \text{by De Morgan (9b)} \\ &= A \cap (A^{c} \cup B) && \text{by the double complement law} \\ &= (A \cap A^{c}) \cup (A \cap B) && \text{by the distributive law (3b)} \\ &= \emptyset \cup (A \cap B) && \text{by the complement law (5b)} \\ &= A \cap B && \text{by the identity law (4a)} \end{aligned}\]

Seven lines against the previous method’s nine, with no logic notation. Two things worth pulling out:

  • Law 12 is applied twice — to the inner difference, then the outer one. Clearing every minus sign first is what makes the rest routine, since none of the other identities mention set difference at all.
  • The final step cites identity law (4a), \(A \cup \emptyset = A\), but is applied to \(\emptyset \cup (A \cap B)\) — the operands reversed. Commutativity (1a) is being used silently. Standard practice, but the step is really two.

Russell’s paradox

When mathematicians wanted to show that all of mathematics could be built on set theory, Bertrand Russell discovered a problem.

Let \(S\) be the set of all sets that are not elements of themselves, \(S = \{A \mid A \text{ is a set and } A \notin A\}\). Is \(S\) an element of itself?

If \(S \in S\), then \(S \notin S\). If \(S \notin S\), then \(S \in S\). So we conclude that both \(S \in S\) and \(S \notin S\), which is impossible.

The natural objection — that a set is never an element of itself — is the right instinct but is not an escape, because nothing in “a set is any collection of objects” rules self-membership out. The contradiction is not that \(S\) is strange; it is that the assumption that every describable collection is a set cannot be maintained.

Several ways to define the basic concepts of set theory were found so that Russell’s paradox does not arise. For more detail, read pages 419–421 (5th ed.) or 378–380 (4th ed.) of the textbook. For more set theory, take MATH3306 Set Theory and Logic.

Definition of a function

A function \(f : X \to Y\) is a subset \(f \subseteq X \times Y\) such that for each \(x \in X\), there is a unique \(y \in Y\) such that \((x,y) \in f\).

So a function is a set of ordered pairs, and the notations are names for the same object:

\[y = 2x + 1 \qquad\text{or}\qquad f(x) = 2x+1 \qquad\text{or}\qquad f = \{(x,y) \in \mathbb{R} \times \mathbb{R} : y = 2x+1\}\]

with \(f(x) = y\) meaning exactly \((x,y) \in f\), which is the bridge between the two styles.

Three graphs: the plot of \(y = 2x+1\) through \((-5,-9)\), \((0,1)\) and \((5,11)\); a curve that is not a function, because a vertical line meets it twice; and a wiggly curve that is a function, despite taking the same value more than once. The asymmetry is the definition: repeated \(y\)-values are fine, repeated \(x\)-values are not. The plots are in functions-on-general-sets.

Worked: Q1 from video 24 — which set of pairs is a function?

Let \(X = \{1,2,3\}\) and \(Y = \{1,2,3,4\}\). Which one of the following is a function from \(X\) to \(Y\)?

There are three conditions to check — \(x \in X\), \(y \in Y\), and \(f(x)\) unique for all \(x \in X\):

Candidate Why
(a) \(\{(1,2), (1,3), (2,4)\}\) ✗ \(f(1) = 2\) and \(f(1) = 3\) — \(f(1)\) is not unique
(b) \(\{(1,2), (2,3), (3,2), (4,1)\}\) ✗ \(4 \notin X\)
(c) \(\{(1,2), (2,3), (3,5)\}\) ✗ \(5 \notin Y\)
(d) \(\{(1,2), (2,1), (3,1)\}\) ✓ \(1,2,3 \in X\) ✓, values \(1,2 \in Y\) ✓, and \(f(1) = 2\), \(f(2) = 1\), \(f(3) = 1\) all unique

Each wrong option breaks a different one of the three conditions — which is what makes the question worth the time. In (d), \(f(2) = f(3) = 1\); two inputs sharing a value is not a problem.

  1. fails twice over. As well as sending \(1\) to two places, it never gives \(3\) a value at all, so it breaks the “for each \(x \in X\)” half of the definition too.

Figure 2: The four candidates drawn out, one panel each, with the offending pairs in red. (a) sends 1 to two places and leaves 3 with no value at all; (b) has a pair starting outside X; (c) has a pair landing outside Y; (d) satisfies all three conditions. Each panel is an arrow diagram: domain left, co-domain right, elements as labelled dots, the two bags named beneath in blue, and each mapping a line carrying a small arrowhead partway along pointing from X to Y.

Drawn out in Figure 2, the three failures are visibly different shapes of mistake: a fan-out from one point of \(X\), a line starting outside \(X\), and a line landing outside \(Y\). Only (d) has exactly one line leaving each of \(1\), \(2\), \(3\), and both endpoints of every line in the right bag.

Q2 from video 24 — co-domain versus range

For a function \(f : X \to Y\) the co-domain is \(Y\) and the range is \(f(X) = \{f(x) : x \in X\}\), which is a subset of \(Y\).

For option (d) above:

\[\text{co-domain} = Y = \{1,2,3,4\} \qquad\qquad \text{range} = \{1,2\} \subseteq Y\]

The distinction in one line: the co-domain is declared when you write \(f : X \to Y\); the range is computed from the pairs. \(3\) and \(4\) are permitted values that this function never takes.

Image and preimage

If \(f : X \to Y\) is any function and \(A\) is any subset of \(X\), then the image of \(A\) is defined by \(f(A) = \{f(x) : x \in A\}\).

If \(f : X \to Y\) is any function and \(B\) is any subset of \(Y\), then the inverse image or preimage of \(B\) is defined by \(f^{-1}(B) = \{x \in X : f(x) \in B\}\).

Both take a set and return a set: \(f(A)\) and \(f^{-1}(B)\) are themselves sets. The emphasis on any matters too: \(f^{-1}(B)\) is defined for every function, invertible or not. It is not an inverse function.

Worked: images and preimages

Let \(X = \{1,2,3\}\) and \(Y = \{1,2,3,4\}\). From Q1 of video 24 above, \(\{(1,2), (2,1), (3,1)\}\) is a function from \(X\) to \(Y\).

So \(f(1) = 2\), \(f(2) = 1\), \(f(3) = 1\).

Asked for Working Answer
(a) image of \(\{1\}\) \(f(1) = 2\) \(f(\{1\}) = \{2\}\)
(b) image of \(\{2,3\}\) \(f(2) = 1\), \(f(3) = 1\) \(f(\{2,3\}) = \{1\}\)
(c) inverse image of \(\{2\}\) only \(1\) maps to \(2\) \(f^{-1}(\{2\}) = \{1\}\)
(d) preimage of \(\{1\}\) both \(2\) and \(3\) map to \(1\) \(f^{-1}(\{1\}) = \{2,3\}\)
(e) preimage of \(\{3,4\}\) nothing maps to \(3\) or \(4\) \(f^{-1}(\{3,4\}) = \emptyset\)

On an arrow diagram, the images follow the arrows forwards and the preimages follow them backwards. Both diagrams are in functions-on-general-sets.

The three things this set of answers is built to show: an image can shrink (b), a preimage can grow (d), and a preimage can be empty (e) when the set sits outside the range. All three are ordinary, not failures — and every answer is a set, so the braces are not optional. In part (c), write \(\{1\}\), not \(1\).

See also