6 - Direct proofs

Terminology

• Axioms - truths that are taken self-evident
• A theorem is an important statement we prove. We will only name results “Theorems” when they are extremely important.
• A proposition is a basic statement we prove.
• A lemma is a (usually minor) result that we prove in order to use it later to prove a bigger result. We use lemmas as a way of breaking up large proofs into smaller, more understandable pieces.
• A corollary is a (usually minor) result that follows easily from another result we have proved.
• Conjecture - we think this is true but we don't know

Trivial Proofs

A proof is trivially true when the premise of the implication is irrelevant. A square box indicates the proof is over.

Sometimes “trivial” proofs are not easy and take some work to prove.

It is always a good idea to understand the premise and conclusion of an implication separately before trying to prove the implication.

Vacuous proofs

If the premise is impossible, the implication is vacuously true.

Trivial, the Q is true. Vacuous, the premise is bogus.

Trivial and vacuous proofs should come from implications

Outline of a direct proof

Given a statement $\forall x\in S,P(x)\Rightarrow Q(x)$, we can prove it directly by assuming the premise $P(x)$ holds and then, using that information, we show that $Q(x)$ must also hold true.

Example:

Proposition. For each $x\in Z$, if $x$ is even, then $5x+3$ is odd.

Proof. Let $x\in Z$ be arbitrary. We will work directly. Assume x is even. This means

$x=2k$ for some $k\in Z$. Thus
$5x+3=5(2k)+3=10k+3=2(5k+1)+1.$

Since $5k+1\in Z$, this means that $5x+3$ is odd. $◻$

Basic outline:

Given $x\in S$, if $P(x)$ is true, then $Q(x)$ is true.

Proof outline.
Let x ∈ S.
We work directly.
Assume P(x).
Do some work (to be filled in). Thus, Q(x) holds.

Write the conclusion before filling in the middle.

In class practice

Proposition.
Let $x\in \mathbb{R}.$ If $x^2<73,$ then $0<1$.
Proof.
The inequality $0<1$ is always true, so the proposition is trivially true. $◻$

Proposition.
Let $a\in \mathbb{Z}$. If $a$ is odd, then $2a$ is even.
Proof.
Since $2a$ is always even for all integers, the proposition is trivially true. $◻$

Proposition.
Let $x\in \mathbb{R}$. If $x<5$, then $x^2-2x\ge -1$.
Proof.
The inequality is equivalent to $(x-1{)}^2\ge 0$ which is true for all $x\in \mathbb{R}$, therefore, the result is trivially true.

Proposition: For each $x\in \mathbb{Z}$, if $x$ is even, then $5x+3$ is odd.

Proof:
Let $x\in \mathbb{Z}$.
We work directly.
Assume that $x\in EVEN$. Thus $x=2k$ for some $k\in \mathbb{Z}$.

We find

Since $5k+1$ is an integer, $5x+3$ is odd.

Proposition: If $n$ is an odd integer, then $n^2-2n+3$ is even.

Proof: Let $n\in \mathbb{Z}$. We work directly. Assume that $n$ is odd. Thus $n=2k+1$ for some $k\in \mathbb{Z}$. Hence
We find

Since $2k^2+1$ is an integer, $n^2-2n+3$ is even.

HW 6

Ben Finch

E 6.1
Proposition. Let $x\in \mathbb{R}$. If $x\ne 3$, then $x^2-2x+3\ne 0$

Proof.
The equation $x^2-2x+3$ is the same as $(x-1{)}^2+2$
Since $(x-1{)}^2$ is always non-negative for the domain $x\in \mathbb{R}$, $(x-1{)}^2+2$ is always positive. This claim is trivially true since the implication is true for all real numbers .

Thus $x^2-2x+3\ne 0$. $◻$

E 6.2
Proposition. Let $n\in \mathbb{N}$. If $2<n<3$, then $7n+3$ is odd.

Proof.
Since $n$ is a natural number, there are no values for $n$ that satisfy the condition of the proposition. Thus, the claim is vacuously true. $◻$

E 6.3
Proposition. If $x$ is an odd integer, then $x^2$ is odd.

Proof.
Let $x\in \mathbb{Z}$.
We work directly.
Assume $x$ is odd. Thus $x=2k+1$ for some $k\in \mathbb{Z}$.
We find

$2k^2+2k$ represents an integer, for example $n$, so we can rewrite this expression for $x^2$ as $2n+1$, which is the definition of an odd number.

Thus, if $x$ is an odd integer, then $x^2$ is odd. $◻$

E 6.4
Proposition. If $x$ is an even integer, then $7x-5$ is odd.

Proof.
Let $x\in \mathbb{Z}$.
We work directly.
Assume $x$ is even. Thus $x=2k$ for some $k\in \mathbb{Z}$.
We find

Since $7k-2$ represents an integer, for example $n$, we can write the expression for $7x-5$ as $2n-1$ which satisfies the definition of an odd number.

Thus, if $x$ is an even integer, then $7x-5$ is odd. $\begin{array}{r}◻\end{array}$

E 6.5
Proposition. Let $a,b,c\in \mathbb{Z}$. If $a$ and $c$ are odd, then $ab+bc$ is even.

Proof.
Let $a,b,c\in \mathbb{Z}$.
We work directly.
Assume $a$ and $c$ are odd. Thus $a,c=2k+1$ for some $k\in \mathbb{Z}$.
We find

Since both $k$ and $b$ are integers, $2kb+b$ is also an integer, so we can rewrite the expression as $2n$, where $n$ represents some integer, which satisfies the definition of an even number.

Thus, If $a$ and $c$ are odd integers, then $ab+bc$ is even. $◻$

E 6.6
Proposition. Let $n\in \mathbb{Z}$. Prove that if $|n|<1$, then $3n-2$ is an even integer.

Proof.
Let $n\in \mathbb{Z}$.
We work directly.
Assume $|n|<1$. Thus $n=0$.
We find that $3(0)-2=-2$, which is an even integer.

Thus if $|n|<1$, then $3n-2$ is an even integer. $◻$

E 6.7
Proposition. Every odd integer is a difference of two squares of integers.

Proof.
We can rewrite the proposition as an implication:
If $x$ is and odd integer, then $x=a^2-b^2$ where $a$ is an even integer and $b$ is an odd integer.
Let $x\in \mathbb{Z}$.
We work directly.
Assume $x\in ODD$. Thus $x=2k+1$ for some $k\in \mathbb{Z}$.
We find that

Thus, If $x$ is and odd integer, then $x=a^2-b^2$ where $a$ is an even integer and $b$ is an odd integer. $◻$