21:I[90314,["https://schon.au/_next/static/immutable/chunks/1x5cg2pe3x4d1.js","https://schon.au/_next/static/immutable/chunks/2bhq7tnhs7omt.js","https://schon.au/_next/static/immutable/chunks/32ncs441skyll.js","https://schon.au/_next/static/immutable/chunks/1t10en_fq84vd.js","https://schon.au/_next/static/immutable/chunks/2099jd3bkl7bl.js","https://schon.au/_next/static/immutable/chunks/3e1nstitxnajz.js"],"default"] 22:I[72436,["https://schon.au/_next/static/immutable/chunks/1x5cg2pe3x4d1.js","https://schon.au/_next/static/immutable/chunks/2bhq7tnhs7omt.js","https://schon.au/_next/static/immutable/chunks/32ncs441skyll.js","https://schon.au/_next/static/immutable/chunks/1t10en_fq84vd.js","https://schon.au/_next/static/immutable/chunks/2099jd3bkl7bl.js","https://schon.au/_next/static/immutable/chunks/3e1nstitxnajz.js"],"Separator"] 23:I[86022,["https://schon.au/_next/static/immutable/chunks/1x5cg2pe3x4d1.js","https://schon.au/_next/static/immutable/chunks/2bhq7tnhs7omt.js","https://schon.au/_next/static/immutable/chunks/32ncs441skyll.js","https://schon.au/_next/static/immutable/chunks/1t10en_fq84vd.js","https://schon.au/_next/static/immutable/chunks/2099jd3bkl7bl.js","https://schon.au/_next/static/immutable/chunks/3e1nstitxnajz.js"],"default"] 24:T371f,### Contraposition The contrapositive of a conditional statement "If $P$ is true, then $Q$ is true" is the conditional statement, "If not $Q$, then not $P$". The contrapositive of $P\to Q$ is $\sim Q\to P$. > [!NOTE] Fact > The contrapositive $C$ of a conditional statement $S$ is logically equivalent to $S$ in the sense that $C$ is true if and only if $S$ is true. **Examples of Contrapositive Statements** *Write the contrapositive of each statement.* - If $A\subseteq B$, is the conditional statement, "If $a\in A$, then $a\in B$". Contrapositive is, "If $a\not\in B$ then, $a\notin A$". Written symbolically as $B^c\subseteq A^c$. Injectivity of $f:X\to Y$ is equivalent to the quantified contrapositive conditional statements: - For any $x_1,x_2\in x$, if $f(x_1)=f(x_2)$ then $x_1=x_2$. Contrapositive is, "For any $x_1,x_2\in x$, if $x_1\neq x_2$ then $f(x_1)\neq f(x_2)$". - "If the square matrix $A$ is invertible then $\det A\neq 0$". Contrapositive is, "If $\text{det }A=0$, then $A$ is not invertible". > [!INFO] Theorem: A characterisation of finite sets > A set $X$ is finite iff every injective function $f:X\to X$ is surjective. #### Mersenne Primes Given any natural number $n>1$, prove that if $2^n-1$ is prime, then $n$ is prime. Such $2^n-1$ are **Mersenne primes.** **Proof.** Hence there are integers $a,b\in\mathbb{Z}$ such that $n=ab$ and $a,b>1$. $2^n-1=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\cdots+2^a+1)$ Note $2^a-1,\ 2^{a(b-1)}+\cdots+1\in\mathbb{Z}$ and both are $>1$ since $a>1$. Hence $2^n-1$ is composite and the contrapositive is proved. *** ### Contradiction **Proof by contradiction as a contrapositive argument.** Suppose you prove statement $P$ by assuming $\sim P$ and logically deducing statement $F$ which is known to be false. This means you have proved $\sim P\to F$. Hence you've proved the contrapositive $\sim F\to P$. But $\sim F$ is true so you have also proved $P$. > [!EXAMPLE] Simple Irrationality Questions > **Proof.** > Prove that $\log_57$ is irrational. Suppose by contradiction that $\log_57$ is rational. > So there exist integers $a,b$ such that $\frac{a}{b}=\log_57$. Hence $5^{\frac{a}{b}}=7$. Take the $b$-th power of both sides to see $5^a=7^b$. > This is a contradiction since $7\mid 7^b$ but $7\nmid 5^a$. Hence $\log_57$ is irrational. #### Applications of Modulo Arithmetic to Diophantine Equations > [!EXAMPLE] > Prove that there are no integer solutions to $7x^2=6y^3-1$. > *** > **Answer:** Suppose by way of contradiction that $x,y\in\mathbb{Z}$ satisfy the Diophantine equation above. Hence, > $$7x^2\equiv 6y^3-1\ \text{(mod 3).}$$ > We show this must be false. Consider 3 cases: > We must have $x\equiv 0$ or $\pm 1\ \text{mod }3$. > We then have respectively $x\equiv 0^2=0$ or $(\pm)^2=1\ \text{mod 3}$. > > Hence, $7x^2\equiv 1x^2=x^2$ since $7\equiv 1\ \text{mod 3}$. > However, $6y^3-1\equiv-1\equiv2\ \text{mod 3}$. We thus obtain a contradiction. #### The Infinitude of Primes > [!INFO] Theorem: (Euclid) There are infinitely many primes. > **Proof.** > Suppose by way of contradiction that there are finitely many primes, say $p_1,p_2,p_3,\dots,p_k$ for some natural number $k$. > > Consider the integer $n=p_1p_2p_3\dots p_k+1$. > It must have a prime factor which must be of the form $p_i$ for some $i\in\{1,\dots,k\}$. However, $p_1p_2\dots p_k+1\equiv 1\ \text{mod }p_i$ so is not divisible by $p_i$, a contradiction. > > Thus there are infinitely many primes. *** ### Mathematical Induction #### Proof by Induction **Setup:** Let $P(n)$ be a predicate where the variable $n$ ranges over $\mathbb{N}$. **Definition:** The truth set of $P(n)$ is $X=\{n\in\mathbb{N}\ \colon\ P(n)\text{ is true}\}$. **Base case:** That is, you can prove $P(0)$ is true, or in other words, $0\in X$. **Inductive Step:** That is, that for all $k\in\mathbb{N},\ P(k)\to P(k+1)$ is true, or in other words if $k\in X\text{ then }k+1\in X$. Here, $P(k)$ is called the **inductive hypothesis**. Peano's axiom of induction means $X=\mathbb{N}$. That is, $P(n)$ is true for all $n\in\mathbb{N}$. We say in this case that we proved $P(n)$ for all $n\in\mathbb{N}$ by induction on $n$. > [!INFO] Theorem: Sums of consecutive cubes > For all $n\in\mathbb{N}$, we have $0^3+1^3+2^3+\cdots+n^3=\frac{1}{4}n^2(n+1)^2$. > > **Proof.** > Base case: Note $P(0)$ holds since $0^3=0=\frac{1}{4}0^2(0+1)^2$. > Inductive step: Assume $P(k)$ holds for some $k\in\mathbb{N}$. > > We wish to prove $P(k+1)$ follows. > $0^3+1^3+\cdots+k^3+(k+1)^3=\frac{1}{4}k^2(k+1)^2+(k+1)^3$ by the inductive hypothesis. > $$\begin{align*} > &=\frac{1}{4}(k+1)^2\left[k^2+4(k+1)\right]\\ > &=\frac{1}{4}(k+1)^2\left(k^2+4k+4\right)\\ > &=\frac{1}{4}(k+1)^2\left(k+2\right)^2=\frac{1}{4}n^2(n+1^2)\text{ when }n=k+1. > \end{align*}$$ > Hence $P(k+1)$ also holds. Thus by mathematical induction $P(n)$ holds for all $n\in\mathbb{N}$. *** #### Strong Induction > [!INFO] Theorem: Strong induction >Suppose $P(n)$ is a predicate or $n\geq n_0, n\in\mathbb{Z}$. Suppose: Base case: $P(n_0),\ P(n_0+1),\dots,P(n_1)$ is true for some $n_1\in\mathbb{Z}$ Inductive step: Whenever $P(n_0),\dots, P(n)$ are true, we have $P(n+1)$ is true. **Proof.** Then $P(n)$ is true for all $n\in\mathbb{Z}$ with $n\geq n_0$. Let $Q(k)$ be the statement that $P(n_0), P(n_0+1),\dots, P(n_0+k)$ is true. Base case: $Q(0)$ is true since $P(n_0)$ is true by strong base case. Inductive step: Suppose, $Q(k)$ is true. If $kBase case: $P(0)$ is true, because $2^0(2\times0+1)=1=a_0$ as required. Inductive step: Suppose $P(k),\ P(k-1)$ are true (inductive hypothesis). We now prove $P(k+1)$ follows. $$\begin{align*} a_{k+1}&=4(a_k-a_{k-1})=2^2\left(2^k(2k+1)-2^{k-1}(2k-1)\right)\\ &=2^{k+1}\left[2(2k+1)\dots(2k-1)\right]\\ &=2^{k+1}\left[2k+3\right]=2^{k+1}\left(2(k+1)+1\right) \end{align*}$$ Thus $P(k+1)$ is true and hence $a_n=2^n(2n+1)$ by induction on $n$. *** #### Law of Well-Ordering > [!INFO] Theorem: Law of Well-Ordering > Suppose $S\subseteq\mathbb{N}$ is non-empty. Then $S$ has a least element. **Proof.** We prove the contrapositive and assume $S\subseteq\mathbb{N}$ has no least element. Let $X=S^c=\mathbb{N}-S$. We will show by strong induction that $X=\mathbb{N}$ so $S\neq\varnothing$. Base case: Note $0\in X$ since otherwise $0\in S$ and is the least element. Strong inductive step: Suppose $0,1,\dots,k\in X$ so are not in $S$. Then $k+1\in X$ since otherwise $k+1$ is the least element of $S$. Thus the strong inductive step is proven to show $X=\mathbb{N}$. Hence $S=X^0=\varnothing$. This proves the contrapositive of the theorem. *** #### Fundamental Theorem of Arithmetic > [!INFO] Theorem: Fundamental theorem of Arithmetic > Every positive integer can be written uniquely as a product of $n$ prime numbers for some $n\in\mathbb{N}$. (Uniqueness is up to permuting factors). **Proof.** We first prove the existence of prime factorisations. We argue by contradiction and assume the set $S$ of positive integers which are not products of primes is non-empty.. The law of well-ordering ensures $S$ has a minimal element say $m$. Note $m$ is not 1 or prime or else its a product of primes. Hence its composite so $m=ab$ for some $a,b\in\mathbb{N}$ with $a,b\lt m$. By minimality of $m$, $a,b\notin S$ so are product of primes say $a=p_1,p_2,\dots,p_n,\ b=q_1,q_2,\dots,q_l$. But then $m=p_1,p_2,\dots,p_n$ $q_1,\dots,q_l$ is a product of primes contradicting $m\in S$. Thus, existence is proved. **Now we prove the uniqueness statement**. This means that if $p_1,\dots,p_a,q_1,\dots,q_b$ are primes and $$p_1p_2\dots p_a=q_1q_2\dots q_b\qquad(\star)$$ then $a=b$ and you can re-index the $q_i$'s so that $p_i=q_i$ for all $i$. We prove this by induction on $a$. Note $p_a\mid q_1q_2\dots q_b$ so by lemma in Lecture 3.4, be the fact $p_a$ is prime we see $p_a\mid q_i$ for some $i$. Swap $q_i$ & $q_b$ to see $p_a\mid q_b$ so $p_a=q_b$ since $q_b$ is prime. Thus dividing $(\star)$ by $p_a=q_b$ we see, $$p_1p_2\dots p_{a-1}=q_1q_2\dots q_{b-1}.$$ By inductive hypothesis, $a-1=b-1$ so $a=b$ and we can also assume by re-indexing that $p_1=q_1,\dots,p_{a-1}=q_{a-1}$. Thus by induction, uniqueness is proven. *** ### Symbolic Logic and Truth Tables **Abstracting logical principles with statement variables** Codify all our logical deductions used in proofs symbolically, in a way which easily distinguishes a valid logical argument from an invalid one. **Logical connectives** Let $p,q$ be statements. One logical connective is ~ (not). Two more are: > [!NOTE] Conjunction > Logical "and" > Write $p \land q$ for the statement, "Both $p$ and $q$ are true" which is true iff both $p$ is true and $q$ is true. > [!NOTE] Disjunction > Logical, **inclusive** "or" > Write $p\lor q$ for the statement, "Either $p$ or $q$ is true" which is true iff both at least one of $p$ or $q$ is true. **Examples** - "It is not P, but rather Q" $\to\ \sim P\land Q$ - "Neither P nor Q" $\to\ \sim (P\lor Q)$ *** #### Compound Statements and Propositional Forms **Compound statement:** A compound statement or compound proposition is a statement consisting of component statements joined by logical connectives. **Propositional form:** A propositional form is an expression consisting of statement variables and logical connectives which becomes a statement whenever the variables are replaced by actual statements. **E.g.** $(P\lor Q)\land R\land(\sim T)$. > [!IMPORTANT] Order of Operations > Given a propositional form, evaluate $\sim$ before $\land,\lor$. Use brackets when necessary. **Example**. (associativity) Technically we should distinguish $(P\land Q)\land R$ from $P\land(Q\land R)$. But both are true precisely when all $P,Q,R$ are true, so denote both by $P\land Q\land R$. Similarly for $P\lor Q\lor R$. *** #### Truth Tables Propositional forms can be viewed as functions with outputs values true or false and inputs also true or false. | p | q | ~p | $p\land q$ | $p\lor q$ | $\oplus$ | | --- | --- | --- | ---------- | --------- | -------- | | T | T | F | T | T | F | | T | F | F | F | T | T | | F | T | T | F | T | T | | F | F | T | F | F | F | > [!IMPORTANT] Last column represents the exclusive or, $p$ or $q$, but **not both**. **Example:** Construct a truth table for the compound proposition $(p\lor q)\land(q\lor r)$. | p | q | r | $p\lor q$ | $q\lor r$ | $(p\lor q)\land(q\lor r)$ | | --- | --- | --- | --------- | --------- | ------------------------- | | T | T | T | T | T | T | | T | T | F | T | T | T | | T | F | T | T | T | T | | T | F | F | T | F | F | | F | T | T | T | T | T | | F | T | F | T | T | T | | F | F | T | F | T | F | | F | F | F | F | F | F | *** #### Tautologies, Contradictions and Contingencies A propositional form is called a: - ==Tautology== if it is always true regardless of the truth values of the statement variables - ==Contradiction== if it is always false for any choice of statements in for the statement variables. - ==Contingency== otherwise. **Example 1:** $p\land(\sim p)$ is a contradiction. $p\lor(\sim p)$ is a tautology. Notation: - A tautology is often denoted T. - A contradiction is often denoted F. **Example 2: Proving tautologies using truth tables** Show that the propositional form $q\ \lor\sim(p\land q)$ is a tautology. | p | q | $p\land q$ | $\sim(p\land q)$ | $q\ \lor\sim(p\land q)$ | | --- | --- | ---------- | ---------------- | ----------------------- | | T | T | T | F | T | | T | F | F | T | T | | F | T | F | T | T | | F | F | F | T | T | $\therefore$ Since the final column contains only **T**s, we can conclude that the compound proposition is a **tautology**. **Example 3: Establishing contradictions via truth tables** Show that the propositional form $q\ \land\sim(p\lor q)$ is a contradiction. | p | q | $p\lor q$ | $\sim(p\land q)$ | $q\ \lor\sim(p\land q)$ | | --- | --- | --------- | ---------------- | ----------------------- | | T | T | T | F | F | | T | F | T | F | F | | F | T | T | F | F | | F | F | F | T | F | $\therefore$ Since the final column contains only **F**s, we can conclude that the compound proposition is a **contradiction**. *** #### Logical (bi)conditional Given the statements, $p,q$ we have the new conditional statement $p\to q$. Their truth tables are: | p | q | $p\to q$ | $p\leftrightarrow q$ | | --- | --- | -------- | -------------------- | | T | T | T | T | | T | F | F | F | | F | T | T | F | | F | F | T | T | Thus, we contain two new logical connectives $p\to q,\ p\leftrightarrow q$. 19:["$","div",null,{"className":"min-h-screen h-full w-full px-8 pb-8 pt-16 space-y-12","children":[["$","div",null,{"className":"flex justify-between flex-col items-start space-y-6 md:items-center md:flex-row","children":[["$","div",null,{"className":"flex flex-col space-y-2","children":[["$","div",null,{"className":"flex items-center gap-2","children":[["$","$L16",null,{"ref":"$undefined","iconNode":[["path",{"d":"M6 22a2 2 0 0 1-2-2V4a2 2 0 0 1 2-2h8a2.4 2.4 0 0 1 1.704.706l3.588 3.588A2.4 2.4 0 0 1 20 8v12a2 2 0 0 1-2 2z","key":"1oefj6"}],["path",{"d":"M14 2v5a1 1 0 0 0 1 1h5","key":"wfsgrz"}],["path",{"d":"M10 9H8","key":"b1mrlr"}],["path",{"d":"M16 13H8","key":"t4e002"}],["path",{"d":"M16 17H8","key":"z1uh3a"}]],"className":"lucide-file-text h-8 w-8"}],["$","h1",null,{"className":"font-semibold text-4xl uppercase","children":"MATH1081"}]]}],["$","p",null,{"className":"text-muted-foreground flex flex-col","children":[["$","span",null,{"className":"capitalize","children":["UNSW 2024 - Trimester 3"," -"," ","week 5"]}],["$","span",null,{"className":"text-sm","children":"Images have been removed to avoid copyright."}]]}]]}],["$","div",null,{"className":"flex items-center gap-2","children":[["$","$L4",null,{"href":"/notes","className":"inline-flex items-center justify-center gap-2 whitespace-nowrap rounded-md text-sm font-medium transition-all disabled:pointer-events-none disabled:opacity-50 [&_svg]:pointer-events-none [&_svg:not([class*='size-'])]:size-4 shrink-0 [&_svg]:shrink-0 outline-none focus-visible:border-ring focus-visible:ring-ring/50 focus-visible:ring-[3px] aria-invalid:ring-destructive/20 dark:aria-invalid:ring-destructive/40 aria-invalid:border-destructive bg-secondary text-secondary-foreground shadow-xs hover:bg-secondary/80 h-9 px-4 py-2 has-[>svg]:px-3","children":[["$","$L16",null,{"ref":"$undefined","iconNode":[["path",{"d":"m12 19-7-7 7-7","key":"1l729n"}],["path",{"d":"M19 12H5","key":"x3x0zl"}]],"className":"lucide-arrow-left h-4 w-4"}]," Notes"]}],["$","$L21",null,{"categories":[],"courseId":"MATH1081","weekId":"week-5","resources":[{"title":"Week 1","file":"week-1"},{"title":"Week 2","file":"week-2"},{"title":"Week 3","file":"week-3"},{"title":"Week 4","file":"week-4"},{"title":"Week 5","file":"week-5"},{"title":"Week 7","file":"week-7"},{"title":"Week 9","file":"week-9"}]}]]}]]}],["$","div",null,{"className":"overflow-hidden","children":[["$","$L22",null,{"orientation":"horizontal"}],["$","$L23",null,{"markdown":"$24"}]]}]]}]