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.