cs2102: Discrete Math

Class 11: Strong Induction (Tue, 27 Sep 2016)

### Schedule

**Problem Set 5** is due **Friday at 6:29pm**.

**Thursday’s Class** may include review for Exam 1. Before 6:59pm
Wednesday, send me topics you would like to review:

- fewer than 10 total requests: class is not being sufficiently challenged and we should be doing more difficult material (except for the 10 requestors who get exam exemptions).
- exactly 10 total requests: all requestors get automatic exam exemptions, review requested topics.
- more than 10 requests implies we should spend Thursday’s class on reviewing requested topics, no exam exemptions.

**Friday, 3:30pm** (Rice Hall Auditorium): Eva Tardos (Cornell University), *Learning and
Efficiency of Outcomes in Games*. (She could definitely help you
answer questions 7-9 on PS5!)

### Exam 1

Exam 1 will be in class on Thursday, 6 October.

**Resources.** You will be permitted to use a single paper page of notes
that you prepare and bring to the exam. It is fine to collaborate with
others to prepare your notes. The page should be no larger than a US
Letter size page ($8.5 \times 11$ inches), and you may write (or
print) on both sides of the page. No other resources are permitted
during the exam.

**Content.** The problems on the exam will cover material from Classes
1–11, Problem Sets 1–5 (including the provided solutions), and MCS
Chapters 1–5. Everything on the exam will be something you have seen
in at least two of these (Classes, Problem Sets, and MCS Book), and
most of the exam will be things you have seen in all three. If you
understand the problems on the problem sets and questions on the class
notes well enough to be able to answer similar questions, you should
do well on the exam.

The main topics the exam will cover include:

Propositions, axioms, and proofs (you should understand what each of these are and how to define them precisely)

Inference rules (how to determine and show if an inference rule is sound or unsound, how to correctly use inference rules in a proof)

Logical formula (how to interpret logical formulas and convert English statements into logic, determine the validity or satisfiability of a formula, and show equivalence or non-equivalence of two formulas)

Logical quantifiers (how to reason about logical formula using $\forall$ and $\exists$, including showing logical equivalence and implication)

Proof methods (you should be able to read and write proofs that use direct proof, contrapositive proof, and proof by contradiction)

Well ordering (you should be able to explain what it means for a set to be well ordered, determine if a given set and operator is well ordered, and be able to construct proofs using the well ordering principle and identify flaws in misuses of the well ordering principle)

Induction (you should understand mathematical induction and be able to construct proofs using induction and identify flaws in misuses of induction in proofs)

For most students, I believe the best way to prepare for the exam will be to (1) go over the problem sets and their solutions, and make sure you understand well any of the problems you did not get before; (2) go through the questions in the class notes and convince yourself you can answer them well; (3) re-read chapters of the book, solving the associated practice problems, especially for any sections on topics where you had difficulty on the problem sets. If you do #1 and understand well the problems on the problem set, you should be confident you’ll do well on the exam; if you struggled on the problem sets, you would benefit from doing #2 and #3 as well.

## Induction Practice

Take-Away Game: start with $n$ sticks; at each turn a player must remove 1, 2 or 3 sticks; player who takes the last stick wins.

Prove: for a Take-Away game with any initial number of sticks, $n$, either Player 1 has a winning strategy or Player 2 does.

Prove: Player 1 has a winning strategy for a Take-Away game with $n$ sticks, if \bigfillin. Otherwise, Player 2 has a winning strategy.

# Strong Induction Principle

Let $P$ be a predicated on $\mathbb{N}$. If

- $P(0)$ is true, and
- $(\forall m \in \mathbb{N}, m \le n . P(n)) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

- $P(m)$ is true for all $m \in \mathbb{N}$.

Show that *strong* induction is not actually stronger than regular induction.

##

Prove that a tree (fully-connected graph with no cycles in it) with $n$ nodes has $n - 1$ edges.

Self-Inverting Relations Challenge Solved! (Sat, 24 Sep 2016)

Challenge 4 has been solved by Henry Spece!

**Challenge 4.**(From Class 9) How many self-inverting relations,

*R*:

*N*

_{k}→

*N*

_{k}, are there? (Where

*N*

_{k}is the set of all non-negative integers less than

*k*, and a relation is self-inverting if

*R*=

*R*

^{-1}.)

Henry’s answer is below:

2^{n*(n+1)/2}For each element in the domain, the number of “connection” possibilities for that element to each element of the codomain (given that it can either be related or not related to a codomain element) is 2

n, wherenis the number of codomain elements.This includes the possibility of the element connecting to itself, because there are two possibilities involving self connection, and 2

^{(n-1)}possibilities for connection to non-identical elements. The product of these two results in 2*2^{(n-1)}= 2^{n}.For each following element in the domain, the relationship with all previous elements which have been assigned relationships is fixed. For example, if element

ain the domain is related to elementbin the codomain, then elementbin the domain must be related to elementain the codomain. This applies equally if elementain the domain is not related to elementbin the codomain, because then elementbin the domain must also not be related to elementain the codomain, or the relation would not be self-inverting.All other relationships between our second element and elements of the codomain are still free to change, though, leaving 2

^{n-1}combinations for the second element considered.This pattern continues

ntimes in total, and by multiplying these possibilities, we get2

^{n}* 2^{n-1}* 2^{n-2}… * 2^{1}Which is the same as 2

^{n + (n-1) + (n-2) + … + 2 + 1}.By reversing the addition sequence we get that the exponent of 2 is the sum of all numbers from 1 to

n, which is equal ton*(n+1)/2.Hence, the number of self-inverting relations for a set of size

nmust be 2^{(n*(n+1)/2)}.

Congratulations to Henry Spece for solving the challenge!

Problem Set 5 (Fri, 23 Sep 2016)

**Problem Set 5** is now posted, and is due on **Friday, 30
September at 6:29pm**.

Class 10: In(tro)duction (Thu, 22 Sep 2016)

### Schedule

**Problem Set 4** is due **Friday at 6:29pm**.

Next week, you should finish reading MCS Chapter 5 (Induction). Another presentation of Induction is Chapter 10 from the Book of Proof (you are not required to read this, but it is encouraged and has lots more examples of proofs by induction).

Exam 1 will be in class on Thursday, 6 October.

## Links

Chapter 10: Induction from the Book of Proof

The Onion, Bush Earmarks 1.5 Billion Gold Stars For Education.

# Power Sets (continued from Class 9)

The **power set** of $A$ ($\textrm{pow}(A)$) is the set of all subsets of
$A$: $B \in \textrm{pow}(A) \iff B \subseteq A$.

Prove that the size of the power set of a set $S$ with $|S| = N$ is $2^N$.

**Proof using Well-Ordering Principle**

The goal is to prove for all sets $A$: $|\textrm{pow}(A)| = 2^{|A|}$.

Recall (from Class 9) that $N_k = { n | n \in \mathbb{N} \wedge n < k } $ and $|\mathbb{N}_n| = n$.

Because of the bijection between any set $A$ where $|A| = n$ to $\mathbb{N}_n$, we can prove the general property by showing $\forall n \in \mathbb{N} \ldotp P(n)$ where $P(n) ::= |\textrm{pow}(\mathbb{N}_n)| = 2^n$.

We follow the structure of every well-ordering proof:

- Define the set of counterexamples: $$ C ::= { n \in \mathbb{N} | \quad |\textrm{pow}(\mathbb{N}_n)| \neq 2^n } $$
- Assume $C$ is $\fillin\fillin\fillin$.
- By the well-ordering principle, there must be some smallest element, $m \in C$.
Reach a contradiction: we show that $\fillin\fillin\fillin$ holds.

- Since $m$ is the smallest element of $C$, $P(n)$ must hold for all $\fillin\fillin\fillin$.
- We know $P(0)$ is true since $\mathbb{N}_0 = \emptyset$ and $\textrm{pow}(\emptyset) = \fillin\fillin\fillin\fillin$. We have, $|\textrm{pow}(\mathbb{N}_0)| = \fillin\fillin = \fillin\fillin$, satisfying $P(0)$.
- Thus, $m > 0$. This means $m - 1 \in \mathbb{N}$.
- So, we know $P(\fillin\fillin)$ holds.
- Thus, we can construct $\textrm{pow}(\mathbb{N}
*{m})$ by keeping all the elements of $\textrm{pow}(\mathbb{N}*{m - 1})$ and adding each of those elements with $(m-1)$ inserts. More formally, $$ \textrm{pow}(\mathbb{N}*m) = \textrm{pow}(\mathbb{N}*{m - 1}) \quad \cup \bigcup*{S \in \textrm{pow}(\mathbb{N}*{m - 1})} (S \cup \fillin\fillin\fillin) $$ The size of this set is $2 |\textrm{pow}(\mathbb{N}*{m - 1})|$ since it contains two sets for each set in $\textrm{pow}(\mathbb{N}*{m - 1})$ (the original one, and the one with $m-1$ added, which we know is a new set since $m - 1 \notin \mathbb{N}_{m - 1}$). - Since $P(m-1)$, we know $|\textrm{pow}(\mathbb{N}
*{m - 1})| = \fillin\fillin\fillin$. The size of the new set, $|\textrm{pow}(\mathbb{N}*{m})| = 2 \cdot 2^{m - 1} = 2^{m}$. This means that $P(m)$ holds.

Hence, $C$ must be empty. We reached a contradiction using the well-ordering principle by showing the $P(m)$ holds for $m \in C$, which must mean the $C$ is empty. If there are no counter-examples, then $P(n)$ holds for all $n \in \mathbb{N}$.

# Induction Principle

Let $P$ be a predicated on $\mathbb{N}$. If

- $P(0)$ is true, and
- $P(n) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

- $P(m)$ is true for all $m \in \mathbb{N}$.

## Template for Induction Proofs

- State, “We prove by induction.”
- Define a predicate, $P(n)$. This is the
*induction hypothesis*. Our goal is to show that $P(n)$ is true for all $n \in \mathbb{N}$. - Prove $P(0)$ is true. (
*base case*or*basis step*.) - Prove that $P(n) \implies P(n + 1)$ for every $n \in \mathbb{N}$. (
*induction step*) - Conclude that $P(n)$ is true for all $n \in \mathbb{N}$ by induction.

How is the method of *proof by induction principle* similar to and different from *proof by well-ordering principle*?

## Induction Practice

Prove the non-negative integers are well ordered by the induction principle.

###

Prove the power set size property, $|\textrm{pow}(A)| = 2^{|A|}$, by induction.

###

Problem Set 3 Comments (Thu, 22 Sep 2016)

The solutions and comments for PS3 are now posted in collab: PDF

You should find your graded assignment as a new PDF attachment with markup on it in collab (if you submitted with teammates, please check with your partners).

The meaning of the scores is the same as for PS1 and PS2. A score of 6 means you got everything we expected out of this assignment, and 5 means you did well for the most part by had some answers that should have been better. Scores above 6 are for excellent work. (In the gradebook, collab sometimes shows the grades scaled by 100 for some buggy reason. Although receiving a score of 100+ is possible in theory, no one received more than 8 points for this assingment. If you see a score about 100, the meaning is that score divided by 100.)

Class 9: Cardinality (Tue, 20 Sep 2016)

### Schedule

This week you should finish reading MCS Chapter 4 (section 4.5) and Section 5.1. We will discuss Induction (Section 5.1) next class.

**Problem Set 4** is due **Friday at 6:29pm**.

**Challenge Problem.**How many self-inverting relations,

*R*:

*N*

_{k}→

*N*

_{k}, are there? (Where

*N*

_{k}is the set of all non-negative integers less than

*k*, and a relation is self-inverting if

*R*=

*R*

^{-1}.)

## Links

# Relation Practice

The *inverse* of a relation $R: A \rightarrow B, G \subseteq A \times B$ is defined by reversing all the arrows:
$$
R^{-1}: B \rightarrow A, G^{-1} \subseteq B \times A
$$

$$ (b, a) \in G^{-1} \iff \fillin\fillin\fillin\fillin $$

What does it mean if $R \equiv R^{-1}$?

# Set Cardinality

**Finite Cardinality.** If $A$ is a finite set, the *cardinality* of
$A$, written $|A|$, is the number of elements in $A$.

Does this definition require adding a new fundamental set operation?

#

**Alternate definition:** The *cardinality* of the set
$$
N_k = { n | n \in \mathbb{N} \wedge n < k }
$$
is $k$. If there is a *bijection* between two sets, they have the same
cardinality.

#

If there is a *surjective relation* between $A$ and $B$ what do we know
about their cardinalities?

##

If there is a *surjective function* between $A$ and $B$ what do we know
about their cardinalities?

If there is a *total surjective function* between $A$ and $B$ what do we know
about their cardinalities?

##

If there is a *total surjective injective function* between $A$ and $B$
what do we know about their cardinalities?

##

What is the cardinality of $A \cup B$?

#

# Power Sets

The **power set** of $A$ ($\textrm{pow}(A)$)is the set of all subsets of $A$:
$$
B \in \textrm{pow}(A) \iff B \subseteq A.
$$

Prove that the size of the power set of a set $S$ with $|S| = N$ is $2^N$ using the well-ordering principle. (See MCS 4.5.1 for an alternate proof.)

#

#

Survey Questions (Part 3) (Tue, 20 Sep 2016)

Here’s the third (and final!) installment of responses to questions submitted in the registration surveys (see Part 1 and Part 2 for the earlier responses). If you missed your chance to ask a question on the registration survey, or have new questions now the course is further along, feel free to send them (directly or anonymous is fine if you prefer).

How you might view things more normally, one’s view of “free time” changes a lot after having a family. Before that, I would have considered my teaching and research work as the main thing I do, and the time I’m not doing that as “free time”, which I would mostly spend playing and watching soccer, music, and mostly bad TV shows.

Now, I view the main things I do as revolving around my children (4-year old daughter and 1 ½-year old son), and can mostly schedule the rest of my life around that (one of the perks of being a professor, instead of having a real job!). I do get to do lots of fun things with the kids but don’t really consider that “free time” in the traditional sense.

Since its been a while, here’s the picture from Class 1:

It was generated by this (very ugly and brute force) python code:

```
import numpy as np
import matplotlib.pyplot as plt
def ellip_curve():
x = np.arange(-2, 10, 0.1);
y = np.sqrt(x ** 3 + 7)
plt.plot(x, y)
plt.show()
def ellip_curve_field():
xpoints = []
ypoints = []
G = 629
for x in range(500):
for y in range(500):
if y ** 2 % G == (x ** 3 + 7) % G:
xpoints.append(x)
ypoints.append(y)
plt.plot(xpoints, ypoints, marker='+', linestyle='none', color='r')
plt.show()
ellip_curve_field()
```

I picked 629 just because its one of my favorite numbers, but the fact that is has two large factors (17 * 37) makes it produce a less regular graph than we would get for a more divisible number. For example, here is the graph for modulus 628 (2 * 2 * 157):

^{256}- 2

^{32}- 977 for bitcoin’s curve, which is otherwise the same as this one).

My research is in computer security and applied cryptography, which is entirely built on discrete math. I will try to integrate this into some of the lectures, but definitely have some classes toward the end of the semester that get more into how discrete math is essential for cryptography, and maybe even how some of the problems you’re learning about in this class can be used to enable zero-knowledge proofs (that is, proving that you know something without revealing anything about it) and multi-party computation (enabling two people to compute a function together without revealing any information about their inputs).

*coding*as the process of turning a well described algorithm into code in some programming language. This course won’t help too much with that. It is more related to

*programming*, which I view as the process of finding a program that solves some problem. This includes both devising the algorithms and data structures to use, and writing the code to implement them. This course should help you get better at constructing programs and reasoning about whether or not they are correct.

Away from Charlottesvile, the Recurse Center is very cool (when I visited it was called Hacker School), and they have students for summer sessions.

Lots of students have great experiences doing research over the summer, and there are many ways for students to get involved in research groups and have paid positions over the summer (including in mine).

I don’t want to mention specific companies for internships publicly here, but there are some that I’ve heard students have great experiences at, and other where the experiences are more mixed. I’m happy to share my thoughts on this privately during office hours (or make an appointment to meet some other time).

Anonymous Feedback Comments (Mon, 19 Sep 2016)

This anonymous comment was submitted through collab:

Hello Professor!

I have never been very strong at math, and whenever I take a math class I have to try very hard to keep up. This class has been the first time I have ever done a proof and I am having difficulty even getting a grasp of even the basics of this material. Would it be possible to work through more example problems in class in order to get an idea of how to apply these concepts? Also, I have sometimes have difficulty following the symbols that are used when you write in mathematical notation, would it be possible to explain some of the more complex symbols, or go a bit slower when writing them?

Thanks!

I understand what you are saying, and do appreciate the comment.

First, on the notations. If I use a notation that is unfamiliar, please
stop and ask for me to define it, or at least post on slack `#inclass`

so someone else will notice and clarify it. Notations are meant to be a
convenient and compact way to write things down, and should be
obfuscating the content.

On the example problems, I think you are right that we should spend a bit more time in lecture going through examples, but I also think large-scale lectures like we have for this class are just about the worst possible medium for doing this kind of technical work. (I mostly agree with Robert Talbert’s description of Four things lecture is good for and that lectures are a terrible way to cover material and transfer information.)

The reason large-scale lectures are such a bad format for going through technical examples and learning from them is that the way to learn from examples is to understand each step by figuring it out yourself, with the right leading questions to get you to that step. And, problems don’t have just one way of solving them, so you don’t want to go through a pre-set sequence of steps, but find a path to a solution that makes most sense for whoever is working on it. Spending lecture time going through techincal examples inevitably will be boring for a significant fraction of the class (that could already solve that problem on their own), and will be bewildering for some other fraction of the class (that misses some step in the explanation or is thinking about the problem in some other way). The best way to learn from examples is to go through them in very small groups (ideally one-on-one), where everyone can understand and contribute to each step. The next best way is to read examples at your own pace. Going through written examples has the benefit that everyone can go through at their own pace, and go back over steps that didn’t make sense, and then try to work out the solution on their own. (The disadvantage is that if what is written doesn’t cover some path that you are thinking about, or doesn’t explain something that is unclear, then there is no way to get more information from the static page.)

The book (at least in my view) does do a great job with most example problems, and has many good examples. As I mentioned before, my assumption is that if no one asks questions about content, including examples, in the book, that means that everyone understood it and it is not worthwhile to spend time in lecture repeating material you already understand.

Similarly, I expect everyone to read through the provided solutions to the problem sets, which I hope are clear and understandable, but you should ask questions if not. Even if you did well on an assignment, it should be worthwhile to read through the solutions, which often provide more depth or different approaches to solving problems.

So, the best thing to do is to come to office hours to go through examples in person. Next, to ask questions about examples from the book or problems on the problem sets that are unclear, and then I’ll go through those in class.

That said, I do appreciate that it will sometimes be useful to go through more basic examples in class, and will try and do this more, but balance it with my goals of making class interesting and worthwhile for people who are able to understand the text on their own.

Problem Set 2 Comments (Mon, 19 Sep 2016)

The solutions and comments for PS2 are now posted in collab: PDF

The grades will be released soon. The grading scale for PS2 is similar to what was used for PS1 (there is no “out of” goal, or “maximum” score), but scores are intended to reflect whether or not you got what was intended out of the assignment (or did better than those expectations). See the Problem Set 1 Comments for the meaning of different scores.

Problem Set 4 (Fri, 16 Sep 2016)

**Problem Set 4** is now posted, and is due on **Friday, 23
September at 6:29pm**.