Direct Proofs and Counterexamples

MATH1061

Definitions

We begin by defining even and odd.

An integer $n$ is even if and only if $n$ is twice some integer.

$$n\text{ is even}⟺\exists k\in \mathbb{Z}\text{ such that }n=2k$$

An integer $n$ is odd if and only of $n$ is twice some integer plus one.

$$n\text{ is even }⟺\exists k\in \mathbb{Z}\text{ such that }n=2k+1$$

Next, lets define the terms prime and composite.

An integer $n$ is prime if and only if $n>1$ and for all positive integers $r$ and $s$, if $n=rs$ then $r=1$ or $s=1$.

An integer is composite if and only if $n>1$ and $n=rs$ for some positive integers $r$ and $s$ with $r\ne 1$ and $s\ne 1$

Proving Existential Statements

To show $\exists x\in D$ such that $P(x)$ is true, iot is enough to find one example of an element $x\in D$ for which $P(x)$ is true.

Example:

There exists a positive integer $x$ such that $x>30$ and $x$ is composite.

$$\begin{array}{rl}x& =32\\ Then32>30\cap 32& =2\times 16\\ Where2,16\in {\mathbb{Z}}^{+}& \cap 2\ne 1,16\ne 1\\ \therefore x=32& \text{ is a positive integer}\end{array}$$

Direct Proof of Universal Statements

One way to show that $\forall x\in D$, if $P(x)$ then $Q(x)$ is true,

$$\begin{array}{rl}1.& Supposex\in D\text{ and }P(x)\text{ is true.}\\ 2.& \text{Show that the conclusion }Q(x)\text{ is true using definitions.}\end{array}$$