Logic and Proofs

A proof is a verification of a proposition by a chain of logical deductions from a set of axioms. There are several different methods of proof that mathematicians and logicians use to demonstrate the truth of a statement. In this article, we will discuss some common proof methods.

Before diving deep into proofs, it’s useful to discuss a more general definition of a proof. A proof is a method of ascertaining/establishing/verifying the truth.

Examples of proof methods include:

• Observation or experimentation: This is a common method of proof. It involves observing a phenomenon and then using the observation to prove a statement, for example, observing the gravity and seeing its effects.

• Sampling: This is a method of proof that involves taking a sample of a population and then using the sample to prove a statement about the population. For example, if you want to prove that the average height of a population is 5 feet, you can take a sample large enough of people and then use the sample to prove the statement.

• Inner Conviction: This is a method of proof that involves using your own personal conviction to prove a statement. For example, if you believe that the earth is flat, you can use your own personal conviction to prove that the earth is flat.

• “I don’t see why not”: This is a method that transfers the burden of proving/disproving a statement to the opposing party and making it their job to prove you wrong instead of you coming up with a proof in the first place.

Before we proceed with talking about formal proof methods, it’s important to define some terms.

Definitions

• Proposition: A proposition is a statement, that is either true or false. For example

3 + 2 = 5 // this is a true proposition

3 + 2 = 6 // this is a false proposition

• Predicate: A predicate is a proposition whose truth or falsehood depends on the value of a variable. For example

$$ \forall n \in \mathbb{N} \quad n^2 + n + 41\ is \ a\ prime \ number $$

This predicate is true for all natural numbers n < 40. This proposition is false since the predicate is not true for all values of n.

Another example of a proposition is

$$ 313\times(x^3+y^3)=z^3\ has\ no\ positive\ integer\ solutions $$

This proposition is also false because it is not true for all values of x, y and z. The first counterexample involves numbers with over a thousand digits!

• Implication: An implication is a proposition p implies q where p and q are propositions. The implication proposition is true if q is true or p is false.

$$ p \implies q $$

Examples of implication propositions:

If it rains, you will get wet.

If pigs could fly, I would be king.

• Axiom: An axiom is a proposition that is assumed to be true without proof. For example, the commutative property of addition is an axiom.

$$ if\ a = b \And b = c \implies a = c $$

The above statement has no proof but it seems pretty obvious that it is true. This is an axiom.

Properties of axioms

Consistency: A set of axioms is consistent is consistent if it does not contain any contradictions. In other words, you cannot prove a proposition to be true and false at the same time using this set of axioms.

Completeness: A set of axioms is complete if it contains all the true propositions. In other words, you can prove any true proposition using this set of axioms.

Soundness: A set of axioms is sound if it contains no false propositions. In other words, you cannot prove a false proposition using this set of axioms.

Godel’s Incompleteness Theorem

Godel’s incompleteness theorem states that any consistent set of axioms (Including mathematics) is incomplete. In other words, there will always be a true proposition that cannot be proven using the set of axioms. To learn more about Godel’s incompleteness theorem, check out this video: