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

![[Screen Shot 2023-09-15 at 11.46.56 AM.png]]

![[Screen Shot 2023-09-15 at 11.50.56 AM.png]]

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

![[Screen Shot 2023-09-15 at 11.54.16 AM.png]]

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. $◻$