MAT102 Lecture 06B

• 04RelationsExercises_Students.pdf

• 03LogicContExercises_Students.pdf
  • A set is roofed when there is a real number that is greater than or equal to any element in the set
    • Bounded from above
    • $\mathrm{\exists }r\in \mathbb{R},\mathrm{\forall }x\in A:x\le r$
      • #tk try using $\mathrm{\forall }r\in \mathbb{R}$ and $\mathrm{\exists }r\in A$ and does this imply umbrella'd
      • Being topped is this $\mathrm{\forall }r\in \mathbb{R},\mathrm{\exists }x\in A:x\le r$
      • So for every $r$, there is a number less than $r$.
      • Does this imply umbrella'd
      • Umbrella'd means $\mathrm{\forall }x\in \mathbb{R},\mathrm{\exists }u\in A,x<u$
      • If something is topped, then it can be umbrella'd
      • However if something is umbrella'd it is topped.
    • Example:
      • ${\mathbb{Z}}^{-}$
      • $\{n\in \mathbb{Z}:n<0\}$ is roofed by $0$
    • Non-example:
      • $\{2n:n\in \mathbb{Z}\}$
      • No $r\in \mathbb{R}$ where it's larger than all even numbers
  • A set is umbrella'd if there is no maximal element:
    • Every element of the set has an element in the set which is larger
    • $A\subseteq \mathbb{R}$
    • $\mathrm{\forall }x\in A,\mathrm{\exists }u\in A:x<u$
    • $\mathbb{Z}$ is umbrella'd
      • Not roofed
    • Non-example:
      • $\{1\}$
        • But this is roofed
    • If $(0,1)$ umbrella'd
      • This is umbrella'd
      • You can always reach higher
    • $[0,1]$ is not umbrella'd
      • You can't choose something higher if you choose $1$
• Proposition:
  • If $A,B\subseteq \mathbb{R}$ are roofed, then $A\cup B$ is a roofed set.
  • $\mathrm{\exists }r\in \mathbb{R},\mathrm{\forall }x\in A:x\le r$
  • Let $A_t$ be the roof-point of $A$ and $B_t$ be the roof-point of $B$. Where $A_t,B_t\in \mathbb{R}$
  • Cases:
    • $A_t<B_t$
      • This means that $B_t$'s roof-point is higher, so if we do $A\cup B$, we already know that $A_t<B_t$, so it is still roofed under the point $B_t$
    • $A_t>B_t$
      • This means that $A_t$'s roof-point is higher, so $A\cup B$ means that it's roofed by $A_t$
    • $A_t=B_t$
      • Then this means that it doesn't matter which roof-point we pick, we can say that $A\cup B$ is roofed by $\text{rand}(A_t,B_t)$
  • $A\cup B$ is roofed by $max(A_t,B_t)$
  • If $x\in A\cup B$
  • so $x\in A$ or $x\in B$
  • If $x\in A$
    • Then $x\le A_t$
  • If $x\in B$
    • Then $x\le B_t$
  • So if $x\in A\cup B$ then $x\le max(A_t,B_t)$
• Solution:
  • Let $A$ and $B$ be roofed
  • There is an element $r_A$ such that $x\le r_A,\mathrm{\forall }x\in A$
  • and an element $r_B$ such that $x\le r_B,\mathrm{\forall }x\in B$
  • Counterexample:
    • Let $r=r_A+r_B$ if $x\in A\cup B$ then either $x\in A$ or $x\in B$
    • If $x\in A$ then $x\le r_A\le r_A+r_B$
    • $r_A=1$
    • $r_B=-4$
    • $x\le 1\le -3$
    • Is not true
  • With absolute value:
    • Let $r=\left|r_A\right|+\left|r_B\right|$ if $x\in A\cup B$ then either $x\in A$ or $x\in B$
    • If $x\in A$ then $x\le \left|r_A\right|\le \left|r_A\right|+\left|r_B\right|$
    • If $x\in B$ then $x\le \left|r_B\right|\le \left|r_A\right|+\left|r_B\right|$
    • So $r$ is a roof for $A\cup B$
• Proposition:
  • If $A,B\subseteq \mathbb{R}$ are roofed, then $A\cap B$ is a roofed set. #tk
  • If $x\in A\cap B$ then $x\in A$ and $x\in B$
  • Cases:
    • Disjoint:
      • If they're disjoint, then there is no intersection, so anything is larger
      • $A\cap B=\mathrm{\varnothing }$
    • $x\in A\cap B$
      • $\mathrm{\exists }r\in \mathbb{R},\mathrm{\forall }x\in A:x\le r$
      • $x\le max(A_t,B_t)$
      • Choose the roof point to be $max(A_t,B_t)$
      • Either way, we still have a roofed set
      • This means that $x\in A$ and $x\in B$ so $x\le max(A_t,B_t)$
• 1
  • Suppose $P,Q$ and $R$ are propositions, prove $P⟹(Q\vee R)$
  • We know that $P⟹(Q\vee R)$
  • This means $\mathrm{\neg }P\vee (Q\vee R)$
  • We just need $P$ to be false, or $Q$ or $R$ to be true.
  • $\begin{array}{ccccc}P& Q& R& \mathrm{\neg }P\vee (Q\vee R)& (\mathrm{\neg }P\vee Q)\vee R\\ T& T& T& T& T\\ T& T& F& T& T\\ T& F& T& T& T\\ T& F& F& F& F\\ F& T& T& T& T\\ F& T& F& T& T\\ F& F& T& T& T\\ F& F& F& T& T\end{array}$
• 2
  • if $m,n\in \mathbb{z}$ and $m^3+n^3$ is odd then either $m$ is odd or $n$ is odd. #tk try contrapositive
    • $m=2k+1\vee n=2\ell +1⟸m^3+n^3=2g+1$
    • $m=2k\wedge n=2\ell ⟹m^3+n^3=2g$
    • contrapositive
    • claim: if $m$ and $n$ are even then $m^3+n^3$ is even for $m,n\in \mathbb{z}$
    • proof:
      • $m=2k$
      • $n=2\ell$
      • $m^3+n^3$
      • $8k^3+8{\ell }^3$
      • $4k^3+4{\ell }^3$
      • i can divide by $2$ which means that $m^3+n^3$'s result is in fact even.
      • So this can take the form of $2p$ where $p=4k^3+4{\ell }^3$
  • $m^3+n^3=2g+1$
  • So then either $m=2k+1$ or $n=2l+1$
  • Suppose $m$ is even
  • Then $n$ is odd
  • $m=2k$
  • $m^3=8k^3$
  • $m^3$ is even
  • So then $n^3=\underset{\text{odd}}{\underbrace{(m^3+n^3)}}-\underset{\text{even}}{\underbrace{m^3}}$
  • This results in something odd, so we've shown that $n^3$ is odd.

  ---

  • $P=m^3+n^3$ is odd
  • $Q=m$ is odd
  • $R=n$ is odd
  • If $m$ is odd, then we're done
  • Suppose $m$ is even, so then show that $n$ is odd
  • Know:
    • $m=2k$
    • even + even = even
      • Because $2k$
    • odd + odd = even
      • Because $2k$
    • even + odd = odd
      • Because $2k+1$ is odd and $2k$ is even
  • $m=2k$
  • So $m^3=8k^3$ which is even still
  • So $m^3+n^3$ is $8k^3+n^3$
    • This must be odd per prop $P$
    • So the only way to get an odd number out of this is if $n$ was odd. Because only with even + odd can we get an odd number out.
    • So $n$ is odd.
• 2: solution
  • If $\underset{P}{\underbrace{m^3+n^3}}$ is odd then $\underset{Q}{\underbrace{m\text{ is odd}}}$ or $\underset{R}{\underbrace{n\text{ is odd}}}$
  • Lemma:
    • If $n^3$ is odd, then $n$ is odd
    • Use the contrapositive
    • If $n$ is even then $n^3$ is even
      • $n=2k$ for some $k\in \mathbb{Z}$
      • $(2k{)}^3=8k^3$
      • $2(4k^3)$ is even
  • If $m^3+n^3$ is odd and $m$ is even then $n^3$ must be odd
  • Proceed by contradiction, straightforward, etc.
  • By lemma, $n$ is odd if $n^3$ is odd.