next up previous
Next: Online comments about Test Up: Homework Assignments Previous: Homework 7

Homework 8

Homework 8

Due Tuesday, March 14.

Define the predicates Even(x) and Odd(x) in the language of 
our theory of arithmetic (this is easy).

Prove the theorem (Ax.Even(x) <+> Odd(x)) formally using only
axioms and perhaps theorems proved in class.

It is permissible to prove this as two theorems:

(Ax.(Even(x) | Odd(x)))


(Ax.(~(Even(x) & Odd(x))))

if you don't like working with xor!

Comments added after March 15 discussion:  

proving either (Ax.(Even(x) | Odd(x))) or (Ax.(~(Even(x) & Odd(x))))
by itself is acceptable.  The second one is harder -- it needs
the theorem that each nonzero natural number has a predecessor.

Randall Holmes