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)