Starting with Definitions

Subsection 8.2.3 Starting with Definitions

It is very common, in doing proofs in mathematics, to appeal to formal definitions of the objects that we’re working with. This tends to cut down a lot on handwaving.

Prove:

[1] For all integers a, b, and c, if a is divisible by b and b is divisible by c, then a is divisible by c.

We can rewrite this in our logical notation if we want to. Sometimes it makes the claim clearer. So we can write:

[1] a, b, c ((Div(a, b)  Div(b, c))  Div(a, c))

Recall that a is divisible by b if and only if b  0 and:

there exists some integer n such that a = b * n.

(For example, 15 is divisible by 5 because 15 = 5 * 3.) So we have that (Div(a, b)  Div(b, c)) is equivalent to saying that b and c are nonzero and there exist integers n and m such that:

[2] a = b * n

[3] b = c * m

Substituting c * m for b in [2], we get:

[4] a = c * m * n

Give the name k to m * n. Then we have:

[5] a = c * k

So we have that a is divisible by c (by using the same definition that we used to get started).

Exercises Exercises

1.

Prove that if a is an even integer and b is an odd integer, then a+b is odd. (Hint: start with the definitions that we’ve already given for Even(x) and Div(x, y)). Write a definition for Odd(x). Then write your proof.)

Definition 8.2.1.

Assuming a universe of the integers:

\(\forall\) x (Even(x) \(\equiv\) Div(x, 2))

\(\forall\)x (\(\forall\)y (Div(x, y) \(\equiv\) ((y \(\neq\) 0) \(\wedge\) \(\exists\)z (x = y\(\cdot\)z))))

And, combining them, we have that x is even if and only if it can be written as 2z for some integer z.

Answer.

Solution.

Recall these two definitions (assuming a universe of integers):

x (Even(x)  Div(x, 2))

x (y (Div(x, y)  ((y  0)  z (x = yz))))

We can restate the combination of these as: x is even if and only if it can be written as 2z for some integer z.

We’ll also need one other definition that we haven’t written explicitly before:

x (Odd(x)  z (x = 2z +1))

Proof.

Because a is even, we have that: a = 2t, for some integer t.

Because b is odd, we have that: b = 2y + 1, for some integer y.

\begin{gather*} So: a + b = 2t + 2y + 1 \\ = 2(t + y) + 1 \\ = 2z + 1, for some integer z (namely, t + y). \end{gather*}

Thus a + b is odd.

2.

Prove that for all odd integers a and b, ab is also odd. (Hint: Start with the definition of odd integer.)

Answer.

Solution.

Recall the definition of an odd integer:

x (Odd(x)  z (x = 2z +1))

Proof.

Since a and b are odd, there exist integers n and m such that a = 2n + 1 and b = 2m + 1. So:

\begin{gather*} ab = (2n + 1) (2m + 1) \\ = 4nm + 2n + 2m + 1 \\ = 2(2nm + n + m) + 1 \end{gather*}

Letting k = 2nm + n + m, we have that ab = 2k + 1. Thus ab too is odd.

3.

Prove that the sum of any two rational numbers is also rational. Hint: Recall the definition of a rational number:

∀x (Rational(x) ≡ (∃y, z (Integer(y) ∧ Integer(z) ∧ (z ≠ 0) ∧ (x = \(\frac{y}{z}\)))))

In other words, x is rational if and only if it is the quotient of two integers and the denominator is not 0.

Answer.

Solution.

Consider any two rational numbers r and s. There exist integers n, m, y, and z such that m \(\neq\) 0 and z \(\neq\) 0 and:

\begin{equation*} r = \frac{n}{m} \end{equation*}

and

\begin{equation*} s = \frac{y}{z} \end{equation*}

So,

\begin{gather*} r + s = \frac{n}{m} + \frac{y}{z} \\ = \frac{nz + ym}{mz} \end{gather*}

The product of two integers is also an integer. And the sum of two integers is also an integer.

So r + s is the quotient of two integers and is thus rational.