Skip to main content
Contents Index
Search Book
Search Results:
No results.
Readability settings Prev Up Next \(\require{cancel}
\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\bbrac}[1]{\bigl(#1\bigr)}
\newcommand{\Bbrac}[1]{\Bigl(#1\Bigr)}
\newcommand{\correct}{\boldsymbol{\checkmark}}
\newcommand{\incorrect}{\boldsymbol{\times}}
\newcommand{\inv}[2][1]{{#2}^{-{#1}}}
\newcommand{\leftsub}[3][1]{\mathord{{}_{#2\mkern-#1mu}#3}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\sqrtop}{sqrt}
\newcommand{\lgcnot}{\neg}
\newcommand{\lgcand}{\wedge}
\newcommand{\lgcor}{\vee}
\newcommand{\lgccond}{\rightarrow}
\newcommand{\lgcbicond}{\leftrightarrow}
\newcommand{\lgcimplies}{\Rightarrow}
\newcommand{\lgcequiv}{\Leftrightarrow}
\newcommand{\lgctrue}{\mathrm{T}}
\newcommand{\lgcfalse}{\mathrm{F}}
\newcommand{\boolnot}[1]{{#1}'}
\newcommand{\boolzero}{\mathbf{0}}
\newcommand{\boolone}{\mathbf{1}}
\newcommand{\setdef}[2]{\left\{\mathrel{}#1\mathrel{}\middle|\mathrel{}#2\mathrel{}\right\}}
\newcommand{\inlinesetdef}[2]{\{\mathrel{}#1\mathrel{}\mid\mathrel{}#2\mathrel{}\}}
\let\emptyword\emptyset
\renewcommand{\emptyset}{\varnothing}
\newcommand{\relcmplmnt}{\smallsetminus}
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\cmplmnt}[1]{{#1}^{\mathrm{c}}}
\newcommand{\disjunion}{\sqcup}
\newcommand{\cartprod}{\times}
\newcommand{\words}[1]{{#1}^\ast}
\newcommand{\length}[1]{\abs{#1}}
\newcommand{\powsetbare}{\mathcal{P}}
\newcommand{\powset}[1]{\powsetbare(#1)}
\newcommand{\funcdef}[4][\to]{#2\colon #3 #1 #4}
\newcommand{\ifuncto}{\hookrightarrow}
\newcommand{\ifuncdef}[3]{\funcdef[\ifuncto]{#1}{#2}{#3}}
\newcommand{\sfuncto}{\twoheadrightarrow}
\newcommand{\sfuncdef}[3]{\funcdef[\sfuncto]{#1}{#2}{#3}}
\newcommand{\funcgraphbare}{\Delta}
\newcommand{\funcgraph}[1]{\funcgraphbare(#1)}
\newcommand{\nmathrel}[1]{\mathrel{\not #1}}
\newcommand{\relset}[3]{#1_{{} #2 #3}}
\newcommand{\gtset}[2]{\relset{#1}{\gt}{#2}}
\newcommand{\posset}[1]{\gtset{#1}{0}}
\newcommand{\geset}[2]{\relset{#1}{\ge}{#2}}
\newcommand{\nnegset}[1]{\geset{#1}{0}}
\newcommand{\neqset}[2]{\relset{#1}{\neq}{#2}}
\newcommand{\nzeroset}[1]{\neqset{#1}{0}}
\newcommand{\ltset}[2]{\relset{#1}{\lt}{#2}}
\newcommand{\leset}[2]{\relset{#1}{\le}{#2}}
\newcommand{\natnumlt}[1]{\ltset{\N}{#1}}
\DeclareMathOperator{\id}{id}
\newcommand{\inclfunc}[2]{\iota_{#1}^{#2}}
\newcommand{\projfunc}[1]{\rho_{#1}}
\DeclareMathOperator{\proj}{proj}
\newcommand{\funcres}[2]{\left.{#1}\right\rvert_{#2}}
\newcommand{\altfuncres}[2]{\left.{#1}\right\rvert{#2}}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\flr}{flr}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\funccomp}{\circ}
\newcommand{\funcinvimg}[2]{\inv{#1}\left({#2}\right)}
\newcommand{\card}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\cardop}{card}
\DeclareMathOperator{\ncardop}{\#}
\newcommand{\EngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \mathrm{c}, \, \dotsc, \, \mathrm{y}, \, \mathrm{z} \}}
\newcommand{\ShortEngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \dotsc, \, \mathrm{z} \}}
\newcommand{\eqclass}[1]{\left[#1\right]}
\newcommand{\partorder}{\preceq}
\newcommand{\partorderstrict}{\prec}
\newcommand{\npartorder}{\npreceq}
\newcommand{\subgraph}{\preceq}
\newcommand{\subgraphset}[1]{\mathcal{S}(#1)}
\newcommand{\connectedsubgraphset}[1]{\mathcal{C}(#1)}
\newcommand{\permcomb}[3]{{#1}(#2,#3)}
\newcommand{\permcombalt}[3]{{#1}^{#2}_{#3}}
\newcommand{\permcombaltalt}[3]{{\leftsub{#2}{#1}}_{#3}}
\newcommand{\permutation}[2]{\permcomb{P}{#1}{#2}}
\newcommand{\permutationalt}[2]{\permcombalt{P}{#1}{#2}}
\newcommand{\permutationaltalt}[2]{{\permcombaltalt{P}{#1}{#2}}}
\newcommand{\combination}[2]{\permcomb{C}{#1}{#2}}
\newcommand{\combinationalt}[2]{\permcombalt{C}{#1}{#2}}
\newcommand{\combinationaltalt}[2]{{\permcombaltalt{C}{#1}{#2}}}
\newcommand{\choosefuncformula}[3]{\frac{#1 !}{#2 ! \, #3 !}}
\DeclareMathOperator{\matrixring}{M}
\newcommand{\uvec}[1]{\mathbf{#1}}
\newcommand{\zerovec}{\uvec{0}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Activities 6.11 Activities
Activity 6.1 .
(a) Write a technical definition for the word
car .
(b)
Using only your technical definition (that is, ignoring your common sense notions of the word
car ), decide whether a transport truck should be called a car. Then do the same for a train.
Note. Do not go back and modify your definition of
car ; test the objects
transport truck and
train against whatever definition you initially came up with in
Task a .
(c) What is the point of this activity?
Activity 6.2 .
A
square number is an integer which is equal to the square of some integer. An integer is
square free if it is not divisible by any square number other than
\(1 \text{.}\)
(a) Is
\(0 \) a square number? Is it square free?
(b) Does there exist a negative square number?
(c) Is every negative number square free?
(d) Is every prime number square free?
(e) Is every square free number prime?
(f) Does there exist an integer which is both a square number and square free?
Activity 6.3 .
The following statement is a basic (and very useful) fact about real numbers.
Triangle Inequality : For every pair of real numbers
\(x \) and
\(y \text{,}\) \(\abs{x+y} \le \abs{x} + \abs{y} \text{.}\)
Use the above statement to directly prove the following extended version of the inequality,
without resorting to considering cases of positive/negative for any of the variables.
For every triple of real numbers
\(x \text{,}\) \(y \text{,}\) and
\(z \text{,}\) \(\abs{x+y+z} \le \abs{x} + \abs{y} + \abs{z} \text{.}\)
Remark Using the two-number version of the inequality to prove the three-number version is an example of
inductive reasoning , something that we will soon investigate further.
Activity 6.4 .
Suppose you are analyzing the rules for a complicated table-top game, and you have come to the following realization.
Given any trio of distinct wizards where the first is zapping the second, at least one of the following must also occur: the first is zapping the third or the third is zapping the second.
If you were to approach proving this statement using the advice you read on how to handle statements involving disjunction in
Procedure 6.5.1 , the first sentence of your proof would be as follows.
And the last sentence of your proof would be as follows.
Activity 6.5 .
What is the difference between
proving the contrapositive and
proof by contradiction ?
Activity 6.6 .
(a) A positive integer that is greater than
\(1 \) and
not prime is called
composite .
Write a technical definition for the concept of
composite number with a similar level of detail as in the “more complete” definition of
prime number given in
Example 6.1.1 .
Note Don’t just define it as “not prime.” And make sure that the equality
\(7 = 1 \times 7 \) can’t be used to justify the statement “
\(7 \) is composite” by your definition (because prime
\(7 \) is most definitely
not composite).
(b)
Prove by proving the contrapositive: If
\(2^n - 1 \) is prime, then
\(n \) is prime.
Hint .
You may find the following “difference of powers” factorization formula useful:
\begin{equation*}
a^m - b^m = (a-b)(a^{m-1} + a^{m-2}b + a^{m-3}b^2 + \dotsb + a^2b^{m-3} + ab^{m-2} + b^{m-1}) \text{.}
\end{equation*}
Activity 6.7 .
(a) Write down a technical definition of the term
rational number .
(b)
Prove directly: The sum of two rational numbers is a rational number.
(c)
Prove by contradiction: The sum of a rational number and an irrational number is irrational.
(d)
Disprove by counterexample: The sum of two irrational numbers is irrational.
Activity 6.8 .
(a) Prove that a positive number
\(n \) is square free if and only if for every factorization
\(n = ab \text{,}\) the integers
\(a \) and
\(b \) do not share a common factor other than
\(1 \text{.}\)
(b) Prove that a positive number is square free if and only if it is not divisible by the square of a prime number.
Activity 6.9 .
A pair of prime numbers
\(p_1,p_2 \) is called a
twin prime pair if
\(p_2 = p_1 + 2 \text{.}\) A prime number is called an
isolated prime if it is not part of a twin prime pair.
(a) Determine the first (smallest) four twin prime pairs.
(b) Determine the first (smallest) two isolated primes.
(c) Prove that if
\(p, p+2 \) is a twin prime pair with
\(p \ge 5 \text{,}\) then
\(p+1 \) is divisible by
\(6 \text{.}\)
(d) Prove that if
\(p, p+2 \) is a twin prime pair, then
\(p-2,p \) and
\(p+2,p+4 \) cannot be twin prime pairs.
