Week #6

Week #6

#15

non-boolean function
floor(x) is the largest integer <= x
Now prove forall x in R, floor(x) < x+1

Assume x in R           # generic
Then floor(x) <= x # from definition
Then x < x+1          # add x to both sides 0<1
Then floor(x) < x+1   # transitivity
Conclude forall x in R, floor(x) < x+1

Using more if the definition
forall x in R, y = floor(x) <=> (y in Z) and (y <= x) and (forall z in Z, z<=x => z<=y) # The full definition of floor.
Now prove forall x in R, floor(x) > x-1

Assume x in R                    # generic
Then floor(x) in Z             # from definition
Then floor(x) + 1 in Z         # Z closed under +
Then floor(x) + 1 > floor(x)   # add floor(x) to 1>0
Then floor(x) + 1 > x          # by contrapositive, since floor(x) > floor(x) and floor(x)+1 in Z
Then floor(x) > x-1            # subtract 1
Conclude ...

Proving something false
Define a sequence:
forall n in N, a_n = floor(n/2) == n//2
# 0, 0, 1, 1, 2, 2, 3, 3, ......
Now prove:
S: exists i in N, forall j in N, j>i => a_j = a_i
# This claim is false, disprove it.
neg S: forall i in N, exists j in N, j>i and a_j != a_i

Assume i in N
Pick j = i+2, Then j in  # N closed under +
Then j>i
Then a_j = floor(j/2) = floor((i+2)/2) = floor(i/2 + 1) > x+1 = i/2 >= floor(i/2)
Then a_i != a_j
Conclude ....




#16

e.g Prove: forall n in N, n2 + n is even
Proof:
Assume n in N
Then n is even or n is odd
Case 1: assume n is even
Then exists k in N, n = 2k,      # defn of even
Then n2 + n = n(n+1)
                    = 2k(2k+1)
Then exists k0 in N, n2+n = 2k0  # k0 = k(2k+1) in N
# k, 2, 1 in N, N closed under +,*
Then n2 + n is even              # defn of even
Case 2: assume n is odd
Then exists k in N, n = 2k + 1   # defn of odd
Then n2 + n = n(n+1)
= (2k+1)(2k+2)
= 2(2k+1)(k+1)
Then exists k0 in N, n2+n = 2k0  # k0 = (2k+1)(k+1) in N
# k, 2, 1 in N, N closed under +,*
Then n2 + n is even              # defn of even
Then n2+n is even, since it is so in both possible assumptions
Conclude ...


e.g. Prove forall e in R+, exists d in R+, forall x in R, |x-3|<d => |x2-3^2|<e

Proof:
Assume e in R+
Pick d=min(1,e/7) /*This place can be blank at first*/, Then d in R+
Assume x in R
Assume |x-3|<d
Then |x2-3^2|= |(x-3)(x+3)|
= |x-3||x+3|
< d|x-3|          # |x-3|<d, multiply by |x+3|
= d|x-3+3+3|
= d(|x-3|+6)      # |x+y|<=|x|+|y|
= d(d+6)
  <= d(1+6)         # d <= 1
<= e              # d <= e/7
Then |x2-3^2| < e
Conclude ...