How Do You Know When to Use a Arbitrary in a Proof for Logic

\(\def\d{\displaystyle} \def\course{Math 228} \newcommand{\f}[1]{\mathfrak #ane} \newcommand{\s}[1]{\mathscr #ane} \def\Due north{\mathbb Due north} \def\B{\mathbf{B}} \def\circleA{(-.5,0) circumvolve (ane)} \def\Z{\mathbb Z} \def\circleAlabel{(-i.v,.6) node[to a higher place]{$A$}} \def\Q{\mathbb Q} \def\circleB{(.5,0) circle (1)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\C{\mathbb C} \def\circleC{(0,-1) circumvolve (1)} \def\F{\mathbb F} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\A{\mathbb A} \def\twosetbox{(-2,-1.5) rectangle (2,i.5)} \def\10{\mathbb X} \def\threesetbox{(-2,-2.5) rectangle (2,one.v)} \def\Eastward{\mathbb E} \def\O{\mathbb O} \def\U{\mathcal U} \def\prisoner of war{\mathcal P} \def\inv{^{-1}} \def\nrml{\triangleleft} \def\st{:} \def\~{\widetilde} \def\rem{\mathcal R} \def\sigalg{$\sigma$-algebra } \def\Gal{\mbox{Gal}} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\land{\wedge} \def\And{\bigwedge} \def\entry{\entry} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Vee{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Th}} \def\entry{\entry} \def\saturday{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\dom{\mbox{dom}} \def\rng{\mbox{range}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[ii]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#i:#ii]{}} \newcommand{\va}[ane]{\vtx{above}{#one}} \newcommand{\vb}[one]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\v}{\vtx{higher up}{}} \def\circleA{(-.5,0) circle (ane)} \def\circleAlabel{(-one.5,.6) node[to a higher place]{$A$}} \def\circleB{(.v,0) circle (one)} \def\circleBlabel{(1.five,.6) node[above]{$B$}} \def\circleC{(0,-ane) circumvolve (1)} \def\circleClabel{(.5,-2) node[correct]{$C$}} \def\twosetbox{(-ii,-1.four) rectangle (2,one.4)} \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.iv)} \def\ansfilename{practise-answers} \def\shadowprops{{fill up=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circumvolve with fuzzy edge 10 percentage}}} \newcommand{\hexbox}[three]{ \def\x{-cos{thirty}*\r*#ane+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(ninety:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- wheel; \draw (\x,\y) node{#3}; } \renewcommand{\bar}{\overline} \newcommand{\card}[ane]{\left| #one \right|} \newcommand{\twoline}[2]{\brainstorm{pmatrix}#1 \\ #2 \end{pmatrix}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Investigate! 27

Decide which of the following are valid proofs of the following statement:

If $a b$ is an even number, then $a$ or $b$ is even.

Suppose $a$ and $b$ are odd. That is, $a=2k+1$ and $b=2m+1$ for some integers $thou$ and $m\text{.}$ Then
\begin{align*} ab \amp =(2k+1)(2m+1)\\ \amp =4km+2k+2m+one\\ \amp =ii(2km+k+m)+1. \stop{align*}
Therefore $ab$ is odd.
Assume that $a$ or $b$ is even - say it is $a$ (the case where $b$ is even will be identical). That is, $a=2k$ for some integer $chiliad\text{.}$ And so
\begin{align*} ab \amp =(2k)b\\ \amp =2(kb). \end{align*}
Thus $ab$ is fifty-fifty.
Suppose that $ab$ is even simply $a$ and $b$ are both odd. Namely, $ab = 2n\text{,}$ $a=2k+ane$ and $b=2j+1$ for some integers $north\text{,}$ $k\text{,}$ and $j\text{.}$ Then
\begin{marshal*} 2n \amp =(2k+1)(2j+ane)\\ 2n \amp =4kj+2k+2j+1\\ n \amp = 2kj+k+j+\frac{1}{2}. \stop{marshal*}
But since $2kj+thousand+j$ is an integer, this says that the integer $n$ is equal to a non-integer, which is impossible.
Let $ab$ be an even number, say $ab=2n\text{,}$ and $a$ be an odd number, say $a=2k+1\text{.}$
\begin{align*} ab \amp =(2k+1)b\\ 2n \amp =2kb+b\\ 2n-2kb\amp =b\\ 2(n-kb)\amp =b. \end{align*}
Therefore $b$ must be even.

Anyone who doesn't believe at that place is creativity in mathematics conspicuously has not tried to write proofs. Finding a fashion to convince the earth that a particular statement is necessarily true is a mighty undertaking and can often be quite challenging. There is not a guaranteed path to success in the search for proofs. For example, in the summer of 1742, a German mathematician past the proper name of Christian Goldbach wondered whether every even integer greater than ii could be written every bit the sum of two primes. Centuries later on, we yet don't have a proof of this apparent fact (computers accept checked that "Goldbach's Conjecture" holds for all numbers less than $4\times 10^{18}\text{,}$ which leaves simply infinitely many more numbers to check).

Writing proofs is a fleck of an art. Like whatsoever art, to be truly keen at it, you need some sort of inspiration, too as some foundational technique. Just as musicians tin learn proper fingering, and painters tin can learn the proper way to agree a brush, we tin wait at the proper way to construct arguments. A adept place to commencement might exist to study a classic.

Theorem three.ii.1

There are infinitely many primes.

Proof

Suppose this were non the case. That is, suppose there are only finitely many primes. And then there must be a last, largest prime, call it $p\text{.}$ Consider the number

\begin{equation*} N = p! + 1 = (p \cdot (p-1) \cdot \cdots 3\cdot 2 \cdot ane) + 1. \end{equation*}

Now $N$ is certainly larger than $p\text{.}$ Also, $North$ is not divisible by any number less than or equal to $p\text{,}$ since every number less than or equal to $p$ divides $p!\text{.}$ Thus the prime factorization of $Northward$ contains prime number numbers (perchance only $N$ itself) all greater than $p\text{.}$ Then $p$ is non the largest prime, a contradiction. Therefore there are infinitely many primes.

This proof is an case of a proof by contradiction, ane of the standard styles of mathematical proof. First and foremost, the proof is an argument. It contains sequence of statements, the final being the determination which follows from the previous statements. The argument is valid so the conclusion must be true if the premises are true. Permit's go through the proof line past line.

Suppose at that place are only finitely many primes. [this is a premise. Note the utilize of "suppose."]
There must be a largest prime number, call information technology $p\text{.}$ [follows from line one, by the definition of "finitely many."]
Permit $N = p! + i\text{.}$ [basically merely annotation, although this is the inspired part of the proof; looking at $p! + 1$ is the key insight.]
$N$ is larger than $p\text{.}$ [past the definition of $p!$]
$Due north$ is not divisible by whatever number less than or equal to $p\text{.}$ [by definition, $p!$ is divisible by each number less than or equal to $p\text{,}$ and so $p! + ane$ is not.]
The prime factorization of $N$ contains prime number numbers greater than $p\text{.}$ [since $N$ is divisible by each prime number in the prime factorization of $N\text{,}$ and by line 5.]
Therefore $p$ is not the largest prime. [by line 6, $N$ is divisible by a prime larger than $p\text{.}$]
This is a contradiction. [from line 2 and line 7: the largest prime is $p$ and there is a prime larger than $p\text{.}$]
Therefore there are infinitely many primes. [from line ane and line 8: our only premise pb to a contradiction, so the premise is faux.]

We should say a bit more than about the concluding line. Upward through line eight, we have a valid argument with the premise "there are only finitely many primes" and the conclusion "there is a prime larger than the largest prime number." This is a valid argument as each line follows from previous lines. And so if the premises are truthful, then the determination must exist true. However, the determination is Not true. The but way out: the premise must be simulated.

The sort of line-by-line assay nosotros did higher up is a not bad way to actually understand what is going on. Whenever you come across a proof in a textbook, you lot really should make sure y'all empathize what each line is proverb and why it is true. Additionally, it is as important to empathize the overall structure of the proof. This is where using tools from logic is helpful. Luckily there are a relatively pocket-sized number of standard proof styles that keep showing upward again and again. Being familiar with these tin can assist empathize proof, besides as give ideas of how to write your own.

Subsection Direct Proof

The simplest (from a logic perspective) fashion of proof is a direct proof. Oftentimes all that is required to prove something is a systematic caption of what everything ways. Direct proofs are specially useful when proving implications. The general format to prove $P \imp Q$ is this:

Assume $P\text{.}$ Explicate, explicate, …, explicate. Therefore $Q\text{.}$

Often we desire to prove universal statements, perchance of the form $\forall x (P(x) \imp Q(x))\text{.}$ Over again, we will want to assume $P(x)$ is truthful and deduce $Q(x)\text{.}$ But what about the $10\text{?}$ We want this to work for all $10\text{.}$ We accomplish this by fixing $x$ to exist an arbitrary element (of the sort we are interested in).

Here are a few examples. Offset, nosotros will set up up the proof construction for a direct proof, then fill in the details.

Case 3.2.ii

Show: For all integers $n\text{,}$ if $northward$ is fifty-fifty, then $north^two$ is fifty-fifty.

Solution

The format of the proof with be this: Let $n$ be an capricious integer. Presume that $n$ is even. Explain explain explain. Therefore $northward^ii$ is fifty-fifty.

To fill in the details, nosotros will basically only explain what it means for $n$ to be even, and then see what that means for $n^2\text{.}$ Here is a complete proof.

Proof

Let $n$ exist an capricious integer. Suppose $n$ is fifty-fifty. So $n = 2k$ for some integer $k\text{.}$ Now $n^ii = (2k)^ii = 4k^2 = 2(2k^ii)\text{.}$ Since $2k^2$ is an integer, $due north^ii$ is even.

Case three.2.3

Prove: For all integers $a\text{,}$ $b\text{,}$ and $c\text{,}$ if $a|b$ and $b|c$ then $a|c\text{.}$ Here $10|y\text{,}$ read "$x$ divides $y$" ways that $y$ is a multiple of $x$ (so $ten$ volition divide into $y$ without balance).

Solution

Even before nosotros know what the divides symbol means, we tin set upwards a direct proof for this argument. It volition become something similar this: Allow $a\text{,}$ $b\text{,}$ and $c$ exist arbitrary integers. Presume that $a|b$ and $b|c\text{.}$ Dot dot dot. Therefore $a|c\text{.}$

How do we connect the dots? We say what our hypothesis ($a|b$ and $b|c$) really ways and why this gives u.s. what the conclusion ($a|c$) actually ways. Some other way to say that $a|b$ is to say that $b = ka$ for some integer $k$ (that is, that $b$ is a multiple of $a$). What are we going for? That $c = la\text{,}$ for some integer $50$ (because we desire $c$ to be a multiple of $a$). Here is the consummate proof.

Proof

Allow $a\text{,}$ $b\text{,}$ and $c$ be integers. Assume that $a|b$ and $b|c\text{.}$ In other words, $b$ is a multiple of $a$ and $c$ is a multiple of $b\text{.}$ So at that place are integers $k$ and $j$ such that $b = ka$ and $c = jb\text{.}$ Combining these (through commutation) we get that $c = jka\text{.}$ But $jk$ is an integer, so this says that $c$ is a multiple of $a\text{.}$ Therefore $a|c\text{.}$

Subsection Proof past Contrapositive

Recall that an implication $P \imp Q$ is logically equivalent to its contrapositive $\neg Q \imp \neg P\text{.}$ At that place are plenty of examples of statements which are difficult to prove directly, just whose contrapositive can easily exist proved directly. This is all that proof by contrapositive does. It gives a directly proof of the contrapositive of the implication. This is plenty because the contrapositive is logically equivalent to the original implication.

The skeleton of the proof of $P \imp Q$ by contrapositive volition always look roughly like this:

Presume $\neg Q\text{.}$ Explicate, explicate, … explain. Therefore $\neg P\text{.}$

Every bit before, if there are variables and quantifiers, we ready them to be arbitrary elements of our domain. Here are a couple examples:

Case 3.2.iv

Is the statement "for all integers $n\text{,}$ if $n^2$ is even, so $n$ is even" true?

Solution

This is the converse of the statement we proved higher up using a straight proof. From trying a few examples, this statement definitely appears this is true. So let's prove it.

A direct proof of this statement would require fixing an arbitrary $n$ and assuming that $n^ii$ is even. Simply it is not at all clear how this would permit us to conclude anything about $n\text{.}$ Only because $n^two = 2k$ does non in itself advise how nosotros could write $n$ as a multiple of 2.

Attempt something else: write the contrapositive of the argument. We get, for all integers $north\text{,}$ if $n$ is odd and so $n^2$ is odd. This looks much more promising. Our proof will look something like this:

Let $n$ be an capricious integer. Suppose that $n$ is not fifty-fifty. This means that …. In other words …. But this is the same equally proverb …. Therefore $n^2$ is not even.

At present we make full in the details:

Proof

We will prove the contrapositive. Let $n$ be an arbitrary integer. Suppose that $n$ is not even, and thus odd. Then $n= 2k+1$ for some integer $k\text{.}$ Now $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\text{.}$ Since $2k^2 + 2k$ is an integer, we see that $northward^two$ is odd and therefore not even.

Instance three.2.v

Prove: for all integers $a$ and $b\text{,}$ if $a + b$ is odd, then $a$ is odd or $b$ is odd.

Solution

The problem with trying a direct proof is that it will be hard to separate $a$ and $b$ from knowing something virtually $a+b\text{.}$ On the other hand, if we know something about $a$ and $b$ separately, then combining them might give united states information almost $a+b\text{.}$ The contrapositive of the statement we are trying to prove is: for all integers $a$ and $b\text{,}$ if $a$ and $b$ are fifty-fifty, then $a+b$ is even. Thus our proof will accept the following format:

Permit $a$ and $b$ exist integers. Assume that $a$ and $b$ are both even. la la la. Therefore $a+b$ is fifty-fifty.

Here is a complete proof:

Proof

Let $a$ and $b$ be integers. Assume that $a$ and $b$ are even. Then $a = 2k$ and $b = 2l$ for some integers $k$ and $l\text{.}$ Now $a + b = 2k + 2l = two(k+ane)\text{.}$ Since $1000 + fifty$ is an integer, we see that $a + b$ is fifty-fifty, completing the proof.

Note that our supposition that $a$ and $b$ are even is really the negation of $a$ or $b$ is odd. We used De Morgan's law here.

We have seen how to prove some statements in the form of implications: either directly or past contrapositive. Some statements are not written every bit implications to begin with.

Example 3.two.6

Consider the argument, for every prime number number $p\text{,}$ either $p = 2$ or $p$ is odd. We can rephrase this: for every prime number $p\text{,}$ if $p \ne ii\text{,}$ then $p$ is odd. At present try to prove it.

Solution

Proof

Allow $p$ be an arbitrary prime. Assume $p$ is not odd. So $p$ is divisible past two. Since $p$ is prime, it must have exactly 2 divisors, and it has 2 equally a divisor, then $p$ must exist divisible past only ane and 2. Therefore $p = 2\text{.}$ This completes the proof (by contrapositive).

Subsection Proof past Contradiction

There might be statements which really cannot be rephrased every bit implications. For instance, "$\sqrt 2$ is irrational." In this case, information technology is hard to know where to start. What can nosotros assume? Well, say we desire to bear witness the statement $P\text{.}$ What if nosotros could testify that $\neg P \imp Q$ where $Q$ was false? If this implication is true, and $Q$ is false, what can we say near $\neg P\text{?}$ It must be false as well, which makes $P$ true!

This is why proof by contradiction works. If we can prove that $\neg P$ leads to a contradiction, then the only conclusion is that $\neg P$ is simulated, so $P$ is truthful. That'southward what we wanted to bear witness. In other words, if information technology is impossible for $P$ to exist false, $P$ must be true.

Here are a couple examples of proofs by contradiction:

Example iii.2.7

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

Solution

Proof

Suppose not. And then $\sqrt 2$ is equal to a fraction $\frac{a}{b}\text{.}$ Without loss of generality, presume $\frac{a}{b}$ is in lowest terms (otherwise reduce the fraction). So,

\begin{equation*} 2 = \frac{a^2}{b^2} \end{equation*} \begin{equation*} 2b^two = a^2 \finish{equation*}

Thus $a^2$ is even, and every bit such $a$ is even. And then $a = 2k$ for some integer $k\text{,}$ and $a^2 = 4k^ii\text{.}$ We then have,

\begin{equation*} 2b^2 = 4k^2 \end{equation*} \brainstorm{equation*} b^2 = 2k^2 \end{equation*}

Thus $b^2$ is fifty-fifty, and as such $b$ is fifty-fifty. Since $a$ is also even, nosotros run across that $\frac{a}{b}$ is non in lowest terms, a contradiction. Thus $\sqrt 2$ is irrational.

Example 3.2.8

Prove: In that location are no integers $x$ and $y$ such that $x^2 = 4y + 2\text{.}$

Solution

Proof

We go on by contradiction. So suppose there are integers $10$ and $y$ such that $x^2 = 4y + two = 2(2y + 1)\text{.}$ So $x^ii$ is even. Nosotros accept seen that this implies that $ten$ is even. So $x = 2k$ for some integer $one thousand\text{.}$ And so $x^2 = 4k^2\text{.}$ This in turn gives $2k^ii = (2y + 1)\text{.}$ Only $2k^2$ is fifty-fifty, and $2y + 1$ is odd, so these cannot exist equal. Thus nosotros have a contradiction, and then there must not be any integers $x$ and $y$ such that $x^2 = 4y + 2\text{.}$

Example 3.2.nine

The Pigeonhole Principle: If more than $n$ pigeons fly into $n$ dove holes, so at least one dove pigsty will comprise at least two pigeons. Bear witness this!

Solution

Proof

Suppose, contrary to stipulation, that each of the pigeon holes incorporate at well-nigh ane pigeon. And then at nigh, there will be $n$ pigeons. But we assumed that in that location are more than $due north$ pigeons, so this is impossible. Thus in that location must be a pigeonhole with more than one pigeon.

While we phrased this proof as a proof past contradiction, we could have also used a proof by contrapositive since our contradiction was simply the negation of the hypothesis. Sometimes this volition happen, in which case yous can utilize either mode of proof. In that location are examples still where the contradiction occurs "far away" from the original argument.

Subsection Proof past (counter) Example

Information technology is almost NEVER okay to show a statement with simply an example. Certainly none of the statements proved above can be proved through an instance. This is because in each of those cases we are trying to show that something holds of all integers. Nosotros merits that $n^ii$ being even implies that $n$ is even, no matter what integer $n$ we pick. Showing that this works for $n = 4$ is non fifty-fifty close to enough.

This cannot be stressed enough. If you are trying to bear witness a statement of the class $\forall 10 P(10)\text{,}$ you admittedly CANNOT prove this with an example. ¹ This is non to say that looking at examples is a waste of time. Doing then will often give you an thought of how to write a proof. Merely the examples do non vest in the proof.

However, existential statements can be proven this manner. If we want to bear witness that in that location is an integer $n$ such that $n^2-due north+41$ is non prime, all we need to do is observe one. This might seem like a silly thing to want to prove until you try a few values for $n\text{.}$

$north$	1	2	three	four	5	6	7
$n^2 - n + 41$	41	43	47	53	61	71	83

And so far we have gotten only primes. You might exist tempted to conjecture, "For all positive integers $n\text{,}$ the number $n^2 - n + 41$ is prime number." If you lot wanted to prove this, you lot would need to use a straight proof, a proof past contrapositive, or another fashion of proof, only certainly it is not enough to requite even vii examples. In fact, we can prove this conjecture is faux by proving its negation: "There is a positive integer $n$ such that $n^two - northward + 41$ is not prime." Since this is an existential argument, it suffices to show that in that location does indeed exist such a number.

In fact, we tin can quickly meet that $n = 41$ volition requite $41^two$ which is certainly not prime number. You might say that this is a counterexample to the conjecture that $n^2 - n + 41$ is always prime number. Since and then many statements in mathematics are universal, making their negations existential, we can often show that a statement is false (if information technology is) by providing a counterexample.

Instance iii.two.10

Above we proved, "for all integers $a$ and $b\text{,}$ if $a+b$ is odd, then $a$ is odd or $b$ is odd." Is the antipodal true?

Solution

The converse is the argument, "for all integers $a$ and $b\text{,}$ if $a$ is odd or $b$ is odd, then $a + b$ is odd." This is false! How do nosotros show information technology is false? Nosotros demand to show the negation of the converse. Let's look at the symbols. The converse is

\brainstorm{equation*} \forall a \forall b ((O(a) \vee O(b)) \imp O(a+b)). \stop{equation*}

We want to prove the negation:

\begin{equation*} \neg \forall a \forall b ((O(a) \vee O(b)) \imp O(a+b)). \end{equation*}

Simplify using the rules from the previous sections:

\begin{equation*} \exists a \exists b ((O(a) \vee O(b)) \wedge \neg O(a+b)). \end{equation*}

Equally the negation passed by the quantifiers, they changed from $\forall$ to $\exists\text{.}$ We then needed to have the negation of an implication, which is equivalent to asserting the if part and not the then part.

Now nosotros know what to do. To testify that the converse is fake we need to find two integers $a$ and $b$ and then that $a$ is odd or $b$ is odd, simply $a+b$ is not odd (then fifty-fifty). That's easy: 1 and 3. (remember, "or" means 1 or the other or both). Both of these are odd, but $1+3 = 4$ is not odd.

Subsection Proof past Cases

Nosotros could go on and on and on about different proof styles (nosotros haven't fifty-fifty mentioned induction or combinatorial proofs here), but instead we volition terminate with 1 final useful technique: proof by cases. The idea is to bear witness that $P$ is true past proving that $Q \imp P$ and $\neg Q \imp P$ for some argument $Q\text{.}$ So no matter what, whether or not $Q$ is truthful, we know that $P$ is true. In fact, we could generalize this. Suppose we desire to prove $P\text{.}$ Nosotros know that at to the lowest degree i of the statements $Q_1, Q_2, \ldots, Q_n$ are true. If we tin show that $Q_1 \imp P$ and $Q_2 \imp P$ and then on all the way to $Q_n \imp P\text{,}$ then we can conclude $P\text{.}$ The key thing is that we desire to be sure that one of our cases (the $Q_i$'s) must be true no matter what.

If that last paragraph was confusing, peradventure an example will brand things meliorate.

Example 3.2.11

Prove: For any integer $due north\text{,}$ the number $(n^three -northward)$ is even.

Solution

It is hard to know where to first this, because we don't know much of anything about $northward\text{.}$ We might be able to bear witness that $n^3 - n$ is fifty-fifty if nosotros knew that $n$ was fifty-fifty. In fact, nosotros could probably evidence that $n^three-due north$ was fifty-fifty if $n$ was odd. Simply since $n$ must either exist even or odd, this will be enough. Here'south the proof.

Proof

We consider two cases: if $n$ is even or if $n$ is odd.

Case 1: $n$ is even. Then $north = 2k$ for some integer $k\text{.}$ This give

\begin{align*} n^three - n \amp = 8k^3 - 2k\\ \amp = two(4k^2 - k), \stop{align*}

and since $4k^ii - one thousand$ is an integer, this says that $n^iii-due north$ is even.

Case 2: $n$ is odd. So $due north = 2k+ane$ for some integer $k\text{.}$ This gives

\begin{align*} n^3 - n \amp = (2k+1)^3 - (2k+1)\\ \amp = 8k^3 + 6k^2 + 6k + ane - 2k - 1\\ \amp = 2(4k^three + 3k^two + 2k), \finish{align*}

and since $4k^3 + 3k^2 + 2k$ is an integer, nosotros see that $north^three - north$ is even again.

Since $n^3 - n$ is even in both exhaustive cases, we see that $n^3 - n$ is indeed always even.

Subsection Exercises

1

Consider the argument "for all integers $a$ and $b\text{,}$ if $a + b$ is fifty-fifty, then $a$ and $b$ are even"

Write the contrapositive of the argument.
Write the antipodal of the argument.
Write the negation of the statement.
Is the original statement true or imitation? Prove your answer.
Is the contrapositive of the original statement true or false? Prove your respond.
Is the converse of the original statement true or false? Prove your answer.
Is the negation of the original statement true or false? Prove your respond.

Solution

For all integers $a$ and $b\text{,}$ if $a$ or $b$ is not even, then $a+b$ is not even.
For all integers $a$ and $b\text{,}$ if $a$ and $b$ are even, so $a+b$ is fifty-fifty.
There are numbers $a$ and $b$ such that $a+b$ is even simply $a$ and $b$ are not both even.
Simulated. For instance, $a = iii$ and $b = five\text{.}$ $a+b = 8\text{,}$ only neither $a$ nor $b$ are even.
Faux, since it is equivalent to the original statement.
True. Let $a$ and $b$ exist integers. Assume both are even. Then $a = 2k$ and $b = 2j$ for some integers $chiliad$ and $j\text{.}$ Only then $a+b = 2k + 2j = 2(k+j)$ which is even.
True, since the statement is simulated.

2

Consider the statement: for all integers $n\text{,}$ if $north$ is even and so $8n$ is even.

Prove the statement. What sort of proof are y'all using?
Is the converse true? Evidence or disprove.

Solution

Direct proof.

Proof

Let $n$ exist an integer. Assume $n$ is even. Then $n = 2k$ for some integer $one thousand\text{.}$ Thus $8n = 16k = 2(8k)\text{.}$ Therefore $8n$ is even.
The converse is false. That is, there is an integer $n$ such that $8n$ is even but $due north$ is odd. For instance, consider $north = 3\text{.}$ And so $8n = 24$ which is fifty-fifty but $north = 3$ is odd.

3

Your "friend" has shown you a "proof" he wrote to testify that $i = 3\text{.}$ Here is the proof:

Proof

I merits that $one = three\text{.}$ Of course nosotros can exercise anything to one side of an equation as long as nosotros also practice it to the other side. And so subtract two from both sides. This gives $-ane = 1\text{.}$ At present foursquare both sides, to go $i = 1\text{.}$ And we all concord this is true.

What is going on here? Is your friend's argument valid? Is the argument a proof of the claim $1=three\text{?}$ Carefully explicate using what we know nearly logic. Hint: What implication follows from the given proof?

4

Suppose you accept a collection of v-cent stamps and 8-cent stamps. We saw earlier that it is possible to make any amount of postage greater than 27 cents using combinations of both these types of stamps. But, let's ask some other questions:

What amounts of postage stamp can you brand if y'all simply use an even number of both types of stamps? Show your answer.
Suppose you fabricated an even amount of postage. Evidence that you lot used an even number of at least one of the types of stamps.
Suppose you fabricated exactly 72 cents of stamp. Evidence that yous used at to the lowest degree half-dozen of 1 type of postage.

5

Suppose that you would like to evidence the following implication:

For all numbers $n\text{,}$ if $n$ is prime so $n$ is solitary.

Write out the beginning and end of the argument if y'all were to evidence the statement,

Straight
By contrapositive
By contradiction

You practice non need to provide details for the proofs (since you practise not know what lone means). However, make sure that you provide the outset few and last few lines of the proofs so that we can see that logical structure you lot would follow.

half dozen

Prove that $\sqrt iii$ is irrational.

Solution

Proof

Suppose $\sqrt{iii}$ were rational. Then $\sqrt{3} = \frac{a}{b}$ for some integers $a$ and $b \ne 0\text{.}$ Without loss of generality, assume $\frac{a}{b}$ is reduced. Now

\begin{equation*} 3 = \frac{a^2}{b^2} \terminate{equation*} \brainstorm{equation*} b^two 3 = a^2 \terminate{equation*}

So $a^2$ is a multiple of 3. This tin can only happen if $a$ is a multiple of 3, so $a = 3k$ for some integer $yard\text{.}$ Then nosotros have

\brainstorm{equation*} b^ii iii = 9k^two \end{equation*} \begin{equation*} b^ii = 3k^2 \end{equation*}

And then $b^2$ is a multiple of three, making $b$ a multiple of 3 besides. Simply this contradicts our supposition that $\frac{a}{b}$ is in lowest terms.

Therefore, $\sqrt{3}$ is irrational.

vii

Consider the statement: for all integers $a$ and $b\text{,}$ if $a$ is fifty-fifty and $b$ is a multiple of three, so $ab$ is a multiple of half-dozen.

Bear witness the argument. What sort of proof are you lot using?
State the converse. Is it true? Prove or disprove.

8

Prove the statement: For all integers $due north\text{,}$ if $5n$ is odd, then $n$ is odd. Clearly state the style of proof you lot are using.

Solution

We volition prove the contrapositive: if $n$ is fifty-fifty, then $5n$ is even.

Proof

Let $n$ be an arbitrary integer, and suppose $n$ is even. And then $north = 2k$ for some integer $thou\text{.}$ Thus $5n = 5\cdot 2k = 10k = two(5k)\text{.}$ Since $5k$ is an integer, we run into that $5n$ must be fifty-fifty. This completes the proof.

9

Prove the argument: For all integers $a\text{,}$ $b\text{,}$ and $c\text{,}$ if $a^2 + b^2 = c^2\text{,}$ and then $a$ or $b$ is even.

10

Bear witness: $x=y$ if and just if $xy=\dfrac{(x+y)^two}{4}\text{.}$ Annotation, you will demand to bear witness ii "directions" hither: the "if" and the "only if" part.

11

The game TENZI comes with twoscore 6-sided dice (each numbered 1 to 6). Suppose you lot roll all 40 die.

Bear witness that there volition be at least seven dice that state on the aforementioned number.
How many dice would you have to roll earlier you were guaranteed that some four of them would all match or all be different? Prove your answer.

Solution

This is an instance of the pigeonhole principle. Nosotros can prove it by contrapositive.

Proof

Suppose that each number just came up half dozen or fewer times. So there are at most six 1's, six 2's, then on. That's a total of 36 dice, and then yous must not take rolled all 40 dice.
We tin can take 9 die without whatever 4 matching or any four existence all unlike: three 1'south, three 2'south, iii 3'due south. We will prove that whenever y'all coil 10 die, you will ever get iv matching or all being different.

Proof

Suppose you roll 10 dice, but that there are Non iv matching rolls. This means at most, there are iii of any given value. If we merely had three different values, that would be only 9 dice, so there must be 4 different values, giving 4 die that are all unlike.

12

Bear witness that $\log(7)$ is irrational.

Solution

We give a proof past contradiction.

Proof

Suppose, contrary to stipulation that $\log(7)$ is rational. Then $\log(7) = \frac{a}{b}$ with $a$ and $b \ne 0$ integers. By backdrop of logarithms, this implies

\brainstorm{equation*} vii = 10^{\frac{a}{b}} \terminate{equation*}

Equivalently,

\begin{equation*} vii^b = 10^a \end{equation*}

Simply this is incommunicable as any power of 7 will be odd while any power of ten will be even. Therefore, $\log(7)$ is irrational.

13

Prove that there are no integer solutions to the equation $x^2 = 4y + 3\text{.}$

xiv

Testify that every prime greater than 3 is either one more or one less than a multiple of 6.

Hint

Prove the contrapositive by cases.

15

For each of the statements below, say what method of proof you should utilise to prove them. And then say how the proof starts and how information technology ends. Bonus points for filling in the middle.

At that place are no integers $x$ and $y$ such that $x$ is a prime greater than 5 and $10 = 6y + 3\text{.}$
For all integers $northward\text{,}$ if $north$ is a multiple of 3, then $n$ tin can be written as the sum of consecutive integers.
For all integers $a$ and $b\text{,}$ if $a^2 + b^2$ is odd, and then $a$ or $b$ is odd.

Solution

Proof by contradiction. Get-go of proof: Presume, for the sake of contradiction, that at that place are integers $10$ and $y$ such that $x$ is a prime greater than 5 and $x = 6y + three\text{.}$ End of proof: … this is a contradiction, then at that place are no such integers.
Directly proof. Start of proof: Let $n$ be an integer. Assume $n$ is a multiple of 3. End of proof: Therefore $north$ can be written as the sum of consecutive integers.
Proof past contrapositive. Start of proof: Permit $a$ and $b$ exist integers. Assume that $a$ and $b$ are even. End of proof: Therefore $a^2 + b^2$ is even.

16

A standard deck of 52 cards consists of 4 suites (hearts, diamonds, spades and clubs) each containing 13 different values (Ace, 2, 3, …, 10, J, Q, Thousand). If you lot depict some number of cards at random you might or might not accept a pair (two cards with the same value) or three cards all of the same suit. However, if you draw enough cards, you volition be guaranteed to take these. For each of the following, observe the smallest number of cards you would demand to draw to exist guaranteed having the specified cards. Prove your answers.

Three of a kind (for example, three vii'due south).
A flush of five cards (for case, five hearts).
Iii cards that are either however adjust or all different suits.

17

Suppose you are at a party with 19 of your closest friends (so including you, there are 20 people in that location). Explicate why there must be to the lowest degree two people at the party who are friends with the aforementioned number of people at the party. Assume friendship is always reciprocated.

18

Your friend has given you his list of 115 best Doctor Who episodes (in order of greatness). It turns out that you have seen 60 of them. Show that there are at least 2 episodes you take seen that are exactly four episodes apart.

19

Suppose you have an $n\times northward$ chessboard just your dog has eaten 1 of the corner squares. Can you still embrace the remaining squares with dominoes? What needs to be true about $n\text{?}$ Requite necessary and sufficient weather condition (that is, say exactly which values of $northward$ piece of work and which practise not piece of work). Prove your answers.

twenty

What if your $n\times northward$ chessboard is missing 2 opposite corners? Testify that no affair what $n$ is, you will not be able to cover the remaining squares with dominoes.

How Do You Know When to Use a Arbitrary in a Proof for Logic

Source: http://discrete.openmathbooks.org/dmoi2/sec_logic-proofs.html

\(north\)	1	2	three	four	5	6	7
\(n^2 - n + 41\)	41	43	47	53	61	71	83

How Do You Know When to Use a Arbitrary in a Proof for Logic

Investigate! 27

Theorem three.ii.1

Proof

Subsection Direct Proof

Case 3.2.ii

Proof

Case three.2.3

Proof

Subsection Proof past Contrapositive

Case 3.2.iv

Proof

Instance three.2.v

Proof

Example 3.two.6

Proof

Subsection Proof past Contradiction

Example iii.2.7

Proof

Example 3.2.8

Proof

Example 3.2.nine

Proof

Subsection Proof past (counter) Example

Instance iii.two.10

Subsection Proof past Cases

Example 3.2.11

Proof

Subsection Exercises

1

2

Proof

3

Proof

4

5

half dozen

Proof

vii

8

Proof

9

10

11

Proof

Proof

12

Proof

13

xiv

15

16

17

18

19

twenty

0 Response to "How Do You Know When to Use a Arbitrary in a Proof for Logic"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel