2.4: Mathematical Proof

Proof is an undefined term. It is also central to mathematics. Mathematicians, the group of people of whom you are currently part, think of proofs in two, related contexts. First proving a statement is about understanding that statement. When we can explain an idea based on already understood and accepted ideas, we understand the new statement. Second a proof is a means of communicating an understanding of a statement.

Note that the process of proving a statement is often inelegant and the result is often messy. At this point another trait of mathematicians comes into play: we love to produce better versions of things. We can take this messy result and clean it up to communicate it in a (more) elegant way.

First set proofs

Consider the statement: $A \cap B \subseteq A$. This statement is about being a subset. It begins with an intersection ($A \cap B$) and ends with another set $(A)$. So we need to start with $x \in A \cap B$ and end up with $x \in A$. To bridge we have only the definition of intersection. It says $x \in A \cap B$ implies $x \in A$ and $x \in B$ The first part is all we need.

Theorem $\PageIndex{1}$: An intersection is a subset of either set.

For any two sets A and B, $A \cap B \subseteq A$.

Proof

Let $x \in A \cap B$. By definition of intersection $x \in A \cap B$ implies $x \in A$. Thus $x \in A \cap B$ implies $x \in A$. This is the definition of subset, so $A \cap B \subseteq A$.

Consider the statement: $A-B \subseteq \neg B$. This statement is also about being a subset. This begins with the set difference $A−B$ and ends with the set complement $\neg B$. So we need to start with $x \in A − B$ and end up with $x \in \neg B$. To bridge this we can use both the definition of set difference and the definition of set complement. The set difference definition tells us that $x \in A-B$ means $x \in A$ and $x \not\in B$. The second part looks like set complement. But that requires that $x \in U$. Thus this will only work if \(A \subseteq U\) (that is $A$ and $B$ have the same universal set).

Theorem $\PageIndex{2}$: A set difference is part of the complement.

For any two sets $A, B \subseteq U, A-B \subseteq \neg B$.

Proof

Let $x \in A-B$. By definition of set difference $x \not\in B$ Because \(A \subseteq U\), $a \in U$. Combining these two produces $x \in U-B=\neg B$. Thus $x \in A-B$ implies $x \in \neg B$. Hence $A-B \subseteq \neg B$.

Practice

Checkpoint $\PageIndex{3}$

Prove $A \cap B \subseteq B$.

Checkpoint $\PageIndex{4}$

Prove $A \cap B \subseteq A \cup B.$