This is an ongoing series intended to help aspiring young (or young at heart) learners make the transition from the computation-based mathematics taught in US public schools and proof-based mathematics found at higher levels of mathematics education. See here for Part One. See here for Part Two. For a list of notation and definitions, see here.

 

As mentioned last time, following your nose might not always be the best approach. Therefore, it only makes sense for us to learn some other techniques for proving stuff. Here is a very important proof strategy, and some examples of it in action.

 

Contradiction

A proof by contradiction follows a very simple premise. Suppose you want to prove the statement \(P\) is true. You first assume that \(P\) is actually false, and then use deduction to “prove” something false. Since we can show that this resulting statement is actually true, that tells us that \(P\) had to be true all along.

 

Let’s consider an example. Recall from Part 2 our definitions of a topology and open sets.

Definition: Let \(T\) be a topology on \(X\) and \(S\subseteq X\). A limit point of \(S\) is an element \(x\in  X\) such that for every open set \(U\in T\) with \(x\in U\), there is some point \(y\in U\cap S\) with \(y\not=x\).

Notice that just from this definition, \(x\) need not be in \(S\). This leads to the following definition.

Definition: If \(T\) is a topology on \(X\), then a set \(U\subseteq X\) is a closed set if it contains all of its limit points.

This is different from the more standard definition of a closed set, which is as follows:

Definition: If \(T\) is a topology on \(X\), then a set \(U\subseteq X\) is a closed set if \(\{x\in X: x\not\in U\}\)  (called the complement of \(u\) and denoted by \(U^c\)) is open.

Having two definitions like this could cause problems, as it might be possible for a set to have one property and not the other. Then it would be ambiguous what we actually mean by the term closed. For this reason, we will prove that any set with one property automatically must have the other, thus making sure this isn’t an issue.  There are two things we need to do. First, given a set which contains all of its limit points, we need to show that its complement is open. Second, given a set whose complement is open, we must show it contains all of its limit points. We shall use an argument by contradiction in each case.

First, suppose \(U\) contains all of its limit points but its complement is not open. Then there is some point \(x\in U^c\) such that for any open set \(V\) with \(x\in V\), \(V\cap U\) is nonempty.

•  (Here we will use a different contradiction argument to prove such a point exists. This “argument within an argument” will be indented to make the structure a bit more clear.) If there were no such point, then for each \(x\in U^c\) let \(V_x\) be an open set containing \(x\) which has empty intersection with \(U\), e.g. \(V_x\subseteq U^c\). Then \(\bigcup_{x\in U^c}V_x\) is an open set by the third property of a topology, but \(\bigcup_{x\in U^c}V_x=U^c\): If \(x\in U^c\), then \(x\in V_x\subseteq \bigcup_{x\in U^c}V_x\). If \(y\in \bigcup_{x\in U^c}V_x\), then \(y\in V_x\subseteq U^c\) for some \(x\in U^c\). Therefore \(U^c\in T\), contradicting our assumption that it was not. Thus such an \(x\) must exist.

Now notice that \(x\) is a limit point of \(U\): For any open set \(V\) containing \(x\), \(V\cap U\) is not empty. But \(x\in U^c\), so \(x\not\in U\), so \(V\cap U\) contains something not equal to \(x\). This is the definition of being a limit point, so we have a contradiction of the assumption that \(U\) contains all of its limit points. Therefore the complement of \(U\) must be open. This completes the proof that any set with the first property must have the second property.

 

Now suppose that \(U\) is a set such that \(U^c\) is open but there is a limit point \(x\) of \(U\) such that \(x\in U^c\). But since \(U^c\) is open, by the definition of a limit point we must have \(y\not=x\) with \(y\in U\cap U^c\). But then \(y\in U\), which contradicts the fact that \(y\in\{x\in X:x\not\in U\}=U^c\). Therefore \(U^c\) cannot contain a limit point of \(U\), so \(U\) must contain all of its limit points. This completes the proof that every set with the second property must have the first property, and our proof as a whole.

 

Argument by contradiction is an important and powerful tool in mathematics. Some of the most famous proofs in all of mathematics (the proof that there are infinitely many primes and the proof that the square root of 2 is irrational) use a contradiction argument. It’s important to learn and become comfortable with proving statements using arguments with this structure.