Let's start by talking about one of the discrete structures that we'll be examining in more detail later: the natural numbers. You may be familiar with the natural numbers already as "whole numbers" or maybe slightly more formally as "nonnegative integers" (we consider 0 to be a natural number, though this is disputed by various kinds of mathematicians).
For instance, here is a definition you may or may not have run across recently as you began to learn how to program.
Let $n$ be a natural number. The factorial $n!$ is defined by \[n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1.\] This makes for a nice programming exercise.
def factorial(n):
result = 1
for i in range(1,n+1):
result = result * i
return resultHowever, there is a lot that we had to assume and fill in ourselves. For instance,
The lack of imprescision in our initial definition leaves these things to the programmer to interpret and is one reason why this involves a bit of thought on their part. But this is exactly the reason why this is not the formal definition for the factorial. Consider the following definition.
Let $n$ be a natural number. The factorial $n!$ is defined as follows:
This seems strange at first. For instance, there are two cases to deal with. But more strange is the fact that the second case uses the factorial in its definition. This seems like circular reasoning, but if we try and unpack the definition, we'll see that we get exactly what we wanted.
So let's try this. What's $3!$? According to the definition, $3! = 3 \times 2!$. Okay, so what's $2!$? According to the definition, $2! = 2 \times 1!$. But what's $1!$? According to the definition, $1! = 1 \times 0!$. But what's $0!$? According to the definition, $0! = 1$. Putting it all together, we have the following. \begin{align*} 3! &= 3 \times 2! \\ &= 3 \times (2 \times 1!) \\ &= 3 \times (2 \times (1 \times 0!)) \\ &= 3 \times (2 \times (1 \times 1)) \end{align*}
Here, we've already made use of a very sophisticated mathematical idea: substitution.
Going through this process, we see that this definition has another benefit: it directly gives us the algorithm for computing the factorial.
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)This is the classical example of a recursive algorithm.
But why are we allowed to do this? When can we do this? How do we know this is correct?
But what is an integer? What is a number? We've been fine with these concepts because we intuitively understand them to represent amounts of stuff, but this is not really a formal definition.
But why do we need formal definitions? In mathematics, these are important for really nailing down the properties of things that we want to study. Of course, that's a very ivory tower kind of ideal. More recently, though, we started making use of some machines that really need these things nailed down: computers. And although we're trying, we're not at the point yet where we can rely on a computer's intuition for certain tasks.
So what does a formal definition of the natural numbers look like? Such a definition can't rely on our intuition from childhood, so it will look quite different. The most famous of these come from the Italian mathematician Giuseppe Peano in the late 19th Century.
The set of natural numbers, denoted $\mathbb N$, is defined as follows:
There are a few things we need to examine about this definition. First, we have an element that we've just called $z$. This happens to be the thing that we call zero or 0. Here I've made a deliberate choice not to use 0 to make it clear there's nothing particularly special about this element. $\operatorname{succ}$ is a function called the successor function.
It so happens that all of the numbers we already know and love can be described using this definition. One or 1 is $\operatorname{succ}(z)$. Two, or 2, is $\operatorname{succ}(\operatorname{succ}(z))$. But notice that we never actually defined these other natural numbers: the only natural number we explicitly defined was our zero. Every other number is expressed as the successor of another number.
Again, this seems like a strange definition at first, but notice how similar it is to our definition of the factorial from before. This is not a coincidence! We can play the same game that we did with the factorial.
Is $3$ a natural number? Well, here, we're using $3$ as a shorthand for \[\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))).\] So how do we know if $\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z)))$ is a natural number? Well, we have to figure out if it's the successor of a natural number, or if the argument to $\operatorname{succ}$ is also a natural number. So we look at $\operatorname{succ}(\operatorname{succ}(z))$ and see if that's a natural number. Again, this depends on the argument to $\operatorname{succ}$, so we check to see if $\operatorname{succ}(z)$ is a natural number. We go through the same argument and check if $z$ is a natural number. It is! So we can conclude that $3$ was a natural number after all.
This definition for the natural numbers (and the definition for factorial from above) is an example of a recursive or inductive definition. These are definitions that are defined in terms of itself. But how can this work out? The key lies in the two parts of the definition.
The first part of the definition is called the base case. The base case defines the most basic element of the definition. Often, one can think of this as kind of the "smallest" or "least" case. The second part of the definition is called the recursive or inductive case. This is the part of the definition that refers to itself.
So what can we do with this? One of the first things we learn when we learn about numbers is how to add them together, so let's do that. Now, we typically think of adding in terms of combining numbers of things together. However, we need to try to do this without that kind of intuition, because as we discussed before, computers do not know that putting three apples and five apples together makes eight apples.
For natural numbers $m$ and $n$, we define addition on the natural numbers, denoted $m + n$, as follows:
Let's think about this definition a bit. We want to add two natural numbers, $m$ and $n$. What should be the outcome? Well, let's think about the first one, $m$. Recall our definition for natural numbers: it's either $z$ or the successor of some other natural number.
Okay, so if $m = z$, that is $m$ is zero, then adding it to $n$ should just produce $n$ (at this point, I need to point out that we didn't really define zero's properties, but let's set that aside for later).
But what if it's not $z$? Then $m = \operatorname{succ}(p)$, where $p$ is some other natural number. At this point, we have a few pieces to work with: we have the natural numbers $m$, $p$, and $n$ (and $m$ and $p$ are related), and we have two functions, $\operatorname{succ}$ and $+$.
The key here is to think about what $p+n$ is in relation to $m+n$. We know that $p$ is the number that comes "before" $m$, which means that $p+n$ should be the number that comes before $m+n$. And so, we arrive at $m+n = \operatorname{succ}(p+n)$.
Let's try to do some simple math: what's $2+3$? By following our definitions from above, we get: \begin{align*} 2+3 &= \operatorname{succ}(\operatorname{succ}(z)) + \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))) \\ &= \operatorname{succ}(\operatorname{succ}(z) + \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z)))) \\ &= \operatorname{succ}(\operatorname{succ}(z + \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))))) \\ &= \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))))) \\ &= 5 \end{align*}
Now, observe that this definition looks a lot like our factorial and natural number definitions. This also leads to an algorithm!
def plus(m,n):
if m == z:
return n
else:
p = pred(m) # i.e. m = succ(p)
return succ(plus(p,n))Admittedly, this is not really as nice because we actually need to go through the work of defining our own natural number class and methods. This is admittedly burdensome in an object-oriented language like Python, so we'll leave that for now (but it would make for a neat programming exercise).
As an aside, this kind of reasoning is much easier to accomplish in a language that supports pattern matching and algebraic data types, which many functional programming languages do. For example, here's how you'd do the above in (Typed) Racket:
(define-type Nat (U 'Z Succ))
(define-struct Succ ([p : Nat]) #:transparent)
(: plus (-> Nat Nat Nat))
(define (plus m n)
(match m
['Z n]
[(Succ p) (Succ (plus p n))]))And here's how you'd do it in Haskell:
data Nat = Z | Succ Nat
plus :: Nat -> Nat -> Nat
plus Z n = n
plus (Succ p) n = Succ (plus p n)Notice that in these code snippets that even if you don't know the language, it's not hard to see how our definitions fit into place.
Now, we can continue this line of thinking and reproduce much of Peano's work in defining basic results on natural numbers (for example, how do we define multiplication?), but let's stop for now and consider what we've done here.
By considering our definitions a bit more carefully, we've made it much easier to write programs for them. This suggests that if we really tried, we could specify mathematics formally enough that the programs would write themselves, so to speak. And once we have the right definitions and all of the scaffolding in place, it's almost spooky how natural the translation to code is. This also suggests that we're currently not formal enough.
I should mention that our goal for this course is not to be able to formally specify mathematics so that we can write programs for them. This still happens to be a fairly specialized task. However, the underlying prinicple is important: being able to communciate effectively about mathematics will expedite the process of solving problems and this is important whether you're a mathematician trying to prove a theorem or a programmer trying to design and implement an algorithm.
There are still some missing links though. For instance, there was an awful lot of handwaving going on when we were trying to convince ourselves that our definition of addition was really correct. Intuitively, it makes sense, but again, we would like to be able to convince ourselves with something more solid. What we are looking for is proof.
In order to talk about proof, we have to talk about the field of mathematics that the idea of proof is rooted in: logic. Mathematical logic is the study of reasoning from the point of view of mathematics. It's a rich and deep field of study in its own right, but in the context of computer science, the development of mathematical logic in the early 20th century leads directly to the notions of computability.
For the purposes of this course, the basics of mathematical logic allow us to develop a language to express mathematical ideas and a framework in which to prove their validity. There are two parts to this. We first describe how to say things and we then follow up with how to construct proofs about those things.
For instance, you've probably run across particularly math-y statements like
For all integers $n \geq 5$, $2^n \gt n^2$.
This appears to be (mostly) natural language, but the statement itself is one of the things that we want to (and can) express using mathematical logic. In the strictest sense, the language is really just a collection of symbols and some rules about how to arrange them. So, you're allowed to write something that looks like this, but not that, and so on and so forth. The magic comes when we define meaning for these symbols.
The basic element of logic is the proposition. A proposition is a statement that is either true or false. All mathematical results will be a statement that's either true or false. Even something as simple as $2+2 = 4$ is a proposition: the statement asserts that the addition of 2 and 2 is equivalent to 4. This happens to be true. But $2+2 = 5$ is also a proposition—one which is false.
We call particularly important propositions that have been proven to be true theorems. Less important propositions are called lemmas. We can think of lemmas as propositions that we don't really care about except in the service of proving more important theorems. A corollary is a proposition that follows immediately as a consequence of a theorem.
We can then combine several propositions together to create more interesting and complex propositions. This is done by using logical connectives, which modify the meaning of the propositions they combine in various ways.
There are four basic logical connectives, called the Boolean connectives, after George Boole who defined them in 1854. We will define and consider each one.
Suppose we have the following propositions, which were clearly written a few years ago:
$\neg p$ is called negation and is pronounced "not $p$". $\neg p$ is true if and only if $p$ is false.
Then $\neg q$ is the proposition "I cannot take two weeks off". Note that negation is a unary connective, in that it only applies to one proposition, while all the other connectives are binary. Observe also that propositions stated negatively are considered to be positive propositions modified by negation.
$p \wedge q$ is called conjunction, and is pronounced "$p$ and $q$". $p \wedge q$ is true if and only if both $p$ and $q$ are true.
This connective expresses the idea that both $p$ and $q$ are true. For instance, $q \wedge r$ is the proposition "I can take two weeks off and I can fly to Tokyo".
$p \vee q$ is called disjunction and is pronounced "$p$ or $q$". $p \vee q$ is true if and only if $p$ is true or $q$ is true or both.
For example, $q \vee r$ is the proposition "I can take two weeks off or I can fly to Tokyo". One tricky thing to note with English is that many times we use "or" to mean "exclusive or". For instance, when you are asked whether you prefer beef or chicken, the expectation is that you may only choose one and not both. This logical connective allows for both $p$ and $q$ to be true, which corresponds to something like "and/or" in English.
$p \rightarrow q$ is called implication and is pronounced "if $p$, then $q$". $p \rightarrow q$ is true if and only if $q$ is true or $p$ is false.
For example, $p \rightarrow r$ would be the proposition "If flights to Tokyo are under 900 CAD, then I can fly to Tokyo". The direction in which you read this connective is very important. For instance, it may be the case that flights to Tokyo may not be under 900 CAD but I may still be able to fly. Here, $p$ is called the hypothesis and $q$ is called the conclusion.
Implication is probably less familiar than conjunction or disjunction but it's particularly important since it's heavily used in expressing mathematical statements. Unlike conjunction and disjunction, implication is not commutative, which means that $p \rightarrow q$ and $q \rightarrow p$ are not necessarily logically equivalent. Here, $q \rightarrow p$ is called the converse of $p \rightarrow q$.
One way to think about implications is as a claim, as we do in mathematics. Is the claim true? This depends on whether the hypothesis is true. If the hypothesis isn't true, then the claim can be considered vacuously true. This is sort of like when you begin a claim about all positive numbers that are less than 0: you can say anything about these numbers because they don't exist!
However, if the hypothesis is true, then the truth of our claim depends on whether the conclusion is also true. If it is, then all is right with the world. But if our hypothesis is true while our promised conclusion is false, then we have to conclude that we didn't know what we were talking about and that our claim was false after all. The word promise here points to another way to think about implication: as a promise that whenever the hypothesis is true, the conclusion must also be true.
Note that the Boolean connectives are not the only logical connectives out there. There are a few more that are in common use in programming or computer engineering. It also isn't true that the Boolean connectives are necessary, in the sense that if you take one of the Boolean connectives out, there's a way to rewrite any proposition that uses the connective we took out by using a combination of the other three. In fact, we only need two of the Boolean connectives, or one bespoke connective to express everything we could using the four Boolean connectives.
Now, one thing you might notice is that propositions as we've defined them don't quite let us say everything we may want to. For instance, if I wanted to say something like
$x$ is odd and $x$ is less than $y$
then I can certainly define propositions for them. For instance, $p$ can be "$x$ is odd" and $q$ can be "$x$ is less than $y$". This would give us the statement $p \wedge q$, which is not very satisfying or helpful. We see that there's no way to express the fact that the two different propositions are really talking about the same $x$. This is because we have been using propositional logic, which deals with propositions as the basic thing we want to talk about. But what if we want to talk about things? For that, we need to expand our language a bit further.
First, we need to determine a domain of discourse, which is the set to which all of our objects belong. This can be something like the natural numbers $\mathbb N$ or the integers $\mathbb Z$ or matrices or functions or graphs and so on. There's also nothing stopping us from making our domain the set of all dogs, if what we really wanted to do was express statements about dogs, or other "real-world" types of objects. This occurs less in math but more in places like database theory.
Then, we want to express properties and relationships about the objects in our domain. For this, we need to define predicates. Predicates are written $P(x_1, x_2, \dots, x_k)$ and can be thought of as statements about things $x_1$ through $x_k$.
This is enough to get us something like $P(x) \wedge Q(x,y)$ for the example statement from above. Already, we have the ability to say more interesting things. Notice that we are able to say that $x$ is the same among the two statements and that we're able to relate $x$ and $y$.
But what are $x$ and $y$? At this point, they are both not anything at all and at the same time can be anything. This is because they are variables to which we have not given any meaning. One way we can use them is to set them, say like $x$ is 3 and $y$ is 5. A more interesting thing to do is to quantify them by using quantifiers.
The symbol $\forall$ is called the universal quantifier and is read "for all". The statement $\forall x \in S, P(x)$ is true if and only if $P(x)$ is true for every element $x \in S$.
The symbol $\exists$ is called the existential quantifier and is read "there exists". The statement $\exists x \in S, P(x)$ is true if and only if $P(x)$ is true for at least one element $x \in S$.
Basically, we use $\forall$ when we want to make a statement about all objects in our domain ("every dog is a good boy") and we use $\exists$ when we want to say that there is some object out there in our domain that has a particular property ("there is a dog that can play Jenga").
Suppose $E(x)$ is the statement "$x$ is an even number". We can use predicates and quantifiers together with the logical connectives we introduced with propositional logic to say things like $\forall x \in \mathbb Z, E(x) \rightarrow \neg E(x+1)$, which says that "for every integer $x$, if $x$ is even, then $x+1$ is not even".
We can define statements that relate more than one object. Suppose $L(x,y)$ is the statement "$x$ is less than $y$". We can consider the following proposition: $$\forall x \in \mathbb N, \exists y \in \mathbb N, L(x,y).$$ This reads "for every natural number $x$, there exists a natural number $y$ such that $x \lt y$". This statement turns out to be true: every natural number does have some other natural number that it's less than. Now, let's consider the following similar statement, where the order of the quantifiers is reversed: $$\exists y \in \mathbb N, \forall x \in \mathbb N, L(x,y).$$ Here, we're saying that there is a natural number $y$ for which every natural number $x$ is less than it. In other words, this says that there is a "biggest" natural number, which is obviously not true. As we can see, the order of the quantifiers matters.
A proof is a proof. What kind of a proof? It's a proof. A proof is a proof, and when you have a good proof, it's because it's proven.
So far, we have covered how to say things, but ultimately, what we want to do is verify whether a statement is true or not. This is done by means of proof. Informally, a proof is really just an argument that a statement is valid based on some premises.
In mathematics, the premises are a set of facts, like $x+y = y+x$. In very formal settings, we are extra careful to specify exactly which facts we "know" already. Then, if we apply those facts in certain ways which are described by some rules, we can arrive at some statement, which we know must be true because we followed the rules.
For example, consider the following statement that we saw earlier.
For all integers $n \geq 5$, $2^n \gt n^2$.
Within this statement, there are some facts that we need to know already in order to work with if we want to "prove" this statement. We must know facts about the set of integers, the constants $2$ and $5$, the predicates $\geq$ and $\gt$, and the function for exponents.
In the most formal versions of this process, we get to the level of manipulation of symbols, akin to string rewriting. Less formally, what we are trying to do is begin with a set of statements that represent facts that we already know and try to apply rules to these facts so that we can construct a "true" statement by the end of the process. Any statement that we can arrive at by following these rules is considered "valid" and the steps that we take constitute the proof.
The rules that govern how we can manipulate our statements are called inference rules. We can define a whole bunch of these inference rules and by using these rules, we can manipulate formulas to acquire other formulas. Inference rules are often specified in the following way: \[\frac{\alpha_1 \quad \alpha_2 \quad \cdots \quad \alpha_n}{\beta}.\]
This rule says that if I know that statements $\alpha_1, \alpha_2, \dots, \alpha_n$ are valid, then I can conclude that $\beta$ is also valid. A statement $\alpha_i$ is valid if we already know it beforehand (i.e. it is a known, given fact) or if it shows up at some earlier point in the proof. The reason for this is that since we were able to get to $\alpha_i$ at some point earlier in the proof, we must have obtained it by following our proof rules. Therefore, if we stopped at the point that we got $\alpha_i$, we would have a proof if $\alpha_i$.
Inference rules define a proof system. The proof system that we'll be referring to is natural deduction, which was defined by Gerhard Gentzen in the 1930s, and contains rules that correspond to common patterns of proof used by human mathematicians. There are other proof systems which are geared for other purposes, such as use with computers or the study of proof systems.
We won't actually be learning or using natural deduction to prove things. Instead, we'll be walking through basic proof techniques and noting how and where they correspond to rules that are defined in natural deduction.
The main inference rule for implication is called modus ponens or $\rightarrow$-elimination ($\rightarrow\!e$) and is defined by $$\frac{p \rightarrow q \quad p}{q} \rightarrow\!e.$$
What does this rule mean? It's an argument of the form
Here, it's easy to see that the statement "The bus is late" takes the place of $p$ and the statement "I will miss my transfer" takes the place of $q$. For instance, the following argument follows the same structure:
We can rewrite this so that it's even more abstract.
Notice that this is just a linear form of our inference rule from above. There's nothing that says that $p \rightarrow q$ and $p$ have to appear in this order. Also note that in very formal proofs, we cite the rule we're applying along with which lines we're applying the rule to.
One thing to notice that the content of the argument has no bearing on whether it's valid or not. The only thing that matters is whether we have followed the rules to get from one statement to the next. This is not unlike how many people try to argue on the internet.
Another set of simple rules concerns conjunction. First are the simplification or $\wedge$-elimination rules. These are two rules of the form $$\frac{p \wedge q}{p} \wedge\!e_\ell \quad \frac{p \wedge q}{q} \wedge\!e_r.$$ Intuitively, this says that if $p \wedge q$ is a valid proposition, then we can conclude $p$ (or $q$). Such an argument looks like this:
Then, we can combine rules. Consider the following argument.
A similar argument using natural language would look like,
Along with $\wedge$-elimination, we have $\wedge$-introduction: \[\frac{p \quad q}{p \wedge q} \wedge\!i\] which basically says that if we have two valid statements, we can join them together with $\wedge$.
It seems very obvious that we can get $p$ from $p \wedge q$ and it seems superfluous that we would have to simplify the statement. After all, the rules dealing with $\wedge$ are just how combining statements in natural language works. For informal mathematical proof, like what we'll be doing in the rest of the course, these rules are never cited for explicitly for this reason. But it's important to point out that the nature of formal proof requires that these things cannot be assumed and the rules need to be strictly followed. This is not unlike programming, and in fact, there are some fascinating and fundamental connections between formal proof and programs.
From a less mathematical point of view, these rules can be considered forms of argumentation. These rules, together with a base set of rules define a proof system for us to work with. In this sense, argumentation and proof are really the same thing. We begin with a set of premises and try to use the rules to arrive at a conclusion. If we can do this, then we've formed a valid argument or proof.
This is a very mathematically formal notion of proof that we won't dive into too much more of. I mention it because it does form a basis from which we can explore the more informal notion of proof, which we will be using to demonstrate the validity of mathematical claims. So rather than introducing the nitty-gritty of inference rules and proof systems, we will introduce proof techniques and mention briefly their more formal origins.
The first method is called direct proof. The most basic instance of this is by simply applying our rules for conjunction and implication. This is direct because all we're doing is combining statements and following implications.
Most theorems are statements that are implications, which are statements of the form $p \rightarrow q$. This corresponds to the inference rule $\rightarrow$-introduction: \[\frac{\boxed{\begin{matrix}p \\ \vdots \\ q\end{matrix}}}{(p \rightarrow q)} \rightarrow\!i\] What this rule means is that in order to prove such statements, we assume $p$ and then use that assumption to show that the conclusion $q$ is true. Why is there a box? This is a way to show that $p$ exists as an assumption inside the box, since it's not one of our given facts. You can think of the box as the "scope" of $p$ and that $p$ isn't valid outside of the box (i.e. where we assume it).
Consider the following proposition.
If $x \gt 4$, then $x^2 \gt 9$.
Here, $p$ is "$x \gt 4$" and $q$ is "$x^2 \gt 9$". Our proof then goes like this.
Assume that $x \gt 4$. Then $x$ is positive. We multiply both sides of the inequality to get $x^2 \gt 4x$. Multiplying the inequality by $4$ gives us $4x \gt 4^2 = 16$. Then combining these inequalities, we have $$x^2 \gt 4x \gt 16 \gt 9.$$ Therefore, $x^2 \gt 9$.
From this, we can see that a proof of $p \rightarrow q$ involves
Here, step (2) is a bit thin on details, but this is where the clever combining of mathematical facts and knowledge happens, so there's not much we can say regarding the structure of the proof.
The proposition we just proved actually wasn't technically correct because it is missing an important detail: what's $x$? In fact, what we really want to prove is the following proposition.
For all real numbers $x$, if $x \gt 4$, then $x^2 \gt 9$.
This complicates things because now, instead of a simple implication, we have a universally quantified implication. So instead of $p$ and $q$, we have $P(x)$ and $Q(x)$ and we need to prove the statement \[\forall x \in \mathbb R, P(x) \rightarrow Q(x).\]
So how do we prove this? At first glance, it seems like we have a lot of work to do, because we have to show that this statement holds for every real number. One way we can attempt this is to plug in every real number and check if the statement holds. This is bad because there are uncountably many real numbers.
Instead, what we do is "pick" a generic representative and continue our argument with that representative. Since we just choose an arbitrary element with nothing special about it except that we know it's a real number, we can conclude that our statement must hold for any real number, because we could've picked any of them.
Let's see an example of this.
Let $u$ be an arbitrary real number. Assume that $u \gt 4$. Then $u$ is positive. We multiply both sides of the inequality to get $u^2 \gt 4u$. Multiplying the inequality by $4$ gives us $4u \gt 4^2 = 16$. Then combining these inequalities, we have $$u^2 \gt 4u \gt 16 \gt 9.$$ Therefore, $u^2 \gt 9$.
Since $u$ was arbitrary, we can conclude that for all real numbers $x$, if $x \gt 4$, then $x^2 \gt 9$.
Observe that once we "chose" $u$, our proof looked exactly the same as the one before.
Formally, this corresponds to the inference rule $\forall$-introduction: \[\frac{\boxed{\begin{matrix} u \qquad \\ \vdots \\ P(u) \end{matrix}}}{\forall x P(x)} \forall i\]
This rule looks complicated (and the notation admittedly is), but it actually tells us exactly what a proof for $\forall x \in S, P(x)$ looks like.
Existentially quantified statements are of the form $\exists x \in S, P(x)$. In this case, the statement claims that there is at least one element for which $P(x)$ is satisfied. So in order to prove this statement, we need to find an element that works or somehow show that one is out there. Consider the following proposition.
There is a real number $x$ such that $x^2 + 4x + 4 = 0$.
One possible proof is as follows.
Let $x = -2$. Then $(-2)^2 + 4 \cdot (-2) + 4 = 8 - 8 = 0$.
This is a perfectly valid proof, because we've shown that there's a real number that works: $-2$. One particular apocryphal account of such a proof is from 1903, regarding F.N. Cole who proved that there existed a number of the form $2^n - 1$ that was not prime by getting up at an AMS conference and showing that $2^{67} - 1 = 193,707,721 \times 761,838,257,287$ silently on a chalkboard. However, this is probably the most exciting one of those stories and it's not clear that it's even accurate. Generally speaking, these proofs aren't very satisfying because they don't tell us how these answers came about. Something more insightful might be the following.
Consider $x^2 + 4x + 4 = 0$. We can factor this equation to obtain $(x+2)^2 = 0$. This means that $x+2 = 0$ and therefore, the only real number satisfying this equation is $x = -2$.
This proof is more insightful and gives us an idea of how to approach similar problems. However, sometimes this isn't possible, and we don't have a clear way to find or construct a specific number. In the worst case, the best we can do is to show that there has to be an element out there that works, but without any idea of how to obtain it.
Formally, this corresponds to the inference rule $\exists$-introduction: \[\frac{P(t)}{\exists x P(x)} \exists i\] which says that once you have a proof of $P(t)$, where $t \in S$, you can immediately conclude that $\exists x \in S, P(x)$. So a proof of $\exists x \in S, P(x)$ will involve the following,
In the following, we will consider several examples of indirect proof. What makes these proof methods different is that rather than proving the original statement, we prove an equivalent statement, often involving negation.
A proof by counterexample can be thought of as a disproof of a statement of the form $\forall x \in S, P(x)$. If we want to disprove this statement, we would be proving the statement $\neg (\forall x \in S, P(x))$.
But what is $\neg (\forall x \in S, P(x))$? Of course, one can prove this formally, but in the interests of time, we can come up with some informal reasoning that will give us the bones of the argument that a formal proof would properly attach some meat to.
The statement $\forall x \in S, P(x)$ says that $P(x)$ holds for every element $x \in S$. So if this statement is not true, that is $\neg (\forall x \in S, P(x))$ or not every element in $x \in S$ satisfies $P(x)$, this means that there is some element $t \in S$ such that $P(t)$ doesn't hold. That is, $\exists x \in S, \neg P(x)$.
This gives us the following equivalence which we will state without proof.
Let $S$ be a set and $P$ be a predicate. Then,
So what we are doing when we prove a statement $\neg (\forall x \in S, P(x))$ by counterexample is proving the statement $\exists x \in S, \neg P(x)$. This is just an existentially quantified statement, which we've just seen how to prove.
For every integer $n$, if $n$ is even, then $n^2$ is odd.
This claim can be written in the form $\forall n \in \mathbb Z, P(n) \rightarrow Q(n)$. What we need to do is show that $\exists n \in \mathbb Z, \neg (P(n) \rightarrow Q(n))$. Recall that an implication $p \rightarrow q$ is false only in one case: when $p$ is true but $q$ is false.
We will disprove the claim. Let $n = 2$, which is an even integer. Then $n^2 = 4$, which is not an odd integer. Therefore, there is an integer $n$ such that $n$ is even and $n^2$ is not odd, which must mean the claim was incorrect.
Proofs by counterexample have the following form.
As noted earlier, this is just the template for existentially quantified statements but with a bit of dressing up at the beginning.
Whether such proofs are easy depends on how easy it is to find a counterexample. There are many examples of conjectures that have yet to be disproven because the claim holds for an enormous number of cases and the search for a counterexample has yielded nothing so far. However, numbers can get very large, so we can never count out the possiblity of finding a counterexample to these claims someday (for example, recall the story about $2^{67} - 1$ from above). This is just to say that finding a counterexample is not always going to be easy.
This proof technique makes use of the following fact.
Let $p$ and $q$ be propositions. Then $p \rightarrow q \iff \neg q \rightarrow \neg p$.
The statement $\neg q \rightarrow \neg p$ is called the contrapositive of $p \rightarrow q$. Again, we will make use of the fact that these two statements are logically equivalent. Rather than assuming $p$ and constructing a proof for $q$, we can prove the logically equivalent statement by assuming $\neg q$ and proving $\neg p$.
Consider the following proposition.
For all real numbers $x$, if $x^5 - 3x^4 + 2x^3 - x^2 + 4x - 1 \geq 0$, then $x \geq 0$.
This may be offputting because the hypothesis of this proposition is quite complicated. However, proving the contrapositive gives us an easier, but indirect, route.
Let $x$ be an arbitrary real number. We will prove the contrapositive,
If $x \lt 0$, then $x^5 - 3x^4 + 2x^3 - x^2 + 4x - 1 \lt 0$.Note that we make use of the fact that $\neg (a \geq b)$ is equivalent to $a \lt b$.
So, we assume that $x \lt 0$. Then this means that $x^5 \lt 0$, $2x^3 \lt 0$, $4x \lt 0$, $-3x^4 \lt 0$, $-x^2 \lt 0$, and $-1 \lt 0$. Adding these together, we obtain $$x^5 - 3x^4 + 2x^3 - x^2 + 4x - 1 \lt 0.$$ Thus, the contrapositive holds, and therefore, the original implication holds.
From this, our approach for proving $p \rightarrow q$ is the following,
Observe that this is really just an implication proof with a bit of dressing up. It's this dressing up that makes things indirect.
This proof technique is similar to the contrapositive, in that our proof is indirect. First, we need another idea from propositional logic.
Let $p$ be a proposition. Then the statement "$p \wedge \neg p$ is true" is a contradiction.
Based on the definition for conjunction, $p \wedge \neg p$ will always be false, since this basically says $p$ is true and $p$ is false, something that we know can't be correct.
The proof template for proving $p \rightarrow q$ looks like the following.
Before we see an example, we have another logical equivalence to introduce.
Let $p$ and $q$ be propositions. Then,
These are known as De Morgan's laws. You can think of the quantifier negation we saw in Theorem 1.21 as the generalized version of this. We are now ready to show the following.
For all real numbers $x,y$, if $x+y \lt 10$, then $x \lt 5$ or $y \lt 5$.
Let $x,y$ be arbitrary real numbers. First, we assume that $x+y \lt 10$. Then, we assume for the sake of contradiction that $x \geq 5$ and $y \geq 5$. Adding these two inequalities together gives us $x+y \geq 10$. But this contradicts our very first assumption, that $x+y \lt 10$. Therefore, our assumption that $x \geq 5$ and $y \geq 5$ could not have been true. Thus, $x \lt 5$ or $y \lt 5$.
Proofs by contradiction can often give us proofs of existence indirectly. A direct proof of an existentially quantified statement would involve finding or constructing a candidate element $t$ such that $P(t)$ holds. However, one can use contradiction to show that an element can't not exist without actually saying what that element is. This is one reason why direct proofs are preferred.
Now, we can return to our definition of addition from before. We now have the ability to say something about our definition. For example, we might make the following claim.
For all $n \in \mathbb N$, $n+z = n$.
This seems pretty straightforward, but how can we convince ourselves that this is actually true? We might try a few examples to test it.
If $n = z$, we have $z + z = z$ by Definition 1.6(1).
If $n = \operatorname{succ}(z)$, we have \begin{align*} \operatorname{succ}(z) + z &= \operatorname{succ}(z + z) & \text{Definition 1.6(2)} \\ &= \operatorname{succ}(z) &\text{Definition 1.6(1)} \end{align*}
If $n = \operatorname{succ}(\operatorname{succ}(z))$, we have \begin{align*} \operatorname{succ}(\operatorname{succ}(z)) + z &= \operatorname{succ}(\operatorname{succ}(z) + z) & \text{Definition 1.6(2)} \\ &= \operatorname{succ}(\operatorname{succ}(z + z)) &\text{Definition 1.6(2)} \\ &= \operatorname{succ}(\operatorname{succ}(z)) &\text{Definition 1.6(1)} \end{align*}
If $n = \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z)))$, then we have \begin{align*} \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))) + z &= \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z)) + z) & \text{Definition 1.6(2)} \\ &= \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z) + z)) & \text{Definition 1.6(2)} \\ &= \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z + z))) &\text{Definition 1.6(2)} \\ &= \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))) &\text{Definition 1.6(1)} \end{align*}
So, this looks a lot like our computation for the factorial, in that it is very repetitive. However, that is the key to our proof: the observation here is that our computation of $n+z$ depends on the computation of whatever the number that comes before $n$ is. By the first line of our computation, we have that \[\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))) + z = \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z)) + z)\] but we've already proven what $\operatorname{succ}(\operatorname{succ}(z)) + z$ is! We could instead write something like \begin{align*} \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))) + z &= \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z)) + z) & \text{Definition 1.6(2)} \\ &= \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))) &\text{Proof of $\operatorname{succ}(\operatorname{succ}(z)) + z$} \end{align*}
What would be convenient is if there were a way to use this idea: that we know that if we can prove a property $P$ for a natural number $n$, we can use that proof to prove that $P$ also holds for $\operatorname{succ}(n)$.
This is the idea behind the principle of mathematical induction. This is a consequence of the Peano definitions for natural numbers. We can state this for a property $P$ in first-order logic as \[P(0) \wedge \forall k \in \mathbb N, (P(k) \rightarrow P(k+1)) \rightarrow \forall n \in \mathbb N, P(n).\] What this tells us is that if we can show that the hypothesis, $P(0) \wedge \forall k \in \mathbb N, P(k) \rightarrow P(k+1)$, is true, then we can conclude that $\forall n \in \mathbb N, P(n)$.
This gives us a proof template for proving things specifically about natural numbers. So if we want to prove $\forall n \in \mathbb N, P(n)$, all we need to do is provide a proof for $P(0) \wedge \forall k \in \mathbb N, P(k) \rightarrow P(k+1)$. Since this is a conjunction, we need to prove two things: $P(0)$ and $\forall k \in \mathbb N, P(k) \rightarrow P(k+1)$.
These two cases happen to mirror our definition of the natural numbers: the proof of $P(0)$ is called the base case, while the proof of $\forall k \in \mathbb N, P(k) \rightarrow P(k+1)$ is called the inductive case. The form of these statements gives us the following proof template:
We will prove this by induction on $n$.
Base case. If $n = z$, then \begin{align*} n + z &= z + z &\text{substitution} \\ &= z &\text{Definition 1.6(1)} \\ &= n &\text{substitution} \end{align*} Therefore, our claim holds for the base case.
Inductive case. Now, suppose $n = \operatorname{succ}(k)$ for some arbitrary $k \in \mathbb N$ and assume that $k+z = k$. We will show that $\operatorname{succ}(k) + z = \operatorname{succ}(k)$. Consider the following: \begin{align*} \operatorname{succ}(k) + z &= \operatorname{succ}(k + z) &\text{Definition 1.6(2)} \\ &= \operatorname{succ}(k) &\text{inductive hypothesis} \end{align*} Therefore, our claim holds for the inductive case and therefore, $n + z = n$ for all natural numbers $n$.
A common use for induction is for proving properties of sums or sequences of integers. The following is a common example.
For every $n \in \mathbb N$, $\sum \limits_{i=0}^n i = \frac{n(n+1)}2$.
If you've been taught this formula before, then you've probably been told the story of Gauss solving this problem when he was a child—a story which has been embellished over the last century and a half. However, his teachers in this story, in assigning $n = 100$, gave him an easy out since he only needed to consider one instance of the problem, so his solution does not use induction. We don't have that luxury, since we want to prove that this formula holds for all $n$.
We will prove this by induction on $n$.
Base case. If $n = 0$, then $\sum \limits_{i=0}^0 i = 0$ and $\frac{0 \cdot (0+1)}2 = 0$. Therefore, $\sum \limits_{i=0}^n i = \frac{n(n+1)}2$ holds for $n = 0$.
Inductive case. Let $k \in \mathbb N$ be arbitrary and assume that $\sum \limits_{i=0}^k i = \frac{k(k+1)}2$. We will show that $\sum \limits_{i=0}^{k+1} i = \frac{(k+1)(k+2)}2$. Then, we have the following: \begin{align*} \sum_{i=0}^{k+1} i &= \sum_{i=0}^k i + (k+1) \\ &= \frac{k(k+1)}2 + (k+1) & \text{by ind. hyp.} \\ &= (k+1) \cdot \left(\frac k 2 + 1 \right) \\ &= (k+1) \cdot \left(\frac k 2 + \frac 2 2 \right) \\ &= \frac{(k+1)(k+2)}2 \end{align*}
Thus, $\sum \limits_{i=0}^n i = \frac{n(n+1)}2$ holds for $n = k+1$. Therefore, $\sum \limits_{i=0}^n i = \frac{n(n+1)}2$ holds for all $n \in \mathbb N$.
The fact that the structure of proofs by induction mirrors recursive definitions is an important detail. This is very similar to our observation that the structure of recursive algorithms very closely matches the structure of recursive definitions. This suggests that induction can be applied to other recursive structures, beyond just the natural numbers.