Proof by Contraspositive

I remember the days when I used to boast and announce, "Proofs? Please, they come second nature to me!"  I can still recall that horrendously loud laugh with which I used to flood the rooms of my poor, confused friends.

It still haunts me... I mean them.

Only this week did I realize that in reality, I only knew how to write out the structure.  And not just that; I only knew how to write out direct proof structure.  My ego has been in hiding ever-since...

After a number of fruitless past trials that left me frustrated, I came to the realization that there could be times when a direct proof doesn't necessarily work.  In such cases, resolving to an alternative proof mechanism is required.  This is where proof by contraspositive comes into play.

To refresh your memory, a contrapositive of an implication is equivalent to the implication itself.

∀x ∈ L, P(x) => Q(x)   <====> ∀x ∈ L, ¬ Q(x) => ¬ P(x)

How does that help with proving something that doesn't 'respond' to a direct proof?  Proving the contrapositive instead of the implication will simultaneously prove the original implication!

The proof structure for the above contrapositive is:

Assume x ∈ L  # x is a generic L

     Assume ¬ Q (x)  # assuming antecedent

              Then ..... # finding a link between ¬ Q(x) and ¬ P(x) 
                              # using proven mathematical theories and logic

              Then ¬ P(x)   # then ¬ Q(x) => ¬ P(x)

      Then P(x) => Q(x) # since an implication is equivalent to its contrapositive

Then ∀x ∈ L, P(x) => Q(x) # Assumed x, got result.

In conclusion, if a direct proof doesn't work, try using the contrapositive (especially if it becomes easier to prove), before rejecting the claim.

Proofs

During our lecture on Tuesday, we were introduced to 'proofs': the mechanism used by mathematicians and computer scientists to accept or reject claims about the world.  It seemed a little arbitrary to myself as I had not been exposed to the concept before.  But at the same time, I was excited to challenge myself by learning something new.

Proving something true is not an easy task, especially when you are not aware of the reason of the validity  The first step towards proving  or disproving something should be to understand why it is true (or not); convincing yourself before anyone else is a vital step.  This is why I set out to make arguments from common beliefs that I could prove/disprove as this course progresses.

For now, here is my humble list:

1. If the users rated the book five stars, then they liked it
2. If the clouds are dark, it will rain.
3. Someone who doesn't eat meat can survive.

DeMorgan's Law

    This week, we tackled many means of representing the same logical statement with a different combinations of symbols.  One rule that I found especially interesting was DeMorgan's Law; it simply shows the effect of negation on logical symbols, including a strange effect on both conjunction and disjunction.   I found that making visual representations helps.

    For the following example, we shall assume that A(x) represents the set of people who like apple pies, and C(x) will represent  the set of people who prefer cherry pies.

I'm quite sure there are many of us who would devour both with equal enthusiasm, and as such, this example will start out with a simple statement to represent the likes of us; 
A(x) ∧  C(x).   (Figure 1). 

(For the sake of simplicity, I will omit quantifiers in this representation.)

Negating the above: 
¬ (A(x)  ∧   C(x)). (Figure 2)

    As we already know, the negation sign "bubbles" through the statement until it hits the closing bracket, messing with virtually everything in its way.  After all constituents have been negated, we get something familiar, but with a twist:
 ¬ A(x)  ∨  ¬ C(x).   (Figure 3).  

   The intersection, or  is know as the conjunction, becomes a disjunction, uniting the negated sets! It is also important to note that negating a disjunction yields a conjunction much in the same way. 

  In conclusion, DeMorgan's Law shows how the statement with the negation lingering outside of the brackets is equivalent to the statement with the negation "bubbled" in to affect every element, including conjunction and disjunction symbols.

Introductory Logic: Universal Quantification

On a normal circumstance, I am not easily fascinated by crude and factual topics I might encounter in a course, unless I can somehow manage to find an application for such concepts in my everyday life.  Thus far, I have found the introductory logic laws and rules covered in CSC165 to be incredibly engaging; you can apply the concepts to anything from a problem set in your homework to the logical reasoning behind the validity of cosmic laws that govern our universe. You can logically account for every situation and come up with a beautiful argument that an intellectual is unlikely to reject.

To start simply and cover one very basic example of a logical statement, one must mention the concept of a universal claim.  Things in logic are looked at from two perspectives: "all" or  "some" elements in a set are claimed to have a certain property.  For now, I will go over the universal quantification; a method that accounts for and studies all items in a set.  Let's take on example: For all elements in the set of Animal Kingdom denoted as AK, each element is an Animal, with the set of "Animal" being denoted as A. To write that using symbols, ∀ x ∈ AK,  A(x), or "Every element in the set of  Animal Kingdom is an Animal."

To prove this statement, one must go through each and every item in the set of Animal Kingdom and make sure that each of those elements is indeed an Animal; prove that there are no counter-examples.  To disprove this statement, one needs to find find only one element in the set of Animal Kingdom which is not also an element in the set Animal; provide one counter-example.

Getting started

I'm very excited to be starting this course this term.  I immensely enjoyed our first lecture this past Tuesday; hopefully it'll be the first of many great ones.  I have no expectations so far about the course, only a little bit of enthusiasm and slight anticipation! Even though I do not have any previous experience at mathematical proofs, I am confident that CSC165 will prove to be an intellectually-stimulating journey.  After all, who doesn't like to get a little challenged? Let's get started!