Proof me wrong! - The order when establishing proof

An important part of complying with scientific standards is the use of the scientific method to determine whether an equation holds more than empirical truth in itself. What we need here is a method for understanding, properly, if a mathematical expression holds truth. We will focus on the form this time around.

If we were to use the example:

∀ x ∈ Z, | x | > 0 ⇒ ∃ z ∈ Z, x < z

We would have the following steps for establishing the proof:

        Assume ∀ x ∈ Z # domain assumption 

                Assume | x | > 0 # antecedent 

                        Let z' = ... # some value that depends on x 

                        [proof of z' ∈ Z] 

                        Then, z' ∈ Z 

                        [proof of x < z']

                        Then, x < z' 

                Then ∃ z ∈ Z, x < z # introducing ∃
        Then ∀ x ∈ Z, | x | > 0 ⇒ ∃ z ∈ Z, x < z

Let's dissect these steps, separating it by their indentation. We would have, in this case, 3 indents:

• Overall proof
• If 'antecedent', then 'right-hand side statement'
• Proof of 'right-hand side statement' for limited or universal variable

If we were to work it the other way around, we would have:

• Proof that the 'right-hand side statement' holds itself true for a variable that belongs to the desired domain and scope (∃ or ∀)
• Since it was proven that the 'right-hand side statement' is true for a variable that belongs to the domain and scope, given the antecedent, we can conclude that it holds true for the desired domain
• Since it was proven with the antecedent, and the antecedent depends on the domain limitations, then the whole statement must be true.

While this was explained using several words, it is important not only to learn the structure, but also to understand why it is used in such a way.

Does the order of establishing domains change the way you read something?

A few weeks ago, just as we had started the semester, I read a question that asked whether these two sentences were the same:

∃ x ∈ A, ∀ y ∈ A, P(x, y) ⇒ Q(x)

∀ y ∈ A, ∃ x ∈ A, P(x, y) ⇒ Q(x)

I remember thinking that these two sentences might be the same in one of those fashions were the order of the factors does not affect the result. Oh boy was I wrong! It is very easy to notice the difference when we put it in words:

For some x that belong to A, all y that belong to A satisfy this...

For all y that belong to A, there is an x that belongs to A such that...

I tried not to dwell too much into the latter part of the equation since it is not relevant to our point. The final point being that it does not only make a difference the way in which the variables and domains are established, but also that it becomes easy to understand once you try it out in English!

For All This is False = For Not Some, This is True

What I found rather charming from last week was that there is more than one Mathematical way to say the same thing. While I was commenting on how clean and refined mathematical expressions could be, in such a way that they reduce ambiguity to zero, I found this to be some sort of conundrum (specially when you have an approach to explaining things, and the recipient has another).

Let's focus on one expression that has two different approaches! Let's say for example x and y are courses that belong to C, which is a set that is made by courses taught at UofT. We also have a function P(x, y), where x is a prerequisite of y. The question is, how should we right the following statement?

MAT135 has no prerequisites

We would then have to put it in terms we could understand, correctly using the proper quantifiers. So we could say that:

• For any course x, there is no course that is a prerequisite of MAT135.

∀ x ∈ C, ¬ P(x, MAT135)

•  For not some x, there is a course that is a prerequisite of MAT135. 

¬ ∃ x ∈ C, P(x, MAT135)

This is nothing but a small example of how things could be approached in a different way. While this seems a little obvious since it is a game that could be simplified as Positive - Negative = Negative - Positive, there are some other complex statements that could be described in different ways.

Bottomline, not everything has one single answer. Or perhaps we should say...

∃ x ∈ A, ∃ y ∈ A, ∃ z ∈ Q, S(x, z) ∧ S(y, z) ∧ x ≠ y

Note: Where x and y are answers that belong to A, z is a question that belongs to Q, and S(x, z) is a function such that x is a solution to z.

The 1, 2, 3... and 4 of Problem Solving

Mathematical expressions are never misunderstood. When a person states 6 + 6, the meaning of that statement will be the same wherever you go. That is, unlike modern languages, math has a precise meaning for every construction. Hence, when constructing a computer algorithm, we need to make sure that our thoughts are conveyed properly by machines. That is where Mathematical Expressions come in.

In other words, we use math as the medium through which we are going to solve problems. Once the problem is properly conveyed in mathematical form, we can attempt to solve it using computer applications.

Polya and the 4 Steps to Solving Problems
Decades ago, G. Polya came with several steps on how to solve problems. While some people will find this obvious or redundant, it is important to remember that true scientists apply a structured, consisten methodology in everything they do. This includes problem solving.

Quickly stated, Polya suggests that we:

1. Understand the problem
2. Devise a plan
3. Carry out the plan
4. Look back

Taken from G. Polya, "How to Solve It", 2nd ed., Princeton University Press, 1957, ISBN 0-691-08097-6.

Example:
A study conducted by Toronto's City Council has shown that there is a positive correlation between the quality of street performers in the city and the amount of tourists coming to the city. The Mayor believes that most street performers are talentless, thus explaining the decline in tourism for the last decade. He wants you to come up with a way to improve the quality of street performers in an economical way. As a scientifically driven person, you apply Polya's steps on "How to Solve It".

Step 1: Understand the problem
What do we know about street performers? Are all street performers talentless? How do we determine if a street performer is good or not? By asking ourselves as many questions about and surrounding the problem, we are able to fully get a grasp of what needs to be done. Visualizing the problem also helps understanding it.

S is the universe of street performers in Toronto.
G is the set that contains good street performers.
A is the set that contains active street performers.

So we want the intersection between G and A to increase in size; we probably want to aim for A to become a subset of G.

Step 2: Devise a plan
Has there ever been a similar problem that has been solved? If that were the case, we could apply that solution to this problem. Since this is a unique problem, we need to come up with a unique solution. To make A a subset of G, we would need to either: a) encourage more good street performers to become active while deterring the rest from performing, or b) make the rest become good.

The most economical way would be a) since it trusts on good performers not needing additional training. Hence, the plan will consist of forcing street performers to apply for permits. When applying, they need to show their skills. A panel of judges will decide whether they are worthy of a permit or not.

Step 3: Carry out the plan
Did the plan solve the problem? Apparently, the plan was a limited success. Some people started renting their permits, creating a situation where some permit owners would have other performers working for them. While this was not the case of the majority, it still needs to be addressed.

Step 4: Look back
We need to review every step in the plan. Can any improvement be done to the steps in order to avoid people renting their permits? If modifying previous steps doesn't solve the problem, perhaps we could introduce extra steps to ensure the success of the plan.