Importance of the Order of Quantifiers

I remember at the beginning of CSC165, there was a stark warning to pay attention to the order of quantifiers in writing a claim. It seemed obvious at the time, but finally in A3 I still erroneously proved a claim by mixing up the claim.

Fo all e in R+, there exists d in R+, for all x, y in R+, |x-y| > d => |x+y| > e

From the second assignment, I'd been confused about how to prove a claim when there are different variables in the antecedent and consequent, but I fortunately learned that the way to connect the two was to write one of the variables in terms of the other (d, e in this case).

Remembering this, I excitedly got to work with the first version of my proof:

|x+y| <= e => |x-y| <= d # contrapositive

Assume |x+y| <= e

Let d = |x+y|

Then |x-y| <= |x+y|

-x+y <= -x-y

x-y > x+y

x /> x+2y # x, y in R+

Well that didn't quite work out as I'd expected...

I have no idea what I "proved" there. I thought this implied that the claim was false for a while (since that's what I'd "proved" here), until I was told that the "d" I'd picked here depends on x and y, and that can't happen if d come before x and y in the quantifier (before they're introduced), but that means I can use e.

Now it makes a lot more sense. The informal version of the proof can be written in one line:

|x-y| <= |x| + |y| # the addition of two positive numbers will always >= the subtraction of the same numbers

= |x + y| < e = d # letting d be e

Sometimes the simplicity of proofs really quite amaze me. When I was first exposed to proofs in MAT137, I'd always thought constructing proofs of my own would be out of my reach since the lines seem to have come out of nowhere. Now I see it just takes a bit of manipulation that comes with creativity and attentiveness to really understand each component of the claim, and the rest will follow. Additionally, the proofs that we've been introduced to in this course so far actually aren't as arbitrary as I'd initially thought. They actually all follow a set structure and method, and this realization has definitely made proofs a lot less intimidating.

A Few Types of Proofs in CSC165

Just wanted to write a little reference post for myself regarding the proofs we've covered so far in this course with a few tips regarding each.

1. Equality proofs

- Determine whether or not to prove or disprove claim, and write the appropriate negated claim if the goal is to disprove

- Read the claim carefully and make use of each part

- Try to make intuitive sense of what the claim is trying to say before attempting to prove/disprove, to figure out which route to take

e.g.

For all x in R, for all y in R, x >= y => floor(x) >= floor(y)

Assume x in R, y in R, x >= y # this claim is true

Then floor(y) in Z

Then floor(x) in Z # since the claim beings with universal quantifier, cannot prove by "picking" variables

For all z in Z, z <= x => z <= floor(x)

By definition floor(y) <= y # of floor function

Then floor(y) <= y <= x

Then for all z in Z, z <= x => z <= floor(x)

Pick z = floor(y) # since z is given in definition, using definition of floor function to prove claim

Then floor(y) <= x => floor(y) <= floor(x)

2. Big-O proofs

- Write out claim in symbolic form

- Determine whether to prove/disprove, only pick the variables for components that are existentially quantified

- Don't forget to restate claim using Big O notation at the end (i.e. then polynomial in O(polynomial))

e.g. Write a detailed structured proof that 7n^3 - 4n + 1 in O(8n^4 - 5n^2 + 3n)

There exists c in R+, there exists B in N, for all n in N, n >= B => 7n^3 - 4n + 1 <= C(8n^4 - 5n^2 + 3n)

Pick c' = 1

Pick B' = 8

Assume n in N, n >= B

Then 7n^3 - 4n + 1 < 7n^3 + 1 <= 7n^3 + n^3 = 8n^3 <= n(n^3) # n >= 8 = n^4 < 3n^4 = 8n^4 - 5n^4 < 8n^4 - 5n^2 < 8n^4 - 5n^2 + 3n

Then 7n^3 - 4n + 1 <= C(8n^4 - 5n^2 + 3n)

Then n>= B >= 7n^3 - 4n + 1 <= C(8n^4 - 5n^2 + 3n)

Then there exists c in R+, there exists B in N, for all n in N, n >= B => 7n^3 - 4n + 1 <= C(8n^4 - 5n^2 + 3n)

Then 7n^3 - 4n + 1 in O(8n^4 - 5n^2 + 3n)

3. Polynomial implications

- Assume antecedent and try to get the consequent working forward from the antecedent

- For existential variables, leave blank and work forwards first, then fill in the value

e.g. For all x in Z, (there exists y in Z, x = 3y + 1) => (there exists y in Z, x^2 = 3y +1)

Assume x in Z

Assume y in Z, x = 3y + 1

Let y' be such that x = 3y'+1 # leave blank until proof is complete

Then x^2 = (3y + 1)^2 = 9y^2 + 6y + 1

Then 3(3y^2 + 2y) + 1

Then 3y' + 1

Then there exists y in Z, x^2 = 3y + 1

Then (there exists y in Z, x = 3y + 1) => (there exists y in Z, x^2 = 3y +1)

Then for all x in Z, (there exists y in Z, x = 3y + 1) => (there exists y in Z, x^2 = 3y +1)

Proofs Using Definitions

With A2 due on Monday, I spent the weekend grinding through the rest of the proofs that I'd yet to complete.

There were two things that clicked for me during this assignment.

Days before I began tackling this assignment, I'd read over the assignment and its requirements briefly. We'd covered the floor function in class in a previous lecture, but I didn't completely understand the definition at the time. In fact, I was fascinated that so much could be said and contained with just a few symbols. Since A2 required a good understanding of this definition, I finally had to look closer, which brings me to my first realization:

1. Each symbol is crucial to understanding the symbolic statement (i.e. definitions, claims)

I'd struggled for about 15 minutes before I succumbed to inquiring about whether or not there was a mistake in the definition for the floor function presented in the assignment.

Namely, in the definition,  \forall z \in\mathbb{Z}, z \leq x \Rightarrow z \leq \floor{x}, if I set:

z = 3.2

x = 3.4

Then z \leq x, but z \geq \floor{x}. I was confused. Then I realized that z can only be an integer; I'd missed an integral part of the definition.

Armed with this knowledge, I went onto tackle Claim 1.1

\forall x \in\mathbb{R}, \forall y \in\mathbb{R}, x \textgreater y \Rightarrow \floor{x} \geq \floor{y}

This was the first time I'd used a definition directly to prove a claim.

My first attempt consisted of trying to manipulate x > y in some way so that x = y, which would then satisfy \floor{x} \geq \floor{y}. Bad attempt - that would only prove the equality and ignore the inequality.

In my second attempt, I saw that I had to somehow make \floor{y} in \floor{x} \geq \floor{y}, z, from the definition, so that z \leq \floor{x}. Eventually, seeing that z \in\mathbb {Z}, since \floor{y} \in\mathbb{Z}, letting z = \floor{y}, the proof was devised at last.

\begin{proof}

  Assume $x \in\mathbb{R}, y \in\mathbb{R}, x > y$

    \\\quad Then $\floor{y} \in\mathbb{Z}$

    \\Then $\floor{x} \in\mathbb{Z}$

    \\Then $\forall z \in\mathbb{Z}, z < x \Rightarrow z \leq \floor{x}$

    \\By definition, $\floor{y} \leq y $

    \\Then $\floor{y} \leq y < x $

    \\Then $(\forall z \in\mathbb{Z}, z \leq x \Rightarrow z \leq \floor{x})$

    \\Pick $z = \floor{y}$

    \\Then $\floor{y} \leq x \Rightarrow \floor{y} \leq \floor{x}$

    \\Then $\floor{y} \leq y < x \Rightarrow \floor{y} \leq x \Rightarrow \floor{y} \leq \floor{x} $

    \\Then $x \textgreater y \Rightarrow \floor{x} \geq \floor{y}$

    \\Then $\forall x \in\mathbb{R}, y \in\mathbb{R}$

\end{proof}

(As a side note, I've yet to fully comprehend the LaTex syntax. I definitely need to brush up on that knowledge before attempting my next assignment.)

The most enlightening part of the assignment was perhaps in understanding what Claim 1.2 was asking for. 

\forall x\in\mathbb{R}, \forall e \in\mathbb{R}^+, \exists

  d \in\mathbb{R}^+, \forall w\in\mathbb{R}, |x-w|< d

  \Rightarrow |\floor{x}  - \floor{w}| < e

After more than half an hour of scouring around the web for inspiration, and speaking with another student, it finally became clear that the claim is the definition of the continuous function, which brought me to the second thing that clicked during this assignment. 

2. The delta epsilon proof for continuous functions

Having taken MAT137 last year, I remember having first been exposed to this rigorous definition. I was so confused with the introduction of proofs at that time. However, following this assignment, it finally made more sense (and as I'd become more familiar with reading symbols throughout CSC165, I wish I'd taken this course prior to taking MAT137).

Essentially the claim said that the floor function was a continuous function, which is clearly false. However, the challenge remained to disprove the claim. 

This assignment has definitely helped in solidifying my knowledge of the ways in which one can approach a proof (e.g. there had been multiple instances where I'd 'picked' a value to prove in an universal claim, and where I attempted to prove an existential claim using a universal method, terrible). Being precise is so crucial in math and CS, and it looks like I'll just have to keep practising to adopt a more keen eye.

Overall, I'm happy to say that I'm finally starting to gain an intuitive understanding of how proofs are approached and to gain an appreciation of rigour in math.