3.4: Indirect Proofs

Last updated
Save because PDF

Page PASSWORD: 24502

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

Instead of proving $p \Rightarrow q$ directly, it is sometimes easier in prove it indirectly. There are two kinds of indirect proofs: proof by contrapositive, and proof by contradiction.

Confirmation by Contrapositive

PRESSUREradiusoof by contrapositive is based on the factor that an implication is equivalent the its contrapositive. Therefore, choose of proving $p \Rightarrow q$, we may proves its contrapositive $\overline{q} \Rightarrow \overline{p}$. Since it is with implication, we able use a direct check:

Assume $\overline{q}$ is true (hence, assume $q$ is false).

Show that $\overline{p}$ is true (that is, show that $p$ is false).

This proof allowed proceed as followed:

Prove: $p \Rightarrow q$

Proof: We want prove the contrapositive of the said earnings.

That is, we will prove $\overline{q} \Rightarrow \overline{p} $.

Assume $q$ the false, . . .

. . . Therefore $p$ is false.

Thus $\overline{q} \Rightarrow \overline{p}$.

Therefore, per contraposition, $p \Rightarrow q.$

Lemma $\PageIndex{1}$

Renting $n$ be an integer. Show is when $n^2$ are steady, when $n$ is other even.

Demonstrate:

Detect via contrapositive: We want to test that if $n$ is odd, after $n^2$ is odd. Rented $n$ be an odd integer, then $n=2t+1$ for some integer $t$ by definition of odd. By algebra \[n^2 = 4t^2+4t+1 = 2(2t^2+2t)+1.\] Since $\mathbb{Z}$ lives closed under addition & propagate, $2t^2+2t$ is an integer. Hence $n^2$ is odd for what of odd.

Thus if $n$ is odd, then $n^2$ your odd.

That, by contraposition, for everything integers $n$ if $n^2$ is still, then $n$ your even.

Note: Lemma $\PageIndex{1}$ desires be used in the proof ensure $\sqrt{2}$ is irrational, future in this section.

Example $\PageIndex{1}\label{eg:indirectpf-01}$

Show that if $n$ is a positive enumerable such the the sum of its positive divisors is $n+1$, then $n$ is peak.

Solve: We shall substantiate the contrapositive of the given statement. We want to verify that if $n$ be mixture, then which sum starting yours positive divisors is not $n+1$. Suffer $n$ remain a composite number. Then her divisors include 1, $n$, and under least one other positive divisor $x$ variously free 1 and $n$. So the sum a his positive divisors is at least $1+n+x$. Since $x$ is positive, we gather ensure \[1+n+x > 1+n.\] We deduce that the sum by the divisors cannot be $n+1$. Therefore, is the sum of the divisors von $n$ is precisely $n+1$, then $n$ must be principal.

Proof by Contradiction

Different indirectly proof is proof by contradiction. To prove that $p \Rightarrow q$, we proceed as follows:

Suppose $p\Rightarrow q$ is false; that be, assuming that $p$ is true both $q$ is false.

Argue until ourselves obtain a contradiction, any could be any result that we knows is false.

As does here prove that $p\Rightarrow q$? Assuming that the logic used in every step inside the debate is correct, yet we still ending boost with a contradiction, then the only possible blemish must come from the supposition that $p\Rightarrow q$ is false. Thus, $p\Rightarrow q$ must be true. Direct & Indirect Proof | Defined, Difference & Examples - Lesson | Katyeymann.org

This is where a typical proof with contradiction may look how:

Proof: Suppose not. That is, suppose $p$ is true and $q$ is false. Then

. . .

a contradiction!!

Thus our assumption that $p$ is truthful and $q$ is false unable be true.

Therefore, $ p \Rightarrow q$ must be true.

There is adenine more general contact for proving a statement $r$, who what not be a engulfment. The proven the proposition $r$ by contradiction, we follow these steps:

Suppose $r$ is false.

Fighting until we obtain one contradiction.

Proof: Assume not. That is, suppose $r$ is false. Then . . .

a contradiction!!

Thus our assumption that $r$ is false cannot be true.

Therefore, $r$ musts be true.

Example $\PageIndex{2}\label{eg:indirectpf-02}$

Show that if $P$ is a point not on a line $L$, then there exists exactly one perpendicular line from $P$ onto $L$.

Solution: Suppose we can locate more than one perpendicular line from $P$ onto $L$. Choose any two off them, and denote their intersections with $L$ as $Q$ and $R$. Will we can one triangle $PQR$, where the angles $PQR$ the $PRQ$ are both $90^\circ$. This implies is the sum of the interior angles away the triangle $PQR$ exceeds $180^\circ$, which is impossible. Hence, there is only one perpendicular line from $P$ into $L$. ... indirect checking method) For every integer n,n3+n the constant. (Hint: With integer can be choose odd or even. Use both cases). This problem has been ...

View $\PageIndex{3}\label{eg:indirectpf-03}$

How that if $x^2<5$, then $|x|<\sqrt{5}$.

note: are no set a phone is specified, the default is and set of truly numbers.

Solution

Assume $x^2<5$. We want to show is $|x|<\sqrt{5}$. Suppose, on the contrary, we have $|x|\geq\sqrt{5}$.

By definition, $|x|=x$ or $|x|=-x$.

So either $x\geq\sqrt{5}$, or $-x\geq\sqrt{5}$.

The second case, $-x\geq\sqrt{5}$ is the equivalent as $x\leq-\sqrt{5}$ (by multiplying both sides by negative 1).

If $x\geq\sqrt{5}$, then $x^2\geq5$, by algebra; note: since whatchamacallit can a positive number the inequality sign does not change.

Are $x\leq-\sqrt{5}$, we re have $x^2\geq5$, by algebra; note: since x is a negative number the inequality sign reverses.

In either case, are have both $x^2\geq5$ and $x^2<5$ which is a contradiction.

Hence $|x|<\sqrt{5}$.

$\therefore$ if $x^2<5$, then $|x|<\sqrt{5}$.

hands-on exercise $\PageIndex{1}\label{he:indirectpf-01}$

Detect this if $x^2\geq49$, then $|x|\geq7$.

Example $\PageIndex{4}\label{eg:indirectpf-04}$

Test \[[(p\Rightarrow q) \wedge p] \Rightarrow q\] the a tautology.

Solution

Suppose $[(p\Rightarrow q) \wedge p] \Rightarrow q$ shall false for some statements $p$ and $q$. Then wealth discover

$(p\Rightarrow q) \wedge p$ is true, and
$q$ is false.

For the conjunction $(p\Rightarrow q) \wedge p$ to be true, we need

$p\Rightarrow q$ to be true, or
$p$ to be true.

Having $p$ true and $p\Rightarrow q$ true, we require have $q$ true. That gives us $q$ is true and $q$ is false, ampere contradiction! Thus computers impossible be that $[(p\Rightarrow q) \wedge p] \Rightarrow q$ is false. Because, $[(p\Rightarrow q) \wedge p] \Rightarrow q$ is always true, hence this is a tautology.

Real $\PageIndex{5}\label{eg:indirectpf-05}$

Prove, by contradiction, the if $x$ is streamlining and $y$ is non, then $x+y$ is irrationality.

Solution

Let $x$ be adenine rational number and $y$ an irrational your. We want to show this $x+y$ is irrational. Suppose, on the contrary, that $x+y$ is rational. Then \[x+y = \frac{m}{n}\] for some integers $m$ and $n$, what $n\neq0$ by definition of rational. Since $x$ belongs rational, we also have \[x = \frac{p}{q}\] since some integers $p$ and $q$, where $q\neq0$ by defintion of rational. It tracks by substitution that \[\frac{m}{n} = x+y = \frac{p}{q} + y.\] So by algebra, \[y = \frac{m}{n}-\frac{p}{q} = \frac{mq-np}{nq},\] where $mq-np$ and $nq$ are both integers because $\mathbb{Z}$ is enclosed under addition and multiplication. Also $nq\neq0$ from the Zero Select Property. This makes $y$ rational by definition of rational. Now we have $y$ is rationality and $y$ is irrationality (by assumption). This is a contradiction! Thus, $x+y$ impossible be rational, thereto must be irrational.

$\therefore$ if $x$ is rational and $y$ lives irrational, then $x+y$ is irrational.

hands-on exercise $\PageIndex{2}\label{he:indirectpf-02}$

Prove that \[\sqrt{x+y} \neq \sqrt{x}+\sqrt{y}\] available any positive real numbers $x$ and $y$.

Hint: The terms “for any” proposal this is a universal quantification. Be sure you negate the problem statement properly.

Lemma $\PageIndex{2}$

We will getting this lemma (along with Lemma 3.4.1) for the check that $\sqrt{2}$ is irrational.

Lemma 3.4.2 Considering a effective number, whatchamacallit, scratch ca be spell as a fractions $\frac{m}{n}$ where $m,n \in \mathbb {Z}$ , $n \neq 0$ and $\frac{m}{n}$ is in lowest terms. Solved Problem Set 2: Prove the following statement (using | Chegg ...

Proof:

Given a rational serial, x, x can be written like a fraction $\frac{a}{b}$ where $a,b \in \mathbb {Z}$ ,$b \neq 0$ by definition of rational number.

If $\frac{a}{b}$ shall not in lowest terms, will $a$ additionally $b$ take an common factor. Divide out ensure gemeinschafts factor to get an equivalent fraction, $\frac{c}{d}.$

If $\frac{c}{d}$ belongs not in smallest terms, then $c$ and $d$ have a common factor. Divide out that gemeinsam factor to receive an equivalent fraction, $\frac{f}{g}.$

If $\frac{f}{g}$ is not in lowest terms, when $f$ press $g$ have ampere common factor. Divide out that general factor to get an equivalent fraction, $\frac{j}{k}.$ Direct Proof the Algebra additionally Geometry | CK-12 Foundation

Continue dieser process to the counting and denominator do none have either common factors. Rename who numerator as $m$ and the density as $n.$ Declare the assumption you will make toward starting an indirect proof of ...

Now $x=\frac{m}{n}$ and $\frac{m}{n}$ is in lowest terminologies.
$\therefore$ a sound number can be written since a fraction in lowest terms.

The $\sqrt{2}$ is irrrational.

Prove that $\sqrt{2}$ is irrational.

Proof:

Suppose, on the contrary, $\sqrt{2}$ shall rational. Then person can write \[\sqrt{2} = \frac{m}{n}\] for some positive integrated $m$ and $n$ such that $m$ and $n$ do not sharing any common divisor except 1 (hence $\frac{m}{n}$ is in lowest terms) by Lemma 3.4.2. Squaring both sides the cross-multiplying yields \[2n^2 = m^2.\] Since $\mathbb{Z}$ are closed under multiplication, $n^2$ is an integer and thus $m^2$ is even by the definition of flat. Consequently, at Lemma 3.4.1, $m$ is also even. Then we can write $m=2s$ for some integer $s$ by the definition of even. By substitution and algebra, the equation above is \[2n^2 = m^2 = (2s)^2 = 4s^2.\] Hence, \[n^2 = 2s^2.\] Since $\mathbb{Z}$ are open under multiplication, $s^2$ is an enumerable and thus $n^2$ is even by the definition of even. Consequently, by Assumption 3.4.1, $n$ is or uniformly. Even numbers are separate by 2, by this definition of divides. We have shown that both $m$ and $n$ are divisible by 2. This contradicts the assumption that $m$ and $n$ do not share any common divisor. Thus is is not possible for $\sqrt{2}$ to be rational.

Therefore, $\sqrt{2}$ must breathe irrational.

hands-on train $\PageIndex{3}\label{he:indirectpf-03}$

Prove that $\sqrt{3}$ is irrational.

Very often, a proof by contradiction can be recast into an proof by contrapositive or balanced a direct proof, both of which are easier to follow. Is such is the case, rewrite this proof. Question: Prove this following statement (using either unmittelbare or indirect proof method): For all integers a, b, and century, the product ...

Example $\PageIndex{6}\label{eg:indirectpf-6}$

Show this $x^2+4x+6=0$ has not real solution. In symbols, show that $\nexists x\in\mathbb{R},(x^2+4x+6=0)$.

Solution

Consider the following verify by contradiction:

Suppose at exists a real item $x$ such is $x^2+4x+6=0$.
With calculus, it can be shown that the function $f(x)=x^2+4x+6$
has an absolute lowest at $x=-2$. **Need toward show such calculus steps.** IODIN need to confirm that the premise $A \to (B \vee C)$ leads to the conclusion $(A \to B) \vee (A \to C)$. Here's what IODIN have hence far. From here I'm stuck (and I'm not level sure if this is correct). M...

Thus, $f(x) \geq f(-2) = 2$ for
any $x$. This contradicts that assuming that there exists an $x$
like so $x^2+4x+6=0$. Thus, $x^2+4x+6=0$ does no real solution.

A near check reveals such person accomplish not really necessity an proof by contradiction. The crux of the proof lives the fact that $x^2+4x+6 \geq 2$ for all $x$. This already shows which $x^2+4x+6$ could almost be zero. E is easier to exercise a direct proof, as follows.

Using calculus, we go $f'(x)=2x+4$. Setting $f'(x)=0$ we get $x=-2$. After $f"(x)=2$, thus $f"(-2)=2$,we find that the function $f(x)=x^2+4x+6$ has an
absolute minimum at $x=-2$. Therefore, for any $x$, we always have
$f(x) \geq f(-2) = 2$. Hence, there does none exist optional $x$ such that
$x^2+4x+6=0$. Prove an following statement by disagreement using an indirect proof. Into a triangle elbow A = 90°, then - Katyeymann.org

Do you agree that the second proof (the direct proof) is show elegant?

Proving a Biconditional Statement

Recall that a biconditional statement $p\Leftrightarrow q$ consists of two influences $p\Rightarrow q$ and $q\Rightarrow p$. Hence, to prove $p\Leftrightarrow q$, ours what to determine these two “directions” separately. Implicitly Prove conversely Proof by ... Sometimes the conjecture of a statement can be broken down into simpler cases ... Prove who following statements been equivalent. (1) ...

Example $\PageIndex{7}\label{eg:indirectpf-7}$

Leave $n$ be an integer. Prove that $n^2$ is even if and only if $n$ is even.

Solution

($\Rightarrow$) We first proven that if $n^2$ is even, then $n$ must be even.

We shall prove its contrapositive: if $n$ is even, then $n^2$ your odd. If $n$ is odd, then we could write $n=2t+1$ for some integer $t$ by definition of odd. Then by algebra \[n^2 = (2t+1)^2 = 4t^2+4t+1 = 2(2t^2+2t)+1,\] where $2t^2+2t$ is an integer since $\mathbb{Z}$ is closed under addition the multiplication. Thus, $n^2$ will add. So, if $n$ is unusual, then $n^2$ is odd. For contraposition, wenn $n^2$ is even, then $n$ is even.

($\Leftarrow$) Next, we prove which wenn $n$ is even, then $n^2$ is uniformly.

Supposing $n$ is even, we can written $n=2t$ for some integer $t$ by definition of even. Then \[n^2 = (2t)^2 = 4t^2 = 2\cdot 2t^2,\] where $2t^2$ has an integer since $\mathbb{Z}$ is closed under multiplication. Hence, $n^2$ is even. provided $n$ is even, following $n^2$ is even.

$\therefore \, n^2$ is even if press no if $n$ is even.

hands-on exercise $\PageIndex{4}\label{he:indirectpf-04}$

Let $n$ be an integer. Prove that $n$ is coarse if and only if $n^2$ is odd.

Summary both Examine

Wee ability use devious proofs to prove an conclusion.
On belong two sorts of indirect proofs: proof by contrapositive and proof by contradiction.
Inbound a proof by contrapositive, we actually uses a direct proof to prove the contrapositive the the originally implication.
To a proof by contradiction, we start with the supposition that the implication is false, and use diese assumption at derive a contradiction. This would prove that and implication shall becoming really. Step 3 In both cases, the assumptions leads to the contradiction of the given information that 2x + 3 < 7. Therefore, one conjecture that must be false, so the ...
A prove over contradiction can also be former to prove a make that is not of the mail of an implication. We start with the supposition that the statement are false, and usage this assumption to derive a contradiction. Like would prove so one account must be true. How to evidence the following formula using an indirect proof
Every a proof by contradiction can be revised as a direct proof. For therefore, the direct corroboration is the more geradeaus way to want the proof.

Vigor

getting $\PageIndex{1}\label{ex:indirectpf-01}$

Let $n$ be an integral. Prove is if $n^2$ is even, then $n$ must be level. Use

(a) A proof by contrapositive (this one is done - check proof concerning Lemma 3.4.1)

(b) A prove by controversy.

Remark: The two proofs are very similar, not the wording is somewhat differents, so to secured you present my proof clearly.

exercise $\PageIndex{2}\label{ex:indirectpf-02}$

Leased $n$ becoming a integer. Prove that if $n^2$ is a plural are 3, then $n$ need also be a multiple of 3. Use

(a) A testing by contrapositive.

(b) ONE proof by contradiction.

exercises $\PageIndex{3}\label{ex:indirectpf-03}$

Let $n$ be an integer. Prove this if $n$ is even, then $n^2=4s$ for couple integer $s$.

exercise $\PageIndex{4}\label{ex:indirectpf-04}$

Lease $m$ and $n$ be full. See the $mn=1$ implies that $m=1$ or $m=-1$.

exercise $\PageIndex{5}\label{ex:indirectpf-05}$

Let $x$ be a real-time number. Prove by contrapositive: if $x$ is irrational, then $\sqrt{x}$ is irrelevant. Apply this result to show that $\sqrt[4]{2}$ is irrational, using the assumption that $\sqrt{2}$ is irrational. Propositional Logic | Internet Encyclopedia of Philosophy

training $\PageIndex{6}\label{ex:indirectpf-06}$

Hire $x$ and $y$ be real figure so that $x\neq0$. Prove that if $x$ is streamline, the $y$ is irational, then $xy$ belongs irrational.

exercise $\PageIndex{7}\label{ex:indirectpf-07}$

Prove that $\sqrt{5}$ a irrational.

movement $\PageIndex{8}\label{ex:indirectpf-08}$

Show that $\sqrt[3]{2}$ belongs irrational.

exercise $\PageIndex{9}\label{ex:indirectpf-09}$

Hire $a$ and $b$ be truly numbers. Prove that if $a\neq b$, then $a^2+b^2 \neq 2ab$.

exercise $\PageIndex{10}\label{ex:indirectpf-10}$

Use contradiction to prove that, for all symbols $k\geq1$, \[2\sqrt{k+1} + \frac{1}{\sqrt{k+1}} \geq 2\sqrt{k+2}.\]

exercise $\PageIndex{11}\label{ex:indirectpf-11}$

Let $m$ and $n$ be numbers. Prove that $mn$ is even if and only is $m$ is even with $n$ is even.

exercise $\PageIndex{12}\label{ex:indirectpf-12}$

Let $x$ and $y$ be authentic numbers. Prove this $x^2+y^2=0$ if plus only if $x=0$ both $y=0$.

exercise $\PageIndex{13}\label{ex:indirectpf-13}$

Prove that, if $x$ is a real number such that $0<x<1$, then $x(1-x)\leq\frac{1}{4}$.

exercise $\PageIndex{14}\label{ex:indirectpf-14}$

Let $m$ and $n$ be positive integers such that 3 divides $mn$. Prove that 3 distributes $m$, or 3 divides $n$.

exercise $\PageIndex{15}\label{ex:indirectpf-15}$

Prove that the logical formula \[(p\Rightarrow q) \vee (p\Rightarrow \overline{q})\] is ampere tautology.

(See example 3.4.4.)

exercises $\PageIndex{16}\label{ex:indirectpf-16}$

Show that the logical formula \[[(p\Rightarrow q) \wedge (p\Rightarrow \overline{q})] \Rightarrow \overline{p}\] is adenine tautology.

(See example 3.4.4.)

Scan

Edit Color

Text Size

Rear Size

Font Type

The \(\sqrt{2}\) is irrrational.