Direct Proofs

Why do we prove things?

In mathematics everything needs to be rigorously proven in order for it to be truly accepted and believed as rule. This runs counter to a lot of other fields in which something is to be believed true if there is sufficient evidence supporting it. In physics, you can drop an object a million times and be confident at saying it is a law that a dropped object will fall, in math it does not matter how many examples you have that verify your claim if you can’t explain the underlying reason it works; if you want to see why see this thread of large counter examples.

This is not strictly for mathematicians either though, computer scientists are held to the same standard. How do you know that your code truly works? You can run some tests cases sure, but if there is some unaccounted for error you might end up costing your company a large amount of money. You need to be able to prove that your code works all the time.

At the end of the day, if you don’t prove your work in any field haters will say its fake¹ and we all know that there is no greater catharsis than proving some stupid dumbass on the internet wrong.

The Axioms

You might have the thought “why do we need to prove it by writing it down, math is the language of the universe so can’t I just provide you evidence and thats good enough?” This is a fair question but misses something big, what is the universe?

No seriously, in mathematics we are working with simplified rules and numbers to make proofs and statements, but how are those rules proved? And how do you prove the rules that prove those rules? And what about the rules that prove those rules? You could keep going deeper and deeper and realize that at some point you will just need to take an assumption as ground truth and work from there. These statements that we assume to be true are called axioms, and your choice of axiom completely determines everything about the mathematics you work with.

For example, there are multiple different types of geometry, and some of which have their differences in how parallel lines interact with each other; classically they never cross, but what if they did ²?

Definition: An axiom is a statement that is assumed to be true, generally with the purpose of proving other statements.

For our class, we will not be referencing Axioms very regularly, however if you are curious you could check out several resources that mention the axioms they use, my personal favorite being Terry Tao’s Analysis I book.

The Direct Proof

Now that we have explained why we prove things, lets actually show how you would go about proving something. The most simple proof that we can do is called the Direct Proof, which is the way that you are likely most familiar with proving things to people in speech. We begin by starting with some statement we know to be true, and then continually make steps that we know to be true to bring us to our next true statement. From the IMPLIES truth table we know that if $P=1$ and $(P\rightarrow Q)=1$ then the only row that this occurs is $Q=1$. As such we can make chains of statements starting at $P$ that eventually reach to our end goal that we wish to claim.

Definition: A direct proof is a proof that starts with some initial true statement $P$, before moving down a true set of implications $$P\rightarrow P_1\rightarrow P_2 \rightarrow\ldots\rightarrow P_n \rightarrow Q$$ where $P_i$ represents some intermediate step and $Q$ is the end goal.

A Not Mathy Direct Proof

In order to show you that a direct proof is literally just a written out explanation of steps that eventually lead you to an end goal, lets consider a funny little minor example to see what a proof looks like.

Example 1: Prove that if there are no people on an escalator, the escalator is always faster than taking the stairs.

You might think “Wow thats pretty wordy for a math class, don’t we deal with numbers?” to which my answer is that you best get used to the words cause higher level math involves a shitton of proofs and text. Even in a more mathy example we’ll find ourselves using a surprising amount of text. Speaking of which

A More Mathy Example

We can’t put it off forever and its finally time to do some math. Don’t psych yourself out though, just move along in steps of what is true.

Example 2: $(P\rightarrow Q) \equiv (\bar{Q}\rightarrow\bar{P})$, where $\equiv$ means the two expressions are equivalent to each other.

Proof by Contrapositive: A Less Direct, Direct Proof

In the previous section we proved that $\bar{Q}\rightarrow\bar{P}$ was the exact same expression as $P\rightarrow Q$, as such if we want to prove that $P\rightarrow Q$, we are completely allowed to prove $\bar{Q}\rightarrow\bar{P}$ instead.

This is called a Proof by Contrapositive as the expression $\bar{Q}\rightarrow\bar{P}$ is called the contrapositive of the original expression. While this might seem weird and unique, just know that it’s literally just a direct proof.

Example 3: What is the contrapositive of the statement “If it rains, I will cancel my plans”?

What the heck is Q.E.D.?

Q.E.D. is an abbreviation of the latin phrase quod erat demonstrandum which translates to “what was to be shown”. Back in ye-onder days Greek mathematicians would end all their proofs with the phrase as a sort of mathematical mic drop. People eventually shorted it to Q.E.D. and have been using it to mention that the proof is complete since.

More modern notation³ has people mostly using a box, either $\square$ or $\blacksquare$ because its easier to write on a board, but you can use any symbol you want. I’m actually quite partial to seeing students complete their proofs with funny stupid little images.