Finding the Perfect Substitution

While we were looking at the form structure when finding proof, I noticed that I had no recollection whatsoever on how to do it. I remember, while studying number theory, that there were some neat tricks on how to prove a certain expression for n and then n + 1, and finally for n + k. In essence, we are finding proof here of a single expression, but when we have to related expressions, the dynamics are a bit different, so here we will now focus on a postulate that involves two expressions and the way to tackle this problem, as well as finding the perfect substitution to get our desired result.

If we were to use the example:

∀ x ∈ Z, ∃ y ∈ Z, x = y + 1 ⇒ ∃ z ∈ Z, x^2 = z + 1

We would have the following steps for establishing the proof:

        Assume ∀ x ∈ Z # domain assumption

                Assume ∃ y ∈ Z, x = y + 1 # antecedent 

                        Let y' be a value that depends on x... # some value that depends on x 

                        Then, y' ∈ Z 

                        Let z' = y^2 + 2y
                        Then, z' ∈ Z
                        If x^2 = (y' + 1)^2 = y'^2 + 2y' + 1 and z' = y^2 + 2y
                        Then, x^2 = z' + 1

                Then ∃ z ∈ Z, x^2 = z + 1 # introducing ∃
        Then ∀ x ∈ Z, ∃ y ∈ Z, x = y + 1 ⇒ ∃ z ∈ Z, x^2 = z + 1

Let us focus now on the bold part. How did we find it? Easy: we knew where we wanted to go. If we are going from x to x^2, then we know that the expression on the left will be squared. Rearrange things a little bit, and voila!

Floors and Ceilings - Almost getting there!

From this week's lecture I found quite intriguing the importance that floor and ceiling functions play in computer theory. At the beginning I was rather skeptical of their usefulness, but that just came to show how vast the applications of computational logic really are. I'll just go ahead and offer two examples that have to do with my current programming level with Python:

• Mod Operand (% in Python)
• x % y = x - y floor (x/y)
• In mathematical expression: ∀ x in Z, ∀ y in Z, ∃ z in Z, z = x - y (floor (x/y))
• Rounding (round() in Python)
• round(x) = floor (x + 1/2)
• In mathematical expression: ∀ x in R, ∃ y in Z, y = floor (x + 1/2)

The important lesson here is not think harshly about some functions in mathematical reasoning. Perhaps we should apply the logic that, if it has its own symbol, it must be rather important. While doing some research about the floor and ceiling functions, I found that there are plenty more applications to it! Hopefully in a near future we will be able to see some more.

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!