Sunday, December 17th, 2023

How would you prove that something you say is true? Or not true? Today we went over mathematical ways to do it.

Starting with notations.

With these notations, we can transform statements into mathematical expressions. Below are a few examples.

All cats have 9 tails.

∀ C∈{cats}, C has 9 tails

No number is both even and odd.

∀ n∈{number}, ~(n∈{even}∩ n∈{odd})

These notations really help when you are trying to determine whether something is true or not.

There are also 3 major proof methods we use:

Logical deduction.

This is the method where you build off of simple facts or lemmas, and use the structure a→b, b→c and thus a→c.

A classic example would be proving that I have a brain.

Statement A: I am a human.

Statement B: all humans have a brain

Statement C: therefore, I have a brain.

2. Mathematical Induction

This is a method where you build off of a base case, and use the inductive step to prove that the statement is true for all numbers.

An example would be proving that 1+2+3+...+n=(n)(n+1)/2.

Base case: n=1. 1=(1)(2)/2=1.

Inductive step: assume that 1+2+3+...+n=(n)(n+1)/2 when n=X.

Then, when n=X+1, 1+2+3+...+X+(X+1)=(X)(X+1)/2+(X+1)=(X+1)(X+2)/2, which is also true.

Therefore, 1+2+3+...+n=(n)(n+1)/2 for all integers n≥1.

3. Proof by contradiction

This is a method where you assume the statement you are trying to prove is false, and find a contradiction. This is usually used when you need more information.

An example would be proven that there are infinitely many prime numbers.

To use proof by contradiction, we assume that there are finitely many primes, p1,p2,...,pn. We see that if these were the only primes, then the number p1*p2*...*pn+1 is not divisible by any of the primes, but it is not on the list. Therefore, we reach a contradiction, and there are infinitely many primes.

However, these proof methods can often be misused. We used a couple of examples to illustrate this.

Logical deduction:

Claim: 1 cat have 9 tails

Statement A: no cat has 8 tails

Statement B: 1 cat has 1 more tail than no cat

Statement C: therefore, 1 cat has 8+1=9 tails

The mistake is simple: in Statement A, the no cat refers to ~ ∃ cat, but the second no cat refers to 0 cats. These are not interchangeable.

Mathematical Induction:

Claim: all horses have the same color

Base case: when there is 1 horse, it has the same color as all horses.

Inductive step: when any set of n horses are of the same color, we can separate it into 2 groups with 1 and n-1 horses respectively. Take the group with n-1 horses, and combine it with another horse that is not included in the original n horses. They all have the same color. Combining all n+1 horses, and they must be of the same color.

The mistake is a bit more complex: the inductive step does not work when n=1, and n-1=0.

Proof by contradiction:

Claim: All numbers are interesting.

Reasoning: Assume that there exists a group of uninteresting numbers. There must be a smallest number that is interesting. However, the fact that it is the smallest uninteresting number is pretty interesting. Therefore, there is a contradiction, and all numbers are interesting

The mistake here lies in the assumption that there is a smallest uninteresting number. If the set of uninteresting numbers is infinite and decreases, then there is no smallest uninteresting number.

A bit of a challenge: geometry proofs

Claim: all triangles are isosceles

The mistake comes from the position of Q. R should lie between A and B, while C should lie between A and S.

If you are interested in more proofs and proof methods, email me directly or contact me on discord. I will supply you with practice proofs.

## Comments