Definitions of even and odd
One of the most fundamental properties of integers is
their
parity, i.e. their evenness/oddness. So we need
to define this notion formally. It is convenient to introduce
the predicates $\text{even}(\cdot)$ and $\text{odd}(\cdot)$ that
are true when their argument is even or odd as appropriate and
false otherwise.
$n$ is even if and only if $\exists k[n=2*k]$.
Note: In full first order logic this would be written as
$\forall n[\text{even}(n) \Leftrightarrow \exists k[n=2*k]]$.
$n$ is odd if and only if $\exists k[n=2*k+1]$.
Note: In full first order logic this would be written as
$\forall n[\text{odd}(n) \Leftrightarrow \exists k[n=2*k+1]]$.
ACTIVITY
The following are results you should be able to prove without
induction. They are all pretty straightforward.
-
Here is a prose proof that 7 is odd: $7 = 2*3+1$.
Why is "$7 = 2*3+1$" sufficient?
Write a numbered step-by-step first-order logic
style proof that starts with $7 = 2*3+1$ as given,
and proves $\text{odd(7)}$.
Note: from now on we will give prose proofs
and skip the step-by-step
unless
explicitly required to do otherwise.
-
Prove that 28 is even and 73 is odd. Prove that 0 is
even and prove that -1 is odd.
-
Prove that the sum of two even numbers is even.
-
Prove that the sum of two odd numbers is even.
-
Prove that if n is an odd positive number, then -n is odd.