Math 55 Definition List

Lecture 1: Propositional Logic

1. A proposition is a declarative sentence that is either true or false but not both. A proposition has a truth value which is either
   $T$ or
   $F$.
2. A letter used to denote a proposition is called a propositional variable.
3. If
   $p$ is a proposition, the negation of
   $p$, denoted
   $\mathrm{\neg }p$, is the proposition "it is not the case that
   $p$". The truth value of
   $\mathrm{\neg }p$ is the opposite of that of
   $p$.
4. If
   $p$ and
   $q$ are propositions, the conjunction of
   $p$ and
   $q$ (denoted
   $p\wedge q$) is the proposition "p and q." Its truth value is
   $T$ when both
   $p$ and
   $q$ are
   $T$, and it is
   $F$ otherwise.
5. If
   $p$ and
   $q$ are propositions,he disjunction of
   $p$ and
   $q$ is the proposition "p or q". Its truth value is
   $T$ when at least one of
   $p$ or
   $q$ is
   $T$, and
   $F$ if both
   $p$ and
   $q$ are
   $F$.
6. If
   $p$ and
   $q$ are propositions, the conditional
   $p\to q$ is the proposition "if
   $p$ then
   $q$". Its truth values are given by the following truth table (which lists its truth values in terms of those of
   $p$ and
   $q$): [see Table 5 in Rosen] The converse of
   $p\to q$ is
   $q\to p$.
7. A compound proposition consists of logical operations (the four listed above) applied to propositions or propositional variables, possibly with parentheses. The truth value of a compound proposition can be mechanically determined given the truth values of its constituents.

Lecture 2: Propositional Functions, Quantifiers, (begin) Rules of Inference

1. A compound proposition which is always true (regardless of the truth values of constituent propositions) is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither is called contingent.
2. Two compound propositions
   $c_1,c_2$ are logically equivalent, denoted
   $c_1\equiv c_2$, if they have the same truth values for all truth values of their propositional variables (and all domains of their propositional functions).
3. The biconditional
   $p\leftrightarrow q$ is the proposition
   $(p\to q)\wedge (q\to p)$ (read "if and only if"). Two propositions
   $p$ and
   $q$ are logically equivalent if
   $p\leftrightarrow q$ is a tautology. This is denotes
   $p\equiv q$. Logically equivalent propositions have the same truth table.
4. The contrapositive of a conditional
   $p\to q$ is
   $\mathrm{\neg }q\to \mathrm{\neg }p$. The contrapositive is logically equivalent to the original conditional.
5. A propositional function is a statement containing one or more variables (taking values in an implicitly or explicitly specified domain) which becomes a proposition when each variable is instantiated with a value.
6. The universal quantification of
   $P(x)$ is the proposition "For all
   $x$ in the domain, $P(x)", denoted
   $\mathrm{\forall }xP(x)$. The existential quantification of
   $P(x)$ is the proposition "There exists an
   $x$ in the domain such that P(x)", denoted
   $\mathrm{\exists }xP(x)$.
7. A variable appearing with a quantifier is called bound. A statement in which every variable appearing in a propositional function is bound is a proposition; otherwise it is not a proposition.

Lecture 3: Rules of Inference for Quantifiers, Direct Proof, Contrapositive, Contradiction

1. An argument is a sequence of propositions each of which is a premise (i.e., an assumption) or a conclusion (i.e., follows from previous propositions via rules of inference).
2. An integer
   $n$ is even if there exists an integer
   $k$ such that
   $n=2k$. An integer
   $n$ is odd if there exists an integer
   $k$ such that
   $n=2k+1$.
3. A real number
   $x$ is rational if there exist integers
   $p$ and
   $q\ne 0$ such that
   $x=p/q$.

Lecture 4: More Proofs, Sets

1. A set is an unordered collection of objects which are called its elements. A set contains its elements, denoted
   $x\in A$. For every
   $x$, the statement "
   $x\in A$" must be a proposition (otherwise
   $A$ is not a set).
2. The set with no elements is called the empty set, denoted
   $\varnothing$.
3. Two sets
   $A$ and
   $B$ are equal, denoted
   $A=B$, if they have the same elements, i.e.
   $\mathrm{\forall }x(x\in A\leftrightarrow x\in B)$.
4. If
   $A$ and
   $B$ are sets,
   $A$ is a subset of
   $B$, denoted
   $A\subseteq B$. if every element of
   $A$ is an element of
   $B$, i.e.,
   $\mathrm{\forall }x(x\in A\to x\in B)$.
5. If
   $A$ is a set, the power set of
   $A$, denoted
   $\mathcal{P}(A)$, is the set of all subsets of
   $A$:
   
   $$\mathcal{P}(A)=\{S:S\subseteq A\}.$$
6. If
   $A$ and
   $B$ are sets, their union is
   
   $$A\cup B=\{x:x\in A\vee x\in B\},$$
   their intersection is
   
   $$A\cap B=\{x:x\in A\wedge x\in B\},$$
   and their difference is
   
   $$A-B=\{x:x\in A\wedge \mathrm{\neg }x\in B\}.$$
   If
   $A$ is a subset of a universe
   $U$ (which is just another set), then the complement of
   $A$ (with respect to
   $U)$ is
   
   $$\bar{A}=\{x\in U:x\notin A\}=U-A.$$

Lecture 5: Functions

1. The cartesian product of two sets
   $A$ and
   $B$ is the set of ordered pairs
   $(a,b)$ such that
   $a\in A$ and
   $b\in B$. It is denoted
   
   $$A\times B=\{(a,b):a\in A\wedge b\in B\}.$$
2. If
   $A$ and
   $B$ are nonempty sets, a function from
   $A$ to
   $B$ is a rule which assigns exactly one element of
   $B$ to each element of
   $A$. This assignment is denoted
   $f(a)=b$. If
   $f$ is a function from
   $A$ to
   $B$ we write
   $f:A\to B$.
   $A$ is called the domain of
   $f$ and
   $B$ is called the codomain.
3. A function
   $f:A\to B$ is onto (surjective) if for every
   $b\in B$ there exists an
   $a\in A$ such that
   $f(a)=b$.
4. A function
   $f:A\to B$ is one to one (injective) if for every
   $a_1,a_2\in A$,
   $f(a_1)=f(a_2)$ implies
   $a_1$=
   $a_2$. (equivalently,
   $a_1\ne a_2$ implies
   $f(a_1)\ne f(a_2)$).
5. A function
   $f:A\to B$ is called a bijection if it is one to one and onto.
6. The composition of
   $f:B\to C$ and
   $g:A\to B$ is the function
   $f\circ g:A\to C$ defined by
   $f\circ g(a)=f(g(a))$.
7. If a function is a bijection, then the function
   $f^{-1}(b)$ which assigns to be the unique element
   $a\in A$ mapping to
   $b$ is called its inverse.
8. If
   $f:A\to B$ and
   $S\subseteq A$ then the image of
   $S$ is
   $f(S)=\{b\in B:\mathrm{\exists }a\in Ss.t.f(a)=b\}$. The inverse image (preimage) of
   $S\subseteq B$ is
   $f^{-1}(S)=\{a\in A:f(a)\in S\}$. The range of
   $f$ is
   $f(A)$.

$$

Lecture 6: Cardinality

1. ${\mathbb{Z}}_{+}$ denotes the set of positive integers.
2. A set
   $A$ is called finite if it is the empty set or if it has exactly
   $n$ elements for some
   $n\in {\mathbb{Z}}_{+}$. The cardinality of
   $A$, denoted
   $|A|$, is
   $n$.
3. Two sets
   $A$ and
   $B$ have the same cardinality, denoted
   $|A|=|B|$, if there is a bijection
   $f:A\to B$ (also called a "one to one correspondence" in this context). If there is an injection
   $f:A\to B$ we say that
   $|A|\le |B|$. If
   $|A|\le |B|$ but
   $|A|\ne |B|$ then we write
   $|A|<|B|$.
4. An infinite set with
   $|A|=|{\mathbb{Z}}_{+}|$ is called countable. An infinite set which is not countable is called uncountable.
5. A function
   $f:{\mathbb{Z}}_{+}\to A$ is called a sequence. If
   $f$ is a bijection the sequence is called an enumeration of
   $A$.

Theorems: The integers and rationals are countable. The interval

$(0,1)$ is uncountable.

Lecture 7: Division, Modular Arithmetic

1. If
   $a\ne 0$ and
   $b$ are integers then
   $a$ divides
   $b$ (denoted
   $a|b$) if there exists an integer
   $k$ such that
   $b=ka$.
2. ("Division Algorithm") If
   $a$ is an integer and
   $d\in {\mathbb{Z}}_{+}$ then there are unique integers
   $q,r$ such that
   $a=dq+r$ and
   $0\le r<d$.
   $q$ is called the quotient and
   $r$ is called the remainder, sometimeds denoted
   $r=a$ mod
   $d$.
3. (Axiom) Well-ordering principle: Every nonempty subset of
   ${\mathbb{Z}}_{\ge 0}$ has a least element.
4. For
   $a,b\in \mathbb{Z}$ we say
   $a\equiv b(modm)$ if
   $m|(b-a)$.
5. If
   $b\in {\mathbb{Z}}_{+}$ and
   $a\in {\mathbb{Z}}_{+}$ then there is a unique way to write
   $a$ as a sum of powers of
   $b$. This is called the base b expansion of
   $a$.

Lecture 8: Primes, GCD, and Bezout's Theorem

1. An integer
   $n>1$ is called prime if it has no divisors other than one and itself. An integer
   $n>1$ is called composite if it is not prime.
2. If
   $a,b$ are integers, not both zero, then the greatest common divisor of
   $a$ and
   $b$, denoted
   $gcd(a,b)$ is the largest
   $d\in {\mathbb{Z}}_{+}$ such that
   $d|a$ and
   $d|b$.

Theorems in this lecture: Infinitude of Primes, Fundamental Theorem of Arithmetic, Bezout's theorem.

Lecture 9: Inverses

Defn.

$\bar{a}$ is an inverse of

$a$ modulo

$m$ if

$a\bar{a}\equiv 1(modm)$.

Lecture 10: Chinese Remainder Theorem, Cryptography

Lectures 12/13: Induction, no definitions

Lecture 14: Graphs, Paths, Circuits, Coloring

A graph is a pair

$G=(V,E)$ where

$V$ is a finite set of vertices and

$E$ is a finite multiset of

$2-$element subsets of

$V$, called edges. If

$E$ has repeated elements

$G$ is called a multigraph, otherwise it is called a simple graph. We will not consider directed graphs or graphs with loops (edges from a vertex to itself).

Two vertices

$x,y\in V$ are adjacent if

$\{x,y\}\in E$. An edge

$e=\{x,y\}$ is said to be incident with

$x$ and

$y$. The degree of a vertex

$x$ is the number of edges incident with it.

A path of length

$k$ in

$G$ is an alternating sequence of vertices and edges

$$x_0,e_1,x_1,e_2,\dots ,x_{k-1},e_k,x_k$$
where

$e_i=\{x_{i-1},x_i\}\in E$ for all

$i=1\dots k$. The path is said to connect

$x_0,x_k$, visit the vertices

$x_0,\dots ,x_k$, and traverse the edges

$e_1,\dots ,e_k$. A path is called simple if it contains no repeated vertices. If

$x_0=x_k$ then the path is called a circuit. Note that in a simple graph (i.e., a graph with no multiple edges), a path is uniquely specified by the sequence of vertices

$x_0,\dots ,x_k$ (as there is only one possible choice of edge between each pair of consecutive vertices). A graph

$G$ is connected if for every pair of distinct vertices

$x,y$ of

$G$, there is a path in

$G$ between

$x$ and

$y$.

A k-coloring of

$G$ is a function

$f:V\to \{1,\dots ,k\}$ such that

$f(x)\ne f(y)$ whenever

$x$ is adjacent to

$y$. A graph is

$k-$colorable if it has a

$k$-coloring. (in class we did the case

$k=2$)

Lecture 15:

$k$-coloring

A graph

$H=(W,F)$ is a subgraph of

$G$ if

$W\subseteq V$ and

$F\subseteq E$. If

$W=V$ then

$H$ is called a spanning subgraph of

$G$.

A k-coloring of

$G$ is a function

$f:V\to \{1,\dots ,k\}$ such that

$f(x)\ne f(y)$ whenever

$x$ is adjacent to

$y$.

Defn. If

$G=(V,E)$ is a graph, a subset

$S\subseteq V$ is called a clique if

$xy\in E$ for every pair of distinct vertices

$x,y\in S$.

$S$ is called an independent set if

$xy\notin E$ for every pair of distinct vertices

$x,y\in S$.

Defn. If

$G=(V,E)$ is a graph, a subgraph

$H$ of

$G$ is called a connected component of

$G$ if

$H$ is connected and maximal, i.e., it is not possible to add any vertices or edges to

$H$ while keeping it connected (formally: if

$H^{\prime }$ is a subgraph of

$G$ such that

$H\ne H^{\prime }$ and

$H$ is a subgraph of

$H^{\prime }$, then

$H^{\prime }$ must be disconnected.).

Lectures 16-17: See the Graph Theory Notes

Lecture 18: Counting

An ordering of

$n$ distinct elements is called a permutation.
An ordered sequence of

$r$ distinct objects chosen from

$n$ distinct objects is called an r-permutation. The number of

$r-$permutations of

$n$ objects is denoted

$P(n,r)$.
An unordered set of

$r$ distinct objects chosen from

$n$ distinct objects is called an r-combination. The number of

$r-$combinations of

$n$ objects is denoted

$(\genfrac{}{}{0ex}{}{n}{k})$ or

$C(n,r)$.

Lecture 19: Permutations and Combinations with repetitions

No definitions.

Lecture 20: Labeled and Unlabeled Tokens in Boxes, Recurrences

A recurrence relation is a recursive definition of a sequence

$(a_0,a_1,a_2,\dots )$.

Lecture 21: Pigeonole Principle

Generalized Pigeonhole principle: If

$N$ objects are placed in

$k$ boxes, then at least one box contains at least

$\lceil N/k\rceil$ objects.

Lecture 22: Probability

$$

$$
An experiment is a well-defined procedure with a set of possible outcomes. An outcome is a complete description of all relevant features of the result of an experiment. The set of all outcomes is called the sample space

$S$. An event is a subset of the sample space

$E\subseteq S$. A probability space consists of a sample space

$S$ along with a function

$p:S\to \mathbb{R}$ satisfying

$p(s)\in [0,1]$ for all

$s\in S$ and

$\sum _{s\in S}p(s)=1$. The probability of an event is

$$\mathbb{P}(E)=\sum _{s\in E}p(s).$$

Lecture 23: Conditional Probability and Independence

Two events

$E,F\subseteq S$ are disjoint if

$E\cap F=\mathrm{\varnothing }$.
If

$E,F$ are events and

$\mathbb{P}(F)>0$ then the probability of

$E$ given

$F$ (also called

$E$ conditional on

$F$) is:

$$\mathbb{P}(E|F)=\frac{\mathbb{P}(E\cap F)}{P(F)}.$$
Two events

$E$ and

$F$ are independent if

$$\mathbb{P}(E\cap F)=\mathbb{P}(E)\mathbb{P}(F).$$
If

$\mathbb{P}(F)>0$ this is equivalent to

$\mathbb{P}(E|F)=\mathbb{P}(E)$ and if

$\mathbb{P}(E)>0$ this is equivalent to

$\mathbb{P}(F|E)=\mathbb{P}(F)$.

Lecture 24: Random Variables and Linearity of Expectation

$$
A random variable on a probability space

$S,p$ is a function

$X:S\to \mathbb{R}$.
The expectation of a random variable is defined as

$$\mathbb{E}X=\sum _{s\in S}p(s)X(s).$$
This may be equivalently rewritten as a sum over the range of

$X$:

$$\mathbb{E}X=\sum _{r\in range(X)}r\cdot \mathbb{P}(X=r).$$

Lecture 25: Examples of Distributions

If

$X:S\to \mathbb{R}$ is a random variable on a probability space, the function

$p_X(r)=\mathbb{P}(X=r)$ is called the distribution of the random variable.

A Bernoulli random variable with bias

$q\in [0,1]$ has distribution

$\mathbb{P}(X=0)=q,\mathbb{P}(X=1)=1-q$.
A Binomial random variable with bias

$q\in [0,1]$ and

$n$ trials has distribution

$\mathbb{P}(X=k)=(\genfrac{}{}{0ex}{}{n}{k})q^k(1-q{)}^{n-k}$ for

$0\le k\le n$.
A Geometric random variable with success probability

$q$ has distribution

$\mathbb{P}(X=k)=(1-q{)}^{k-1}q$ for

$k=1,2,\dots$.

Lecture 26: Algebra with random variables, Variance

If

$X,Y:S\to \mathbb{R}$ are random variables, their sum is defined as

$(X+Y)(s)=X(s)+Y(s)$. If

$c$ is a real number, the scalar multiple

$cX$ is defined as

$(cX)(s)=c\cdot X(s)$. The product is defined as

$(XY)(s)=X(s)Y(s)$. Notice that doing algebra on random variables means doing algebra on their ``outputs''.

Two random variables

$X,Y$ are independent if for all

$r_1,r_2\in \mathbb{R}$, the events

$\{X=r_1\}$ and

$\{Y=r_2\}$ are independent. This condition implies that

$\mathbb{E}XY=\mathbb{E}X\mathbb{E}Y$, which is not true in general.

The variance of a random variable is defined as

$V(X)=\mathbb{E}(X-{\mu }_X{)}^2$ here

${\mu }_X=\mathbb{E}X$.

Lecture 27: Concentration Inequalities

Markov's Inequality: If

$Y$ is a nonnegative random variable, then for every

$t>0$:

$$\mathbb{P}(Y\ge t)\le \frac{\mathbb{E}Y}{t}.$$
Chebyshev's Inequality: If

$X$ is any random variable, then for every

$t>0$:

$$\mathbb{P}(|X-\mathbb{E}X|\ge t)\le \frac{V(X)}{t^2}.$$