Proof by Cases

Some proofs need to be broken down into different cases, through which the whole proof can be evaluated. This makes proving complex proofs easier. In fact, I think we already used this method for proving equivalence. In class, we showed that an implication "P implies Q" is equivalent to its contrapositive "not Q implies not P" by showing:

P	Q	P implies Q	not Q implies not P
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

In each of the four cases above, we showed that P implies Q is true if and only if not Q implies not P is true. Even when P is True and Q is False, both the implication and its contrapositive are False, which means the equivalence still stand. Also note that proof by cases work in a much broader environment than propositions involving boolean variables.

Proofs and non-Boolean Functions, disproofs, and false proofs!

Non-Boolean Functions

In class, we discussed about non-boolean functions such as the floor function which takes in a number and returns the largest integer that is less than or equal to that number. The non-boolean functions can be used to set up more interesting predicates for evaluation. For example, prove that n² + 3n + 127 is a prime number for all natural numbers n. Ok, lets take natural number 0, yes, 127 is a prime number. What about 1? If n = 1, then it equals to 131, yes that is a prime. 2? No...2 is not prime. So the proposition is incorrect. So for non-boolean functions, some input values would be ok, while others are not. The main takeaway is that just because a predicate seems to be true for some values, doesn't mean the whole proposition is true.

Disproving

Now, how do we disprove something? For example, how do we disprove the statement 2+2=5? We just need to prove that 2+2 does not equal to 5. So to disprove any statement S, we need to prove that not S is true. This is very useful, because we would not always get to prove true propositions, we would need to know how to disprove something that is false. The most important thing to notice is that the proposition is false, then we can negate it and start disproving. If we fail to notice that a proposition is false, we can try to prove it, but it wouldn't go anywhere. It is a very bad thing to prove something False to be True.

False Proofs

I think this is the funniest topic in this course. We must remember that the real world exists outside of the realm of mathematics, and there are many types of proofs out there, some of which do not actually prove anything! I think the most prevalent false proof out there is the proof by gut feeling. Our intuition is good for rough estimations and predictions based on bad evidence, which was useful in the wild, when we needed to escape predators lurking in the bushes, but not good for establishing truths.

Indirect Proofs - Proof by Contradiction

Proof by contradiction starts with an assumption that the proposition in question is false, followed by a series of logical deductions that lead to a contradiction of something that we all know to be true, then we can say that the proposition must be true. In simpler terms... if a proposition were false, then something false would be true, and since false cannot be true, our proposition better not be false.

This all sounds very abstract... so lets break it down.

Let P be a proposition
To prove P is true,
    we assume P is false (not P is True)
        this leads to some falsehood (such as 2 is not an even number)
    then not P -> falsehood is True (How? Remember truth tables?)
        the only way for this to work is if not P is false, which means P is true.

This is the same as proving the contrapositive of Truth -> P

Prove using Contrapositive

We already know that "If P implies Q" is logically equivalent to its contrapositive "Not Q implies not P". Therefore, the contrapositive would be equivalent to proving the original statement. In fact, this is sometimes easier to do, and should be used. In class, we used the example "Prove that if x² is odd then x is odd for all natural numbers x". This becomes much simpler to prove if we prove the contrapositive. We just need to remember to indicate that we are proving the contrapositive, and state the contrapositive in the final prove.

For statements like "if x is odd then x² is odd", the antecedent is equivalent to the consequence. To prove that two statements are equivalent, we would need to prove that each statement implies the other. First we prove P implies Q, then we prove Q implies P. Another way to prove equivalence is to use a chain of equivalence, whereby P is equivalent to a second statement which links to a chain of equivalent statements until Q.

Proofs

How do we communicate truth?

We sometimes need to convince other people that what we know or understand is true. How do we do that? We need proof.

Direct proof

A direct proof essentially show that there is a link between an assumption and the result. To form this link, we can use previously proven statements and axioms (e.g. DeMorgan's Law). Each assumption about a claim has its own scope. For instance, in the claim that for all elements of x in set D, x with the property 'P' implies x with property 'Q', we assume x is an element of D, whereby no x is a none-D, and P(x) is assumed true, then P(x) implies Q(x).

Axiomatic Method

Before diving straight into proofs, we should look back to the axiomatic method, a method of establishing truths in mathematics invented by Euclid in C. 300 BCE. He began with simple assumptions that are seemingly undeniable from logic, which are called axioms, and proved many propositions from those assumptions. His proofs consisted of a sequence of logical deductions from previous axioms and previously-proved statements, which finally concludes with the proposition in question. Theorems are important propositions proved through this deductive process.

Lets go back to the direct proofs. A direct proof can prove implications, which are in the form "if P, then Q". One way to prove an implication is to first assume P is true, then show Q is somehow linked to this assumption. Finding this link is not trivial. To visualize this, a Venn Diagram can be helpful. For example, to prove P(x) implies Q(x), we can look for results that P(x) implies, and results that imply Q(x). Now, we can visualize the results that P(x) implies as sets that contain P, while the results that imply Q(x) are contained by Q. Now all we need is to find a patch of containment from P to Q.

One thing to note is that before a structured proof can be written, one should first do some scratch-work while one figures out the logical links. Just keep in mind to keep the scratch-work separate from the final proof.

The Paper Folding Challenge

The Challenge: 

Take a strip of paper, hold it lengthwise, such that the longer side is horizontal, then fold it in half from left to right. Repeat this several times, each time folding from left to right, and halving the strip. You will reach a point where you can no longer physically fold the paper in half any more... 7 is the popular theoretical paper folding limit. Now, unfold the paper and you will realize that the creases sometimes point up and sometimes point down. Wouldn't it be nice if you were able to come up with a solution to predict the result of each fold without actually folding it? This will allow us to fold past the theoretical paper folding limit with our mind!

Understand the problem:

Okay, first, I immediately realized that this is a pattern recognition problem. Essentially, if I can figure out the pattern for which the paper's creases come to be as result of each fold,  I should be able to use that pattern to predict the next fold... Right?

Devise a Plan:

My plan was to first just take a piece of paper, fold it in half, observe, record the results, and repeat. Hold on, maybe there are some obvious facts we can take in account first before we dive into this problem. First, we know in our head that by making a fold, the paper is divided into two equal halves, and a second fold would in turn divide each of those halves into two equal halves.

Carry out the Plan:

After some folding, I realized the following:

• for 2 folds and up, the first crease is always up, while the last crease is always down
• starting from both ends and moving inwards, the each set of creases are alternates to each other
• each fold  does not affect the creases created by the previous fold
• each fold adds alternative up/down creases to the pre-existing creases, such that the first crease is always fronted by an up crease, and followed by a down crease, then each subsequent crease is followed by alternating ups and downs

Look back:

Here is the pattern for folds 1 to 6:

d

udd

uuddudd

uuduuddduuddudd

uuduudduuudduddduuduuddduuddudd

uuduudduuuddudduuuduuddduudduddduuduudduuudduddduuduuddduuddudd

How to do this in Python:

Add code below:

Implication VS Conjunction, Truth Tables, and More!

This post covers both week 3 and week 4's materials.

The Difference between Conjunction and Implication

This took some thinking, and I had some trouble understanding the implicit difference between the two. First, lets see how they are similar. Both implication and conjunction express elements with two properties. In implication for example, if P then Q, means P must be Q. In conjunction, P and Q means that an element is both P and Q. However, the difference is that while implication is one sentence, conjunction deals with two. Another difference is in how their negations are expressed. First, remember that negation simply inverts the truth value of a sentence; that is, for the negation to be True, the sentence has to be False. Now, since the implication can only be false when the assumption is True and the conclusion is False, the negation of the implication is exactly that. On the other hand, the conjunction is False, if one of the sentences is false, or both are false, so it can be written as not P or not Q.

All You Need to Know About Implications

An implication contains statements and conditions; it says that assuming if something is true, then consequently something else is true. An interesting thing about implications is that the only way to falsify it is to show that the assumption is true while the consequence is false. All other configurations of truth/false can verify the implication. So even when the assumption is false, and the consequence is true, the implication as a whole is still true. Actually, as I have stated before, even if the BOTH the assumption and the consequence are false, the implication is STILL true.

Another interesting thing is that knowing the implication means you automatically know its contrapositive. Huh? What's that? The contrapositive is simply the negation of the consequence implying the negation of the assumption. In other words, reverse the implication and apply negation to both sides. A Venn diagram should suffice as a visual explanation. What's more is that the contrapositive of the contrapositive is the original implication. That means the implication and the contrapositive are equivalent!!

Truth Tables

Now that we know about implication and conjunction... and how to verify/falsify them, we can try to verify more complex claims. I think truth tables are the most efficient tools for these kinds of exercises. To set up a truth table, simply count how many predicates you have, then calculate the base 2 to the power of that number, which becomes how many difference truth configurations for your predicates. For example, if you have 3 predicates, then the number of truth configurations is 2^3, which is 8.

DeMorgan's Law

Knowing how truth tables work helped me understand how DeMorgan's Law works. First, a quick summary of DeMorgan's Law:

• negation (S1 and S2) is equivalent to (negation of S1 or negation of S2)
• negation (S1 or S2) is equivalent to (negation of S1 and negation of S2)

Another way to understand these two laws is through Venn diagrams.

Finally, notice that DeMorgan's Law are named as such because they are universally True. In the truth table, this is represented as a column containing all True's. This means that every instance of universal truths can be represented by a truth table where every truth configuration leads to the final evaluation of the claim to be True.