CSC165H1Y Homework Exercise # 3 Summer 2012
1. (a) 9x 2 N;8y 2 N;yx = y
This is true.
Let x = 1
0
Then, x 2 N
Assume y 2 N
0
Then, yx = 1y = y # Math
Then, 8y 2 N;yx = y # Universal Introduction
Then, 9x 2 N;8y 2 N;yx = y # Existential Introduction
(b) 9x 2 N;8y 2 N;4y = x
This is false. In order to disprove the statement, we need to prove the negation.
:9x 2 N;8y 2 N;4y = x () 8x 2 N;9y 2 N;4y 6= x
Assume x 2 N
Let y = x
0
Then, y 2 N # Since x 2 N
Then, 4y = 4x 6= x # Math; x > 0, since we assumed N start with 1
Then, 9y 2 N;4y 6= x # Existential Introduction
Then, 8x 2 N;9y 2 N;4y 6= x # Universal Introduction
Note: the above proof uses the assumption that Natural Numbers do not include 0. In the future, we
will be using the de▯nitions of Natural Numbers which do include 0. This does not change the value of
the statement. The proof, however, would be a bit longer.
We could use proof by cases, specifying a di▯erent value for y when x = 0 (try to work through this!).
Alternatively, consider the following proof:
Assume x 2 N
0
Let y = x + 1
Then, y 2 N # Natural numbers are closed under addition
0
Assume 4y = x
Then, x = 4y = 4(x + 1) = 4x + 4 # Math
Then, 0 = 3x + 4 # subtract x from both sides
Then, x = ▯4=3

More
Less