cs2102: Discrete Math

Problem Set 2 (Fri, 2 Sep 2016)

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

Class 4: Logical Formulas (Thu, 1 Sep 2016)

### Schedule

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

I will not be able to hold my normal office hours on Monday.

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

## Links

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$.

Class 3: Well-Ordering Principle (Tue, 30 Aug 2016)

### 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. There are upcoming office hours: today (Tuesday) 3:30-5pm and 7:30-9:30pm; Wednesday 10am-1pm, 2:30-4pm, 6:30-9:30pm (all of these are in Rice 436), and Dave has office hours Wednesday 1-2pm (in Rice 507). See the course calendar for the full office hours schedule.

**Challenge Problem Opportunity.**It is trivial to show that numbers in Java or C are not we-ordered, but quite challenging to show this for Python. Write a Python program that demonstrates the fact that numbers in Python are not well-ordered.

## Links

*The Well-Ordering Theorem: one of the Greatest Mathematical Controversies of All Time*, Kathryn Mann.

*US aviation authority: Boeing 787 bug could cause ‘loss of control’* (Nigel Jones’ explanation)

Basic Integer Overflows, blexim,
Phrak (Volume 0x0b, Issue 0x3c).

Never need an excuse to watch Gangnam Style.

# Notes and Questions

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

What properties must a sensible ordering function have?

**Trichotomy**. A relation, $\prec$, satisfies the axiom of trichotomy
if exactly one of these is true for all elements $a$ and $b$: $a \prec
b$, $b \prec a$ or $a = b$.

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}$:

- Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
- Assume for contradiction that $C$ is ______________.
- By the well-ordering principle, there must be __________________ , $m \in C$.
- 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$.
- 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.

Office Hours Posted (Sun, 28 Aug 2016)

The Office Hours Schedule is now posted on the Course Calendar. Office hours start this week Monday (August 29). Except for Dave’s, all office hours are in Rice 436. Dave’s office hours are in his office, Rice 507.

**Mondays**

9:30-10:30am Dave (Rice 507)

10:30-2pm Yong Jae, Adam R., Brooke

4-6:30pm Adam G., Sarah

**Tuesdays**

noon-1:30pm Riya

3:30-5pm Luke

7:30-9:30pm Subhan

**Wednesdays**

10am-1pm Yong Jae, Brooke, Harrison

1-2pm Dave (Rice 507)

2:30-5pm Adam G., Gloria

6:30-9:30pm Sarah, Han Jin, Subhan

**Thursdays**

10am-1:30pm Harrison, Luke, Han

3:30-10pm Gloria, Riya, Adam R., Christopher, Subhan, Yaser

**Fridays**

9-11:30am Sarah, Yong Jae

1:30-4pm Luke, Yaser

5-6pm Hussain

**Sundays**

noon-3:30pm Hussain, Yong Jae

4-5:30pm Christopher

Survey Questions (Sat, 27 Aug 2016)

Here are my (in progress) responses to selected questions submitted in the registration surveys. I’ll add more responses here as I go through the rest of your questions. If you have other questions after reading this, feel free to ask them on slack (if you want it to be anonymous, send it as a direct message and I’ll answer it here).

The most useful will be the MIT OpenCourseWare sites for the “6.042: Mathematics for Computer Science” course:

Fall 2010 (Tom Leighton and Marten van Dijk) (this includes lecture videos, mostly by Tom Leighton, which cover many of the topics in the course)

You’ll find lots of examples and problems on these sites.

Another great (free) resource, but less directly matching what we do in
this course, is Richard Hammack’s *Book of
Proof*.

I’m teaching this course mostly because I like teaching foundational courses and especially courses early in the curriculum, both for a first chance to expose students to exciting new ideas and empowering students more dramatically than can be done in later courses. The other reasons I wanted to teach cs2102 are becuase I’ve already taught most of the courses in our curriculum (cs200/cs150/cs1120; cs101 (Udacity); cs2220; cs2150; cs3102; and cs4414) and like to teach new things since I learn more by doing that, and this course seemed more likely to be a good source of ideas for Cville Math Circle than the other core courses I haven’t taught yet.

`LIST`

and see all the source code and read it to
learn how to “cheat” to win the game, and to start changing the code.
The next year, the school got Apple
II’s, which were fantastic
machines with color graphics (that could display on a TV or monitor) and
even a disk drive that you could use to store programs! It was so much fun to be able to play around with BASIC programs to draw on the screen, and eventually figure out how to handle key-presses to make games.
When I was in middle school, I sold my first program, which was a program to keep track of team information for the wrestling coach. Unfortunately, I didn’t test it with more than 10 teammates, so when he tried entering the team in it the program crashed when he got to the 11th person.

I knew programming computers was a lot of fun, but didn’t know anything about computer science (or that I wanted to do it for a career), until taking Gerry Sussman’s 6.001 Structure and Interpretation of Computer Programs course (at MIT in 1989). That opened me to the power and beauty of computer science, beyond just writing programs, and I’ve only had a few digressions since.

As to why cs2102 (and the other theoretical and foundational courses you take) is important, courses like these are the ones that should empower you to envision and execute creative computing beyond standard practice. There are tons of 3-month boot camps that can train most smart people to become adequate web and mobile developers or data scientist programmers, and people who complete these programs are able to find good six-figure jobs. The best of them will stay active in learning new APIs and tools, and develop the experience needed to build increasingly complex projects. If you want to do that you don’t need to do a four-year degree at an expensive University like UVa — there are much easier, faster, and cheaper career paths to being a professional programmer.

On the other hand, people without fundamental understanding of the underlying mathematics and theory of computing (which you should get from cs2102, cs3102, and cs4102), and deep understanding of how computing systems work (which you should get from cs2150, cs3330, and cs4414), are unlikely to do things that really advance the state of computing. Most programmers do things that are unsurprising and mundane; you should aspire to do things that are surprising and indistinguishable from magic.

Although I hope cs2102 will be valuable and exciting on its own, its
real importance in the curriculum and your overall computing
development, is to prepare you well for cs3102 and cs4102. As a whole,
though, the foundational understanding you should get from those courses
should enable you to design, build, and analyze computing systems that
do things people previously thought were not possible (or didn’t even
think about at all!)

Problem Set 1 (Fri, 26 Aug 2016)

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

Class 2: Proof Methods (Thu, 25 Aug 2016)

### Schedule

Before **Friday (tomorrow), 6:29pm**:

- Read, print, and sign the Course Pledge. You should print the PDF version for signing, and submit a scan of your signed pledge using Collab.
- Read Jeremy Kun’s
*Habits of Highly Mathematical People*. - Submit a Course Registration Survey (which includes some questions based on Kun’s essay).

Next week:

- Before Tuesday’s class: Read MCS Chapter 2
- Before Thursday’s class: Read MCS Chapter 3
- Due Friday at 6:29pm:
**Problem Set 1**

Sorry the proof in class got so messed up! Although part of my goal for class today was to illustrated the subjectiveness of human-written and read proofs, I apologize for making things so confusing and broken. I’d updated the notes to include the full proof (hopefully correct now!) at the level of detail intended in class. Its good to see students are being skeptical proof-readers and noticing mistakes like this.

We didn’t get to the “if and only if” proof in the notes in class today, but you are encouraged to try this on your own. We’ll look at this the Well Ordering Principle (Chapter 2) in Tuesday’s class.

**Challenge Problem Opportunity.**I wasn’t very satisfied with my proof of the “Odd-Even Lemma” in class. I hope a student will come up with a better proof. Come up with a proof that passes the “skeptical reader” test and would convince someone with no prior knowledge of odd and even numbers.

## Links

Dan Ariely, *Honor Codes*

The Coq Proof Assistant tool I mentioned in class today is available
from *https://coq.inria.fr/*. (You are not
expected to use this for cs2102, or generate proofs at this level of
rigor or details, but are certainly welcome to if you want!)

*Anatomy of a
Miracle*,
Vanity Fair, June 2009.

Intel’s FDIV bug (there’s even a web page for jokes about Intel’s FDIV bug).

How should one decide what can be accepted as an axiom, and what must be proven?

What is the purpose of a *proof*? (in cs2102? in software development? in algorithm design?)

## Proof from Class

Proposition: If the product of $x$ and $y$ is even, at least one of $x$ or $y$ must be even.

Our goal is to prove the implication, $P \implies Q$, where:

- $P$ is “the product of $x$ and $y$ is even”
- $Q$ is “at least one of $x$ and $y$ must be even”

We will prove the contrapositive. The inference rule,

$$ \infer{P \implies Q}{NOT(Q) \implies NOT(P)} $$ will be the last step in our proof. To be able to use this rule, we need to make the antecedent true. So, our goal is to prove $NOT(Q) \implies NOT(P)$.

To prove an implication, we assume the left side and short the right side. So, our proof begins:

- We prove the contrapositive.
- Assume NOT(at least one of $x$ and $y$ must be even).
- By the meaning of negation, this means both $x$ and $y$ are not even.
- By the “Odd-Even Lemma”, both $x$ and $y$ are odd.
- By the definition of
*odd*, there exist integers $k$ and $m$ such that $x = 2k + 1$ and $y = 2m + 1$. - Substituting, $xy = (2k + 1)(2m + 1) = 4mk + 2m + 2k + 1 = 2(2mk + m + k) + 1$.
- By the closure of addition and multiplication over the integers, there is some integer $r = 2mk + m + k$, so $xy = 2r + 1$.
- By the definition of
*odd*, $xy$ is odd. - By the (not proven) “Even-Odd Lemma”, this means $xy$ is not even.
- So, we have shown NOT(the product of $x$ and $y$ is even).
- Since we concluded this starting from the assumption (step 2), this proves the implication: NOT(at least one of $x$ and $y$ must be even) $\implies$ NOT(the product of $x$ and $y$ is even).
- Using the contrapositive inference rule, we can conclude: the product of $x$ and $y$ is even $\implies$ at least one of $x$ and $y$ must be even. \QEDA

\dbox{ {\bf Challenge Problem Opportunity.} I wasn’t very satisfied with my proof of the “Odd-Even Lemma” in class. I hope a student will come up with a better proof. A proof that passes the “skeptical reader” test and would convince someone with no prior knowledge of odd and even numbers is worth up to 10 bonus points. }

## Proving “If and Only If”

Strategy: To prove $P$ if and only if $Q$:

- Prove $P \implies Q$.
- Prove $Q \implies P$.

*Definition.* The *standard deviation* of a sequence of values $x_1, x_2, \ldots, x_n$ is
$$
\sqrt{\frac{(x_1 - \mu)^2 + (x_2 - \mu)^2 + \ldots + (x_n - \mu)^2}{n}}
$$
where $\mu$ is the mean of the values:
$$
\mu ::= \frac{x_1 + x_2 + \ldots + x_n}{n}
$$.

**Theorem 1.6.1.** The standard deviation of a sequence of values, $x_1,
x_2, \ldots, x_n$ is $0$ *if and only if* all of the $x_i$ values are
equal to the mean of $x_1, x_2, \ldots, x_n$.

The book proves this using a chain of iff implications; prove it using the two-implications strategy.

#

#

#

#

#

#

#

#

*In physics, your solution should convince a reasonable person. In math, you have to convince a person who’s trying to make trouble.*
Frank Wilczek

Class 1: What makes it go? (Tue, 23 Aug 2016)

### Schedule

Before **Thursday’s class**: (visit https://uvacs2102.github.io for the web version of these notes with links)

Join the cs2102 slack group and set up your profile with a pronouncable name (not your UVA email id) (setting up your profile photo is encouraged, but not required).

Read the Course Syllabus and post any questions or comments you have on it on the course slack group (#general).

Read the

*Introduction*and*Chapter 1: What is a Proof?*from the MCS Book. The book is freely available on-line under a Creative Commons License. Students are strongly encrouaged to print out the readings to read them more effectively on paper.

Before **Friday, 6:29pm**:

Read, print, and sign the Course Pledge. You should print the PDF version for signing, and submit a scan of your signed pledge using Collab.

Read Jeremy Kun’s

*Habits of Highly Mathematical People*.Submit a Course Registration Survey (which includes some questions based on Kun’s essay).

Why is most of the math you have used in school previously *continuous*?

What are the differences between how scientists, lawyers, and
mathematicians establish ``*truth*”?

A *proposition* is a statement that is either ________ or _________.

A *predicate* is a proposition whose truth may depend on the value of
variables.

### Proof

A *theorem* is a ____________ that has been proven true.

An *axiom* is a proposition that is *accepted to be true*. Axioms are
not proven; they are *assumed* to be true.

**Definition.** A *mathematical proof* of a proposition is a chain of
*logical deductions* starting from a set of accepted *axioms* that
leads to the proposition.

### Rules of Inference

The possible steps that can be used in a proof are logical deductions based on inference rules.

Inference rules are written as: $$ \infer{\textrm{\emph{conclusion}}}{\textrm{\emph{antecedents}}} $$ This means if everything on top of the rule is established to be true, then you can conclude what is on the bottom.

*Modus Ponens*: To prove *Q*, (1) prove *P* and (2) prove that *P* implies *Q*. ($P \implies Q$ is a notation for $P$ implies $Q$).

$$ \infer{Q}{P,\quad P \implies Q} $$

An inference rule is *sound* if can never lead to a **false** conclusion.

Which of these inference rules are sound?

$$ \infer{Q}{P} \qquad \infer{false}{P, P \implies Q} \qquad \infer{true}{P, NOT(P)} \qquad \infer{P \implies NOT(P)}{P, NOT(P)} \qquad \infer{NOT(Q) \implies P}{NOT(P) \implies Q} $$

##

**Contrapositive:**

$$ \infer{NOT(Q) \implies NOT(P)}{P \implies Q} \qquad \infer{P \implies Q}{NOT(Q) \implies NOT(P)} $$

**Theorem to Prove:** If the product of $x$ and $y$ is even, at least one of $x$ or $y$ must be even.