"Y20HW" refers to the "Homework, material covered" page of the 2020 edition of this course. Y20HW03 refers to class #3 in year 2020.
"ORD" refers to ordinary homework problems, "Bonus" refers to bonus problems. They all count together, but the Bonus problems may take more work per point. Solve the ordinary problems first.
"DM 4.1.15" refers to item 4.1.15 (Chapter 4, Section 1)
in the instructor's online
Discrete Mathematics Lecture Notes.
WARNING. Skip DM Section 2.2 and Chap. 7. DM Sec 2.2 is replaced
by ASY (below) and DM Chap. 7 is replaced by PROB (click "Texts"
on the banner).
WARNING. DM was updated on Nov 6, 2021, at 15:05. Make sure to
refresh your browser.
"ASY 6.21" refers to item 6.21 (Section 6) in the Asymptotic Equality and Inequality handout.
"PROB 7.4.22" refers to item 7.4.22 (Section 4) in the handout
Finite Probability Spaces.
WARNING. The PROB handout was updated on
Thursday, 10-28-2021, at 19:30. Make sure to
REFRESH the link
before solving the problems. To see that you are viewing the current
version, check PROB 7.7.18. It should talk about the "Moonwatchers' Club."
If it does not, you are seeing an earlier, cached version. REFRESH the link.
If that does not help, please clear your browser's cache or try another
browser.
Class 18, Tue 11-30 Inclusion-Exclusion formula. Planar graphs. DO exercises due Thursday, Dec 2.
18.05 STUDY the class notes.
18.15 REVIEW the Inclusion-Exclusion formula.
Let $A_1,\dots,A_k$
be events and let $B = \overline{ \bigcup_{i=1}^k A_i}$ be the complement
of their union.
The Inclusion-Exclusion formula represents $\Pr(B)$
as the alternating sum
$$\Pr(B)=S_0-S_1+-\dots+(-1)^k S_k =\sum_{\ell=0}^k (-1)^{\ell} S_{\ell}\,$$
where $S_{\ell}$ is the sum of the probabilities of the $\ell$-wise
intersections of the $A_i$. Review the class notes for a proof.
18.17 DO Show that the following version of the Inclusion-Exclusion formula is equivalent to the one stated above. $$ \Pr(B) = \sum_{I\subseteq [k]} (-1)^{|I|} \Pr(A_I)$$ where $A_I = \bigcap_{i\in I} A_i$. Note that $A_{\emptyset}=\Omega$.
18.20 DO$^*$ (Bonferroni's inequalities) We use the notation
of Exercise 18.15. With this notation we have
$$\Pr(B)=\sum_{\ell=0}^k (-1)^{\ell} S_{\ell}\,.$$
Let us consider the truncations of this sum: for $j=0,\dots,k$ let
$$ T_j = \sum_{\ell=0}^j (-1)^{\ell} S_{\ell}\,.$$
Prove that for all even values of $j$ we have
$\Pr(B) \le T_j$ and for all odd values of $j$ we have
$\Pr(B) \ge T_j$.
Examples: $S_0-S_1+S_2-S_3 \le \Pr(B) \le S_0-S_1+S_2$.
18.25 DO Let $\Sigma$ be a finite alphabet, $|\Sigma|=k$.
Let $W(n,k)$ denote the set of words of length $n$ over the alphabet
$\Sigma$ such that every letter in $\Sigma$ actually occurs in the word.
Example: Let $n=5$ and $k=3$; let the alphabet be $\Sigma=\{A,B,C\}$.
Then the word $AACBC$ counts toward $W(5,3)$ but the word $AACAC$ does not.
Determine $|W(n,k)|$. Give a simple expression in terms of $n$ and $k$.
This will not be a closed-form expression but it will involve a sum
of which the number of terms only depends on $k$ (not on $n$).
Use Inclusion-Exclusion.
18.28 DO Count the $[n]\to [k]$ surjections. Observe that this number is equal to $|W(n,k)|$.
18.40 (Euler's formula) Let $G$ be a plane representation of a connected graph with $n$ vertices and $m$ edges. Let the plane representation have $r$ regions. Then $n-m+r=2$.
18.42 DO (a) Verify Euler's formula for trees.
(b) Prove Euler's formula by induction on $m$. What are the base
cases?
18.45 DO Verify Euler's formula by direct calculation for the grid graph and for the Platonic solids.
18.50 DO Let $G$ be a planar graph with $n\ge 3$ vertices.
Prove: $m\le 3n-6$.
Prove: If additionally $G$ is triangle-free (has no $K_3$ subgraphs)
then $m\le 2n-4$.
18.52 DO Infer that every planar graph has a vertex of degree $\le 5$.
18.54 DO Infer that every planar graph is 6-colorable.
18.56 Four Color Theorem (Appel--Haken, 1974) Every planar graph is 4-colorable. (Do not attempt to prove this.)
18.60 DO Prove: $K_5$ and $K_{3,3}$ are not planar. Hint: 18.50.
18.62 DO Find a non-planar graph of girth 100. Give a very simple construction. Use the preceding exercise.
Class 17, Thu 11-18 Almost all graphs have diameter 2. Problems due Nov 29.
17.10 DO (Union bound) Let $A_1,\dots,A_m\subseteq\Omega$ be events in the probability space $(\Omega,\Pr)$. Then $$ \Pr\left(\bigcup_{i=1}^m A_i\right) \le \sum_{i=1}^k \Pr(A_i)\,.$$
17.12 DEF We say that the events $A$ and $B$ are almost disjoint if $\Pr(A\cap B)=0$.
17.15 DO Prove: we have equality in the Union bound if and only if the events $A_1,\dots,A_m$ are pairwise almost disjoint, i.e., if $$(\forall i,j)(1\le i < j \le n) \Rightarrow \Pr(A_i\cap A_j)=0\,.$$
17.17 ORD (5 points) Prove: $$\Pr\left(\bigcap_{i=1}^m A_i\right)=0 \not\Rightarrow \Pr\left(\bigcup_{i=1}^m A_i\right) = \sum_{i=1}^k \Pr(A_i)\,.$$ Find the smallest counterexample: smallest $m$ and smallest size of the sample space.
17.20 THEOREM. Fix $0 < p < 1$. Consider the Erdös-Rényi model $\Gbold(n,p)$ of random graphs for all $n\ge 1$. In this sequence of models, almost all graphs have diameter 2.
17.22 EXPLANATION The meaning of this statement is the following. Let $p_n$ denote the probability that a random graph $\calG$ taken from the $\Gbold(n,p)$ distribution has diameter 2. Then $\lim_{n\to\infty} p_n =1$.
17.25 Below we sketch the PROOF. We assume that the set of vertices of our random graph $\calG$ is $[n]$.
17.28 DO Prove: $\Pr(\diam(\calG)=1) = p^{\binom{n}{2}}$.
Note that this quantity rapidly (super-exponentially) approaches zero.
17.32 Let $A_n$ denote the event that $\diam(\calG)\ge 3$.
17.34 DO Observe that to prove the Theorem, we need to show that $\lim_{n\to\infty} \Pr(A_n)=0$.
17.37 Notation. Let $1\le i < j\le n$. (So $i,j$ are vertices of $\calG$.) Let $B_{i,j}$ denote the event that $i$ and $j$ have a common neighbor in $\calG$ and let $C_{i,j}$ denote the event that $\rho(i,j)\le 2$. ($\rho(i,j)$ denotes the distance of $i$ and $j$ in $\calG$.)
17.38 DO Observe that $B_{i,j}\subseteq C_{i,j}$.
17.40 DO Show that for $n\ge 2$, we have $B_{i,j}\neq C_{i,j}$.
17.44 DO Prove: $$\Abar_n = \bigcap_{1\le i < j \le n} C_{i,j}\,.$$
17.48 DO Infer: $$ A_n = \bigcup_{1\le i < j \le n} \Cbar_{i,j} \subseteq \bigcup_{1\le i < j \le n} \Bbar_{i,j}\,. $$
17.50 Therefore, by the Union bound, $$ \Pr(A_n) \le \sum_{1\le i < j \le n} \Pr(\Bbar_{i,j})\,.$$
So to show that $\Pr(A_n)\to 0$, it suffices to show that the quantities $\Pr(\Bbar_{i,j})$ are small.
17.52 DO Prove: $\Pr(\Bbar_{i,j}) = (1-p^2)^{n-2}$.
17.55 DO Infer: $$ \Pr(A_n) \le \binom{n}{2}\cdot (1-p^2)^{n-2}\,.$$
17.60 DO (Exponential decay beats polynomial growth) Let $k, c$ be positive constants, $0 < c \le 1$. Prove: $\lim_{n\to\infty} n^k \cdot c^n = 0$.
17.65 ORD (4 points) Prove: the right-hand side in 17.55 goes to zero as $n\to\infty$ while $0 < p < 1$ is a constant.
This completes the proof of the theorem.
More to follow. Please check back later. Please report any errors.
Class 16, Tue 11-16 Digraphs. Problems due Nov 29.
16.05 STUDY DM Chap 6.4 (Digraph terminology). Study all definitions and solve the exercises numbered 6.1.1--6.4.25. Note that the terminology is the literature is not uniform; please use the definitions in DM 6.4.
16.15 DO DM 6.4.7 (the number of orientations of a graph with $m$ edges is $2^m$).
16.20 DEF An acyclic orientation of a graph is an orientation that is a DAG.
16.22 ORD (3+5 points) Count the acyclic orientations of (a) the cycle $C_n$ $(n\ge 3)$ and (b) the complete graph $K_n$ $(n\ge 1)$. Your answers should be a very simple closed-form expressions. Prove.
16.25 ORD (3 points) DM 6.4.33 (list strong components of digraph in the figure) (you need to list the vertices of each strong component, like $\{a,c,e\},\{b,d,f,g\}$ if there are two strong components and these are the names of their vertices). No proof required.
16.27 ORD (6 points) Prove: a strongly connected digraph has at least $n$ edges.
16.30 DEF Let $G=(V,E)$ be a digraph and $A,B\subseteq V$. We denote by $E(A,B)$ the set of $A\to B$ edges, i.e., $$E(A,B)=\{(u,v)\mid u\in A, v\in B, u\neq v,\text{ and } (u,v)\in E\}.$$ The set of edges leaving $A$ is the set $E(A,\Abar)$ where $\Abar = V\setminus A$ is the complement of $A$. The set $E(\Abar,A)$ is the set of edges entering $A$.
16.32 DEF Let $G=(V,E)$ be a digraph. An cut in $G$ is a set $A\subseteq V$ such that $\emptyset \neq A \neq V$. If $s,t\in V$, $s\neq t$ then an $(s,t)$-cut is a set $A$ such that $s\in A$ and $t\in \Abar$.
16.40 ORD (6 points) Let $G=(V,E)$ be a digraph. Let $s,t\in V$, $s\neq t$. Prove: $t$ is accessible from $s$ if and only if for every $(s,t)$-cut $A$ we have $|E(A,\Abar)|\ge 1$. Clearly separate your proof into an "if" and an "only if" part. In each part, state the assumption(s) and the desired conclusion.
16.43 DO Prove: the digraph $G=(V,E)$ is strongly connected if and only if for every cut $A$ we have $|E(A,\Abar)|\ge 1$.
16.46 DEF We say that a digraph $G=(V,E)$ is Eulerian if $(\forall v\in V)(\deg^+(v)=\deg^-(v))$.
16.48 Bonus (6 points) Prove: If an Eulerian digraph is weakly connected then it is strongly connected. ("Weakly connected" means that the undirected version [we ignore orientation] is connected.)
16.50 DEF A legal coloring of a digraph $G$ assigns colors to the vertices such that adjacent vertices always get different color. So if a digraph has a self-loop, it has no legal coloring. $G$ is $k$-colorable if $k$ colors suffice for a legal coloring. The chromatic number of a digraph is the minimum number of colors required for a legal coloring. (So if a digraph has a self-loop, its chromatic number is infinite.)
16.52 Bonus (7+3 points) (a) Prove: if the outdegree of every vertex in a digraph $G$ is $k$ then $G$ is $(2k+1)$-colorable. (b) Show that for every $k\ge 0$, the bound $2k+1$ is tight.
16.55 ORD (5 points) DM 6.4.22 (every tournament has a Hamilton path)
16.57 Bonus (7 points) DM 6.4.23 (every strongly connected tournament has a Hamilton cycle)
16.59 ORD (4 points) DM 6.4.32 (if the outdegrees of a tournament are equal then $n$ is odd)
16.64 Bonus (7 points) Prove: If $G$ is a DAG then $G$ has a topological sort.
16.66 ORD (6 points) DM 6.4.27 (divisibility digraph has many topological sorts)
16.80 DEF Let $G$ be a graph with $m$ edges. A random orientation of $G$ is an orientation picked uniformly from the $2^m$ orientations. So the size of the sample space is $2^m$; its elements (the elementary events) are the orientations of $G$, and the distribution is uniform.
16.82 DO Let $\Gvec=(V,\Evec)$ be an orientation of the graph $G=(V,E)$. For an edge $e=(u,v)\in\Evec$ let $T_e$ denote the event that a random orientation of $G$ includes the (directed) edge $e$, i.e., that the edges $\{u,v\}\in E$ is oriented as $(u,v)$ as opposed to $(v,u)$. Prove: the events $\{T_e\mid e\in\Evec\}$ are independent balanced events. (Recall: an event is balanced if it has probability $1/2$.)
16.85 Bonus (12 points) Prove that almost every tournament
is strongly connected.
This statement means the following. Let $p_n$ denote the probability
that a random orientation of $K_n$ is strongly connected. Then
$\lim_{n\to\infty} p_n = 1$.
Hint: Study the proof from class that almost every graph has
diameter 2.
16.88 ORD (4 points) Let $X_n$ denote the number of directed 3-cycles in a random tournament on $n$ vertices. Determine $E(X_n)$. Your answer should be a simple closed-form expression in terms of $n$.
16.90 Bonus (9 points) (Continued) (a) Determine $\var(X_n)$. Your answer should be a simple closed-form expression in terms of $n$. Simplicity matters. (b) Show that there exist constants $c,d$ such that $\var(X_n)\sim c n^d$. Determine $c$ and $d$.
More to follow. Please check back later. Please report any errors.
Class 15, Thu 11-11 Graphs. Girth. Distance, diameter. Complete bipartite graphs $K_{r,s}$. Listing non-isomorphic trees up to 6 vertices. Automorphisms. Counting the spanning trees of $K_n$, Cayley's formula (stated), verified for small values. Erdös-Rényi model of random graphs. Problems due Nov 15 unless otherwise stated.
15.05 STUDY Y20HW18.90-18.100 (the Erdös-Rényi model).
15.10 REVIEW PROB Chap. 7.8, especially variance, covariance.
15.15 DO PROB 7.8.19 (variance of sum)
15.20 ORD (3+4 points) Let $0 < p < 1$. Let $X$ denote the
number of edges of a random graph $\calG$ in the $\Gbold(n,p)$ model.
(We fix the set of vertices, $V=[n]$.)
Determine (a) $E(X)$ and (b) $\var(X)$.
Your answers should be very simple expressions in terms of $n$ and $p$.
15.23 ORD (4+5 points) (Continued) Let $3\le k\le n$. Let
$Y$ be the number of $k$-cycles in $\calG$ and let $Z$ be
the number of induced $k$-cycles in $\calG$. Determine
(a) $E(Y)$ and (b) $E(Z)$.
Your answers should be very simple expressions in terms of $n, k$, and $p$.
15.25 Bonus (9 points, due Nov 29) (Continued) Let $T$ be the number of triangles in $\calG$. Let $v(n,p)=\var(T)$. (a) Give a simple expression for $v(n,p)$. (b) Asymptotically evaluate $v(n,p)$ for fixed $p$ as $n\to\infty$. Show that there exists a function $a(p)$ and a constant $c$ such that $v(n,p)\sim a(p)\cdot n^c$ as $n\to\infty$.
15.40 ORD (4+2 points) Let $G$ be a bipartite graph. (a) Prove: $m\le \lfloor n^2/4\rfloor$. (b) Prove that this bound is tight.
15.45 Bonus (6+2 points, due Nov 29) Let $G$ be a triangle-free
graph. (a) Prove: $m\le \lfloor n^2/4\rfloor$.
(b) Prove that this bound is tight.
Hint. Induction on $n$ in steps of two: for the inductive step,
remove a pair of adjacent vertices and apply the inductive hypothesis
to the remaining graph.
15.48 ORD (6 points, due Nov 29) Let $G$ be a graph. Assume the degrees of the vertices are $d_1,\dots,d_n$. Let $S=\sum_{i=1}^n d_i^2$. Let $N$ denote the number of paths of length 2 in $G$. Express $N$ as a simple function of $S,n,m$.
15.50 Bonus (7 points, due Nov 29) Let $G$ be a graph
without 4-cycles (no $C_4$ subgraphs). Prove: $m=O(n^{3/2})$.
State your constant hidden in the big-Oh notation.
Hint. Count the paths of length 2 in $G$.
15.55 Bonus (6 points, due Nov 29) Let $g$ be an integer and let $G$ be a graph of girth $g$. Prove: the diameter of $G$ is at least $(g-1)/2$.
More to follow. Please check back later. Please report any errors.
Class 14, Tue 11-09 Graphs. Induced subgraphs. Spanning subgraphs. Forests, trees. Cartesian product of graphs. Independence number. Chromatic number. Bipartite graphs. Problems due Nov 15 unless otherwise stated.
14.05 STUDY DM Chap. 6.1 (Graph Theory terminology) items 6.1.1--6.1.73.
14.10 STUDY Y20HW16 (class #16 in year 2020).
In the exercises to follow, $G=(V,E)$ is a graph with $n$ vertices and $m$ edges.
14.14 DO The number of induced subgraphs of $G$ is $2^n$.
14.16 DO The number of spanning subgraphs of $G$ is $2^m$.
14.20 ORD (6+2 points) Y20HW16.18ab (Petersen's graph)
14.25 Bonus (5 points, due Nov 29) Y20HW16.20: If $G$ $k$-regular, girth $\ge 5$ then $n\ge k^2+1$.
14.27 ORD (1+1+3 points) Y20HW16.22: Case of equality for $k=1,2,3$.
14.30 DO Y20HW16.35: Tree with $n\ge 2$ vertices has a vertex of degree 1.
14.32 ORD (4 points) Y20HW16.37: Tree: $m=n-1$. You may use the preceding DO exercise without proof.
14.34 DO Every connected graph has a spanning tree, i.e., a spanning subgraph that is a tree.
14.36 ORD (3 points) If $G$ is connected then $m\ge n-1$. You may use the preceding exercises without proof.
14.40 ORD (18 points; lose four points for each mistake) Y20HW16.44: Draw all non-isomorphic 7-vertex trees (by hand), state how many you found. Read Y20HW16.44 carefully.
14.42 DEF Let $k,\ell \ge 3$. The $k\times\ell$ toroidal grid is the Cartesian product of $C_k \Box C_{\ell}$. It has $k\ell$ vertices and $2k\ell$ edges (verify!); it is regular of degree 4.
14.45 ORD (5 points, due Nov 29) Let $k,\ell \ge 3$. When does the $k\times \ell$ toroidal grid NOT have girth 4? Make a clear "if and only if" statement. Prove your answer.
14.50 ORD (3 points, due Nov 29) Y20HW16.70: Diameter of graph vs. diameter of spanning tree.
14.52 Bonus (15 points, due Nov 29) Y20HW16.72: Diameter of graph vs. diameter of spanning tree.
14.65 DEF Y20HW16.140: independent set, maximum independent set, independence number $\alpha(G)$, maximal independent set
14.68 DO $\alpha(G)=1 \Leftrightarrow G\cong K_n$
14.70 DO $\alpha(G)=n \Leftrightarrow G\cong \Kbar_n$
14.72 DO Y20HW16.142: independence number of paths and cycles
14.75 ORD (2 points) Find a connected graph with $n$ vertices and independence number $n-1$.
14.78 ORD (8 points) Prove: if $G$ is regular of degree $\ge 1$ then $\alpha(G) \le n/2$.
14.82 ORD (8 points, due Nov 29) Y20HW16.154: counting the independent sets in the path $P_n$. Note: the empty set is an independent set.
14.85 ORD (6 points, due Nov 29) Y20HW16.144: lower bound on the independence number.
14.88 ORD (6 points, due Nov 29) Y20HW16.145: Ratio of independence number and smallest maximal independent set.
14.91 Bonus (8 points, due Nov 29) Y20HW16.145: Determine the size of the smallest maximal independent set in $C_n$.
14.93 ORD (7 points) Y20HW16.150: independence number of the grid graph
14.100 DEF Legal coloring, $k$-colorability, chromatic number $\chi(G)$
14.102 DO $1\le \chi(G)\le n$
14.104 DO $\chi(G)=n \Leftrightarrow G\cong K_n$
14.106 DO $\chi(G)=1 \Leftrightarrow G\cong \Kbar_n$
14.110 DO Y20HW16.172 and Y20HW16.174: chromatic number of paths and cycles
14.114 DO $\chi(G) \le 1 +\Delta$ where $\Delta$ is the maximum degree of $G$.
14.117 ORD (5 points, due Nov 29)
$1 +\Delta$ upper bound can be far
from true chromatic number. For every $n$, find the maximum of
the ratio $(1+\Delta(G))/\chi(G)$ where the maximum ranges over
all graphs with $n$ vertices. So your answer should be a function
of $n$. Prove your answer.
UPDATE (11-15 15:00) Clarification starting with "For every $n$" added.
Problem deferred to Nov 29. I am sorry if you have already
submitted a solution, please resubmit on Nov 29.
14.120 STUDY the Greedy coloring handout (GREEDY).
14.122 ORD (5 points, due Nov 29) GREEDY Problem (b) "greedy coloring is terrible."
14.125 DEF $G$ is bipartite if $G$ is 2-colorable, i.e., if $\chi(G)\le 2$.
14.127 DO the grid graphs are bipartite.
14.129 DO every tree is bipartite.
14.132 DO Y20HW16.197: Prove: $G$ is bipartite if and only if $G$ has no odd cycle.
14.135 Bonus (8 points, due Nov 29) $G$ has a bipartite subgraph with $\ge m/2$ edges. Prove this using the Probabilistic Method: color the vertices red and blue at random, flipping a fair coin at each vertex. (This is not a legal coloring.) Find the expected number of red-blue edges. Other proofs will not be accepted.
14.140 ORD (6 points) $\alpha(G)\cdot \chi(G)\ge n$.
14.142 ORD (5 points) Y20HW16.204 $\alpha(G)\cdot\chi(G)$ can be quadratic.
14.145 Bonus (10 points, due Nov 29) If $G$ is triangle-free then $\chi(G) \le 1+2\sqrt{n}$.
14.148 STUDY Y20HW16.210 (STORY)
14.150 ORD (5 points) Y20HW16.218: 4-chromatic graph without $K_4$ subgraph.
14.152 Bonus (8 points, due Nov 29) Y20HW16.220: triangle-free graph with chromatic number 4. You don't need to prove that the graph is triangle-free but you do need to prove that it is not 3-colorable.
14.160 DEF Hamilton cycle Y20DEF16.230
14.162 DO Y20HW232: the dodecahedron graph has a Hamilton cycle.
14.164 DO Y20HW234: the Petersen graph has no Hamilton cycle.
14.167 ORD (6 points, due Nov 29) Y20HW16.238: If $k\ell$ is odd then the $k\times \ell$ grid has no Hamilton cycle. Give an elegant, short proof. You may use any of the lower-numbered exercises without proof.
More to follow. Please check back later. Please report any errors.
Class 13, Thu 11-04 Graphs. Accessibility, connected components. Paths, cycles in graphs.
See Class 14 for material covered and exercises.
Class 12, Tue 11-02 Independence of random variables. Graphs. Isomorphism. Problems due Nov 8 unless otherwise stated.
12.05 STUDY PROB Chapter 7.8 (Variance, covariance, Chebyshev's Inequality), Chapter 7.9 (independence of a pair of random variables), and Chapter 7.10 (independence of random variables)
12.10 DEF The covariance of the random variables $X,Y: \Omega\to\rrr$ is the quantity $\cov(X,Y)=E(XY)-E(X)E(Y)$.
12.12 DEF The random variables $X,Y: \Omega\to\rrr$ are positively correlated if $\cov(X,Y) > 0$, uncorrelated if $\cov(X,Y)=0$, and negatively correlated if $\cov(X,Y) < 0$. In other words, we are comparing $E(XY)$ and $E(X)E(Y)$; e.g., "uncorrelated" means $E(XY)=E(X)E(Y)$.
12.15 THEOREM If $X$ and $Y$ are independent random variables then they are uncorrelated.
12.18 ORD (7 points) Show that the converse is false: Construct a probability space and two random variables that are uncorrelated but not independent. Make your sample space as small as possible. Clarity of your definitions, starting with the definition of your probability space, are paramount.
12.22 Bonus (4 points) Prove: If the random variables $X,Y,Z$ are independent (according to PROB Def. 7.10.1) then $X,Y$ are independent.
12.25 DO PROB 7.10.2 ($k$ events are independent $\Leftrightarrow$ their indicator variables are independent).
In the exercises below, $G=(V,E)$ is a graph with $n$ vertices and $m$ edges.
12.35 ORD (4 points) Give a simple description of those graphs $G$ where the "adjacent or equal" relation is an equivalence relation. Your description should be in terms of graphs which have been given a name in class. No proof required.
12.38 DEF A path of length $k$ in a graph $G$ is a subgraph isomorphic to $P_{k+1}$.
12.38 ORD (5 points) Let us say that vertex $y$ is path-accessible from vertex $x$ if there is a path between $x$ and $y$ in $G$. Prove that path-accessibility is an equivalence relation on the set of vertices. If you use a lemma (other exercise), please prove it.
12.40 ORD (4 points) Let $k\le n-1$. Count the paths of length $k$ in $K_n$. Your answer should be a simple closed-form expression (no summation or product signs or dot-dot-dots) using binomial coefficients and factorials (so $k!$ and $\binom{n}{k}$ counts as closed-form expressions). Briefly reason your answer.
12.43 DEF $d(x,y)$, the distance between vertices $x$ and $y$, is the length of a shortest path between them. If there is no path between $x$ and $y$ then their distance if infinite. The diameter of the graph $G$ is $\diam(G)=\max_{x,y\in V} d(x,y)$.
12.45 DO The diameter of the $k\times \ell$ grid graph is $k+\ell-2$, the distance between its opposite corners. (Verify!)
12.48 ORD (6 points, due Nov 15) Let $x$ and $y$ be two opposite corners of the $k\times \ell$ grid graph. Count the shortest paths between $x$ and $y$. Your answer should be a very simple closed-form expression (as defined in 12.40). Briefly reason your answer.
12.50 Bonus (5 points, due Nov 15) What is the maximum number of edges of a disconnected graph with $n$ vertices? Your answer should be a very simple closed-form expression. Prove your answer.
More to follow. Please check back later. Please report any errors.
Class 11, Tue 11-02 Independence of several events. Graphs. Problems due Nov 8 unless otherwise stated.
11.05 STUDY PROB Chap. 7.4 (Independence of multiple events).
11.10 ORD (2 points) PROB 7.4.13(a) (intersection of an empty set of events)
11.13 DO Prove: PROB 7.4.14 (inductive definition and explicit definition of independence are equivalent).
11.15 DO PROB 7.4.15 (explicit definition has $2^-k-1$ effective conditions)
11.17 Bonus (5 points, due Nov 15) PROB 7.4.18 ($|\Omega|\ge 2^k$). You may use lower-numbered exercises from PROB.)
DEF 11.19 An event is balanced if its probability is $1/2$.
11.20 Bonus (6 points) PROB 7.4.19 ($n$ balanced events that are $(n-1)$-wise but not fully independent). Clearly state your probability space. Give a simple description of your events. Simplicity counts.
11.40 STUDY DM Chap. 6.1 (Graph Theory terminology) items 6.1.1--6.1.32.
11.45 NOTATION In the exercises below, $G=(V,E)$ denotes a graph where $V$ and $E$ are sets such that $E\subseteq \binom{V}{2}$. $V$ is called the set of vertices (singular: vertex), $E$ is the set of edges. Notation: $n=|V|$, $m=|E|$.
11.50 ORD (4 points) DM 6.1.6(a) (two non-isomorphic regular graphs with the same number of vertices and the same degree). Give a simple description of your graphs. Give a clear reason why they are not isomorphic.
11.55 DO (Handshake Theorem) DM 6.1.8.
11.58 ORD (2 points) Prove: There is no 3-regular graph with $15$ vertices. (A 3-regular graph is a graph where every vertex has degree 3.)
11.60 ORD (4+4 points, due Nov 15) True or false:
(a) If $G$ is regular and $n$ is odd then $n\mid m$.
(b) If $G$ is regular and $n$ is even then $n\mid m$.
If true, give a simple proof. If false, give the smallest
possible counterexample.
11.63 ORD (2+2+4 points) DM 6.1.11 (self-complementary graphs)
11.65 ORD (5 points, due Nov 15) Prove: if $n\ge 2$ then $G$ has two vertices of equal degree.
11.67 DO Count the edges of the $k\times\ell$ grid graph. Your answer should be a simple expression in terms of $k$ and $\ell$.
11.70 ORD (5 points) Prove: $G$ or $\Gbar$ is connected.
More to follow. Please check back later. Please report any errors.
Class 10, Thu 10-28 Independence of a pair of events. Conditional probability. Positively/negatively correlated events. Independence of three events. Random variables. Expected value. Linearity of expectation. Indicator variables. Expected number of heads in sequence of $n$ coin flips.
10.05
STUDY PROB 7.2 (Conditional probability, probability of causes),
PROB 7.3 (Independence, positive and negative correlation of
a pair of events), Prob 7.4 items 7.4.1--7.4.8 (independence of
three events), 7.7 (Random variables, expected value, indicator
variables, Bernoulli trials).
See WARNING about PROB update above.
10.10 DO (Binomial Theorem) $$(x+y)^n = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}$$
10.12 DO The following special case if often the most useful: $$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k$$
10.15 DO Prove:
$(\forall n\ge 0)(\sum_{k=0}^n \binom{n}{k} = 2^n)$.
Give two proofs: (a) an "algebra proof," using the Binomial Theorem; and
(b) a "combinatorial proof," counting the subsets of $[n]$ in two ways.
10.18 ORD (3+4 points, due Nov 8) Prove: for all $n\ge 0$ we have
$$\sum_{k=0}^n (-1)^k \binom{n}{k}= \begin{cases} 0 &\text{ if }n\ge 1 \\
1 & \text{ if } n=0 \end{cases} $$
Give two proofs: (a) an algebra proof, using the Binomial Theorem
(b) a combinatorial proof, counting even and odd subsets of $[n]$.
Refer to an earlier exercise, do not repeat the proof.
10.30 ORD (3 points) Let $A\subseteq\Omega$ be an event. Prove: $A$ and $A$ are independent if and only if $A$ is a trivial event. (If you use an exercise from PROB, you need to solve it.)
10.33 ORD (4 points, due Nov 8) PROB 7.3.14 ($A\cup B$ vs. $A\cap B$). You may use lower-numbered exercises from PROB without proof.
10.36 ORD (4 points, due Nov 15) PROB 7.3.8 (uniform probability space of prime size)
10.39 ORD (4 points, due Nov 8) PROB 7.3.9 (lower bound on $|\Omega|$ if there exist two nontrivial independent events). You may use lower-numbered exercises from PROB without proof.
10.42 Bonus (6 points, due Nov 8) PROB 7.3.12 (random number even vs divisible by 3)
10.45 ORD (3+5 points) PROB 7.4.7 (a)(b) (three pairwise but not fully independent events)
10.48 Bonus (2+6 points, due Nov 8) PROB 7.4.8 (a)(b) (three non-independent events whose probabilities multiply)
10.60 ORD (3+3 points) (a) PROB 7.7.5 (expected value falls between min and max) (b) Is it possible that $\min X = E(X) < \max X$ ? If no, give a simple proof. If yes, find the smallest example.
10.65 DO (linearity of expectation) PROB 7.7.7
10.68 ORD (7 points) PROB 7.7.21 (mismatched envelopes) Give a clear definition of your probability space. State the size of the sample space. Give a clear definition of the random variables you use. Clarity is paramount and accounts for most of the credit.
10.70 Bonus (7 points, due Nov 8) PROB 7.7.15(a) (expected number of Aces in poker hand). Give a clear definition of your probability space. State the size of the sample space. Give a clear definition of the random variables you use. Clarity is paramount and accounts for most of the credit.
10.75 ORD (7 points, due Nov 8) PROB 7.7.18 (Club of 2000)
10.80 ORD (3+3 points, due Nov 8) PROB 7.7.22 (marbles in cups)
More to follow. Please check back later. Please report any errors.
Class 9, Tue 10-26 Asymptotic analysis of the Birthday Paradox. Finite Probability Spaces.
9.10 DO $(\forall x\in\rrr)(\eee^x \ge 1+x)$. Equality holds if and only if $x=0$.
9.12 DO Let $0\le a_1,\dots,a_k \le 1$. Prove: $$ \prod_{i=1}^k (1-a_i) \ge 1 - \sum_{i=1}^k a_i\,.$$ Equality holds if and only if at most one of the $a_i$ is nonzero.
9.20 REVIEW from class Let $A$ and $B$ be non-empty
sets, $|A|=n$, $|B|=k$. Let $P(n,k)$ denote the probability that
a random function $f\in B^A$ is an injection. (We consider the
uniform distribution over $B^A$.) Let $k=k(n)$ be a function of $n$.
Theorem A If $k(n)=\omega(\sqrt{n})$ (i.e.,
$k(n)/\sqrt{n} \to\infty$), then
$P(n,k(n))\to 0$ (almost surely there will be a collision).
Theorem B If $k(n)=o(\sqrt{n})$ (i.e.,
$k(n)/\sqrt{n} \to 0$), then
$P(n,k(n))\to 1$ (almost surely there will be no collision).
9.25 Bonus (10 points, due Nov 8) Let $A$ and $B$ be non-empty sets, $|A|=n$, $|B|=k$. As above, let $P(n,k)$ denote the probability that a random function $f\in B^A$ is an injection. (We consider the uniform distribution over $B^A$.) Let $k=k(n)$ be a function of $n$. Prove: if $k(n)=\Theta(\sqrt{n})$ then $P(n,k(n))$ is bounded away both from $0$ and from $1$, i.e., there exists a constant $c > 0$ such that for all sufficiently large $n$ we have $c \le P(n,k(n)) \le 1-c$.
9.30 STUDY PROB Sections 7.1 and 7.2.
9.32 DO Solve all exercises in PROB Sections 7.1 and 7.2.
9.35 ORD (6 points) Construct a probability space $(\Omega,\Pr)$ and two events, $A, B\subseteq\Omega$, such that $\Pr(A)=2/3$, $\Pr(B)=4/7$, and $\Pr(A\cap B)=1/4$. Make the sample space as small as possible. Your probability values should be given as fractions of integers reduced to their smallest terms. No decimal approximations. Prove that your sample space is as small as possible.
9.40 ORD (4 points) PROB 7.1.3 (number of trivial events is a power of 2).
9.43 ORD (4 points) PROB 7.1.4 (probability of full house in poker hand). Give exact answer with simple formula and decimal approximation to 4 digits of accuracy.
9.46 ORD (2+4 points) PROB 7.1.6 (a) (b1) (biased coins)
9.49 ORD (4+5 points, due Nov 8) PROB 7.1.7 (a) (b) (bridge) Give exact values by simple formulas involving binomial coefficients. Do not give decimal approximations. Reason your answers.
9.53 ORD (2+3+5+2 points) PROB 7.2.3 (three dice) Reason your answers.
9.56 ORD (3+4+1 points) PROB 7.2.5 (a)(b)(c) (probability of causes) Give the exact values of the probabilities you calculate as fractions of integers reduced to their lowest terms. No decimal approximations. Reason your answers.
More to follow. Please check back later. Please report any errors.
October 23 problem session notes posted.
Class 8, Thu 10-21 Prime Number Theorem (stated). Asymptotic notation.
8.05 STUDY asymptotic notation: ASY 1-3 (asymptotic equality), DM 2.1 (limits), 2.3 (little-oh notaion, 2.4 ($O,\Omega,\Theta$ notation)
8.15 DEF The prime counting function $\pi : \rrr\to\nnn_0$ is defined as $$ \pi(x) = |\{p \mid p\text{ is a prime number and } p\le x\}|\,.$$
For example, $\pi(3)=2$, $\pi(7)=4$, $\pi(10.3)=4$, $\pi(1.7)=0$, $\pi(-10)=0$, $\pi(\pi)=2$. (DO: verify!)
8.17 PRIME NUMBER THEOREM (PNT) (Hadamard and de la Vallée Poussin, 1896) $$ \pi(x) \sim \frac{x}{\ln x}\qquad \text{ as } x\to\infty\,.$$
8.20 NOTATION For $n\ge 1$, let $p_n$ denote the $n$-th prime number. So $p_1=2$, $p_2=3$, $p_3=5$, $p_4=7$, $p_5=11$, etc.
8.22 Bonus (7 points, due Nov 1) Prove: $(\forall n\ge 1)(p_n\ge 3n-5)$.
8.25 Bonus (9 points, due Nov 1) Use the PNT to prove: $p_n \sim n\ln n$.
8.27 ORD (5 points, due Nov 1) Use the preceding exercise to prove: $p_n \sim p_{n+1}$.
8.40 DEF (little-omega notation) Let $a_n, b_n$ be sequences of real numbers. We write $a_n=\omega(b_n)$ if $b_n = o(a_n)$, i.e., if $b_n/a_n \to 0$.
8.42 ORD (5 points) Find two increasing sequences of positive numbers, $a_n$ and $b_n$, such that $a_n\to\infty$, $b_n\to\infty$, and neither of the relations $a_n=O(b_n)$ and $a_n=\Omega(b_n)$ holds. Prove your answer. The definition of the sequences should be simple, and the proof of their correctness should also be simple.
8.44 ORD (2+2+2 points) Prove that the $\Theta$ relation is an equivalence relation on the set of all sequences of real numbers.
8.46 ORD (4+2 points) Prove: (a) If $a_n\sim b_n$ then $a_n = \Theta(b_n)$ but (b) not conversely.
8.48 DO Prove: $a_n\sim b_n$ if and only if $a_n-b_n = o(a_b)$.
8.55 ORD (3 points) Let $z_n$ be a sequence of integers and $L\in\rrr$. Prove: if $\lim_{n\to\infty} z_n = L$ then $L\in\zzz$ and $a_n$ is eventually equal to $L$.
More to follow. Please check back later. Please report any errors.
Class 7, Tue 10-19 Limits of sequences, limits of functions. Asymptotic equality.
7.10 DEF All sequences in this class will be infinite. A sequence of elements of a set $\Gamma$ is a function $a:\nnn_0 \to \Gamma$ with domain $\nnn_0$ and codomain $\Gamma$. Instead of writing $a(0), a(1), a(2),\dots$, we usually write $a_0, a_1, a_2,\dots$. If we do not specify the codomain, we mean a sequence of real numbers.
7.15 DEF Let $A_0, A_1, \dots$ be a sequence of truth values (TRUE/FALSE). We say that this sequence is eventually true if it is true for all sufficiently large $n$, i.e., if $(\exists n_0)(\forall n)(n\ge n_0 \Rightarrow A_n)$. We refer to $n_0$ as a threshold beyond which $A_n$ is true (a "valid" threshold).
7.17 DO Observe that if $n_0$ is a valid threshold then every $n_1 > n_0$ is also a valid threshold.
7.20 DO Prove that $2^n$ is eventually greater than $1000n$. In other words, the statement "$2^n > 1000n$" is eventually true.
7.26 DEF We say that the sequence $(a_n \mid n\in \nnn_0)$ is bounded if $(\exists C\in\rrr)(\forall n)(|a_n| \le C)$. We say that the sequence $(a_n)$ is bounded from above if $(\exists A\in\rrr)(\forall n)(a_n \le A)$. In this case, $A$ is an upper bound on the $a_n$. We say that the sequence $(a_n)$ is bounded from below if $(\exists B\in\rrr)(\forall n)(a_n \ge B)$. In this case, $B$ is a lower bound on the $a_n$.
7.28 DEF We say that the limit of the sequence
$(a_n \mid n\in \nnn_0)$
is the real number $L$ if for all $\epsilon > 0$, the value $a_n$
is eventually within $\epsilon$ of $L$, i.e., for all sufficiently
large $n$ we have $|a_n-L|\le \epsilon$.
More formally, we write that
$$ \lim_{n\to\infty} a_n = L$$
if
$$(\forall \epsilon > 0)(\exists n_{\epsilon})(\forall n)
(n\ge n_{\epsilon} \Rightarrow |a_n-L|\le \epsilon)$$
We call $n_{\epsilon}$ the threshold corresponding to $\epsilon$.
Past this threshold, all members of the sequence fall in the
interval $[L-\epsilon, L+\epsilon]$.
Instead of writing $\lim_{n\to\infty} a_n = L$, we also write
"$a_n\to L$ as $n\to\infty$". In words: $a_n$ approaches $L$
as $n$ goes to infinity.
7.30 DO Observe that the fact the $a_n \to L$ does not change if we change a finite number of elements of the sequence. In fact, we can have $a_n \to L$ even if a finite number of elements of the sequence $(a_n)$ are undefined.
7.32 ORD (3 points) Give a formal definition of the statement $$\lim_{n\to\infty} a_n = \infty\,.$$
7.35 DEF We say that the sequence $(a_n)$ is convergent
if it has a finite limit, i.e., if
$(\exists L\in \rrr)(\lim_{n\to\infty} a_n = L)$. In this case we
say that the sequence $a_n$ converges to $L$.
If the sequence $(a_n)$ does not have a finite limit then we say
that the sequence is divergent.
7.38 ORD (2 points) Prove: if a sequence is convergent then it is bounded.
7.40 DO Find a bounded sequence that is divergent.
Answer. There are many good answers to this question. Such a sequence
needs to oscillate in some sense. Perhaps
the simplest such sequence is $b_n = (-1)^n$.
7.42 ORD (3 points) Prove that the sequence $b_n=(-1)^n$ is divergent.
7.44 ORD (2 points, due Nov 1)
Find a sequence $c_n$ that is bounded from below,
ubounded from above, and does not go to infinity. Your answer should
be simple; simplicity counts. No proof required.
UPDATE (10-25 1am) This problem was deferred by a week.
7.46 DEF We say that the sequence $a_n$ is increasing if $(\forall n)(a_n\le a_{n+1})$. The sequence is strictly increasing if $(\forall n)(a_n < a_{n+1})$.
7.48 DEF We say that the sequence $a_n$ is eventually increasing if it increases for all sufficiently large $n$, i.e., if $$(\exists n_0)(\forall n)(n > n_0 \Rightarrow a_n \le a_{n+1})$$ We define eventually strictly increasing analogously. This terminology is consistent with DEF 7.15.
7.50 ORD (3 points) Find a strictly increasing sequence that does not go to infinity. Prove that your sequence does not go to infinity. Simplicity counts.
7.52 ORD (3 points) Find a sequence that goes to infinity but is not eventually increasing. No proof required but simplicity counts.
7.60 DEF Let $a\in\rrr$ and let $f:(a,\infty)\to\rrr$ be a function whose domain is the infinite interval $(a,\infty)$ and the codomain is $\rrr$. Let $L\in \rrr$. We say that $$\lim_{x\to\infty} f(x) = L$$ if $$(\forall \epsilon > 0)(\exists K_{\epsilon})(\forall x) (x \ge K_{\epsilon} \Rightarrow |f(x)-L|\le\epsilon)\,.$$ Compare this definition with DEF 7.28.
7.62 DO Define what it means that $$\lim_{x\to\infty} f(x) = \infty\,.$$
7.70 THEOREM (L'Hospital's rule) Let $a\in\rrr$. Let $f,g: (a,\infty)\to\rrr$ be differentiable functions. Assume $\lim_{x\to\infty}f(x)=\infty$ and $\lim_{x\to\infty}g(x)=\infty$. Assume further that $$\lim_{x\to\infty}\frac{f'(x)}{g'(x)}$$ exists and is finite. Let us call its value $L$, so $L\in\rrr$. Then the limit $$\lim_{x\to\infty}\frac{f(x)}{g(x)}$$ also exists and is equal to $L$.
7.72 DO Prove: $\lim_{x\to\infty} (\ln x)/x = 0$.
Hint. Use L'Hospital's rule.
7.74 DO Prove: $$(\forall \epsilon > 0) \left(\lim_{x\to\infty}\frac{\ln x}{x^{\epsilon}}\right) = 0\,.$$ Proof. Change of variables: $y := x^{\epsilon}.$ Then $\ln y = \epsilon \ln x$. Therefore $(\ln x)/(x^{\epsilon}) = (1/\epsilon)(\ln y)/y$. Now $(\ln y)/y\to 0$ because $y\to\infty$ as $x\to\infty$. Since $1/\epsilon$ is a constant, it follows that $(1/\epsilon)(\ln y)/y \to 0$.
7.80 ORD (6 points) (exponential growth beats polynomial growth) Prove: $$(\forall C)(\forall \epsilon > 0) \left(\lim_{x\to\infty} \frac{x^C}{(1+\epsilon)^x}\right) = 0.$$ Do not use L'Hospital's rule. Use only a change of variables.
7.90 DEF We say that the sequences, $(a_n)$ and $(b_n)$, are asymptotically equal if $$\lim_{n\to\infty} \frac{a_n}{b_n} = 1\,.$$ We denote this circumstance by $a_n \sim b_n$.
7.92 EXAMPLE $n^2-(100 n)\cos n \sim n^2$.
Proof. $(n^2-100n)/n^2 = 1- 100(\cos n)/n \to 1$ because
|100(\cos n)/n|\le 100/n \to 0$.
7.94 ORD (2 points) What does it mean that a sequence is eventually nonzero? Your definition should be a properly quantified statement.
7.96 ORD (2 points) State in a very simple English sentence what it means that a sequence $S$ is not eventually nonzero. Simplicity matters.
7.98 DO Prove: if $a_n\sim b_n$ then both of these sequences must be eventually nonzero.
7.100 ORD (1+2+2 points, due Nov 1)
Let ENZ denote the set of eventually nonzero
sequences. Prove: asymptotic equality is an equivalence relation
on ENZ. State what property of limits you are using for each condition.
UPDATE (10-25 1am) This problem was deferred by a week.
7.102 DO Prove: $3n^5-17n^3-100n^2-83n+150 \sim 3n^5$.
Proof.
$$\frac{3n^5-17n^3-100n^2-83n+150}{3n^5}= 1 - \frac{17}{3n^2}
-\frac{100}{3n^3} - \frac{83}{3n^4}+\frac{150}{3n^5}$$
Since every term on the right-hand side, except the $1$,
goes to zero, the entire exression goes to $1$.
7.104 DEF A polynomial is a function of the form $p(x)= b_0+b_1 x + b_2x^2 +\dots + b_k x^k$. The $b_i$ are the coefficients of this polynomial. $\rrr[x]$ denotes the set of polynomials with real coefficients and $\zzz[x]$ denotes the set of polynomials with integer coefficients. If $m$ is the largest number such that $b_m\neq 0$ then we say that $b_mx^m$ is the leading term of this polynomial. In this case we say that the polynomial has degree $m$: $\deg(p)=m$. For example, the leading term of $5+8x-10x^2+0\cdot x^3$ is $10x^2$. The zero polynomial (all coefficients are zero) has no leading term. We say that $\deg(0)=-\infty$.
7.106 DO Observe: if $f,g$ are polynomials then $\deg(f+g)\le \max\{\deg(f),\deg(g)\}$.
7.108 DO Find two polynomials, $f$ and $g$, such that $\deg(f+g) < \deg(f)+\deg(g)$.
7.110 DO Prove: $\deg(fg)=\deg(f)+\deg(g)$. Note that this is true even if one of the polynomials is the zero polynomial.
7.112 DO Every nonzero polynomial is asymptotically equal to its leading term. More precisely, let $f\in\rrr[x]$ be a polynomial of degree $k\ge 0$ with leading term $a_k x^k$. Prove: $f(n) \sim a_k n^k$.
7.115 DO Assume $a_n\sim u_n$ and $b_n\sim v_n$. Prove: $a_n b_n \sim u_n v_n$ and $a_n/b_n\sim u_n/v_n$.
7.117 ORD (3 points) Assume $a_n\sim u_n$ and $b_n\sim v_n$. Assume further that both $a_n+b_n$ and $u_n+v_n$ are eventually nonzero. Show that from these assumptions it does not follow that $a_n+b_n \sim u_n+v_n$. Simplicity matters.
7.119 Bonus (6 points) Assume $a_n >0$ and $b_n >0$. Assume further that $a_n\sim u_n$ and $b_n\sim v_n$. Prove: $a_n+b_n \sim u_n+v_n$.
7.122 ORD (4 points) Find two sequences, $a_n$ and $b_n$, such that $a_n\to\infty$ and $a_n\sim b_n$ but $a_n^{\,n} \not\sim b_n^{\,n}$. Prove. Simplicity counts.
7.125 ORD (5 points) Let $a_n > 1$, $b_n >1$. Assume $a_n \sim b_n$. Show that it does not follow that $\ln(a_n)\sim \ln(b_n)$. Simplicity counts.
7.127 DEF Let $a_n > K$. We say that $a_n$ is bounded away from $K$ if $(\exists \epsilon > 0)(\forall n)(a_n \ge K+\epsilon)$.
7.129 Bonus (6 points) Let $a_n > 1$. Assume $a_n$ is bounded away from $1$. Assume further than $a_n\sim b_n$. Prove: $\ln(a_n)\sim \ln(b_n)$.
7.131 ORD (4 points) Find two sequences, $a_n > 1$ and $b_n >1$, such that $a_n/b_n \to\infty$ and $\ln(a_n)\sim\ln(b_n)$. Prove.
7.135 ORD (3+4 points, due Nov 1) (a) Prove: $\lim_{n\to\infty} (\sqrt{n+1}-\sqrt{n}) = 0$. (b) Prove: there exist real numbers $a,b$ such that $\sqrt{n+1}-\sqrt{n} \sim an^b$. Find $a,b$.
7.137 ORD (4 points, due Nov 1) Prove: there exist real numbers $a,b$ such that $\binom{n}{5} \sim a n^b$. Find $a,b$. Elegance counts.
7.140 Theorem (Stirling's formula) $$ n! \sim \left(\frac{n}{\eee}\right)^n \sqrt{2\pi n}$$
7.144 ORD (5 points, due Nov 1) Prove: there exist real numbers $a,b,c$ such that $\binom{2n}{n}\sim a n^b c^n$. Find $a,b,c$. Use Stirling's formula.
More to follow. Please check back later. Please report any errors.
Class 6, Thu 10-14 Counting $k$-subsets via counting injections. Summation and product symbols. Empty sum, empty product. Base-$b$ number system. Equivalence relation, kernel of function, partition. Fundamental Theorem of Equivalence Relations (stated)
6.05 TERMINOLOGY Let $A$ be a finite set. The cardinality of the set $A$ is its size (the number of its elements), denoted $|A|$.
6.08 NOTATION Let $k\ge 0$. A $k$-set is a set of cardinality $k$.
Let $A$ be a set. Then $\binom{A}{k}$ denotes the set of
$k$-subsets of $A$. (A $k$-subset is a subset of cardinality $k$.)
6.12 (combinatorial definition of binomial coefficients)
Let $n, k \ge 0$. Let $A$ be an $n$-set.
Then the symbol $\binom{n}{k}$
denotes the cardinality of the set $\binom{A}{k}$.
So if $|A|=n$ and $k\ge 0$ then
$$\left|\binom{A}{k}\right|=\binom{n}{k}\,.$$
In particular, we have
$$\left|\binom{[n]}{k}\right|=\binom{n}{k}\,.$$
We call the numbers $\binom{n}{k}$ the binomial coefficients.
We read $\binom{n}{k}$ "$n$ choose $k$". LaTeX:
\binom{n}{k}.
6.17 WARNING. We shall learn a general formula for $\binom{n}{k}$. But until then, give combinatorial proofs of the identities in the next set of exercises, i.e., proofs based on the combinatorial definition of binomial coefficients; do not use the formula. Proofs using a formula for the binomial coefficients will not earn credit for these problems.
6.20 NOTATION (recall): $\nnn_0=\{0,1,2,\dots\}$ denotes the set of non-negative integers.
6.23 DO Verify: $(\forall n\in\nnn_0)\left(\binom{n}{0}=\binom{n}{n}=1\right)$.
6.25 DO Verify: $(\forall n,k\in\nnn_0)(n < k \Rightarrow \binom{n}{k}=0\,)$
6.30 DO Prove: If $0\le k\le n$ then $\binom{n}{k}=\binom{n}{n-k}$.
6.34 ORD (Pascal's Identity) (5 points) Prove:
If $0\le k \le n$
then $\binom{n+1}{k+1} = \binom{n}{k}+\binom{n}{k+1}$.
Observe WARNING 6.17.
6.45 DEF We say that the sets $A$ and $B$ are disjoint if $A\cap B=\emptyset$. We say that the set $A_1,\dots,A_k$ are if they are pairwise disjoint, i.e., for every $i\neq j$ we have $A_i\cap A_j=\emptyset$. A disjoint union is the union of disjoint sets. A disjoint union is indicated by a dot on top of the union sign: $A_1\dot\cup A_2\dot\cup\dots\dot\cup A_k$.
6.50 DEF A partition of a set $\Omega$ is a representation of $\Omega$ as the union of non-empty disjoint sets. We write $\Pi=\{B_1,\dots,B_k\}$ for the partition $A=B_1\dot\cup\dots\dot\cup B_k$ where the dots indicate that these sets are pairwise disjoint. The $B_i$ are called the blocks of $\Pi$.
6.53 Example. The set $[3]$ has 5 partitions: $\Pi_1=\{\{1,2,3\}\}$, $\Pi_2=\{\{1,2\},\{3\}\}$, $\Pi_3=\{\{1,3\},\{2\}\}$, $\Pi_4=\{\{2,3\},\{1\}\}$, $\Pi_5=\{\{1\},\{2\},\{3\}\}$.
6.58 DEF Let $f:A\to B$ be a function. The preimage
of $b\in B$ is the set $f^{-1}(b) :=\{a\in A \mid f(a)=b\}$.
Example: Let $g:\rrr\to\rrr$ denote the function $g(x)=x^2$.
Then $g^{-1}(4)=\{-2,2\}$, $g^{-1}(0)=\{0\}$,
$g^{-1}(-1)=\emptyset$.
6.62 DO
Let $f:\Omega\to\Gamma$ be a function and $b\in\Gamma$. Observe
that $f^{-1}(b)\neq\emptyset$ if and only if $b\in\range(f)$.
"Observe" means
"notice that it follows immediately from the definition."
6.66 DEF (Kernel of a function) Let $\Omega$ and $\Gamma$ be sets. A function $f:\Omega\to\Gamma$ defines a partition $\Pi_f$ of the domain of $f$ as follows: $$\Pi_f = \{f^{-1}(b)\mid b\in \range(f)\}$$ The partition $\Pi_f$ is called the kernel of the function $f$.
6.68 DO Show that in the preceding exercise, $\Pi_f$ is indeed a partition of $\Omega$.
6.70 Example. Consider a set $\Omega$ of bright-colored plastic toy bears. (Each bear has just one color.) Let $\Gamma$ be the set of colors. Let $f:\Omega\to\Gamma$ be the function that assigns its color to each bear, so $f(x)=$BLUE means bear $x$ is BLUE. Observe that the kernel of $f$ groups the bears by color.
6.75 ORD (4 points) Prove that every partition is the kernel of some function. More formally, prove the following. Given a partition $\Pi$ of the set $\Omega$, there exists a set $\Gamma$ and a function $f:\Omega\to\Gamma$ such that $\Pi = \Pi_f$.
6.77 COMMENT. The preceding exercise asks you to perform one of the basic tasks of intelligence: naming the blocks of a partition. Different languages have different words for "red," "blue," etc., but all of them solve precisely this exercise in relation to the partition of objects (toy bears) by color (the partition $\Pi_f$).
6.85 DEF Summation symbol. Let $f:\Omega\to\rrr$ be a function, where $\Omega$ is a finite set. We write $\sum_{x\in\Omega} f(x)$ to denote the sum of the values of $f$ for all elements of $\Omega$. So if $\Omega=\{a_1,\dots,a_n\}$ then $$\sum_{x\in\Omega} f(x) = f(a_1)+\dots+f(a_n)\,.$$ We shall refer to $\Omega$ as the domain of the summation.
6.88 CONVENTION $\sum_{x\in\emptyset} f(x) = 0$ (the empty sum is zero)
6.90 DO Prove: If $A,B$ are disjoint finite sets and $\Omega=A\dot\cup B$ then $$\sum_{x\in\Omega} f(x) = \sum_{x\in A} f(x) +\sum_{x\in B} f(x)\,.$$ Observe that the proof requires Convention 6.88. This shows that 6.88 is the only reasonable way to define the empty sum.
6.92 NOTATION $\sum_{i=1}^k f(i) :=\sum_{i\in [k]} f(i)$.
6.94 NOTATION
$$\sum_{1\le i\le j\le n} f(i,j) := \sum_{(i,j)\in \Delta} f(i,j)$$
where $\Delta=\{(i,j)\mid 1\le i\le j\le n\}$.
More generally, what we write under the summation sign should
specify the domain of the summation.
6.96 DO Let $\Pi=\{B_1,\dots,B_k\}$ be a partition of the finite set $\Omega$. Observe: $$\sum_{x\in\Omega} f(x) = \sum_{i=1}^k \sum_{x\in B_i} f(x)\,.$$
6.100 DEF Product symbol. Let $f:\Omega\to\rrr$ be a function, where $\Omega$ is a finite set. We write $\prod_{x\in\Omega} f(x)$ to denote the product of the values of $f$ for all elements of $\Omega$. So if $\Omega=\{a_1,\dots,a_n\}$ then $$\prod_{x\in\Omega} f(x) = f(a_1)\cdot\dots\cdot f(a_m)\,.$$ We shall refer to $\Omega$ as the domain of the product.
6.102 CONVENTION $\prod_{x\in\emptyset} f(x) = 1$ (the empty product is 1)
6.104 DO Observe the following special cases of this convention: $0!=1$, $(\forall a\in\rrr)(a^0=1)$. In particular, $0^0=1$.
6.106 OBSERVE: This convention is consistent with our counting result that $\left|B^A\right|=|B|^{|A|}$ since the set $\emptyset^{\emptyset}$ contains exactly one function (the empty function).
6.109 DO Prove: If $A,B$ are disjoint finite sets and $\Omega=A\dot\cup B$ then $$\prod_{x\in\Omega} f(x) = (\prod_{x\in A} f(x))\cdot(\prod_{x\in B} f(x))\,.$$ Observe that the proof requires Convention 6.102. This shows that 6.102 is the only reasonable way to define the empty product.
6.115 DO Define/verify the product versions of items 6.52--6.56.
6.118 DO Let $\Pi=\{B_1,\dots,B_k\}$ be a partition of the finite set $\Omega$. Verify: $$ |\Omega| = \sum_{i=1}^k |B_i|\,. $$
6.120 DEF (base-$b$ number system) Let $b\in \nnn$, $b\ge 2$.
The digits in the base-$b$ number system are the numbers
$0,1,\dots,b-1$. (So there are $b$ digits.)
Then every non-negative integer $n$ can be uniquely written in the base-$b$
number system, i.e., there exists a unique sequence $a_0,\dots,a_k$ of
base-$b$ digits such that
$$n = \sum_{i=0}^k a_i b^i$$
This expression is the base-$b$ representation of $n$.
This representation is unique except for the leading zeros. (The leading
zeros are those $a_i$ for which $a_i=a_{i+1}=\dots=a_k=0$. So if $a_k\neq 0$
then there are no leading zeros.) So if we delete the leading zeros,
the representation is unique. The $a_i$ are called the base-$b$ digits
of $n$. If there are no leading zeros, we say that $n$ has $k+1$ digits
in base $b$.
Representation of zero.
If $n=0$ then all digits are $0$. So
the representation without leading zeros is the empty sum.
In this case we take $k=-1$ and we say $0$ has $0$ digits in base $b$.
6.121 Familiar examples: decimal (base-10), binary (base-2), octal (base-8) representations. We write $\overline{a_ka_{k-1}\dots a_0}_{(b)}$ to express the base-$b$ representation of $n$.
6.122 DO Prove the existence and uniqueness of base-$b$ representation.
6.123 ORD (3 points, due Mon, Oct 25) Express the decimal number 347 in binary, octal, base-7, and base-11. In base 11, the digits are $0,1,\dots,9,A$. (The value of $A$ is $10$.) No proof required.
6.124 ORD (2+2 points, due Mon, Oct 25) Let $k\ge 0$. Determine the (a) smallest and (b) greatest $k$-digit number in base-$b$. Your answer should be a simple formula, not a representation in any base. No proof required.
6.125 ORD (4 points, due Mon, Oct 25) Let $b\ge 2$. Let
$n$ be a non-negative integer and let $s$ be the sum of its base-$b$
digits. Prove: $n\equiv s \pmod{b-1}$.
Note, in particular, that $b-1\mid n \Leftrightarrow b-1\mid s$.
This is the familiar "divisibility by 9 rule" in decimal.
For instance, 8352 (decimal) is divisible by 9,
because 8+3+5+2 = 18 is divisible by 9.
6.126 ORD (5 points, due Mon, Nov 1) Let $b\ge 2$. Let
$n$ be a non-negative integer and let $t$ be the alternating sum
of its base-$b$ digits, i.e.,
$t = a_0-a_1+a_2-\dots+(-1)^k a_k$ where the $a_i$ are the
base-$b$ digits of $n$. Prove:
$n\equiv t \pmod{b+1}$.
Note, in particular, that $b+1\mid n \Leftrightarrow b+1\mid t$.
This is the familiar "divisibility by 11 rule" in decimal.
For instance, 8052 (decimal) is divisible by 11,
because -8+0-5+2 = -11 is divisible by 11.
6.127 Bonus (8 points, due Mon, Oct 25) (instructor's mother's rule)
At age 6, the multiplication table did not come easily to me.
I had particular difficulty learning that $7\times 8=56$.
My mother, a teacher of first and second grades in elementary school,
pointed out to me that this equation can be written
as $56=7\times 8$, and that certainly helped.
The trouble was that this pattern did not generalize, for instance,
$34\neq 5\times 6$. There was only one more instance where the
pattern worked: $12=3\times 4$.
This was of course all in decimal. The question to you is, determine
all occurrences of this pattern for every base $b\ge 2$. So you need
to find all values of $b\ge 2$ and $0\le a\le b-4$ such that
the value of the base-$b$ number $\overline{a(a+1)}_{(b)}$ is
equal to the product $(a+2)\times (a+3)$. Prove your answer.
6.130 DEF Let $R\subseteq \Omega\times\Omega$ be a relation on the set $\Omega$. We say that $R$ is an equivalence relation if
6.132 DO Observe:
(a) The divisibility relation on $\zzz$ is reflexive
$(x\mid x)$ and transitive but not symmetric:
$4\mid 12$ but $12\nmid 4$, so divisibility is not
an equivalence relation.
(b) The ordering relation "$\le$" on $\rrr$ is reflexive
$(x\le x)$ and transitive but not symmetric:
$4\le 6$ but $6\not\le 4$, so order is not an equivalence
relation on $\rrr$.
6.135 Examples of equivalence relations
6.140 DEF Given a partition $\Pi=\{B_1,\dots,B_k\}$ of the set
$\Omega$, define the relation $\sim_{\Pi}$ on $\Omega$
as follows: for $a,b\in \Omega$ we say that
$a \sim_{\Pi} b$ if $(\exists i)(a,b\in B_i)$, i.e., $a$ and $b$ belong
to the same block of the partition.
LaTeX for the tilde symbol $\sim$ is "\sim".
6.142 DO (Partitions vs. equivalence relations) Prove: $\sim_{\Pi}$ is an equivalence relation on $\Omega$. We call $\sim_{\Pi}$ the equivalence relation defined by the partition $\Pi$.
6.144 DO (uniqueness of partition) Prove: Different partitions define different equivalence relations. In other words, let $\Pi$ and $\Psi$ be two partitions of the set $\Omega$. Prove: if $\sim_{\Pi} = \sim_{\Psi}$ then $\Pi = \Psi$.
6.150 Fundamental Theorem of Equivalence Relations Let $R$ be an equivalence relation on the set $\Omega$. Then $R$ arises from a partition. In other words, $(\exists\text{ partition }\Pi\text{ of }\Omega)(R = \sim_{\Pi})$.
6.152 COMMENT This partition is unique by 6.144. So every equivalence relation uniquely defines a partition.
6.155 DEF The blocks of $\Pi$ are called the equivalence classes
of the equivalence relation $R$.
With these classes in mind, we can informally summarize the Theorem
as saying that equivalence relations classify.
6.157 COMMENT: The role of equivalence relations in concept formation.
This result is fundamental to understanding how intelligent
beings create concepts such as numbers, colors, etc. Natural numbers
arise from the observation that certain pairs of sets have a bijection
between them, and this relation among sets is an equivalence relation.
Members of one of its equivalence classes are "three trees," "three mountain
peaks," "three goats," etc., giving rise to the number "3". Each
equivalence class corresponds to a natural number.
What intelligent beings recognize is not the word "three" but
the equivalence class named "three" in English and "san" in Chinese
etc. The names are different across cultures but the equivalence
relation is the same, and so are the equivalence classes.
This equivalence relation is the concept
of natural numbers. Similarly, the concept of "color"
arises from the relation among objects of having the same color,
and while the names of the colors differ across cultures, the
equivalence relation does not.
Concept formation being the key function of (natural or
artificial) intelligence, arguably,
the Fundametal Theorem of Equivalence Relations could be
called the Fundamental Theorem of Intelligence.
As the example of colors shows, in practical concept forming,
there are borderline (hard to classify) cases. The problem
that intelligence needs to solve is, given a relation $R$ that
is not quite an equivalence relation, find an equivalence
relation that is "close" to $R$. There are interesting methods
that give often quite reasonable solutions to this problem using
linear algebra.
6.160 PROOF of the Fundamental Theorem of Equivalence Relations.
For $a\in \Omega$ let $[a]=\{b\in \Omega\mid a\sim b\}$.
We refer to this as the "candidate equivalence class of $\Omega$."
We need to prove that the candidate equivalence classes partition $\Omega$
and that $\sim$ corresponds to that partition. The proof goes through
a series of observations.
6.160(a) $a\in [a]$ (by reflexivity)
6.160(b) If $a\in [b]$ then $[a]\subseteq [b]$ (by transitivity)
6.160(c) If $a\in[b]$ then $b\in [a]$ (by symmetry)
6.160(d) If $b\in[a]$ then $[a]=[b]$ (from (b) and (c))
6.160(e) $[a]$ and $[b]$ are either disjoint or equal (from (d))
6.160(f) $\bigcup_{a\in \Omega} [a] = \Omega$ (from (a)).
6.162 DO Prove 6.160(a)--(d).
6.165 ORD (5 points, due Mon, Oct 25) Prove 6.160(e). Use 6.160 (a)--(d).
6.170 DEF The $n$-th Bell number $B(n)$ is defined as the number of partitions of $[n]$.
6.172 DO Verify: $B(0)=1$, $B(1)=1$, $B(2)=2$, $B(3)=5$.
6.175 ORD (5 points, due Mon, Nov 1) Prove: $B(n)\le n^n\,.$ Give a very simple surjective solution: find a surjection that maps the set $[n]^{[n]}$ (the set of $[n]\to [n]$ functions) onto the set of partitions of $[n]$. Give a clear definition of your surjection. Do not prove that it is indeed a surjection.
6.180 Bonus (6 points, due Mon, Nov 1)
Prove: $B(n)\le n!$
Find an injective solution: give an injection from the set of
partitions of $[n]$ to the set of permutations of $[n]$.
Give a clear definition of your injection. Do not prove
that it is indeed an injection.
A solution to this problem does not earn you credit for 8.60; you
need to separately execute the instruction in 8.60 to earn credit
for that problem.
6.184 Bonus (6 points, due Mon, Nov 1) Prove: If $0\le k\le n$ then $B(n) \ge k^{n-k}$. Give an injective solution: construct an injection from the set $[k]^{[n-k]}$ to the set of partitions. What you need to do is assign a partition to each function $f:[n-k]\to [k]$ such that distinct functions do not collide (they are not assigned the same partition). Give a clear definition of your injection. Do not prove that it is indeed an injection.
More to follow. Please check back later. Please report any errors.
Class 5, Tue 10-12 Greatest common divisor
5.03 ORD (3 points) Let $A,B$ be finite sets, $|A|=k$ and $|B|=\ell$. Count the relations $R\subseteq A\times B$. Your answer should be a simple formula in terms of $k$ and $\ell$. No proof required.
5.05 DEF The Fibonacci sequence $F_0,F_1,F_2,\dots$ is the sequence $0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,\dots$. The sequence is defined by the initial values $F_0=0, F_1=1$ and the recurrence $F_n=F_{n-1}+F_{n-2}$ $(n\ge 2)$. The members of this sequence are called Fibonacci numbers.
5.08 ORD (3+5 points) (a) Prove:
$(\forall n\in \nnn_0)(F_n < 2^n)$.
(b) $(\forall n\ge 7)(F_n > 2^{n/2})$.
Give proofs by induction using the definition of the Fibonacci sequence.
Do not use any more advanced results not proved in class.
If in doubt, send me email.
UPDATE (10-15 11am): Added last three sentences.
5.12 ORD (4 points) Prove: Consecutive Fibonacci numbers are relatively prime, i.e., $(\forall n\ge 0)(\gcd(F_n, F_{n+1})=1)$.
5.16 CH Let $k,\ell \ge 0$. Prove: if $k\mid \ell$ then $F_k \mid F_{\ell}$. Example: $F_5=5$ and $F_{10}=55$, so $F_5\mid F_{55}$.
5.18 CH Let $k,\ell \ge 0$ and $d=\gcd(k,\ell)$. Prove: $\gcd(F_k, F_{\ell})=F_d$.
5.22 Bonus (9 points) Let $k,\ell \ge 0$ and $d=\gcd(k,\ell)$. Prove: $\gcd(2^k-1,2^{\ell}-1)=2^d-1$.
5.26 ORD (4 points) Let $A$ and $B$ be finite sets.
Let $|A|=k$ and $|B|=\ell$. Fill in the blank:
"$(\forall f\in B^A)(f$ is a surjection$)$ if and only if BLANK."
Your answer should be a simple f.o. formula in the model
$(\zzz;+,\times,0,1,\le)$. No proof required.
UPDATED 10-14 at 10:25am. The previous version did not require a
f.o. formula.
5.30 NOTATION Let $A,B$ be sets. Then $A\setminus B=\{a\in A\mid a\notin B\}$. LaTeX: A\setminus B.
5.32 (a) ORD (2 points) Let $\nnn_0$ denote the set of non-negative integers. Let $f:\nnn_0\times\nnn_0\times\nnn_0\to \nnn_0$ be the function defined by $f(x,y,z)=x^2+y^2+z^2$. Find the smallest positive integer that does not belong to $\range f$. Prove your answer. (A correct solution to 5.35 (b) is not accepted as a solution to this problem.)
5.32 (b) Bonus (7 points) Prove that the set $\nnn_0 \setminus \range(f)$ is infinite.
5.34 Four-square Theorem (Joseph Louis Lagrange, 1770) $(\forall n\in \nnn_0)(\exists x,y,z,w\in\nnn_0)(n=x^2+y^2+z^2+w^2)$.
5.36 DO Write 28 as a sum of four squares.
5.41 STUDY the Euclid's algorithm handout. Solve the exercises in the handout.
5.45 NOTATION We shall write $\Div(n)$ to denote the set of divisors of the integer $n$. (This is not common notation, we are using it for this class only.)
5.48 DO Verify: $\Div(1)=\{\pm 1\}$, $\Div(4)=\{\pm 1, \pm 2, \pm 4\}$, $\Div(14)=\{\pm 1,\pm 2, \pm 7, \pm 14\}$.
5.50 DO $\Div(0)=\zzz$.
5.52 DO $\Div(a)=\Div(-a)$
5.55 DO Prove: $a\mid b \ \Leftrightarrow\ \Div(a)\subseteq\Div(b)$. State, what property of divisibility is expressed by the $\Rightarrow$ direction of this statement. (Answer to the last question: transitivity. Work it out, why.)
5.58 DEF We say that $d$ is a common divisor of $a$ and $b$ if $d\mid a$ and $\mid b$.
5.60 NOTATION $\Div(a,b)=\Div(a)\cap\Div(b)$.
5.62 DO $\Div(a,b)$ is the set of common divisors of $a$ and $b$.
5.64 DO $\Div(a,b)=\Div(b,a)$.
5.66 DO $\Div(a,b)=\Div(\pm a,\pm b)$. (This statement
is shorthand for the following:
$\Div(a,b)=\Div(-a,b)=\Div(a,-b)=\Div(-a,-b)$.)
5.70 DO $\Div(a,0)=\Div(a)$.
5.72 ORD (6 points) ("Euclid's gcd Lemma")
Prove: $(\forall a,b)(\Div(a,b)=\Div(a-b,b))$.
Remember: to prove that two sets, $A$ and $B$, are equal, you have to
show that they mutually contain each other: $A\subseteq B$ and
$B\subseteq A$. Another way of looking at it: $A=B$ means
$(\forall x)(x\in A \Leftrightarrow x\in B)$.
5.75 ORD (4+4 points) True or false? Prove your answer.
(a) $(\forall a,b)(\Div(a,a+b)\subseteq\Div(a,a+2b)$.
(b) $(\forall a,b)(\Div(a,a+b)\supseteq\Div(a,a+2b)$.
5.80 DEF We say that $d$ is
a greatest common divisor (gr.c.d.)
of $a$ and $b$ if
(a) $d\mid a$ and $d\mid b$ ($d$ is a common divisor)
(b) $(\forall e)((e\mid a \wedge e\mid b)\Rightarrow e\mid d))$
($d$ is a common multiple of all common divisors)
Note the indefinite article "a" in the definition.
Indeed, as we shall see, the gr.c.d. is not unique (see 5.86).
But its absolute value is unique (see 5.88).
5.84 DO Prove: $d$ is a gr.c.d. of $a$ and $b$ if and only if $\Div(a,b) = \Div(d)$.
5.85 DO Show that $a$ is a gr.c.d. of $a$ and $0$.
5.86 DO If $d$ is a gr.c.d. of $a$ and $b$ then $-d$ is also a gr.c.d. of $a$ and $b$.
5.88 DO If both $d$ and $f$ are gr.c.divisors of $a$ and $b$ then $f=\pm d$.
5.90 NOTATION If $d$ is a gr.c.d. of $a$ and $b$ then we write $\gcd(a,b)=|d|$. The preceding exercise shows that this notation is unique: every pair of integers has at most one $\gcd$. It remains our job to prove that every pair of integers has at least one gr.c.d.
5.93 DO Prove: $\gcd(a,0)=|a|$.
5.95 DO Prove: $\gcd(a,a)=|a|$.
5.100 THEOREM (Euclid) Every pair of integers has a $\gcd$.
5.102 DO Prove the Theorem.
We need to show that any given $a,b\in\zzz$ have a gr.c.d.
First show the WLOG $a,b\ge 0$. Moreover, if $a=0$ or $b=0$
then we already know that a gr.c.d. exists (5.85). So we may assume
$a,b > 0$. We proceed by induction on $a+b$.
Inductive Hypothesis: If $a',b'\ge 0$ and $a'+b' < a+b$
then $\gcd(a',b')$ exists, i.e., there exists $d$ such that
$\Div(d)= \Div(a',b')$.
Inductive step. WLOG $a\ge b$. (Why?) We know that
$\Div(a,b)=\Div(a-b,b)$. Let $a'=a-b$ and $b'=b$.
Let us apply the Inductive Hypothesis to $(a',b')$.
So $(\exists d)(\Div(d)= \Div(a',b')$. But
$\Div(a',b')=\Div(a-b,b)$ (Euclid's gcd Lemma), so we
are done.
QUESTION: Where did we use the assumption that $a,b > 0$?
5.104 Example. To find $\gcd(-72,28)$, we repeatedly apply Euclid's gcd Lemma: $\Div(-72,28)=\Div(72,28)=\Div(44,28)=\Div(16,28)= \Div(28,16)=\Div(12,16)=\Div(16,12)=\Div(4,12)= \Div(12,4)=\Div(8,4)=\Div(4,4)=\Div(0,4)=\Div(4)$. Therefore $\gcd(-72,28)=4$.
5.106 DO Following the method of Example 5.104, how many steps (applications of Euclid's gcd Lemma) does it take to compute the gcd of $10^6$ and $1$ ? The answer shows that this method is not very efficient. We shall speed it up.
5.110 Division Theorem.
Let $a,b\in\zzz$ and $b\neq 0$. Then there exist $q,r\in\zzz$
such that $a=bq+r$ and $0\le r < |b|$.
$q$ is the integer quotient and $r$ is the remainder.
5.112 Examples. $a=109, b=17$: $109=17\cdot 6+7$.
$a=-109, b=17$: $-109 = 17\cdot (-7)+10$.
5.114 DO Observe: If $b\neq 0$ then $b\mid a$ if and only if $r=0$ in the Division Theorem.
5.116 DO Prove the Division Theorem. First show that WLOG $a\ge 0$. (This is not completely evident!) Then fix $b$ and prove the result by induction on $a$.
5.118 ORD (uniqueness of $q$ and $r$) (6 points) Prove: given $a,b\in\zzz$ with $b\neq 0$, there is only one (not more than one) pair $(q,r)$ that satisfies the conditions of the Division Theorem.
5.120 DO Review the integer division algorithm. Show that it efficiently computes $q$ and $r$.
5.130 STUDY Euclid's algorithm from the handout.
5.132 Bonus (9 points, due Oct 25) Prove: if $b >0$ and $b$ has $n$ binary digits then Euclid's algorithm to find $\gcd(a,b)$ takes at most $2n$ rounds. (One round is one execution of the Division Theorem, which also means one iteration of the while loop.)
More to follow. Please check back later. Please report any errors.
Class 4, Thu 10-07 Sumset. Relations, functions.
Injections, surjections, bijections. The Pigeon Hole Principle.
Counting $A\to B$ functions. Counting injections.
Naive probability. Birthday paradox.
All solution are due Monday, Oct 11, 23:00, except where
otherwise stated.
4.01 LaTeX for the letter $\ell$ is \ell. Avoid using $l$ as the name of variables, use $\ell$ instead, because $l$ can be confused with $t$, $I$, $1$.
4.02 NOTATION. Let $n$ be a non-negative integer. We write $[n]$ to denote the set $[n]=\{1,2,\dots,n\}$. For instance, $[4]=\{1,2,3,4\}$, $[1]=\{1\}$, $[0]=\emptyset$.
4.03 DO $(\forall n\ge 0)(|[n]|=n)$.
4.04 REVIEW the definition of a sumset (DEF 1.11).
4.05 DO If $k,\ell \ge 1$ then $|[k]+[\ell]|=k+\ell -1$.
4.06 ORD (5 points) Let $k,\ell \ge 1$.
Find sets $A,B\subseteq \zzz$
such that $|A|=k$, $|B|=\ell$, $|A+B|=k+\ell -1$, and neither $A$,
nor $B$ contain consecutive integers.
UPDATED 10-11 at 18:50. The previous version erroneously
stated "$k,\ell \ge 0$". Thank you to the student who pointed
out this mistake.
4.08 ORD (3 points) Let $A\subseteq\zzz$.
Determine the sumset $A+\emptyset$.
Your answer should be very simple. Prove your answer.
WARNING (10-1 19:00). An earlier problem stated the answer to this
question. So you need to provide a (short) proof, otherwise
nothing would remain from this problem.
4.12 DEF Recall that a relation between the sets $A$ and $B$ is a subset $R\subseteq A\times B$. We call $A$ the domain and $B$ the codomain of $R$.
4.15 DEF Let $A$ and $B$ be sets. A function $f:A\to B$ is a relation with domain $A$ and codomain $B$, with the following property:
4.16 NOTE ON TERMINOLOGY. The term "unique" means there is only one. This is the traditional meaning of this term in mathematics. For instance, we talk about unique prime factorization of positive integers, meaning they have only one prime factorization. We say that a differential equation has a unique solution if there is only one function that satisfies the equation. This usage differs from recently introduced usage in Computer Science and commerce where one talks about "unique members of a list" (unique callers, unique customers) meaning the distinct members of the list. "Distinct" is the traditional term for this concept, and this is the term we shall use in this course. So we shall say that the list $[a,c,b,c,a]$ has three distinct members, namely $\{a,b,c\}$ (instead of "three unique members"). The element distinctness problem is the algorithmic problem that asks to determine whether all elements of a list are distinct.
4.18 DO Prove that a relation $f\subseteq A\times B$ is a
function if and only if it satisfies the following two conditions:
(a) $(\forall a\in A)(\exists b\in B)((a,b)\in f)$
(b) $(\forall a\in A)(\forall b_1, b_2\in B)
((a,b_1)\in f \wedge (a,b_2)\in f) \Rightarrow (b_1=b_2))$
4.24 DO
Consider the following relations between the sets $[5]$ and $[3]$.
(a) $R=\{(1,3), (4,1), (3,1), (5,3), (2,1)\}$
(b) $S=\{(1,3), (4,1), (5,3), (2,1)\}$
(c) $T=\{(1,3), (4,1), (5,3), (1,2), (3,1), (2,2)\}$
(d) $U=\{(1,3), (4,1), (5,3), (1,2), (2,2)\}$
Prove that $R$ is a function but $S,T,U$ are not functions.
For each of $S,T,U$ determine, which of the two conditions in
Exercise 4.18 are violated.
4.25 NOTATION. We denote the set of $A\to B$ functions by $B^A$. WARNING: The domain goes into the exponent, the codomain in the base! There is a reason for this; see the next exercise.
4.27 DO Prove: $\left|B^A\right|=|B|^{|A|}$.
So, for instance, the number of functions $[n]\to [3]$ is $3^n$.
This function grows exponentially as a functions of $n$.
On the other hand, the number of functions $[3]\to [n]$ is $n^3$.
This function grows polynomially as a functions of $n$.
We shall study rates of growth later.
4.30 DEF Let $f\in B^A$ be a function. Let $a_1, a_2\in A$, $a_1\neq a_2$. We say that $a_1$ and $a_2$ collide if $f(a_1)=f(a_2)$. In this case, we call the unordered pair $\{a_1,a_2\}$ a collision. Let us write $\coll(f)$ for the number of collisions of $f$.
4.33 DO Let $f\in B^A$ be a function. Let $|A|=n$. (a) Prove: $\coll(f)\le n(n-1)/2$. (b) Prove that $\coll(f)=n(n-1)/2$ if and only if $f$ is a constant function, i.e., $(\exists b\in B)(\forall a\in A)(f(a)=b)$.
4.38 DEF We call the function $f:A\to B$ an injection or an injective function if $\coll(f)=0$.
4.40 DO Observe: the function $f\in B^A$ is injective if and only if $(\forall x,y\in A)(f(x)=f(y) \Rightarrow x=y)$.
4.42 DO Observe: there exists an $A\to B$ injection if and only if $|B| \ge |A|$. The "only if" part is a famous principle we state next.
4.44 DO (Pigeonhole principle) If $|A| > |B|$ and $f\in B^A$ then $\coll(f)\ge 1$ ($f$ is not injective).
4.46 Bonus (10 points, due Oct 18) Let $n\ge 1$ and let $S\subseteq [2n]$ be a subset of size $|S|\ge n+1$. Prove: $(\exists a,b\in S)(a\neq b$ and $a\mid b)$.
4.47 ORD (4 points) Prove that in the previous exercise,
the lower bound $|S|\ge n+1$ is tight for every $n\ge 1$,
i.e., the conclusion fails if we permit $S$ to have $n$ elements.
So what you need to do is the following. For every $n\ge 1$, find a subset
$T_n\subseteq [2n]$ such that $|T_n|=n$ and
$(\forall a,b\in T_n)(a\mid b \Rightarrow a=b)$.
4.50 DO Let $|A|=k$ and $|B|=\ell$.
Count the $A\to B$ injections.
Show that the number of $A\to B$ injections is
$$ \ell(\ell-1)\cdots(\ell-k+1)\,.
\qquad\qquad\qquad\qquad\qquad (*)$$
Note that this product has $k$ terms.
Formula $(*)$ is valid even if $\ell < k$, in which case the
number of injections is zero. Indeed, if $\ell < k$, then one
of the terms in $(*)$ will be zero. (DO: Verify!)
4.51 DO Let $|A|=k$ and $|B|=\ell$. Assume $\ell \ge k$.
Prove that the number of $A\to B$ injections is $\ell!/(\ell-k)!$.
Note that this formula makes no sense if $\ell < k$ because the
denominator will be the factorial of a negative number which is
undefined.
Expression $(*)$ is also preferable to the expression $\ell!/(\ell-k)!$
when $k$ is small compared to $\ell$ because the product $(*)$ has
only $k$ terms while this factorial quotient has a total of $2\ell-k$
terms.
4.55 DEF (naive probability) Let us perform an experiment that has $k$ possible outcomes, $e_1,\dots,e_k$, each of them equally likely. We say we choose/get an outcome at random. (Example: we roll a die; the set of possible outcomes is $[6]$.) We consider some of these outcomes favorable; let $\ell$ denote the number of favorable outcomes. Then we say that the probability of a favorable outcome is $\ell/k$ ("number of good cases divided by the number of all cases").
4.57 DO We roll a die. What is the probability that the outcome is a prime number? (Your answer should be $1/2$. Reason this answer.)
4.60 DO Let $q(k,\ell)$ denote the probability that a random function $f: [k]\to [\ell]$ is injective. (So we choose $f\in [\ell]^{[k]}$ "at random" from this set of $\ell^k$ functions.) Prove: $$ q(k,\ell) = \left(1-\frac{1}{\ell}\right)\left(1-\frac{2}{\ell}\right) \cdots \left(1-\frac{k-1}{\ell}\right)\,. $$ This exercise prepares us for the discussion of the birthday paradox. Note that $q(k, 365)$ is the probability that among $k$ students in a class, no two have the same birthday. (We exclude leap years, and we assume that every student has the same chance of having any of the 365 birthdays.) It turns out that $q(23,365)\approx 0.493$, so the probability that among 23 students in a class, there will be two with the same birthday, is approximately $0.507$, greater than $1/2$. This is surprising given how few students make it more likely than not that two of them have the same birthday.
4.75 DEF Let $f\in B^A$. The range of $f$ is the set $$ \range(f) = \{f(a) \mid a\in A\}\,.$$ This is the set of values taken by $f$.
4.76 DO Show: $(\forall b\in B)(b\in \range(f) \Leftrightarrow (\exists a\in A)(f(a)=b))$.
4.78 DO Determine the range of each of the following functions:
(a) $f: \rrr\to\rrr$ defined by $f(x)=x^2$. (This definition is also
expressed as $f: x\mapsto x^2$, where the $\mapsto$ symbol reads "maps to".
In LaTeX: \mapsto.)
(b) $g: [1,\infty) \to \rrr$ defined by $g: x\mapsto 1/x$.
(c) $h: \zzz\to \zzz$ defined by the following statement:
$h(x)$ is the smallest prime number $\ge x$.
[Part (c) was updated 10-09 at 18:40. The previous version
said "$h(x)$ is the greatest prime number $\le x$" but this
$h$ does not work, it is not a function. Why?]
4.80 DO $\range(f) \subseteq \codomain(f)$.
4.82 DO $|\range(f)| \le |\domain(f)|$.
4.85 DEF We call the function $f:A\to B$ a
surjection or a surjective function if
$\range(f) = \codomain(f)$.
In this case we say that $f$ maps $A$ onto $B$.
4.87 DO Observe that the function $f\in B^A$ is surjective if and only if $(\forall b\in B)(\exists a\in A)(f(a)=b)$. In other words, all elements of $B$ occur as values of $f$.
4.89 DO If $f\in B^A$ is surjective then $|B|\le |A|$.
4.91 ORD (4 points) Let $A$ and $B$ be finite sets, $|A|=k$, $|B|=\ell$. Fill in the blank: "A surjection $A\to B$ exists if and only if BLANK." Your answer should be a f.o. formula $\vf$ in the model $(\zzz;+,-\times,0,1,\le)$ (see Ex. 3.07 (2)). See 3.11 and 3.12 on how to build a formula. (Make sure to put parentheses where needed for unambiguous parsing.) Prove your answer. You can use the preceding exercise (4.89).
4.93 DO (Tight upper bound on the sumset)
Let $A,B$ be finite subsets of $\zzz$. Prove:
$|A+B| \le |A|\cdot |B|$.
Hint. Consider the function $h: A\times B\to \zzz$
defined by $h(a,b) = a+b$. Observe that $A+B=\range(h)$.
Combine this observation with the fact that $|A\times B|=|A|\cdot |B|$.
Use Exercise 4.82.
4.95 ORD (6 points)
Let $A,B\subseteq \zzz$ with $|A|=k$ and $|B|=\ell$.
Prove that the upper bound $|A+B|\le k\ell$ is tight for all $k,\ell\ge 0$.
So, for every $k,\ell$ you need to construct sets $A$ and $B$ such that
$|A|=k$, $|B|=\ell$ and $|A+B|=k\ell$. Make your example simple to state and
simple to verify. Simplicity counts.
4.98 Bonus (4+4 points) Let $A\subseteq\zzz$ with $|A|=k$.
(a) Prove: $|A+A| \le k(k+1)/2$. Model your proof after Exercise 4.93.
Use Ex. 4.82.
(b) Prove that this upper bound is tight for every $k\ge 0$.
4.100 Bonus (8+5 points, due Oct 18)
Let $A\subseteq\zzz$ with $|A|=k$.
Give a tight upper bound on the size of $|A+A+A|$. Your answer should
be a simple closed-form expression in terms of $k$. Prove that your upper
bound is (a) correct and (b) tight for every $k$.
4.110 DEF A function $f\in B^A$ is called a bijection if $f$ is both injective and surjective.
4.112 DO Prove: the function $f:A\to B$ is a bijection if and only if its converse $f^{\op}$ (see Ex. 2.28) is also a function. In this case we call $f^{\op}$ the inverse of $f$ and denote it by $f^{-1}$.
4.114 ORD (2 points) Find a bijection from the set $\rrr^+$ (positive real numbers) to the real numbers in the open interval $(0,1)$. Describe your bijection with a simple formula. Argue that your function is bijective by stating its inverse. You do not need to prove that your stated inverse is indeed the inverse. The entire solution should fit on one line.
4.118 DO Let $A,B$ be finite sets. A bijection $A\to B$ exists if and only if $|A|=|B|$.
4.122 ORD (3 points) Let $A$ be a finite set. Recall that $\calP(A)$ denotes the powerset of the set $A$. Find a simple bijection between $\calP(A)$ and the set $[2]^A$ of $A\to [2]$ functions. Argue that your function is bijective by stating its inverse. You do not need to prove that your stated inverse is indeed the inverse. Use this bijection to prove that $|\calP(A)|=2^n$ where $n=|A|$.
4.125 ORD (5 points, due Oct 18) Let $O_n$ denote the set of odd subsets of $[n]$ (subsets of odd size), and $E_n$ the set of even subsets. For all $n\ge 1$, construct a bijection $f_n:O_n \to E_n$. Argue that your function is bijective by stating its inverse. You do not need to prove that your stated inverse is indeed the inverse. The definition of $f_n$ should be very simple.
4.130 ORD (4 points) Count the $[n]\to [2]$ surjections. Your answer should be a closed-form expression (no summation sign of dot-dot-dots). Briefly reason your answer.
4.133 Bonus (7 points, due Oct 18) Count the $[n]\to [3]$ surjections. Your answer should be a simple closed-form expression (no summation sign or dot-dot-dots). Prove your answer.
4.150 DEF Let $A,B,C\subseteq\zzz$. We say that $C$ is the direct sum of $A$ and $B$ if every element of $C$ can uniquely be written as the sum of an element of $A$ and an element of $B$. In other words, $C\subseteq\zzz$ is the direct sum of $A,B\subseteq\zzz$ if the following holds: $(\forall c\in C)(\exists! a\in A, b\in B)(c=a+b)$. We denote this circumstance by $C=A\oplus B$. (LaTeX: A \oplus B.)
4.152 DO If $C=A\oplus B$ then $C=A+B$ but not conversely.
4.154 DO Let $A,B$ be finite subsets of $\zzz$. Prove: $A+B=A\oplus B$ if and only if $|A+B|=|A|\cdot |B|$.
4.160 NOTATION $\nnn_0=\{0,1,2,\dots\}$ denotes the set of non-negative integers.
4.161 ORD (6 points, due Oct 18) Find $A, B\subseteq \nnn_0$ such that $|A|=100$ and $\nnn_0=A\oplus B$.
4.165 Bonus (12 points, due Oct 18) Find two infinite sets $A, B\subseteq \nnn_0$ such that $\nnn_0 = A\oplus B$.
Class 3, Tue 10-05 Brief informal introduction to first-order logic. Relations, functions. Counting $A\to B$ functions.
3.01 Greek letters. We shall use a number of lower case
Greek letters in the following sequence of exercises.
Here are the LaTeX codes for these and some other l.c. Greek letters
frequantly used in mathematics:
$\alpha$ \alpha, $\beta$ \beta,
$\gamma$ \gamma, $\delta$ \delta,
$\epsilon$ \epsilon $\varepsilon$ \varepsilon,
$\zeta$ \zeta, $\eta$ \eta,
$\theta$ \theta, $\vartheta$ \vartheta,
$\kappa$ \kappa, $\lambda$ \lambda, $\mu$ \mu,
$\nu$ \nu, $\xi$ \xi,
$\pi$ \pi, $\rho$ \rho, $\sigma$ \sigma,
$\tau$ \tau, $\phi$ \phi, $\varphi$ \varphi,
$\chi$ \chi, $\psi$ \psi, $\omega$ \omega.
The LaTeX code follows the names of these letters, e.g.,
$\lambda$ is called "lambda", except the variants don't have a
different name, they represent the same letter of the Greek alphabet,
e.g., both $\theta$ and $\vartheta$ are called "theta".
3.05 DEF A model is a set equipped with some operations and relations. The names of these operatinos and relations form the language of the model. We shall always tacitly assume that the "equality" relation ("$a=b$") is part of the language.
3.07 Examples of models: WARNING: this list was updated
on 10-8 at 14:10. The notion of "language" was added.
(1) $(\zzz; +,-,\times,0,1)$: the set of integers
with the binary operations of addition, subtraction, multiplication,
and the nullary operations ("constants") $0$ and $1$.
(2) $(\zzz; +,-,\times,0,1,\le)$: the same as before but we added
the "order" relation ($\le$) to the language. This is then a different
model.
(3) $(\zzz; +,-,\times,0,1,\le,\mid)$: the same as before but we added
the "divisibility" relation to the language. This is again a different
model.
(4) $(\rrr; +,-,\times,0,1)$: the set of real numbers with the
binary operations of addition, subtraction, multiplication,
and the constants $0$ and $1$.
(5) $(\rrr; +,-,\times,0,1,\eee,\pi)$: the same as before, with two
more constants, $\eee$ and $\pi$, added to the language.
(6) $(\rrr; +,-,\times,0,1,\text{absolute value},\le )$: the real numbers
with the binary operations of addition, subtraction, multiplication,
the unary operation "absolute value" ($x\mapsto |x|$"), the nullary
operations $0$ and $1$, and the binary relation $\le$ (order).
(7) $(\rrr; +,-,\times,0,1,\sqrt{|x|})$: the real numbers
with the binary operations of addition, subtraction, multiplication,
the unary operation "square root of the absolute value"
($x\mapsto \sqrt{|x|}$"), and the nullary operations $0$ and $1$.
(8) $(\{0,1\}; \wedge, \vee, \neg, 0, 1)$: the Boolean model:
the set $\{0,1\}$ with the binary Boolean operations $\wedge$ ("AND")
and $\vee$ ("OR"), the unary Boolean operation of negation ($\neg$),
and the nullary Boolean operations $0$ and $1$. (The meaning of
$0$ is "FALSE" and the meaning of $1$ is "TRUE".)
3.10 DEF An atomic formula is a relation symbol that
connects operations performed on variables. It does not
contain any logical connectives or quantifiers. When we assign
values from a model to the variables, the atomic formula takes
the value "TRUE" or "FALSE".
Examples: "$a+b < c^2$",
"$y = x^2-5$", "$m\mid a-b$", "$1\neq 0$".
(The quotation marks are not part of the formula; I am putting
them there only to have clear delimiters to show where a
formula begins and ends.)
3.12 DEF Inductive definition of first-order formulas (f.o. formulas):
3.15 DEF Every f.o. formula $\vf$ is associated with its
set of free variables, $\free(\vf)$, defined inductively as
follows.
(a) If $\vf$ is an atomic formula then $\free(\vf)$ consists of all
variables mentioned in $\vf$.
Examples: $\free(a+b < c^2) = \{a,b,c\}$,
$\free(1\neq 0) = \emptyset$ (empty set)
(b) $\free(\neg(\vf))=\free(\vf)$
(c) If $\Box$ denotes a logical connective then
$\free(\vf \Box \psi)=\free(\vf)\cup \free(\psi)$
Example: $\free(\vf\to\psi)=\free(\vf)\cup \free(\psi)$
(d) If $Q$ is a quantifier and $z$ is a variable then
$\free((Qz)(\vf))=\free(\vf)\setminus \{z\}$.
3.18 Example. Let $\vt$ be the formula
$$\vt = "(y \ge z^2) \to (\exists x)(y=x^2)"$$
To evaluate $\free(\vt)$, we need to parse $\vt$ (build it up
by the rules in DEF 3.10):
$\vt ="(\psi \to \xi)"$ where $\psi = "(y \ge z)"$
and $\xi = "(\exists x)(y=x^2)"$. Now $\psi$ is
and atomic formula, so $\free(\psi)=\{y,z\}$.
The formula $\xi$ has the form $\xi ="(\exists x)(\rho)"$
where $\rho = "(y=x^2)"$ is an atomic formula, so
$\free(\rho)= \{x,y\}$ and therefore
$\free(\xi) = \free(\rho)\setminus \{x\} = \{y\}$.
Finally, $\free(\vt)=\free(\psi)\cup\free(\xi)
= \{y,z\}\cup \{y\} = \{y,z\}$.
3.20 DEF A f.o. sentence is a f.o. formula $\vf$ with no free variables: $\free(\vf)=\emptyset$.
3.22 DO Show that the formula $\eta = "(\forall x)((x\neq 0)\to (\exists y)(xy=1))"$ is a f.o. sentence.
3.24 DEF An interpretation of a f.o. formula $\vf$ in a given model is an assignment of values to the free variables from the model.
3.27 DO Show that under an interpretation, a f.o. formula gains a truth value (TRUE/FALSE).
3.28 Example. Let us take the formula
$\vt = "(y \ge z^2) \to (\exists x)(y=x^2)"$
from exercise 3.18. We found that $\free(\vt)=\{y,z\}$.
Let our model be $\rrr$.
(a) If we assign the values
$y\mapsto 8$ and $z\mapsto 6$ then we get
$\vt(y=8, z=6)= \TRUE$ because the assumption part of
the implication, $"8 > 6^2"$, is false.
(b) If we assign the values
$y\mapsto 40$ and $z\mapsto 6$ then we get
$\vt(y=40, z=6)= \TRUE$ because the conclusion part of
the implication, $"(\exists x)(x^2 = 40)"$, is true.
3.30 ORD (2+3 points) Perform the analysis of the preceding exercise (3.28) for the model $\zzz$. (Same formula, same substitutions, different model.)
3.32 DO Show, that, given a model, a f.o. sentence has a truth value. This truth value depends on the model but does not depend on any assignment of values to the variables.
3.34 Example. Consider the f.o. sentence $\eta = "(\forall x)((x\neq 0)\to (\exists y)(xy=1))"$ from Exercise 3.22. If our model is $\zzz$ then this sentence is false. If our model is $\rrr$ then this sentence is true. DO: prove these statements.
3.36 ORD (3+3 points) Consider the f.o. formula
$$\vt = "(y \ge z^2) \to (\exists x)(y=x^2)"$$
we have studied above. We found that $\free(\vt) = \{y,z\}$.
Let us now consider the formula $\pi = (\forall y,z)(\vt)$.
So $\pi$ is a f.o. sentence.
(a) Is $\pi$ true or false in the model $\rrr$ ?
(b) Is $\pi$ true or false in the model $\zzz$ ?
Prove your answers.
3.40 Bonus (due Oct 18) (8 points)
Find a simple f.o. sentence that
is true in $\zzz$, true in $\rrr$, but false in $\qqq$ (rationals).
Prove that your f.o. sentence has the desired properties.
Simplicity counts. Both the formula and the proof of its
correctness should be simple.
Hint. Make your sentence of the form $\vf = \sigma \vee \tau$
where bot $\sigma$ and $\tau$ are sentences and (a) $\sigma$
is true in $\zzz$ but false in $\qqq$ and in $\rrr$,
and (b) $\tau$ false in $\zzz$ and in $\qqq$ but true in $\rrr$.
3.44 ORD (4 points) Consider the Boolean model (Ex. 3.07 (8)). Find a f.o. formula with four free variables, $x,y,z,w,$ such that the meaning of your formula is
Prove that your formula is right. Warning: your formula cannot involve any operations other than the Boolean operations listed above. In particular, no arithmetic operations $(+,-,\times)$ are permitted.
More to follow. Please check back later. Please report any errors.
Class 2, Thu 9-30 Powerset, Cartesian product, operations,
relations, transitive relations, congruence modulo $m$
All problems are due Monday, October 4, 23:00, except where
otherwise stated.
2.05 DO STUDY Y20HW01, all items (1.10--1.128) except 1.70--1.80 (the Divisor Game, a fun set of problems). Solve all the DO and HW problems in this set; do not hand them in.
2.10 DEF Let $A$ be a set. The powerset $\calP(A)$ is the set of all subsets of $A$.
2.15 DO Prove: If $|A|=n$ then $|\calP(A)|=2^n$.
2.20 DEF The Cartesian product of the sets $A$ and $B$ is the set $A\times B=\{(a,b)\mid a\in A, b\in B\}$.
2.22 DO Prove: If $A,B$ are finite sets then $|A\times B|=|A|\cdot |B|$.
2.24 DEF A binary relation between the sets $A$ and $B$ is a subset $R\subseteq A\times B$. A ternary relation among the sets $A,B$, and $C$ is a subset $R\subseteq A\times B\times C$. Analogously we define $k$-ary relations for every $k$. If we say "relation" without the adjective "binary", "ternary", etc., we refere to a binary relation.
2.25 Supplementary reading: the "Binary relations" entry in Wikipedia.
2.26 EXAMPLE. Let $H$ denote the set of all humans and $W$ the set of al women. A relation between $W$ and $H$ is the "mother of" relation $M=\{(w,h) \mid w\in W,\ h\in H, w$ is the mother of $h\}$.
2.28 DEF The converse (or "opposite") of the binary relation $R\subseteq A\times B$ is the relation $R^{\op}\subseteq B\times A$ defined as $R^{\op}= \{(b,a)\mid (a,b)\in R\}$.
2.30 EXAMPLE. The converse of the "mother of" relation $M$ (Example 2.26) is the "child of" relation $M^{\op}=\{(h,w)\mid h\in H,\ w\in W, h$ is a child of $w\}$.
2.35 DEF A relation between the set $A$ and itself is a relation on $A$: $R\subseteq A\times A$. We also say it is a relation among the elements of $A$. Such relations are also referred to as homogeneous relations as opposed to the heterogeneous relations $R\subseteq A\times B$ where $B$ is not necessarily equal to $A$. By "relations" we shall always refer to homogeneous relations, unless specifically stated otherwise.
2.37 EXAMPLES. The "less than or equal" relation $\{(x,y)\mid x,y\in\rrr,\ x\le y\}$ is a relation among real numbers. "Divisibility" is a relation among integers: $\{(x,y)\mid x,y\in\zzz,\ x\mid y\}$. Congruence is a relation among triangles (or among all shapes) in the plane or in space. "Parallel" and "perpendicular" are relations among lines in the plane or in space.
2.39 NOTATION. Let $R$ be a relation. Then we often use the notation $aRb$ to denote the circumstance that $(a,b)\in R$. For example, we defined the "less than or equal" relation on $\rrr$ as the set $"\le"=\{(x,y)\mid x,y\in\rrr,\ x\le y\}$, but instead of writing $(5,7)\in "\le"$, we simply write $5\le 7$.
2.42 DEF We say that the (homogeneous) relation $R\subseteq A\times A$ is transitive if $$(\forall x,y\in A)((aRb \wedge bRc)\Rightarrow aRc)$$
2.44 LOGIC NOTATION. $\Rightarrow$ denotes the "if $\dots$ then" relation between mathematical statements: if $S,T$ are statements then $S\Rightarrow T$ means "if $S$ then $T$". (LaTeX: S\Rightarrow T.) The $\wedge$ symbol (\wedge) denotes AND. The $\vee$ symbol (\vee) denotes OR. So the full statement above looks like this in LaTeX code: (\forall x,y\in A)((aRb \wedge bRc)\Rightarrow aRc).
2.46 DO Prove that "divisibility" is a transitive relation on $\zzz$: $$(\forall x,y,z\in\zzz)((x\mid y \wedge y\mid z)\Rightarrow x\mid z)\,.$$ What property of arithmetic does your proof use? (Answer: associativity of multiplication. Point out where in your proof do you use it.)
2.50 ORD (additivity of divisibility) (3 points) Prove: $$(\forall d,x,y\in\zzz)((d\mid x \wedge d\mid y)\Rightarrow d\mid x+y)\,.$$ State, what property of arithmetic you use in the proof. Point out, where in the proof you use it.
2.52 DO (additivity of divisibility continued) Prove: $$(\forall d,x,y\in\zzz)((d\mid x \wedge d\mid y)\Rightarrow d\mid x-y)\,.$$
The next part of this section (2.60-2.100) is concerned with the notion of congruence among integers. In all problems on this subject, the universe is $\zzz$.
2.60 DEF We say that $a$ is congruent to $b$ modulo $m$ if $m\mid a-b$. We denote this circumstance by $a\equiv b\pmod m$. In LaTeX: a\equiv b\pmod{m}.
2.62 Examples. $5\equiv 26 \pmod 7$, $4\equiv -21 \pmod 5$, $3\equiv 1\pmod 2$, $5\not\equiv 20 \pmod 7$.
2.64 ORD (2+2+2 points) Express in simple and common English, without referring to the concept of divisibility, when two numbers are congruent (a) modulo 2, (b) modulo 1, (c) modulo 0.
2.66 ORD (2 points) Fill in the blank: "$a\equiv 0 \pmod m$" if and only if "BLANK". Your answer should be a very simple statement in terms of divisibility. No proof required.
2.68 DO Prove that every number is congruent to (a) 0 or 1 modulo 2 (b) 0 or $\pm1$ modulo 3 (c) 0, $\pm1$, $\pm2$, or 3 modulo 6.
2.70 DO Prove: If $p$ is a prime number and $p\ge 5$ then $p\equiv \pm 1\pmod 6$.
2.72 Bonus (3 points) Find all values of $x$ such that $x^2\equiv 4 \pmod x$. Prove that you found all such values.
2.75 ORD (4 points) Prove that congruence modulo a fixed number $m$ is a transitive relation on $\zzz$: $$(\forall m,a,b,c\in\zzz) (((a\equiv b\pmod m) \wedge (b\equiv c\pmod m)) \Rightarrow (a\equiv c\pmod m)) \,.$$ First translate the assumptions and the desired conclusion to the language of divisibility; then refer to a result about divisibility. Which result?
2.78 DO Prove that congruence modulo $m$ is additive:
$$(\forall a,b,x,y)(((a\equiv x \pmod m) \wedge (b\equiv y \pmod m))
\Rightarrow (a+b\equiv x+y \pmod m)\,.$$
First translate the assumptions and the desired conclusion to
the language of divisibility; then refer to a result about divisibility.
Which result?
2.80 DO (Lemma to the multiplicativity of congruence)
Prove: If $a\equiv b \pmod m$ then
$(\forall c)(ac\equiv bc \pmod m)$.
First translate the assumption and the desired conclusion to
the language of divisibility; then refer to a result about divisibility.
Which result?
2.82 ORD (3 points) The cancellation law among integers says that $$(\forall a,b,c)((ac=bc \wedge c\neq 0) \Rightarrow a=b)\,.$$ Prove that the analogous statement for congruences is false. In other words, you need to disprove the following statement: $$(\forall a,b,c,m)(((ac\equiv bc \pmod m) \wedge c\not\equiv 0\pmod m) \Rightarrow a\equiv b \pmod m))\,.$$
2.84 Bonus (3 points) Prove that congruence modulo $m$ is multiplicative: $$(\forall a,b,x,y)(((a\equiv x \pmod m) \wedge (b\equiv y \pmod m)) \Rightarrow (ab\equiv xy \pmod m)\,.$$ To earn full points, do NOT translate the assumptions and the desired conclusion to the language of divisibility. Instead, give a quick proof by combining two of the exercises above. You can use those exercises without proof.
2.86 DO Prove: If $a\equiv b\pmod m$ then
$(\forall k\ge 0)(a^k\equiv b^k\pmod m)$.
Use induction on $k$ and use the multiplicativity of congruence.
2.90 ORD (3 points) Find a value $m$ such that the following statement is true: $(\forall x,y)(((x\equiv y\pmod{12}) \wedge (x\equiv y\pmod{20}))\iff (x\equiv y \pmod m))$. No proof required.
2.94 DO Prove: If $x$ is odd then $x^2\equiv 1\pmod 8$.
2.100 Bonus (6 points) (due Monday, October 11) Let $d(n)$ denote the number of positive divisors of the number $n$. For instance, $d(4)=3$ and $d(6)=4$. Determine, for exactly which positive integers $n$ is the number $d(n)$ odd. Prove your answer. Hint. Experiment with $n\le 30$, find a pattern, make a conjecture, prove.
2.120 DEF A binary operation on a set $A$ is a function
$A\times A\to A$ that takes a pair of input values from $A$ and
outputs a value from $A$. Examples: $A=\zzz$, a binary operation is
addition: $(a,b) \mapsto a+b$. Another example on $\zzz$ is
multiplication: $(a,b)\mapsto ab$.
Examples on the powerset $\calP(\Omega)$ of a set $\Omega$: union:
if $K,L\subseteq \Omega$ then we take $(K,L)\mapsto K\cup L$.
Similarly, intersection: $(K,L)\mapsto K\cap L$.
A unary operation on $A$ takes one input value from $A$ and
outputs one value from $A$. Examples on $\zzz$: shift: $x\mapsto x+1$,
additive inverse: $x\mapsto -x$, square: $x\mapsto x^2$.
Example on $\calP(\Omega)$: complement: $K\mapsto \overline{K}:=
\Omega\setminus K$.
Example on $\rrr\setminus\{0\}$: multiplicative inverse:
$x\mapsto 1/x$. Example on the positive real numbers:
square root: $x\mapsto \sqrt{x}$.
A nullary operation, also called a "constant", takes no input
and outputs a value from $A$. Examples in $\zzz$: 0, 1. Examples
in $\calP(\Omega)$: $\emptyset$, $\Omega$.
2.122 DEF If we have two binary operations, $\Box$ and $\ast$, we say that $\ast$ distributes over $\Box$ if $(a\Box b)\ast c = (a\ast c)\Box (b\ast c)$. For instance, over $\zzz$, multiplication distributes over addition: $(a+b)c=ac+bc$.
2.124 DO Show that in $\calP(\Omega)$, (a) intersection distributes over union: $(K\cup L)\cap M=(K\cap M)\cup(L\cap M)$. (b) Union distributes over intersection. Do not repeat your argument for (a); derive (b) directly from (a) using DeMorgan's rules.
Class 1, Tue 9-28 Quantifiers, divisibility, setmaker notation
1.01 HW (due Thursday, Sep 30, before class, handwritten on paper)
Let $B =\{x\in\zzz\ :\ x\mid x-4\}$. Determine the set $B$.
Your answer should be given as an explicit list of the elements of $B$.
Prove your answer. You may use any DO exercises stated in class.
1.05 DO STUDY Y20HW01, items 1.10--1.62. Solve all the DO and HW problems in this set; do not hand them in.
1.10 DO STUDY Y20HW02, items 2.10--2.40. Solve all the DO and HW problems on that site; do not hand them in.
1.11 DEF (sumset) Let $A,B$ be subsets of $\zzz$, the set of integers. We define their sumset as $A+B = \{a+b \mid a\in A, b\in B\}$. This is an example of the "setmaker bar" notation; the bar reads "such that." (This definition appears as DEF 2.16 in Y20HW02. Study the related problems there.)
1.12 Example Let $A=\{3,4,6\}$ and $B=\{1,3,6,7\}$. Then $A+B = \{4,5,6,7,9,10,11,12,13\}$.
1.13 DO $A+\emptyset = \emptyset$.
1.14 NOTATION For a set $A$ we write $|A|$ to denote the number of elements of $A$, also called the cardinality of $A$, or simply the size of $A$. For instance, $|\{a,c,a,b,c\}|=3.$
1.15 Bonus (due Mon, Oct 4, 23:00 in Latex/PDF on Gradescope)
(5+3 points)
Let $A$ and $B$ be non-empty finite subsets of $\zzz$.
(a) Prove: $|A+B| \ge |A|+|B|-1$.
(b) Prove that this inequality is tight in the following sense.
For all $k,\ell\ge 1$ there exist finite sets $A,B\subseteq\zzz$
such that $|A|=k$, $|B|=\ell$, and $|A+B|=k+\ell-1$.