Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Some vacuous set theory (20 points)

Prove or disprove each of the following statements. Assume that the universal quantifiers range over all sets.

$\begin{enumerate} \item $\forall x\!: \emptyset \in x$. \item $\forall x\!: \emptyset \subseteq x$. \end{enumerate}$

1.1. Solution

1. Disproof: consider the empty set itself; by definition, no x is an element of the empty set, so in particular the empty set is not an element of itself. It follows that

$\exists x\!: \emptyset \not\in x,$

which is logically equivalent to

$\neg \forall x\!: \emptyset \in x.$

2. Proof: Use the definition of subset to expand

$\forall x\!: \emptyset \subseteq x$

latex error! exitcode was 1 (signal 0), transscript follows:

This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013)
entering extended mode
(./latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.tex
LaTeX2e <2011/06/27>
Babel <3.9f> and hyphenation patterns for 78 languages loaded.
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/article.cls
Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/size12.clo))
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/inputenc.sty
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/utf8.def
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/t1enc.dfu)
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/ot1enc.dfu)
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/omsenc.dfu)))
No file latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.aux.
! Missing $ inserted.
<inserted text> 
                $
l.8 \end{document}
                  
[1] (./latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.aux) )
(see the transcript file for additional information)
Output written on latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.dvi (1 page,
 336 bytes).
Transcript written on latex_813dccf52b5544f3a26f5080442b12a4a2bdcde8_p.log.

But no set y is in the empty set, so the implication is vacuously true.

2. A gambling problem (20 points)

The game of duality involves choosing four digits independently and uniformly at random from the range 0, 1, 2, ... 9. You win the game if the sequence of digits you choose contains exactly two distinct digits: 0220, 9199, and 6464 are all winning sequences, but 7777 and 6096 are not. What is the probability of winning this game?

2.1. Solution

There are several ways to count the winning combinations. All basically involve noticing (a) that there are 10*9 = 90 different ways to choose the two digits, and that there are 7 distinct patterns the digits can appear in. To see the second part, observe that once the first digit has been fixed, there are 7 choices for whether the others are equal to it or not, obtained by taking the 2³=8 possibilities and excluding the one all-equal case. This gives 10*9*7 = 630 winning combinations, out of 10⁴ total sequences, for a probability of 630/10⁴ = 0.063 (or 6.3%).

3. A recurrence (20 points)

Find a closed-form expression for a_n as a function of n, where

$\begin{eqnarray*} a_0 &=& 1\\ a_{n+1} &=& 2a_n + 1. \end{eqnarray*}$

Hint: use generating functions or guess the correct solution and prove that it works by an induction argument.

3.1. Solution

The solution is a_n = 2ⁿ⁺¹-1. This can easily be verified by induction by computing a₀ = 2⁰⁺¹-1 = 2-1 = 1 and a_n+1 = 2a_n + 1 = 2(2ⁿ⁺¹-1)+1 = 2^(n+1)+1 - 2 + 1 = 2^(n+1)+1 - 1.

Alternatively, using generating functions, let F generate the sequence {a_n}; then F = 2zF + 1/(1-z). Solving this for F gives

$F = \frac{1}{(1-2z)(1-z)} = \frac{2}{1-2z} + \frac{-1}{1-z},$

where the numerators in the partial fraction expansion are obtained by the usual trick of multiplying by one of the factors in the denominator and then setting z to make it equal to zero. Recalling that 1/(1-z) generates the sequence {1} and 1/(1-2z) generates {2ⁿ}, we get

a_n = 2(2ⁿ) - 1 = 2ⁿ⁺¹ - 1.

4. Logical equivalence (20 points)

Prove that p => (q \/ r) ≡ (p => q) \/ (p => r). You may use either logical equivalences or a truth table.

4.1. Solution

The truth table method is easier to remember but logical equivalences are quicker:

(p => q) \/ (p => r)
≡ (¬p \/ q) \/ (¬p \/ r)
≡ ¬p \/ q \/ r
≡ p => (q \/ r).