Discrete Mathematics

# cs2102: Discrete Math

Problem Set 2 Comments (Wed, 13 Sep 2017)

The Problem Set 2 solutions and comments are now posted in collab: PDF

Class 7: Sets (Tue, 12 Sep 2017)

### Schedule

Problem Set 3 is due Friday at 6:29pm.

# Notes and Questions

What is a data type? What are the differences between a mathematical data type and a data type in your favorite programming language?

#

A set is an unordered colection of objects. A set is defined by its membership operation: $x \in S$ is true if $x$ is in the set $S$. When $x$ is not in $S$ we write it as $x \notin S$. A set has only one copy of each element. Namely, there is no repetition in elements of a set. Also, a set $A$ could be a member o another set $B$, denoted by $A \in B$. Note that members of $A$ are not necessarily members of $B$ unless they are explicitly put in $B$ directly.

## Set Operations

Subset: $\subseteq$ (note that this does not mean strict subset) $$A \subseteq B \iff \forall x \in A. \fillin \in \fillin.$$

Set Equality: $=$ $$A = B \iff A \fillin B \wedge B \fillin A.$$

Set Union: $\cup$ $$\forall x. x \in A \cup B \iff x \in A \fillin x \in B.$$

Set Intersection: $\cap$ $$\forall x. x \in A \cap B \iff x \in A \fillin x \in B.$$

Set Difference: $-$ $$\forall x. x \in A - B \iff x \in A \wedge x \notin B.$$

Set Complement: $\overline{S}$ $$\forall x \in D. x \in \overline{A} \iff x \notin A.$$

($D$ is the domain of discourse”, the universe of all objects under discussion.)

$$S_{R} = \textrm{ the set of all sets that are not members of themselves}$$

Is $S{R} \in S{R}$?

What is the source of this paradox? Note that in this question, we are implicitly assuming that $S{R}$ is a set, but we have never “constructed” this set properly to use it. Namely, here we are implicitly assuming that there is already a “set of all sets” $S{all}$ from which we remove those sets like $T$ for which $T \in T$. By removing all such $T$ from $S_{all}$ we get the set $S_R$.

### Using Quantifiers More Carefully

Note that in some of the propositions that we used to define the set operations (such as union, intersection, etc.) above, we wrote quantified $x$ without saying which set it is from. For example $\forall x. [\dots]$. It is much preferred to always say what $x$ is belonging to when we quantify over $x$. The reason is to avoid traps like that of Russell’s paradox! This should not worry us in this class, as we will always work with well-defined universes that include all the elements of the sets that we work with. Therefore, we can always assume implicitly that $x \in U$ (for a well defined set universe $U$) even if not explicitly mentioned.

#

### Set Practice

Here are some practice problems involving sets. We won’t go through these in class, but you should ask questions about any are unclear. (At least a few of these will be on Exam 1.)

1. Define $A \subset B$ (strict subset).

#

1. Prove $A \cup B \equiv B \cup A$.

#

1. Prove $A - B = \emptyset \iff A \subseteq B$.

#

1. Prove $A = B \iff (\forall a \in A \ldotp a \in B) \wedge (\forall b \in B \ldotp b \in A).$

Problem Set 3 (Fri, 8 Sep 2017)

Problem Set 3 [PDF] is now posted and is due Friday, 15 September at 6:29:00pm.

Class 6: Quantifiers and More (Thu, 7 Sep 2017)

### Schedule

Problem Set 2 is due Friday at 6:29pm.

You should finish reading MCS Chapter 3 by Tuesday (12 September).

If you believe real computing systems have the property that the values you read from memory will match what you wrote there, see:

Sudhakar Govindavajhala and Andrew W. Appel. Using Memory Errors to Attack a Virtual Machine, IEEE Symposium on Security and Privacy 2003.

Bianca Schroeder, Eduardo Pinheiro, Wolf-Dietrich Weber. DRAM Errors in the Wild: A Large-Scale Field Study. SIGMETRICS 2009.

Kaveh Razavi, Ben Gras, Erik Bosman, Bart Preneel, Cristiano Giuffrida and Herbert Bos. Flip Feng Shui: Hammering a Needle in the Software Stack. USENIX Security 2016.

Yuan Xiao, Xiaokuan Zhang, Yinqian Zhang, and Radu Teodorescu. One Bit Flips, One Cloud Flops: Cross-VM Row Hammer Attacks and Privilege Escalation, USENIX Security 2016.

SAT Competition 2017

Millennium Problems on Clay institute’s website. Whether or not we can
solve the satisfiability of a given CNF or 3CNF formula in polynomial time, is the P vs. NP question in this list.

# Programs and Proofs

What does it mean to test a computing system? What does it mean for a computing system to always behave correctly?

Can a mathematical proof guarantee a real computing system will behave correctly?

# Minima

The minimum of a set with respect to some comparator operator is the element which is “less than” (according to that comparator) every other element: $m \in S$ is the minimum of $S$ if and only if $\forall x \in S - { m } . m \prec x$.

$$\forall S \in \textrm{pow}(\mathbb{N}) - { \varnothing } \ldotp \exists m \in S\ldotp \forall x \in S - {m}\ldotp m < x$$

# Formulas, Propositions, and Inference Rules

$P \implies Q$ is a formula.
$\forall P \in { T, F } . \forall Q \in { T, F } . P \implies Q$ is a proposition.
$\infer{Q}{P}$ is an inference rule.

A formula is satisfiable if there is some way to make it true.

$P \implies Q$ is satisfiable:

$\exists P \in { T, F } . \exists Q \in {T, F } . P \implies Q$

We can show a formula is satisfiable by giving one choice for the variable assignments that makes it true. For example, $P = T$, $Q = T$.

A formula is valid if there is no way to make it false.

$P \implies Q$ is not valid:

$\forall P \in { T, F } . \forall Q \in {T, F } . P \implies Q$

This proposition is false, we can chose $P = T$, $Q = F$.

An inference rule is sound if it never leads to a false conclusion. An inference rule $\infer{Q}{P}$ is sound if and only if the formula $P \implies Q$ is valid. So, this way, we can find out whether an inference rule is sound or not, by checking out whether the corresponding formula is valid or not.

# Negating Quantifiers

What is the negation of $\forall x \in S . P(x)$?

What is the negation of $\exists x \in S . P(x)$?

# Satisfiability

Definition. A formula is in SAT if it is in CNF form and it is satisfiable.

Definition. A formula is in 3SAT if it is in 3CNF form and it is satisfiable.

$$(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee \overline{x_2} \vee x_3) \wedge (\overline{x_1} \vee x_2 \vee \overline{x_3})$$

\begin{center} \tiny \begin{math} (x{48} \vee x{4} \vee \overline{x{9}}) \wedge (\overline{x{44}} \vee x{50} \vee \overline{x{37}}) \wedge (\overline{x{8}} \vee \overline{x{1}} \vee x{28}) \wedge (x{21} \vee x{27} \vee \overline{x{32}}) \wedge (x{17} \vee x{29} \vee \overline{x{30}}) \wedge (x{30} \vee x{24} \vee x{37}) \wedge (\overline{x{22}} \vee \overline{x{27}} \vee \overline{x{44}}) \wedge (x{8} \vee \overline{x{25}} \vee \overline{x{24}}) \wedge (\overline{x{44}} \vee x{50} \vee x{14}) \wedge (x{45} \vee x{15} \vee x{37}) \wedge (\overline{x{16}} \vee x{14} \vee \overline{x{36}}) \wedge (\overline{x{33}} \vee x{5} \vee x{26}) \wedge (x{18} \vee \overline{x{7}} \vee \overline{x{24}}) \wedge (x{31} \vee x{38} \vee x{28}) \wedge (x{31} \vee \overline{x{33}} \vee \overline{x{8}}) \wedge (x{49} \vee x{7} \vee \overline{x{6}}) \wedge (x{34} \vee \overline{x{8}} \vee x{46}) \wedge (x{4} \vee \overline{x{5}} \vee \overline{x{35}}) \wedge (x{43} \vee x{27} \vee x{39}) \wedge (\overline{x{46}} \vee \overline{x{40}} \vee \overline{x{27}}) \wedge (\overline{x{25}} \vee x{14} \vee \overline{x{49}}) \wedge (x{38} \vee x{5} \vee x{15}) \wedge (x{9} \vee x{14} \vee \overline{x{19}}) \wedge (x{45} \vee \overline{x{42}} \vee \overline{x{39}}) \wedge (x{34} \vee \overline{x{22}} \vee \overline{x{28}}) \wedge (\overline{x{20}} \vee x{15} \vee \overline{x{8}}) \wedge (\overline{x{44}} \vee \overline{x{10}} \vee \overline{x{9}}) \wedge (x{22} \vee \overline{x{31}} \vee x{14}) \wedge (\overline{x{9}} \vee \overline{x{42}} \vee \overline{x{15}}) \wedge (\overline{x{40}} \vee x{12} \vee \overline{x{32}}) \wedge (\overline{x{20}} \vee \overline{x{6}} \vee \overline{x{15}}) \wedge (\overline{x{37}} \vee x{39} \vee \overline{x{23}}) \wedge (\overline{x{3}} \vee \overline{x{40}} \vee \overline{x{32}}) \wedge (\overline{x{4}} \vee \overline{x{25}} \vee x{7}) \wedge (\overline{x{20}} \vee \overline{x{36}} \vee \overline{x{37}}) \wedge (\overline{x{40}} \vee \overline{x{35}} \vee x{39}) \wedge (\overline{x{43}} \vee \overline{x{40}} \vee \overline{x{7}}) \wedge (x{34} \vee x{44} \vee x{26}) \wedge (x{13} \vee x{27} \vee x{28}) \wedge (x{12} \vee \overline{x{36}} \vee x{7}) \wedge (\overline{x{16}} \vee x{9} \vee \overline{x{24}}) \wedge (\overline{x{48}} \vee x{14} \vee x{28}) \wedge (x{16} \vee x{4} \vee x{40}) \wedge (\overline{x{25}} \vee x{15} \vee x{37}) \wedge (x{47} \vee \overline{x{26}} \vee \overline{x{23}}) \wedge (x{4} \vee \overline{x{13}} \vee x{36}) \wedge (x{48} \vee \overline{x{13}} \vee \overline{x{37}}) \wedge (x{4} \vee x{35} \vee \overline{x{27}}) \wedge (\overline{x{22}} \vee x{47} \vee x{26}) \wedge (\overline{x{22}} \vee \overline{x{46}} \vee x{27}) \wedge (\overline{x{20}} \vee x{49} \vee x{11}) \wedge (x{42} \vee \overline{x{10}} \vee x{28}) \wedge (\overline{x{45}} \vee x{28} \vee \overline{x{37}}) \wedge (x{14} \vee \overline{x{32}} \vee \overline{x{23}}) \wedge (x{22} \vee x{14} \vee x{23}) \wedge (\overline{x{17}} \vee \overline{x{46}} \vee \overline{x{7}}) \wedge (\overline{x{31}} \vee x{46} \vee \overline{x{50}}) \wedge (x{34} \vee \overline{x{41}} \vee x{43}) \wedge (x{17} \vee \overline{x{9}} \vee x{15}) \wedge (x{46} \vee x{14} \vee \overline{x{12}}) \wedge (\overline{x{20}} \vee x{12} \vee x{14}) \wedge (x{41} \vee x{42} \vee \overline{x{15}}) \wedge (x{48} \vee x{46} \vee \overline{x{36}}) \wedge (\overline{x{22}} \vee \overline{x{4}} \vee \overline{x{49}}) \wedge (x{22} \vee x{12} \vee \overline{x{42}}) \wedge (x{13} \vee \overline{x{38}} \vee x{39}) \wedge (x{48} \vee \overline{x{16}} \vee \overline{x{27}}) \wedge (x{17} \vee \overline{x{18}} \vee \overline{x{26}}) \wedge (x{48} \vee \overline{x{40}} \vee \overline{x{35}}) \wedge (\overline{x{43}} \vee \overline{x{40}} \vee \overline{x{49}}) \wedge (x{29} \vee x{11} \vee \overline{x{32}}) \wedge (x{33} \vee \overline{x{17}} \vee x{39}) \wedge (\overline{x{25}} \vee \overline{x{9}} \vee \overline{x{6}}) \wedge (x{40} \vee \overline{x{50}} \vee x{19}) \wedge (x{8} \vee x{10} \vee \overline{x{27}}) \wedge (x{5} \vee x{9} \vee \overline{x{26}}) \wedge (x{45} \vee \overline{x{38}} \vee \overline{x{27}}) \wedge (\overline{x{4}} \vee \overline{x{40}} \vee \overline{x{42}}) \wedge (x{21} \vee x{50} \vee x{12}) \wedge (\overline{x{8}} \vee \overline{x{14}} \vee \overline{x{42}}) \wedge (\overline{x{17}} \vee x{47} \vee \overline{x{27}}) \wedge (x{49} \vee \overline{x{12}} \vee \overline{x{6}}) \wedge (x{27} \vee x{49} \vee \overline{x{32}}) \wedge (\overline{x{29}} \vee \overline{x{12}} \vee \overline{x{26}}) \wedge (x{48} \vee \overline{x{2}} \vee x{6}) \wedge (x{16} \vee x{36} \vee x{49}) \wedge (x{33} \vee \overline{x{12}} \vee \overline{x{26}}) \wedge (\overline{x{33}} \vee x{29} \vee x{49}) \wedge (\overline{x{48}} \vee x{2} \vee x{19}) \wedge (x{25} \vee x{36} \vee x{49}) \wedge (x{21} \vee x{40} \vee \overline{x{14}}) \wedge (\overline{x{34}} \vee \overline{x{44}} \vee \overline{x{6}}) \wedge (x{48} \vee \overline{x{50}} \vee \overline{x{1}}) \wedge (x{5} \vee \overline{x{12}} \vee x{7}) \wedge (x{21} \vee \overline{x{35}} \vee \overline{x{27}}) \wedge (\overline{x{22}} \vee \overline{x{16}} \vee \overline{x{14}}) \wedge (\overline{x{13}} \vee \overline{x{35}} \vee \overline{x{12}}) \wedge (\overline{x{4}} \vee \overline{x{35}} \vee \overline{x{42}}) \wedge (\overline{x{50}} \vee \overline{x{40}} \vee x{7}) \wedge (x{25} \vee x{47} \vee \overline{x{12}}) \end{math} \end{center}

## Converting Truth Tables to DNF

\begin{tabular}{cc|cc} $P$ & $Q$ & $P \implies Q$ & $P \oplus Q$ \ \hline \T & \T & \T & \F
\T & \F & \F & \T
\F & \T & \T & \T
\F & \F & \T & \F
\end{tabular}

The output of the operator is \T\ if and only if the inputs do match one row where the output is \T. So, to get a DNF we can go over all the rows where hte output is \T, and for each write a clause that means we are in that row. Then we OR all such (conjunctive) clauses. For example, for $P \oplus Q$ we get

$$(P \wedge \neg Q) \vee (\neg P \wedge Q)$$

## Converting Truth Tables to CNF

\begin{tabular}{cc|cc} $P$ & $Q$ & $P \implies Q$ & $P \oplus Q$ \ \hline \T & \T & \T & \F
\T & \F & \F & \T
\F & \T & \T & \T
\F & \F & \T & \F
\end{tabular}

The output of the operator is \T\ if and only if the inputs do not match any row where the output is \F. So, to get a CNF we can go over all the rows where hte output is \F, and for each write a clause that means we are not in that row. Then we AND all such clauses. For example, for $P \oplus Q$ we get

$$(\neg P \vee \neg Q) \wedge (P \vee Q)$$

When we are only interested to know whether or not a given formula is satisfiable, we can write a 3CNF that is satisfiable iff the original formula is. In order to do that, we first write an equivalent CNF, and then convert it to a 3CNF (which is not necessarily equivalent, but only guarantees to preserve the satisfiability feature) as follow. For each clause with less than 3 literals such as $(A \lor \neg B)$ we add a dummy variable $C$ (only for this clause) and interprete the $(A \lor \neg B)$ as a formula over all of $A,B,C$ and write a CNF for them (which happens to be 3CNF!). For longer clauses such as $(A \lor B \lor C \lor D)$ we do another trick of breaking them into smaller parts using new dummy variables as follows $(A \lor B \lor \neg X) \wedge (\neg X \lor C \lor D).$

Problem Set 1 Comments (Wed, 6 Sep 2017)

The Problem Set 1 comments are now posted in collab: PDF

Class 5: CNF, Computing, Quantifiers (Tue, 5 Sep 2017)

### Schedule

Problem Set 2 is due Friday at 6:29pm.

Challenge Problem Opportunity. Find the shortest formula that is equivalent to XOR(a, b) using just NAND operations. Shortest means the minimum number of NAND operations. A convincing answer would include a proof that no shorter formula exists.

If you want to learn more about how to learn the logic implemented by a chip and cryptosystems used in car immobolizers, see Reverse-Engineering a Cryptographic RFID Tag (Karsten Nohl, David Evans, Starbug, and Henryk Plötz, USENIX Security Symposium 2008), or this video. Please don’t steal any cars.

# Notes and Questions

Definition: satisfiable. A logical formula is satisfiable if there is some way to make it true. That is, there is at least one assignment of truth value to its variables that makes the forumla true.

Definition: conjunctive normal form (CNF). A logical formula that is written as a conjunction of clauses, where each clause is a disjunction of literals, and each literal is either a variable or a negation of a variable, is in conjunctive normal form. If each clause has excatly three literals, it is called three conjunctive normal form (3CNF).

$$(a_1 \vee a_2 \vee \neg a_3) \wedge (a_1 \vee \neg a_2 \vee a_3) \wedge (\neg a_1 \vee a_2 \vee \neg a_3) \wedge (\neg a_1 \vee a_2 \vee a_3)$$

##

Show that every logical formula can be written in conjunctive normal form. Also, show that if we only care about satisfiability we can always write it in 3CNF form. Namely, for every CNF formula $F$, we can write a 3CNF formula $G$ such that $F$ is satisfiable if and only if $G$ is satisfiable.

What is the maximum number of (different) clauses in a 3CNF formula involving 5 variables?

##

What is the maximum number of (different) clauses in a satisfiable 3CNF formula involving 5 variables?

##

What is the maximum number of (different) clauses in a valid 3CNF formula involving 5 variables?

##

## Logical Quantifiers

$\forall x \in S. P(x)$ means $P$ holds for every element of $S$.
$\exists x \in S. P(x)$ means $P$ holds for at least one element of $S$.

Define valid and satisfiable using logical quantifiers:

#

$\forall x \in S. P(x)$ is equivalent to $\neg(\exists x \in S. \qquad \qquad)$

###

Notation: $\textrm{pow}(S)$ denotes the powerset of $S$. The powerset of a set is the set of all possible subsets of that S. So, $\textrm{pow}(\mathbb{N})$ denotes all subsets of the natural numbers.

Notation: $A - B$ denotes the difference between two sets. It is the elements of $A$, with every element of $B$ removed.

Notation: $\varnothing$ is the empty set. It is the set with no elements: ${ }$.

\begin{center} \Large

$$\fillin S \in \textrm{pow}(\mathbb{N}) - { \varnothing } \ldotp \fillin m \in S\ldotp \fillin x \in S - {m}\ldotp m < x$$ \end{center}

Problem Set 2 (Fri, 1 Sep 2017)

Problem Set 2 [PDF] is now posted and is due Friday, 8 September at 6:29:00pm.

Additional Resources (Thu, 31 Aug 2017)

I’ve added a page, Resources, with links to some suggested resources beyond the course materials. If you find other useful resources, please post them in slack and we’ll add them to this list.

Class 4: Logical Operators and Formulas (Thu, 31 Aug 2017)

### Schedule

Problem Set 1 is due Friday at 6:29pm.

Next week, we will cover the rest of Chapter 3 (Satisfiability and Quantifiers).

Scott Brown, The Life and Work of Augustus De Morgan. Applied Probability 2006.

Ada’s Correspondence with De Morgan (Clay Mathematics Institute)

# Notes and Questions

## Well-Ordering Principle Proof

Odd Summation. (Problem 2.12) Prove that for all $n > 0$, the sum of the first $n$ odd numbers is $n^2$.

# # ## Notations Mathematics and other domains often use many symbols to mean the same thing. Section 3.2 of the book gives some common notations, but there are others in common use. \begin{center} \begin{tabular}{cccc} English & Logic & C, Java, Rust & Python \\ \hline $P$ \smallcaps{implies} $Q$ & $P \implies Q$ {\em or} $P \longrightarrow Q$ & - & - \\ \smallcaps{not}$(P)$ & $\neg P$ {\em or} $\overline{P}$ & \verb+!p+ & \verb+not p+ \\ $P$ \smallcaps{and} $Q$ & $P \wedge Q$ & \verb+p && q+ & \verb+p and q+ \\ $P$ \smallcaps{or} $Q$ & $P \vee Q$ & \verb+P || Q+ & \verb+p or q+ \\ $P$ \smallcaps{xor} $Q$ & $P \oplus Q$ & \verb+p ^ q+ (bitwise) or \verb+p != q+ & \verb+p ^ q+ \\ \end{tabular} \end{center} For what values in Java or C are \verb+p ^ q+ and \verb+p != q+ both valid, but have different meanings? ## Logical Formulas \begin{center} \begin{tabular}{c|c|c} $P$ & \smallcaps{not}$(P)$ & \_\_\_\_\_\_\_\_ \\ \hline \T & \F & \\ \F & \T & \\ \end{tabular} \end{center} How many one-input Boolean operators are there? How many do we need to produce them all? # \begin{center} \begin{tabular}{cc|c|c|c|c|c} $P$ & $Q$ & $P \wedge Q$ & $P \vee Q$ & $P \implies Q$ & \_\_\_\_\_\_\_\_ & $P \oplus Q$ \\ \hline \T & \T & \T & \T & & \T & \F \\ \T & \F & & \T & & \F & \T \\ \F & \T & & \T & & \F & \T \\ \F & \F & & \F & & \T & \F \\ \end{tabular} \end{center} How many two-input Boolean operators are there? # **De Morgan's Laws:** $$\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q) \qquad \neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$$ How can these be written without the $\neg$ in front? ## Prove that it is possible to make all two-input Boolean operators using just \smallcaps{not} and any _odd_ two-input operator. (An operator is _odd_, if the number of outputs that are **True** are odd.) ## **Definition: valid.** A logical formula is _valid_ if there is no way to make it **false**. That is, no matter what truth values its variables have, it is always **true**. (Another name for this is a _tautology_.) **Definition: satisfiable.** A logical formula is _satisfiable_ if there is _some_ way to make it **true**. That is, there is at least one assignment of truth value to its variables that makes the forumla true. For each of the formulas below, determine if it is _valid_ and if it is _satisfiable_. 1. $(P \vee \neg P)$ 2. $(P \vee Q) \wedge (\neg P \vee Q)$ 3. $((P \implies Q) \wedge (Q \implies P)) \vee (P \xor Q)$

Class 3: Well-Ordering Principle (Tue, 29 Aug 2017)

### Schedule

This week, you should read MCS Chapter 2 and MCS Chapter 3 (at least through the end of Section 3.4).

Problem Set 1 is due Friday at 6:29pm.

Office hours started Monday afternoon. See the course calendar for the full office hours schedule.

# Notes and Questions

What properties must a sensible ordering function have?

Definition. A set is ordered with respect to an ordering relation (e.g., $<$), if two things hold. (1) Every pair of inequal elements $a,b$ in $A$ either satisfy $a<b$ or $b<a$. (2) for every three elements $a$, $b$, and $c$, $a < b$ and $b < c$ imply that $a < c$ (this is called transitivity).

Definition. An ordered set,with respect to an ordering relation (e.g., $<$), is well-ordered if all of its non-empty subsets has a minimum element.

Which of these are well-ordered?

• The set of non-negative integers, comparator $<$.
• The set of integers, comparator $<$.
• The set of integers, comparator $|a| < |b|$.
• The set of integers, comparator if |a| = |b|: $a < b$, else: $|a| < |b|$.
• The set of national soccer teams, comparator winning games.

Prove the set of positive rationals is not well-ordered under $<$.

#

Provide a comparison function that can be used to well-order the positive rationals.

### Template for Well-Ordering Proofs (Section 2.2)

To prove that $P(n)$ is true for all $n \in \mathbb{N}$:

1. Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
2. Assume for contradiction that $C$ is ______________.
3. By the well-ordering principle, there must be __________________ , $m \in C$.
4. Reach a contradiction (this is the creative part!). One way to reach a contradiction would be to show $P(m)$. Another way is to show there must be an element $m’ \in C$ where $m’ < m$.
5. Conclude that $C$ must be empty, hence there are no counter-examples and $P(n)$ always holds.

Example: Betable Numbers. A number is betable if it can be produced using some combination of \$2 and \$5 chips. Prove that all integer values greater than \$3 are betable. # # # **Example: Division Property.** Given integer$a$and positive integer$b$, there exist integers$q$and$r$such that:$a = qb + r$and$0 \le r < b\$.
# # _The whole problem with the world is that fools and fanatics are always so certain of themselves, and wiser people so full of doubts._ Bertrand Russell