Introduction to Proofs

Learning how to write mathematical proofs takes time and lots of practice. A proof of a mathematical statement is an explanation of that statement using appropriate notation and terminology. It is very important that you become comfortable with the definitions. If you don't know or understand the formal definitions, then you will not be able to write down your explanations. It would be like trying to explain something to someone in Italian without actually knowing Italian. During this semester, you will read and write mathematical proofs about logical systems. In this tutorial, we will introduce the basics of writing proofs about sets.

The notation "\(x \in X\)", "\(x\not\in X\)", "\(X\subseteq Y\)", "\(X\not\subseteq Y\)" and "\(X\subsetneq Y\)" are statements which may be true or false depending on what \(x\), \(X\) and \(Y\) refer to. The following table summarizes this notation and how to prove that the statement is true.

Notation	Description	To prove
\(x\in X\)	\(x\) is an element of \(X\)	Prove that \(x\) is listed in \(X\) or \(x\) has the property used to define the elements in \(X\).
\(x\not\in X\)	\(x\) is not an element of \(X\)	Prove that \(x\) is not listed in \(X\), or \(x\) does not have the property used to define the elements in \(X\).
\(X = Y\)	\(X\) equals \(Y\)	Prove that \(X\) and \(Y\) contain the same elements.
\(X\ne Y\)	\(X\) is not equal to \(Y\)	Prove that \(X\) and \(Y\) do not contain the same elements.
\(X\subseteq Y\)	\(X\) is a subset of \(Y\)	Prove that every element of \(X\) is an element of \(Y\), or there is no element of \(X\) that is not an element of \(Y\).
\(X\not\subseteq Y\)	\(X\) is not a subset of \(Y\)	Prove that there is some element of \(X\) that is not an element of \(Y\).
\(X\subsetneq Y\)	\(X\) is a proper subset of \(Y\)	Prove that \(X\subseteq Y\) and there is some element of \(Y\) that is not an element of \(X\).
\(X\subset Y\)	Same as \(X\subsetneq Y\)	Same as \(X\subsetneq Y\).
\(X = Y\)	\(X\) equals \(Y\)	Prove that \(X\subseteq Y\) and \(Y\subseteq X\).

How do you prove that two sets are equal? The answer to this question partly depends on who you are trying to convince. In this class, we will err on the side of caution and given fairly detailed proofs.

Fact. For all sets \(A\) and \(B\), \(A=B\) if and only if \(A\subseteq B\) and \(B\subseteq A\).

Why is this true? Well, if \(A\) and \(B\) are equal, then they both name the same collection of objects. I.e., \(B\) is another name for the collection of objects that \(A\) names and vice versa. So, if \(A\) and \(B\) are equal then of course \(A\subseteq B\) since \(A\) is always a subset of itself and \(B\) is simply another name for \(A\). Similarly, we can show \(B\subseteq A\). Conversely, suppose \(A\subseteq B\) and \(B\subseteq A\). We want to know that \(A\) and \(B\) name the same collection of objects. Suppose they didn't, then there should be some \(x\in A\) such that \(x\not\in B\) or some \(y\in B\) such that \(y\not\in A\). Since \(A\subseteq B\), every element of \(A\) is an element of \(B\) so there is no \(x\in A\) such that \(x\not\in B\). Similarly, since \(B\subseteq A\), there is no \(y\in B\) such that \(y\not\in A\). Hence, \(A\) and \(B\) must be the same set of objects.

What about trying to prove that two sets are not equal (i.e., \(A\neq B\))? This turns out to be easier. In order to show that \(A\) does not equal \(B\), you need only find an element in \(A\) that is not in \(B\) or an element of \(B\) that is not in \(A\).

Showing two sets are equal reduces to proving that the sets are subsets of each other. But, how to show that a set is a subset of another set? The general procedure to show \(A\subseteq B\) is to show that each element of \(A\) is also and element of \(B\). This is straightforward if \(A\) and \(B\) are both finite sets. For example, suppose \(A=\{2,3,4\}\) and \(B=\{1,2,3,4,5,6\}\). How do we show that \(A\subseteq B\). Since \(A\) is finite, we simply notice that \(2\in B\), \(3\in B\) and \(4\in B\).

What if \(A\) is the set of even numbers and \(B\) is the set of all integers? We would get awfully tired (and bored) if we waited around to show that each and every element of \(A\) is also an element of \(B\). Imagine \(A\) and \(B\) are two boxes, and you would like to know whether all the elements in \(A\)'s box are also in \(B\)'s box. Suppose you reach in box \(A\) and select an element, say the number 10. After inspecting 10, you notice that 10 is in fact an integer and so must also be an element of box \(B\). But you are not satisfied, since you cannot be sure that the next element you choose from \(A\) will also be an element of \(B\). In fact, even if you have shown that the first million even integers are all members of box \(B\), you cannot be sure that the next element you select from box \(A\) will in fact be an integer. Instead, you should consider the property that all elements of \(A\) have in common and show that any object satisfying that property must be an element of \(B\). If \(x\in A\), then \(x\) is an even number, so \(x=2\cdot n\), where \(n\) is some integer. Then, since if \(n\) is an integer, then \(2\cdot n\) is also an integer; we must have that every element of \(A\) is also an element of \(B\). Later in the semester we will learn other techniques for proving statements about infinite sets.

Examples

In this section, we give two examples of mathematical proofs.

Claim 1. For all sets \(A\) and \(B\), \(\overline{A}\cup \overline{B}=\overline{A\cap B}\).

Proof. We must show that \(\overline{A}\cup \overline{B}\subseteq\overline{A\cap B}\) and \(\overline{A\cap B}\subseteq \overline{A}\cup \overline{B}\).

Suppose that \(x\in \overline{A}\cup \overline{B}\). Then \(x\in \overline{A}\) or \(x\in \overline{B}\). There are two cases. First, suppose that \(x\in\overline{A}\). Then, \(x\not\in A\). This implies that \(x\not\in A\cap B\) (this follows since if \(x\) is not in \(A\) then \(x\) is not in both \(A\) and \(B\)). Hence, \(x\in\overline{A\cap B}\). Second, suppose that \(x\in\overline{B}\). A similar argument shows that \(x\in\overline{A\cap B}\). Hence, in either case, \(x\in\overline{A\cap B}\). Therefore, \(\overline{A}\cup \overline{B}\subseteq\overline{A\cap B}\).

Suppose that \(x\in \overline{A\cap B}\). Then, \(x\not\in A\cap B\), and so \(x\not\in A\) or \(x\not\in B\). Hence either \(x\in\overline{A}\) or \(x\in\overline{B}\). If \(x\in \overline{A}\), then since \(\overline{A}\subseteq \overline{A}\cup \overline{B}\), we have that \(x\in \overline{A}\cup\overline{B}\). Similarly, if \(x\in\overline{B}\), then \(x\in\overline{A}\cup\overline{B}\). In either case, \(x\in\overline{A}\cup\overline{B}\). QED

Warning

Notice that \(x\not\in A\cap B\) does not imply that \(x\not\in A\) and \(x\not\in B\). The "and" in italics should be an "or". Make sure you clearly understand the logic here, since this is often misunderstood by students.

Claim 2. For all sets \(A\) and \(B\), \(A\subseteq B\) if and only if \(A\cap B=A\).

Proof. We must show that \(A\subseteq B\) implies \(A\cap B=A\) and \(A\cap B=A\) implies \(A\subseteq B\).

We first show that \(A\subseteq B\) implies \(A\cap B=A\). Suppose that \(A\subseteq B\). We must show that \(A\cap B=A\). I.e. we must show (1) \(A\cap B\subseteq A\) and (2) \(A\subseteq A\cap B\). The first statement is trivial, it is always the case that \(A\cap B\subseteq A\). For the second statement, suppose that \(x\in A\). We must show \(x\in A\cap B\). Since \(A\subseteq B\) and \(x\in A\), we have that \(x\in B\). Hence \(x\in A\cap B\).

Second, we must show that \(A\cap B=A\) implies \(A\subseteq B\). Suppose that \(A\cap B=A\). We must show \(A\subseteq B\). Let \(x\in A\). Then \(x\in A\cap B\) since \(A=A\cap B\). Hence \(x\in B\). QED

Venn Diagrams

A Venn diagram is a picture that represents all the possible relationships between sets. For example, the following pictures represents all the possible relationships between two sets \(A\) and \(B\):

A Venn diagram.

There are 4 distinct regions in the above picture:

• region \(1\) is for items that are not in \(A\) and not in \(B\);
• region \(2\) is for items in \(A\) that are not in \(B\);
• region \(3\) is for items in both \(A\) and \(B\); and
• region \(4\) is for items that are not in \(A\) and are in \(B\).

It is important to remember that in Venn diagrams, some of the regions might be empty, i.e., the region does not contain any elements. For example, if \(A\subseteq B\), region \(2\) does not contain any elements (since every element in \(A\) is in \(B\)). To represent this subset relation between \(A\) and \(B\) we can draw the \(A\) region inside the \(B\) region: Techincally, this is called a Euler diagram. Eurler diagrams do not represent the regions that are known to be empty.

Subset

Typically, one shades a region corresponding to a set in a Venn diagram. For example, the 4 regions described above are shaded as follows (each region is labeled with the corresponding set):

The 4 regions of a Venn diagram .

Shading multiple regions in a Venn diagram corresponds to different ways to combine sets using union, intersection, complement, set difference, and symmetric difference. Since there are 4 different regions for two sets, there are 16 different ways to shade these regions (since any subset of the set of 4 regions can be shaded, recall that if \(X\) is a set with 4 elements, then the powerset has \(2^4=16\) elements). The next Figure shows all of the 16 possible shaded regions for two sets \(A\) and \(B\) labeled with the corresponding set. The lines represent the subset relation (read from the bottom to the top). For instance, the line from the \(A\cap B\) diagrm to the \(A\) diagram means that \(A\cap B\subseteq A\).

All shaded Venn diagrams for two sets.

Extra Reading

• Chapter 4 of Open Logic Initiative Notes on Sets, Functions and Relations.

• For a more comprehensive introduction to writing mathematical proofs, I strongly recommend the following books:

  • Joel David Hamkins, Proof and the Art of Mathematics, The MIT Press, 2020.

  • Richard Hammack, Book of Proof, 2013.

Exercises

1. Prove that for all sets \(A\) and \(B\), \(A\setminus B = A\cap \overline{B}\)

   Answer

   Proof. We must show that \(A\setminus B\subseteq A\cap \overline{B}\) and that \(A\cap \overline{B}\subseteq A\setminus B\). Suppose that \(x\in A\setminus B\). Then \(x\in A\) and \(x\not\in B\). Since \(x\not\in B\), we have that \(x\in \overline{B}\). Hence, \(x\in A\cap \overline{B}\). Therefore, \(A\setminus B\subseteq A\cap \overline{B}\). Now, suppose that \(x\in A\cap \overline{B}\). Then, \(x\in A\) and \(x\in\overline{B}\). Since, \(x\in\overline{B}\), we have that \(x\not\in B\). Hence, \(x\in A\setminus B\). Therefore, \(A\cap \overline{B}\subseteq A\setminus B\). QED

2. Prove that for all sets \(A\) and \(B\), \(\overline{A}\cap \overline{B}=\overline{A\cup B}\).

   Answer

   Proof. We must show that \(\overline{A}\cap \overline{B} \subseteq \overline{A\cup B}\) and \(\overline{A\cup B} \subseteq \overline{A}\cap \overline{B}\). Suppose that \(x \in \overline{A}\cap \overline{B}\). Then \(x \in \overline{A}\) and \(x\in \overline{B}\). Hence, \(x\not\in A\) and \(x\not\in B\). This implies that \(x\not\in A\cup B\) (for if \(x\in A\cup B\), then \(x\in A\) or \(x\in B\)). Hence, \(x\in \overline{A\cup B}\); and so, \(\overline{A}\cap \overline{B} \subseteq \overline{A\cup B}\).

   Suppose that \(x\in \overline{A\cup B}\) Then \(x\not\in A\cup B\). This means that \(x\not\in A\) and \(x\not\in B\). Hence, \(x\in \overline{A}\) and \(x\in\overline{B}\); and so, \(x\in \overline{A}\cap \overline{B}\). Therefore, $ \overline{A\cup B}\subseteq \overline{A}\cap \overline{B}$.
   QED

3. Suppose that \(F:A\rightarrow B\). Prove or disprove the following: If \(X\subseteq A\) and \(Y\subseteq A\), then \(F(X\cap Y) = F(X)\cap F(Y)\).

   Answer

   Claim. It not the case that if \(X\subseteq A\) and \(Y\subseteq A\), then \(F(X\cap Y)\neq F(X)\cap F(Y)\).

   Proof. To prove this, we must find counterexample. Let \(A=\{1,2,3\}\) and \(B=\{a,b,c\}\). Lef \(F:A\rightarrow B\) be defined as follows: \(F(1)=c\), \(F(2)=b\) and \(F(3)=c\). Now, let \(X=\{1,2\}\) and \(Y=\{2,3\}\). Then \(X\cap Y=\{2\}\) and

   \[ F(X\cap Y)=F(\{2\})=\{F(2)\}=\{b\}. \]

   But, we also have that:

   \[ F(X)\cap F(Y)=\{F(1),F(2)\}\cap \{F(2),F(3)\}=\{c,b\}\cap \{b,c\}=\{b,c\} \]

   Hence, \(F(X\cap Y)\neq F(X)\cap F(Y)\). QED

   Note

   It is true that for any function \(F:A\rightarrow B\) and all subsets \(X,Y\subseteq A\), \(F(X\cap Y)\subseteq F(X)\cap F(Y)\) (for a proof see below).

4. Suppose that \(F:A\rightarrow B\). Prove or disprove the following: If \(X\subseteq A\), \(Y\subseteq A\) and \(F\) is injenctive,then \(F(X\cap Y)=F(X)\cap F(Y)\).

   Answer

   Claim. If \(X\subseteq A\), \(Y\subseteq A\) and \(F\) is injenctive,then \(F(X\cap Y)=F(X)\cap F(Y)\).

   Proof. Suppose that \(F:A\rightarrow B\) is a 1-1 function. Let \(X\subseteq A\) and \(Y\subseteq A\). We must show that (1) \(F(X\cap Y)\subseteq F(X)\cap F(Y)\) and (2) \(F(X)\cap F(Y)\subseteq F(X\cap Y)\).

   Notice that (1) is true even if \(F\) is not 1-1. Let \(y\in F(X\cap Y)\). Then there is an element \(x\in X\cap Y\) such that \(F(x)=y\). Since \(x\in X\cap Y\), \(x\in X\) and \(x\in Y\). Therefore, \(y=F(x)\in F(X)\) and \(y=F(x)\in F(Y)\). Hence, \(y\in F(X)\cap F(Y)\).

   We now prove (2). Let \(y\in F(X)\cap F(Y)\). Then \(y\in F(X)\) and \(y\in F(Y)\). Since \(y\in F(X)\) there is \(x_1\in X\) such that \(F(x_1)=y\). Since \(y\in F(Y)\), there is \(x_2\in Y\) such that \(F(x_2)=y\). Since \(F\) is 1-1, \(x_1=x_2\). Therefore \(x_1=x_2\in X\cap Y\); and so, \(y=F(x_1)=F(x_2)\in F(X\cap Y)\). QED

5. Suppose that \(F:A\rightarrow B\). Prove or disprove the following: If \(X\subseteq B\) and \(Y\subseteq B\), then \(F^{-1}(X\cap Y)=F^{-1}(X)\cap F^{-1}(Y)\).

   Answer

   Claim If \(X\subseteq B\) and \(Y\subseteq B\), then \(F^{-1}(X\cap Y)=f^{-1}(X)\cap F^{-1}(Y)\).

   Proof. Let \(F:A\rightarrow B\) be any function and suppose \(X\subseteq B\) and \(Y\subseteq B\). We must show \(F^{-1}(X\cap Y)\subseteq F^{-1}(X)\cap F^{-1}(Y)\) and \(F^{-1}(X)\cap F^{-1}(Y)\subseteq F^{-1}(X\cap Y)\).

   Suppose that \(x\in F^{-1}(X\cap Y)\). Then \(F(x)\in X\cap Y\). Hence \(F(x)\in X\) and \(F(x)\in Y\). Since \(F(x)\in X\), \(x\in f^{-1}(X)\). Since \(F(x)\in Y\), \(x\in f^{-1}(Y)\). Therefore, \(x\in F^{-1}(X)\cap F^{-1}(Y)\).

   Suppose that \(x\in F^{-1}(X)\cap F^{-1}(Y)\). Then \(x\in F^{-1}(X)\) and \(x\in F^{-1}(Y)\). Therefore, \(F(x)\in X\) and \(F(x)\in Y\). Hence, \(F(x)\in X\cap Y\); and so, \(x\in F^{-1}(X\cap Y)\). QED