General

Tips

• Always be suspicious of all statements. Be super critical. Don’t be naïve.
• Don’t agree with a statement without knowing why it is true. Don’t disagree with a statement without knowing why it is false.
• It is easier to disprove a statement than to prove it. So, try to disprove any statement given to you first before you start trying to prove it. Only after you have tried hard and you can’t disprove it, then consider proving it. In the middle, you might gain some insight on how to disprove it while trying to prove it.
• Be extremely precise in your statements and words.
• Internalise all definitions. No need to memorize but you should be able to apply any defintion to prove/disprove logical statements and argue using new definitions.
• CS1231S will be a lot easier if you apply metacognition. Think about how you think and learn. Use that to understand how you can understand definitions better.

Admin

• Don’t follow the theorem, proposition and lemma numbers blindly. They may differ from year to year based on the Prof’s slides.
• If you spot any typo or think I’ve made a mistake in these notes, please email me at [email protected]

1. Speaking Mathematically

<aside> 💡 Triangle Inequality (Theorem 4.4.6): $|x + y| \leq |x| + |y|$

</aside>

<aside> 💡 Lemma 4.4.4: For any $r \in \mathbb{R}, -|r| \leq r \leq |r|$

</aside>

• Basic properties of integers: closure, commutativity, associativity, distributivity, trichotomy (exactly one of the following is true for 2 integers $x,y, \ x < y \text{ or } x = y \text{ or } x > y$
• Even: An integer $n$ is even $\iff$ $\exist k \in \mathbb{Z},\ n = 2k$
• Odd: An integer $n$ is odd $\iff$$\exist k \in \mathbb{Z}, \ n = 2k+1$
• You may assume that every integer is even or odd but not both
• Divisibility: If $n$ and $d$ are integers and $d \neq 0$, then $d \mid n \iff \exist k \in \mathbb{Z} \text{ s.t. } n= dk$