KindiakMath

The whole point of examining logic is to develop crucial proof techniques that will aid us for future studies. This is the primary application, and arguably the most crucial one, of examining logic and even tautologies.

Each proof technique is still a compound expression that we can verify to be a tautology, so we can verify that they work just like normal compound expressions.

Each proposition on the left-hand side is either assumed or proven to be a theorem, and the proof techniques ensure that the right-hand side will be a theorem too.

The fundamental proving technique has to be modus ponens, which is essentially a direct proof .

Theorem 1 (Modus Ponens). Let be propositional variables. Then

Proof: Writing implications as disjunctions,

where we used the identity law , which can be easily verified.

Throughout the rest of the discussion, we will abbreviate each valid proof technique by . So modus ponens is abbreviated by

This means that if we have established that is true and is true, we can logically conclude that must be true. In particular,

This is how we prove theorems. We will also abbreviate the proof technique obtained by chaining implications

by .

Sometimes, it is easier to prove an equivalent statement of a direct proof. One such equivalence is called the contrapositive.

Theorem 2 (Proof by Contrapositive). Let be propositional variables. Then

Proof. Observe that

By modus ponens, . The implication is known as the contrapositive of the implication .

A closely related proof technique is known as modus tollens. It is, in a sense, the mirror argument of modus ponens.

Theorem 3 (Modus Tollens). Let be propositional variables. Then

Proof. Using Theorem 2 and double negation,

.

Modus tollens is used to prove by first establishing and via a proof by its contrapositive .

Throughout our discussion, we have been replacing and . This idea is generalised to a proof by cases.

Theorem 4 (Proof by Cases). Let be propositional variables. Then

Proof. Writing implications as disjunctions,

Other proof techniques include specialisation, which is the rather mundane tautology , generalisation, which is given by , and two-directional proof, given by

The implication is the converse of the implication .

Yet, we have not unveiled two of the most powerful tools. The first is a proof by contradiction, which helps us establish by showing that leads to a brick wall.

Theorem 5 (Proof by Contradiction). Let be a propositional variable. Then

Proof. Writing implications as disjunctions,

The last technique is called proof by induction. Intuitively, it follows from chaining implications together. However, the notion of depends on the definition of , which can get too technical for a first discussion in discrete mathematics. We will state it here without proof for completeness.

Theorem 6 (Proof by Induction). For any natural number , let be a proposition. Suppose the following hold:

• ,
• for any natural number , .

Then for any natural number .

Proof. Roughly speaking, chaining implications yields

Hence, by modus ponens,

We will provide a more complete proof when discussing in a future post.

These proof techniques, coupled with some set-theoretic starting points (for introductory discrete mathematics, we will use naïve set theory as our launchpad), will help us prove most of mathematics. But before doing so, we need two more notions in order to make headway into mathematics—universal and existential quantifiers.

—Joel Kindiak, 16 Nov 24, 2236H