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.

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. For a list of notation and definitions, see here.

Proofs make math go. When it comes to verifying whether or not a statement is true, mathematicians have the highest possible bar: a deductive proof. A deductive proof of a statement from assumptions is such that the statement is always true if the assumptions are true. Contrast this with something like the scientific method, which argues that a statement is likely true or false based on observational tests. In this case, it’s always possible (albeit unlikely with proper controls) that our observations were affected by some unconsidered factor, or random chance gave us poor observations to work from. In math, we do not allow arguments that could fall victim o this. In some sense, we account for every possible factor, even the most zany of possibilities, to ensure that the statement is always true.

At a basic level, definitions make proofs go. Definitions are exactly what you think they are based on the usual use of the word, but with an important caveat to consider. In everyday language, we have an intuition about certain words, phrases, and terms that may occasionally run counter to the “official” definition. Even worse (from a mathematician’s perspective,) some definitions depend on context or a person’s subjective taste: A tasty meal for me might not be a tasty meal for you. In mathematics, this subjectivity cannot happen. If your definition is ambiguous, then it is not a mathematical definition at all. This idea of being free from ambiguity is sometimes known as being “well-defined.” We’ll demonstrate how this might lead to struggles with your intuition with a familiar term from calculus, but first we need some background.

Definition: A topological space is a set \(X\) together with a set \(T\subseteq\mathcal{P}(X)\) satisfying the following properties:

• \(\emptyset\in T\) and \(X\in T\)
• If \(A,B\in T\), then \(A\cap B\in T\)
• If \(Y\subseteq T\), then \(\bigcup_{A\in Y} A\in T\)

We call \(X\) the space, \(T\) the topology, and the elements of \(T\) open sets.

Definition: Let \(X\) and \(Y\) be topological spaces with topologies \(T_X\) and \(T_Y\) respectively. A function \(f:X\to Y\) is continuous if \(f^{-1}(A)\in T_X\) for all \(A\in T_Y\).

Now consider the function \(f:\mathbb{N}\to\mathbb{R}\) defined by \(f(x)=\pi+x\). Let the topology for \(\mathbb{N}\) be \(\mathcal{P}(\mathbb{N})\). Now notice that no matter what the topology on \(\mathbb{R}\) is, \(f\) is a continuous function: If \(Y\subseteq\mathbb{R}\), then \(f^{-1}(A)\subseteq\mathbb{N}\). Therefore by definition, \(f^{-1}(A)\in\mathcal{P}(\mathbb{N})\). Thus the function is continuous by our definition of continuity, as the inverse of any subset (and hence all open subsets) is open. If we were to graph this function though, our intuition might tell us that it isn’t continuous as it is just a handful of discrete points in the plane. Strange situations like these are why paying attention to definitions is so important in mathematics.

Congratulations! You’ve already seen a proof now. We proved that the function \(f\) is continuous using the definition. Let’s go through it again, changing the format slightly to make it a bit more clear what is going on. First, we want to prove that \(f\) is continuous. By the definition of continuity, that means that we need to show that \(f^{_1}(A)\in\mathcal{P}(\mathbb{N})\) for all \(A\in T_\mathbb{R}\). (Here \(T_\mathbb{R}\subseteq\mathcal{P}(\mathbb{R})\). Normally the continuity of a function would depend on the topology of its image, but in this case the topology of the domain is nice.) Of course it is true, by the definition of the inverse image, that \(f^{-1}(X)\subseteq\mathbb{N}\) for all \(X\subseteq\mathbb{R}\), so \(f^{-1}(X)\in\mathcal{P}(\mathbb{N})\). In particular, this is true for all \(X\in T_\mathbb{R}\). Thus \(f\) is continuous.

Notice that at each step, we proceeded in the simplest way we could: we wanted to show \(f\) was continuous, so we attempted to show directly that it satisfied the definition. To show that it satisfied the definition, we looked directly at the inverse image. Using that definition and the definition of the power set, we were able to finish our argument. This style of arguing, just looking at definitions and moving in the simplest possible way forward, is sometimes known as “following your nose.” Following your nose isn’t always going to work out, though, so next time we’ll go over some common proof strategies.

Check Your Understanding

Check Your Understanding-Solutions

Common Notations:

\(\mathbb{N}\): The set of natural numbers \(1,\ 2,\ 3,\ \dots\) and so on. It is a matter of style whether or not to include \(0\) in \(\mathbb{N}\), we shall do so unless explicitly stated otherwise.

\(\mathbb{Z}\): The set of positive and negative whole numbers, \(\dots, -2,\ -1,\ 0,\ 1,\ 2,\ \dots\)

\(\mathbb{Q}\): The rational numbers, e.g. the numbers which can be represented as a fraction of two integers where the denominator is nonzero.

\(\mathbb{R}\): All real numbers.

Informal Notions:

Set: A collection of things.

Empty Set: The unique set with no elements, denoted by \(\emptyset\).

Set Builder Notation: If \(P(x)\) is some statement about elements of a set \(Y\), then \(\{x\in Y:P(x)\}\) is the set containing all objects \(x\in Y\) that satisfy \(P(x)\). As an example, if \(P(x)\) says “\(x\) is even”, then \(\{x\in\mathbb{N}:P(x)\}\) is the set of even natural numbers.

Subset: If \(X\) and \(Y\) are sets, then \(Y\) is a subset of \(X\), written \(Y\subseteq X\), if everything in \(Y\) is in \(X\).

Elements: If \(X\) is a set and \(a\) is something inside the collection represented by \(X\), we say \(a\) is an element of \(X\) and write \(a\in X\).

Power Set: If \(X\) is a set, then the power set of \(X\), written \(\mathcal{P}(X)\), is the set whose elements are exactly the subsets of \(X\).

Union: If \(A\) and \(B\) are sets, then \(A\cup B\) denotes their union, the set of all elements in at least one of \(A\) or \(B\). If \(T\) is a set of sets, then \(\bigcup_{A\in T} A\) denotes the union of all the elements of \(T\), i.e. \(a\in \bigcup_{A\in T} A\) if and only if \(a\in A\) for some \(A\in T\).

Intersection: If \(A\) and \(B\) are sets, then \(A\cap B\) denotes their intersection, the set of all elements in both\(A\) and \(B\). If \(T\) is a set of sets, then \(\bigcap_{A\in T} A\) denotes the intersection of all the elements of \(T\), i.e. \(a\in \bigcap_{A\in T} A\) if and only if \(a\in A\) for all \(A\in T\).

Set Equality: Two sets are considered equal if they have the same elements. That is, if every element of \(A\) is in \(B\) and every element of \(B\) is in \(A\), then \(A=B\). Equal sets are indistinguishable, so if \(A=B\) and \(A\in C\), then \(B\in C\).

Function: A function \(f:X\to Y\) is a set of pairs \((x,y)\) such that \(x\in X\), \(y\in Y\), and for every \(x\in X\) there is a unique \(y\in Y\) such that \((x,y)\in f\). If \((x,y)\in f\), then we say \(f(x)=y\). Note that the \(y\) only needs to be unique for a fixed \(x\), we can choose the same \(y\) for multiple \(x\)’s but only one \(y\) per \(x\).

Inverse Image: If \(f:X\to Y\) is a function and \(A\subseteq Y\), then \(f^{-1}(A)=\{x\in X: f(x)\in A\}\).

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.

If you’re reading this, you probably like math to some extent. Or someone is making you read it, but let’s be optimistic and assume the former! Before we get into the nitty-gritty, though, you should probably know WHAT you’re reading.

What is this series about?

The goal of this series is to help aspiring mathematicians (or anyone looking to broaden their mathematical horizons) understand the difference between computationally-based math (arithmetic, middle-school algebra, calculus, etc.) and proof-based math (abstract algebra, topology, mathematical logic, etc.) Mathematics undergoes a paradigm shift some time after the calculus sequence: it’s no longer about applying algorithms that you’ve been told to memorize to compute some number of formula. Rather, it asks you to use your knowledge of mathematical facts, properties, theorems, etc. to discover more facts, properties, theorems, etc. The difference between the two is palpable, and if you’re anything like me the transition can be a bit overwhelming, especially if you’re studying on your own. This series aims to provide some example and tips to better illustrate how to think about proofs.

Who is this for?

The target audience is anyone who would like to have a better understanding of the flow of higher level mathematics, a feel for what it’s all about so to speak. The amount of mathematical sophistication required to understand each entry may vary, but a serious attempt will be made to make each one accessible to anyone regardless of mathematical skill.

If you struggle with the basics, like arithmetic or high school algebra, it might be prudent to refresh your knowledge in these areas first: mathematics is notorious for building on itself, and trying to learn higher level concepts without a solid understanding of the basics is like trying to play a game of Jenga with hooves instead of hands.

If you’re already an accomplished “prover,” i.e. you’ve taken a proof-based mathematics course at the university level and passed, then this series might move a bit too slowly for you.

If you’re looking for help understanding a specific mathematical concept, such as differentiation, the quadratic equation, ideals of rings, and so on, then this probably won’t help with that. Examples will be used to illustrate our talking points, but the main focus won’t be on understanding specific techniques or notions.

If you’re still here, and those disclaimers didn’t drive you away, then great! In the next entry we’ll get right into the thick of things, learning how to think about definitions and proofs in a mathematical sense.

Quantifiers – Structure, Universe, and Scope

If you’re thinking about learning math beyond the standard high school curricula, chances are you’ve either seen quantifiers already or will see run into them very soon. Getting comfortable with quantifiers is critical for studying higher levels of mathematics, but fortunately they are quite simple. Quantifiers appear before a statement, and tell you what that statement applies to. As an example, we’ll consider the statement “\(x\) is an even number,” and write it as \(E(x)\) for shorthand. (E.g. \(E(2)\) stands for “\(2\) is an even number” and \(E(5)\) stands for “\(5\) is an even number.”)

There are two types of quantifiers. The first type is the universal quantifier, written as \(\forall\), and followed by a variable which will give us a name to reference. The universal quantifier is usually spoken in English as “for all,” and as this might suggest it tells you to apply the statement to “everything.” (We’ll discuss exactly what “everything” means a little later.) As an example, we might say \(\forall x\ E(x)\). In other words, this says “For all \(x\), \(x\) is an even number.”

The second type is the existential quantifier, written as \(\exists\). In English we would say “there exists.” It uses the same structure as a universal quantifier, so we could say \(\exists x\ E(x)\). This would say “There exists an \(x\) that is an even number.”

It is important to observe that the universal quantifier and the existential quantifier are in some sense opposites of each other: If \(P(x)\) is any statement about \(x\), then \(\forall x\ P(x)\) is true, i.e. every \(x\) satisfies \(P(x)\), if and only if the statement “There exists an \(x\) such that \(P(x)\) is not true” is true. Similarly, \(\exists x\ P(x)\) is true if and only if “For all \(x\), \(P(x)\) is not true” is false. (Often the symbol \(\neg\) is used to denote the negation of something, e.g. \(\neg P(x)\) would be read as “\(P(x)\) does not hold.” For example, we could rewrite “There exists an \(x\) such that \(P(x)\) is not true” as \(\exists x\ \neg P(x)\).)

The Universe

    When reading quantifiers, it is absolutely critical that you know what the “universe” is in context. Here the universe is some collection of objects, not necessarily all of them, and we only care about the statement applied to that specific collection. For example, consider the following statement:

\[\forall x\ \forall y\ \text{If }x<y\text{ then }\exists z\ \text{with }x<z\text{ and }z<y\]

In English, this says “For every \(x\) and \(y\), if \(x\) is less than \(y\), then there is a \(z\) with \(z\) greater than \(x\) and less than \(y\).” Is this statement true?

The answer is actually a little complicated. Suppose our universe is all of the integers, or whole numbers. (Think \(1\), \(-5\), \(372\), and so on, but no simplified fractions with a denominator that isn’t \(1\) are allowed.) Then this statement is false: If \(x=0\) and  \(y=1\), then \(x<y\) is certainly true, but there is no whole number \(z\) which is bigger than \(0\) but smaller than \(1\). Notice, though, that \(\frac{1}{2}\) does satisfy these inequalities, but it is not in our universe. Now if we let our universe be all possible fractions, not just the integers, then the statement becomes true. For any fractions \(x\) and \(y\) with \(x<y\), consider \(\frac{x+y}{2}\). This is clearly a fraction, as it is the sum of two fractions divided by \(2\), so it is in our universe. Furthermore, \(x<\frac{x+y}{2}\) and \(\frac{x+y}{2}\), so it satisfies our inequalities. (To see this last fact, note that \(2x=x+x<x+y\) since \(x<y\) and \(2y=y+y>x+y\) for the same reason.)

Keep this in mind when dealing with quantifiers: a statement can easily be true in one universe and false in another. In fact, some areas of mathematics have healthy research communities dedicated to finding exactly which “universes” a specific statement holds for. (The classification of all finite simple groups is a famous example, if a bit complicated: https://en.wikipedia.org/wiki/Classification_of_finite_simple_groups )

The Scope of a Quantifier

One final thing to keep in mind when reading quantifiers: the scope. Consider the following statement:

\[\forall x\ \text{if }\exists z\ z<x\text{ then }\forall y\ y<x+y\]

The scope of a quantifier is the amount of the statement that the quantifier applies to. In the above example, \(\forall x\) applies to the whole statement, \(\exists z\) only applies to the portion between if and then, and the \(\forall y\) only applies to the part after then. In general it’s good practice to use parentheses/brackets/braces to separate the scope of a variable for absolute clarity. We could rewrite the above as:

\[(\forall x\ \text{if }\{\exists z\ z<x\}\text{ then }[\forall y\ y<x+y])\]

The meaning of this statement has no longer changed, but it is now much more clear at a quick glance which quantifiers apply where.

Different scopes, like different universes, can change the meaning of a statement. When writing down statements it’s best to be as clear as possible with your quantifiers to avoid confusion.