Formula & theorem reference

Existence. Consider the set of nonnegative integers of the form a - bk for integer k: \{\ldots, a-2b,\ a-b,\ a,\ a+b,\ a+2b,\ \ldots\} \cap \{0, 1, 2, \ldots\}. This set is nonempty — for k negative enough, a-bk grows without bound in the positive direction — so by the well-ordering principle it has a least element; call it r, achieved at some k=q, so r = a-bq, i.e. a = bq+r. If r \ge b, then r-b = a-b(q+1) \ge 0 would be a smaller nonnegative element of the same set, contradicting that r was least. So 0 \le r < b.

Uniqueness. Suppose a = bq_1+r_1 = bq_2+r_2 with both remainders in [0,b). Subtracting gives b(q_1-q_2) = r_2-r_1, so b divides r_2-r_1. But -b < r_2-r_1 < b, and the only multiple of b strictly between -b and b is 0, so r_1=r_2, which forces q_1=q_2 as well.

Both are checked directly by truth table -- a finite, exhaustive check suffices since there are only 2^2=4 rows to consider for two atoms.

First law. At p=T,q=T: left side \neg(T\wedge T)=\neg T=F; right side \neg T\vee\neg T=F\vee F=F. At p=T,q=F: left side \neg(T\wedge F)=\neg F=T; right side F\vee T=T. At p=F,q=T: left side \neg(F\wedge T)=T; right side T\vee F=T. At p=F,q=F: left side \neg(F\wedge F)=T; right side T\vee T=T. Every row matches.

Second law. At p=T,q=T: left side \neg(T\vee T)=F; right side F\wedge F=F. At p=T,q=F: left side \neg(T\vee F)=F; right side F\wedge T=F. At p=F,q=T: left side \neg(F\vee T)=F; right side T\wedge F=F. At p=F,q=F: left side \neg(F\vee F)=T; right side T\wedge T=T. Every row matches.

Checked by truth table over the two atoms p, q. At p=T,q=T: the premise (p\implies q)\wedge p = T\wedge T=T, and q=T, so the whole conditional is T\implies T=T. At p=T,q=F: p\implies q=F, so the premise F\wedge T=F, making the whole conditional F\implies \text{anything}=T. At p=F,q=T: p=F makes the premise (\cdot)\wedge F=F, so the conditional is again T. At p=F,q=F: same reasoning, premise is F, conditional is T. Every row is true, so this is a tautology -- the argument form is valid regardless of what p and q actually are.

Checked by truth table. At p=T,q=T: \neg q=F, so the premise (p\implies q)\wedge\neg q = T\wedge F=F, making the conditional F\implies\text{anything}=T. At p=T,q=F: p\implies q=F, so the premise is F\wedge T=F, conditional is T. At p=F,q=T: \neg q=F, premise is F, conditional is T. At p=F,q=F: p\implies q=T, \neg q=T, premise is T\wedge T=T; the conclusion \neg p=T here too, so the conditional is T\implies T=T. Every row is true, confirming this argument form is valid for every p, q.

First law. \forall x\, P(x) is true exactly when P(x) holds for every x \in D. So \neg(\forall x\, P(x)) is true exactly when it is NOT the case that P(x) holds for every x -- that is, when at least one x \in D fails P(x), i.e. some x satisfies \neg P(x). That is precisely the condition for \exists x\, \neg P(x) to be true. The two sides are true in exactly the same cases, so they are equivalent.

Second law. \exists x\, P(x) is true exactly when at least one x \in D satisfies P(x). So \neg(\exists x\, P(x)) is true exactly when NO x \in D satisfies P(x) -- that is, when every x \in D satisfies \neg P(x). That is precisely the condition for \forall x\, \neg P(x) to be true. Again, the two sides agree in every case.

This principle isn't derived from something more basic in this course — it's taken as one of the foundational properties of the integers themselves (equivalent to the well-ordering principle: every nonempty set of integers bounded below has a least element, a fact from set theory this course doesn't build). The domino-chain intuition is a genuine guide to why it's believable — P(n_0) is true, and the inductive step means each true case knocks over the next one — but making that intuition airtight for infinitely many dominoes is exactly what the well-ordering principle supplies, and that belongs to a foundations-of-mathematics course, not this one. It's used freely here because every course that reaches integers uses it freely.

Rather than taking this as a second, separate axiom alongside the Principle of Mathematical Induction, it can be built from that ordinary principle directly — the only genuinely new idea is what statement to induct on.

Given P(n) satisfying strong induction's two hypotheses, define a new statement Q(n): "P(n_0), P(n_0+1), \ldots, P(n) are all true." Q(n_0) holds because that's exactly the base case. And if Q(k) holds — every one of P(n_0) through P(k) is true — then the strong inductive step says P(k+1) is true too, so Q(k+1) (everything through P(k+1)) holds as well. That's the base case and inductive step of the ordinary Principle of Mathematical Induction, applied to Q instead of P — so Q(n) is true for every n \ge n_0. Since Q(n) includes P(n) as one of its conjuncts, P(n) is true for every n \ge n_0 too.

This principle is taken as a foundational property of the natural numbers, not derived from something more basic in this course — it is equivalent to the Principle of Mathematical Induction, and either one can be taken as the starting axiom with the other proved from it.

Sketch of the equivalence. Suppose the Principle of Mathematical Induction holds, and let S be a nonempty set of natural numbers with no least element. Let P(n) be the statement "0, 1, \ldots, n are all not in S." P(0) holds, since if 0 \in S it would trivially be the least element. If P(k) holds (none of 0 through k are in S) and k+1 \in S, then k+1 would be S's least element, contradicting the assumption — so k+1 \notin S either, giving P(k+1). By induction, P(n) holds for every n, meaning no natural number is ever in S — contradicting S nonempty. So every nonempty S must have a least element after all.

B \subset A is false only when B contains some element that A lacks. Take B = \varnothing: it contains no elements at all, so there is nothing it could possibly contain that A doesn't also contain. The condition for B \subset A to fail can never be met, so \varnothing \subset A holds automatically — for every set A, including A = \varnothing itself.

(\Rightarrow) Suppose A = B. Then every element of A is an element of B (they're the same set), so A \subseteq B. By the same reasoning B \subseteq A.

(\Leftarrow) Suppose A \subseteq B and B \subseteq A. Take any element x. If x \in A, then x \in B since A \subseteq B. If x \in B, then x \in A since B \subseteq A. So x \in A exactly when x \in B -- the two sets have identical elements, which is what A = B means.

Both are proved by double inclusion, checking an arbitrary element x \in U against each side.

First law. x \in \overline{A \cup B} means x \notin A \cup B, which means x \notin A and x \notin B (an element outside a union is outside both pieces). That is exactly x \in \overline{A} and x \in \overline{B}, i.e. x \in \overline{A} \cap \overline{B}. Every step above reverses, so the two sets have identical elements.

Second law. x \in \overline{A \cap B} means x \notin A \cap B, which means x \notin A or x \notin B (an element outside an intersection is missing from at least one piece). That is exactly x \in \overline{A} or x \in \overline{B}, i.e. x \in \overline{A} \cup \overline{B}. Again every step reverses.

Both arguments are the exact set-theoretic translation of propositional De Morgan's laws, with \cup standing in for \vee, \cap for \wedge, and complement for negation.

Building a subset of A is n independent yes/no decisions, one per element: for each of the n elements, decide whether it goes into the subset or not. By the product rule, the number of ways to make n independent binary decisions is 2 \cdot 2 \cdots 2 (n factors), which is 2^n. Each distinct sequence of decisions produces a distinct subset, and every subset arises from exactly one sequence of decisions, so this count is exact, not an estimate.

For example, n = 0 gives 2^0 = 1: the only subset of \varnothing is \varnothing itself, matching \mathcal{P}(\varnothing) = \{\varnothing\}.

Adding |A| and |B| counts every element of A \cup B at least once, but any element lying in both sets gets counted twice -- once inside |A| and once inside |B|. Subtracting |A \cap B| removes exactly one of those two duplicate counts for each such element, leaving every element of A \cup B counted exactly once. Formally, A \cup B splits into the three disjoint pieces A \setminus B, A \cap B, and B \setminus A, so |A \cup B| = |A \setminus B| + |A \cap B| + |B \setminus A|. Since |A| = |A \setminus B| + |A \cap B| and |B| = |B \setminus A| + |A \cap B|, adding |A|+|B| double-counts |A \cap B| by exactly one extra copy, which the subtraction removes.

Two things must be shown: g \circ f is one-to-one, and g \circ f is onto.

One-to-one. Suppose (g\circ f)(a_1) = (g\circ f)(a_2), i.e. g(f(a_1)) = g(f(a_2)). Since g is one-to-one, this forces f(a_1) = f(a_2). Since f is one-to-one, this forces a_1 = a_2. So g\circ f sends distinct inputs to distinct outputs.

Onto. Let c \in C be arbitrary. Since g is onto, there is some b \in B with g(b) = c. Since f is onto, there is some a \in A with f(a) = b. Then (g\circ f)(a) = g(f(a)) = g(b) = c, so every c \in C is hit.

Both properties hold, so g \circ f is a bijection.

Existence. Define f^{-1}(b) for b \in B as follows: since f is onto, some a \in A satisfies f(a) = b; since f is one-to-one, that a is the only one. So b \mapsto a is a well-defined rule, and it is total since every b \in B has such an a. Call this rule f^{-1}. By construction f(f^{-1}(b)) = f(a) = b, and f^{-1}(f(a)) = f^{-1}(b) = a.

Uniqueness. Suppose h: B \to A is another function with h(f(a)) = a for every a and f(h(b)) = b for every b. Fix b \in B and let a = f^{-1}(b), so f(a) = b. Then h(b) = h(f(a)) = a = f^{-1}(b). Since b was arbitrary, h = f^{-1}.

By definition \lfloor x \rfloor is the greatest integer no larger than x, so \lfloor x \rfloor \le x directly. If \lfloor x \rfloor \le x - 1 held, then \lfloor x \rfloor + 1 would also be an integer no larger than x, contradicting that \lfloor x \rfloor is the greatest such integer — so x - 1 < \lfloor x \rfloor. The ceiling inequalities mirror this argument with "greatest integer \le x" replaced by "least integer \ge x" throughout.

For the identity, let n = \lfloor x \rfloor, the greatest integer with n \le x. Then -n \ge -x, and -n is the least such integer (any smaller integer -m < -n would give m > n with m \le x, contradicting that n is greatest). So -n = \lceil -x \rceil, i.e. \lceil -x \rceil = -\lfloor x \rfloor; replacing x with -x gives \lceil x \rceil = -\lfloor -x \rfloor.

Intersection. a \in f^{-1}(S \cap T) iff f(a) \in S \cap T iff f(a) \in S and f(a) \in T iff a \in f^{-1}(S) and a \in f^{-1}(T) iff a \in f^{-1}(S) \cap f^{-1}(T).

Union. The same chain with "and" replaced by "or" at every step proves f^{-1}(S \cup T) = f^{-1}(S) \cup f^{-1}(T).

Complement. a \in f^{-1}(S') iff f(a) \in S' iff f(a) \notin S iff a \notin f^{-1}(S) iff a \in \big(f^{-1}(S)\big)'.

Each step is a biconditional, not just an implication, so every equality above holds in both directions and for every function f — none of the three arguments ever used that f is one-to-one or onto.

Every a\in A satisfies a\sim a by reflexivity, so a\in[a] and the classes cover A. Suppose two classes [a] and [b] share an element c, so c\sim a and c\sim b. By symmetry a\sim c, and by transitivity a\sim c and c\sim b give a\sim b. Then for any x\in[a], x\sim a and a\sim b give x\sim b, so x\in[b], and the same argument in reverse gives [b]\subseteq[a]. Hence [a]=[b]: two classes that share even one element are the same class, so distinct classes never overlap. Combined with the classes covering A, this makes the collection of distinct classes a partition of A.

Reflexivity: every x\in A lies in whichever block contains it, so x shares that block with itself, giving x\sim x. Symmetry: if x and y share a block, that same fact says y and x share a block, so x\sim y implies y\sim x. Transitivity: if x,y share block A_i and y,z share block A_j, then y lies in both A_i and A_j; since the blocks of a partition are pairwise disjoint, A_i=A_j, so x and z share that same block and x\sim z. Thus \sim is an equivalence relation. For any x\in A_i, an element y satisfies x\sim y exactly when y\in A_i too, so the equivalence class [x] is precisely the block A_i containing x.

The form solves the recurrence. Substitute a_n = c_1 r_1^n + c_2 r_2^n into the right side of A a_{n-1} + B a_{n-2}: A\left(c_1 r_1^{n-1} + c_2 r_2^{n-1}\right) + B\left(c_1 r_1^{n-2} + c_2 r_2^{n-2}\right) = c_1 r_1^{n-2}\left(Ar_1 + B\right) + c_2 r_2^{n-2}\left(Ar_2 + B\right). Since each r_i satisfies r_i^2 = Ar_i + B (that is exactly what being a root of x^2 - Ax - B = 0 means), Ar_i + B = r_i^2, so the right side becomes c_1 r_1^{\,n} + c_2 r_2^{\,n} = a_n. The proposed form satisfies the recurrence for every choice of c_1, c_2, regardless of the initial conditions.

The constants are pinned down uniquely. Requiring a_0 and a_1 to match the given starting values produces the linear system c_1 + c_2 = a_0, \qquad c_1 r_1 + c_2 r_2 = a_1. This system has exactly one solution for (c_1, c_2) whenever r_1 \neq r_2, since its determinant r_2 - r_1 is then nonzero. Combined with the first part, this shows the resulting a_n is not merely a solution matching the initial conditions — it is the only one, because any sequence satisfying a second-order recurrence is completely determined once a_0 and a_1 are fixed.

Sanity check: take a_n = 3a_{n-1} - 2a_{n-2} with a_0 = 2, a_1 = 3. The characteristic equation x^2 - 3x + 2 = 0 factors as (x-1)(x-2)=0, giving roots r_1=1, r_2=2. Solving c_1+c_2=2, c_1+2c_2=3 gives c_1=1, c_2=1, so a_n = 1 + 2^n. Checking directly: a_2 should be 3(3)-2(2)=5, and the formula gives 1+2^2=5. They agree.

This isn't really a theorem to prove so much as a fact to see. Lay the first choice's m options down the rows of a grid and the second choice's n options across the columns. Every cell of that grid is exactly one valid pairing — one option from the first choice matched with one option from the second — and every valid pairing lands in exactly one cell. A grid with m rows and n columns has m \times n cells. Counting the pairings and counting the cells are the same question, so they have the same answer. Chaining a third independent choice onto the pair just replaces each cell of that grid with a fresh n_3-row stack, and multiplication absorbs each new stage the same way.

This is just the counting principle, run r times in a row. The first position in the arrangement can be filled by any of the n items. The second position can be filled by any of the n - 1 items that remain (one has been used). The third by any of the n-2 remaining, and so on, down to the rth position, which has n - (r-1) = n - r + 1 choices left. Multiply across all r positions: P(n,r) = n \cdot (n-1) \cdot (n-2) \cdots (n - r + 1). That product has exactly r factors, starting at n and counting down. To see it equals \frac{n!}{(n-r)!}, write n! in full and notice the tail end cancels: n! = \bigl[n(n-1)\cdots(n-r+1)\bigr] \cdot (n-r)!, so dividing both sides by (n-r)! leaves exactly the product above.

Start from P(n,r), which counts every arrangement of r chosen items. Each unordered group of r items corresponds to many of those arrangements — specifically, every one of the r! ways to reorder that same group is a different permutation but the exact same combination. So P(n,r) overcounts each combination by a factor of r!, and dividing it out gives the true count: C(n,r) = \frac{P(n,r)}{r!} = \frac{n!/(n-r)!}{r!} = \frac{n!}{r!\,(n-r)!}.

Count the size-k subsets of an n-element set \{1, 2, \ldots, n\} two ways. The left side, \binom{n}{k}, counts them directly. For the right side, split every size-k subset by whether it contains the element n or not — an exhaustive, non-overlapping split. A subset containing n is n together with a size-(k-1) subset of the remaining n-1 elements: \binom{n-1}{k-1} such subsets. A subset not containing n is a size-k subset chosen entirely from those same n-1 elements: \binom{n-1}{k} of those. Every size-k subset falls into exactly one of the two cases, so the two counts add to the original total.

Suppose, for contradiction, that every one of the m boxes holds at most one object. Then the total number of objects placed is at most m \cdot 1 = m. But n objects were placed, and n > m, so n \leq m and n > m both hold — an impossibility. So some box must hold at least 2 objects.

The general form follows the same contradiction. If every box held strictly fewer than \lceil n/m \rceil objects, each box would hold at most \lceil n/m \rceil - 1 objects, giving a total of at most m\bigl(\lceil n/m \rceil - 1\bigr) < n objects placed — contradicting that all n objects were placed somewhere.

Each edge e = \{u, v\} of G has exactly two endpoints, u and v (a loop at v is the case u = v, still contributing two to that one vertex's degree count, which is exactly why a loop is defined to add 2 to \deg(v) rather than 1). Build the sum \sum_{v\in V}\deg(v) by counting, for every edge, how many times that edge gets counted across the whole sum.

Fix one edge e=\{u,v\}. It is counted once when computing \deg(u) (since e is incident to u) and once more when computing \deg(v) (since e is also incident to v), and it is never counted in any other vertex's degree, since e touches no vertex besides u and v. So every edge contributes exactly 2 to the total \sum_{v\in V}\deg(v), and there are |E| edges, giving \sum_{v \in V} \deg(v) = \sum_{e \in E} 2 = 2|E|.

The odd-degree count is even. Split V into V_{\text{even}} (even degree) and V_{\text{odd}} (odd degree). Then \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2|E|, an even number. The first sum is a sum of even numbers, so it's even. Subtracting an even number from an even number leaves an even number, so \sum_{v \in V_{\text{odd}}} \deg(v) is even too. A sum of odd numbers is even only when there is an even count of them (an odd count of odd numbers always sums to something odd), so |V_{\text{odd}}| itself must be even.

Sanity check: a triangle (3 vertices, each of degree 2) has degree sum 2+2+2=6, and 2|E| = 2(3) = 6 -- matches, and 0 vertices have odd degree, which is indeed even.

Induct on n. A tree with n = 1 vertex has no edges at all, and n - 1 = 0, so the base case holds.

Assume every tree on k vertices has exactly k - 1 edges, for some k \geq 1. Let T be a tree on k + 1 vertices. Every tree with more than one vertex has at least one leaf (a vertex of degree 1) — following any path outward without repeating a vertex must eventually stop somewhere, since T is finite and acyclic, and it can only stop at a vertex with no unused edge left, degree 1. Remove that leaf v and its single incident edge. What remains is still connected (no other vertex's connections ran through v, since v had only one edge) and still acyclic (deleting a vertex can't create a cycle), so it is a tree on k vertices. By the inductive hypothesis it has k - 1 edges. Adding v's one edge back gives T exactly (k - 1) + 1 = k edges, which is (k+1) - 1, as required.

By induction, every tree on n vertices has n - 1 edges for all n \geq 1.

Count nodes level by level, where the root sits at level 0. Level 0 can hold at most 1 = 2^0 node. Every node on a level has at most two children, so the maximum count at least doubles from one level to the next: level 1 holds at most 2 = 2^1 nodes, level 2 at most 4 = 2^2, and in general level i holds at most 2^i nodes.

A tree of height h has levels 0 through h, so its total node count is at most \sum_{i=0}^{h} 2^i = 2^{h+1} - 1, the standard geometric sum. Equality holds exactly when every level attains its own maximum, i.e. every level is completely filled — the definition of a perfect binary tree.

Searching for a key x starts at the root and, at each node visited, either finds x, or moves to exactly one child (left if x is smaller than the current node's key, right if larger) by the binary search tree property. Each comparison either ends the search or descends one level deeper, so the search visits at most one node per level. A tree of height h has levels 0 through h, giving at most h + 1 nodes on any single root-to-leaf path, hence at most h + 1 comparisons before the search must end (either at a match or at an empty child, meaning x is absent).

Since f(n) = O(g(n)), there exist constants c_1 > 0 and n_1 such that f(n) \leq c_1 \cdot g(n) for every n \geq n_1. Since g(n) = O(h(n)), there exist constants c_2 > 0 and n_2 such that g(n) \leq c_2 \cdot h(n) for every n \geq n_2.

Let n_0 = \max(n_1, n_2) and c = c_1 c_2. For every n \geq n_0, both inequalities above hold at once, so

This is exactly the Big-O condition for f(n) = O(h(n)), witnessed by c = c_1 c_2 and n_0 = \max(n_1, n_2).

The Conditional Probability formula, applied to P(A\mid B) and to P(B\mid A) separately, gives two ways to write the same joint probability: P(A\text{ and }B) = P(A\mid B)\,P(B), \qquad P(A\text{ and }B) = P(B\mid A)\,P(A). Both right-hand sides equal the same quantity, so they equal each other: P(A\mid B)\,P(B) = P(B\mid A)\,P(A). Dividing both sides by P(B) (nonzero by hypothesis) isolates P(A\mid B): P(A\mid B) = \frac{P(B\mid A)\,P(A)}{P(B)}.

This is a weighted average, and the weighting is what makes it meaningful over the long run. Imagine repeating the underlying random process N times, for very large N: outcome x_i will occur approximately N p_i times (that's what "probability p_i" means in the long run). The total payout across all N trials is then approximately \sum_i x_i \cdot (N p_i), and dividing by N trials to get the average payout per trial leaves exactly \sum_i x_i p_i — the probabilities' role as relative frequencies is what turns a plain average into a probability-weighted one.

Let the sample space be S = \{s_1, s_2, \ldots, s_n\} with P(s_i) = p_i. By definition, a random variable's expected value is a sum taken directly over the sample space: E(aX+bY) = \sum_{i=1}^{n} \big(aX(s_i) + bY(s_i)\big)\,p_i. Distribute p_i across the sum inside each term, then split the single sum into two sums, since addition of finitely many numbers can always be regrouped this way: \sum_{i=1}^{n} \big(aX(s_i)p_i + bY(s_i)p_i\big) = a\sum_{i=1}^{n} X(s_i)p_i + b\sum_{i=1}^{n} Y(s_i)p_i. The two resulting sums are exactly E(X) and E(Y) by definition, so E(aX+bY) = a\,E(X) + b\,E(Y). Nowhere did this argument use P(X=x, Y=y) = P(X=x)P(Y=y) — the independence condition — which is exactly why the result holds regardless of whether X and Y are independent.