# Theorem and Definition Reference

Useful tip: If you use a browser like Google Chrome, clicking on the lecture slide link in an entry will take you to that slide in the PDF.

0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

## A

Antecedent

In an implication of the form "If P is true, then Q is true", the antecedent is the term "P is true".

Source: Lecture 02, Slide 14.

Arbitrary Choice

In mathematical proofs, an arbitrary choice of $x$ is a statement that $x$ is left unspecified so that any result proven about $x$ holds for any choice of $x$

Source: Lecture 01, Slide 24.

Arity

The arity of a predicate is the number of arguments it can take.

Source: Lecture 08, Slide 22.

Associative Operator

A binary operator $\diamond$ is called associative when for any $a,b,c$ we have: $a\diamond (b \diamond c)=(a \diamond b) \diamond c$

Source: Lecture 01, Slide 59.

## B

Base Case (or Basis)

In a proof by induction, the first step in which you prove that P is true for 0.

Source: Lecture 03, Slide 6.

Biconditional

A biconditional is a statement of the form "P if and only if Q", often abbreviated "P iff Q".

Source: Lecture 02, Slide 27.

Biconditional Operator (Logic)

The biconditional operator $\leftrightarrow$ is used to represnet two-directional implication (i.e. "$p\leftrightarrow q$" means "$p \rightarrow q$" and "$q \rightarrow$p$".) Source: Lecture 07, Slide 22. Bijective Functions (Bijections) A function that associates each element of the codomain with a unique element of the domain. Source: Lecture 10, Slide 91. Binary Operator A binary operator is an operator that operates on two operands. For example: +,-,XOR Source: Lecture 01, Slide 48. Bit A bit is a value that can be either 0 or 1. The set$\mathbb{B}$={0,1} is the set of all bits. Source: Lecture 01, Slide 47. Bitstring A bitstring is a finite sequence of bits (0s and 1s). Source: Lecture 01, Slide 73. ## C Cantor's theorem Cantor's theorem states that every set is strictly smaller than its power set. If$S$is a set, then$|S| \lt |\mathcal P \left({S}\right)| $. Source: Lecture 00, Slide 87. Cantor-Bernstein-Schroeder Theorem If$S$and$T$are sets where$|S| \leq |T|$and$|T| \leq |S|$, then$|T| = |S|$. Source: Lecture 11, Slide 25. Cardinality The cardinality of a set is the number of elements it contains. Source: Lecture 00, Slide 46. Proof: Lecture 11, Slide 104. Cardinality Comparison$|S| = |T|$if there exists a bijection f from S to T. Source: Lecture 11, Slide 5.$|S| \leq |T|$if there exists a injection f from S to T. Source: Lecture 11, Slide 24.$|S| < |T|$iff$|S| \leq |T|$and$|S| \neq |T|$. Source: Lecture 11, Slide 101. Cartesian Product The Cartesian Product$A \times B$is defined as$\{(a, b) | a \in A, b \in B \}$Source: Lecture 11, Slide 6. Chromatic number The chromatic number of a graph is the minimum number of colors needed to color a graph. Source: Lecture 06, Slide 62. Codomain If f is a function from A to B, we call B the codomain of f. Source: Lecture 10, Slide 68. Commutative Operator A binary operator$\diamond$is called commutative when the following is always true:$a\diamond b = b \diamond a$Source: Lecture 01, Slide 69. Complete Induction See Principle of Complete (or Strong) Induction below. Source: Lecture 05, Slide 5. Connected In an undirected graph, two nodes$u$and$v$are called connected if there is a path from$u$to$v$. We denote this as$u\leftrightarrow v$. If$u$is not connected to$v$, we write$u\not\leftrightarrow v$. Source: Lecture 06, Slide 16. Connected Component A connected component of an undirected graph$G=(V,E)$is a non empty set$C\subseteq V$where • For any nodes$u,v\in C$, the relation$u\leftrightarrow v$holds. • For any nodes$u\in C$and$v\in V-C$, the relation$u\not\leftrightarrow v$holds. Source: Lecture 06, Slide 25. Consequent In an implication of the form "If P is true, then Q is true", the consequent is the term "Q is true". Source: Lecture 02, Slide 14. Contrapositive The contrapositive of the statement "p → q" is the statement "¬q → ¬p". Source: Lecture 08, Slide 7. Cycle A cycle in a graph is a path from a node to itself. Source: Lecture 06, Slide 13. ## D De Morgan's Laws The following two equivalences are called De Morgan's Laws:$\lnot(p \land q) \equiv \lnot p \lor \not q$and$\lnot(p \lor q) \equiv \lnot p \land \lnot q$. Source: Lecture 07, Slide 50. Direct Proof A proof that starts with an initial set of assumptions then applies simple logical steps to directly derive a result. Source: Lecture 01, Slide 10. Disproof A disproof is an argument establishing why a statement is false. This is often done by stating you will disprove a statement, writing its negation, and writing a normal proof that the statement is false. Source: Lecture 02, Slide 4. Domain If f is a function from A to B, we call A the domain of f. Source: Lecture 10, Slide 68. Domain of Discourse (First-Order Logic) The set of objects to which any variable can refer. Source: Lecture 08, Slide 20. ## E Equivalence (Logic) Two propositional formulas are called equivalent if they have the same truth tables. Source: Lecture 08, Slide 5. Even Number An integer$n$is even if there exists some integer$k$such that$n=2k$Source: Lecture 01, Slide 11. Existential Statement An existential statement is a statement of the form: "There exists an$x$for which$P(x)$is true. The negation of an existential statement is a universal statement. Source: Lecture 01, Slide 37. Existence and uniqueness proof An existence and uniqueness proof is one where you show that there is at least and at most one object of a type. Source: Lecture 06, Slide 38. ## F First-Order Logic A logical system for reasoning about properties of objects. Augments the logical connectives from proposition logic with predicates, functions, and quantifiers. Source: Lecture 08, Slide 16. Function A function f is a mapping from one set A to another set B such that every element of A is associated with a single element of B. For each a âˆˆ A, there is some b âˆˆ B with f(a) = b. If f(a) = bâ‚€ and f(a) = bâ‚?, then bâ‚€ = bâ‚?. Source: Lecture 10, Slide 68. Function (First-Order Logic) A function maps objects to one another. Source: Lecture 08, Slide 16. ## G Graph A graph is an ordered pair$G=(V,E)$where$V$is a set of nodes, and$E$isi a set of edges, which are either ordered pairs or unordered pairs of elements from$V$. Source: Lecture 06, Slide 4. ## H ## I Identity Element An identity element for a binary operator$\diamond$, is some value$z$such that for any$a$,$a\diamond z=z\diamond a=a$Source: Lecture 01, Slide 22. Implication An implication is a statement of the form: If P is true, then Q is true. Source: Lecture 02, Slide 13. Implication (Logic) The$\rightarrow$connective is used represent implications. The statement$p \rightarrow q$means that "whenever$p$is true,$q$is true as well. The only truth values of p and q that make an implication false are when p is true and q is false. Otherwise, the implication is true." Source: Lecture 07, Slide 18. Inductive Hypothesis In a proof by induction during the inductive step: the assumption that$P$is true for$k$Source: Lecture 03, Slide 6. Inductive Step In a proof by induction: prove that if$P$is true for some arbitrary natural number$k$, then$P$must also be true for$k+1$Source: Lecture 03, Slide 6. Injective Functions (Injections) A function is called injective (or one-to-one) if each element of the codomain has at most one element of the domain that maps to it. Source: Lecture 10, Slide 82. Integers The set$\mathbb{Z} = \left\{ ..., -2, -1, 0, 1, 2, ... \right\}$is the set of all the integers. Source: Lecture 00, Slide 22. Irational number An irrational number is a number that is not rational. Source: Lecture 02, Slide 49. ## K k-colorable An undirected graph$G=(V,E)$is k-colorable iff the nodes in$V$can be assigned one of$k$different colors such that no two nodes of the same color are joined by an edge. Source: Lecture 06, Slide 62. ## L Lemma A lemma is a smaller result proven specifically as a stepping stone towards a larger result. Source: Lecture 01, Slide 63. Length (Cycle) The length of a cycle is the number of edges in that cycle. Source: Lecture 06, Slide 13. Length (Path) The length of a path is the number of edges it contains, which is one less than the number of nodes in the path. Source: Lecture 06, Slide 9. Logical Operator A logical operator is an operator that takes in some number of bits and produces a new bit as output. Source: Lecture 01, Slide 47. Loop Invariants "If P is true before we perform an action, it is true after we perform an action." Source: Lecture 03, Slide 54. ## M Mapping If f is a function from A to B, we say that f is a mapping from A to B. Source: Lecture 10, Slide 68. Mathematical Proof An argument that demonstrates why a mathematical statement is true. Source: Lecture 01, Slide 7. ## N Natural numbers The set$\mathbb{N} = \left\{0, 1, 2, 3 ... \right\}$is the set of all the natural numbers. Source: Lecture 00, Slide 22. Natural Numbers Cardinality Theorem:$|\mathbb{N}| = |\mathbb{N}^2|$. Source: Lecture 11, Slide 21. Theorem:$|\mathbb{N}| \neq |\mathbb{R}|$. Source: Lecture 11, Slide 61. Negation The negation of statement X is the opposite of the statement. This is often used to disprove a statement. Source: Lecture 02, Slide 5. Negating First-Order Statements$\neg \forall x. \varphi \equiv \exists x. \neg \varphi\neg \exists x. \varphi \equiv \forall x. \neg \varphi\neg(p \wedge q) \equiv p \to \neg q\neg(p \to q) \equiv p \wedge \neg q$Source: Lecture 09, Slide 33. Null Set A set which contains no elements is called a null set, also represented as$\phi$. Source: Lecture 00, Slide 16. ## O Odd Number An integer$n$is odd if there exists some integer$k$such that$n=2k+1$Source: Lecture 01, Slide 11. Ordered Pair An ordered pair (a, b) is a pair of elements in a specific order. Source: Lecture 05, Slide 65. ## P Path A path from$v_1$to$v_n$is a sequence of nodes$v_1,v_2,\ldots,v_n$where$\{v_k, v_{k+1}\}\in E$for all natural numbers in the range$1\le k\le n-1$. Source: Lecture 06, Slide 9. Piecewise Functions Functions specified with different rules applying to different elements. Source: Lecture 10, Slide 75. Pigeonhole Principle If m objects are placed into n bins, where m>n then some bin contains at least 2 objects. Source: Lecture 10, Slide 08. Planar Graph A planar graph is a graph where there is a way to draw it in a 2D plane without any of the edges crossing. Source: Lecture 06, Slide 57. Predicate (First-Order Logic) A predicate describes properties of an object. Applying a predicate to arguments produces a proposition, which is either true or false. Source: Lecture 08, Slide 22. Principle of Mathematical Induction The principle of mathematical induction states that if$P(0)$is true and for any$k \in \mathbb{N}$, if$P(k)$being true implies$P(k+1)$is true, then$P(n)$is true for all$n \in \mathbb{N}$. Source: Lecture 03, Slide 4. Principle of Complete (or Strong) Induction The principle of complete (or strong) induction states that if$P(0)$is true and for any$k \in \mathbb{N}$, if$P(0), P(1), \dots, P(k)$all being true implies$P(k+1)$is true, then$P(n)$is true for all$n \in \mathbb{N}$. Source: Lecture 04, Slide 60. Proof An argument that demonstrates why a conclusion is true. Source: Lecture 01, Slide 6. Proof by Contradiction A proof by contradiction works as follows: • To prove that P is true, assume that P is not true. • Based on the assumption that P is not true, conclude something impossible. • Assuming the logic is sound, the only valid explanation is that the original assumption must have been wrong. • Therefore, P can't be false, so it must be true. Source: Lecture 02, Slide 45. Proof by Induction A proof by induction is a way to use mathematical induction to show that some result is true for all natural numbers n. Source: Lecture 03, Slide 6. Proposition A proposition is a statement that is, by itself, either true or false. Source: Lecture 07, Slide 5. Propositional Logic Propositional logic is a mathematical system for reasoning about propositions and how they relate to one another. Source: Lecture 07, Slide 11. Propositional Connective (Logic) One of the following: negation, conjunction, disjunction, implication, biconditional, true, false. Source: Lecture 08, Slide 4. Propositional Variable (Logic) A propositional variable is a variable that is either true or false. Source: Lecture 07, Slide 12. Power Set The power set of any set$S$, written$\mathcal P \left({S}\right)$, is the set of all subsets of$S$, including the empty set and$S$itself. Source: Lecture 00, Slide 43. ## Q Quantifier (First-Order Logic) A quantifier is a statement that expresses that some property is true for some or all choices that could be made. Source: Lecture 08, Slide 29. ## R Rational number A rational number is a number that can be written as$r = p/q$where$p$and$q$are integers and$q\neq 0$. Source: Lecture 02, Slide 49. ## S Self-Inverting Operator A binary operator$\diamond$with identity element$z$is called self-inverting when for any$a$we have:$a\diamond a=z$Source: Lecture 01, Slide 57. Set A Set is an unordered collection of distinct objects, which can be anything (including other sets). Source: Lecture 00, Slide 12. Set builder notation A set builder notation is a mathematical notation for describing a set by stating the properties that its members must satisfy. Source: Lecture 00, Slide 25. Simple Cycle A simple cycle in a graph is a cycle that does not revisit any nodes or edges (except the start/end node). Source: Lecture 06, Slide 14. Simple Path A simple path in a graph is a path that does not revisit any nodes or edges. Source: Lecture 06, Slide 14. Strong Induction See Principle of Complete (or Strong) Induction below. Source: Lecture 05, Slide 5. Subset A set$S$is a subset of set$T$(denoted$ S \subseteq T $) if all elements of$S$are also elements of$T$. Source: Lecture 00, Slide 40. Lecture 10, Slide 87. ## T Tournament A tournament is a contest for$n \ge 1$people in which each person plays exactly one game against each other person, and there are no ties. Source: Lecture 04. Slide 39. Tournament Graph A visual representation of a tournament. Source: Lecture 04. Slide 39. Truth Table A truth table is a table showing the truth value of a propositional logic formula as a function of its inputs. Source: Lecture 07, Slide 14. ## U Universal Statement A universal statement is a statement of the form: "For all$x$,$P(x)$is true. The negation of an existential statement is an existential statement. Source: Lecture 01, Slide 37. Unordered Pair An unordered pair is a set {a, b} of two elements (remember that sets are unordered). Source: Lecture 05, Slide 65. ## V Vacuous Truth A statement of the form "All objects of type$P$are also of type$Q$" is called vacuously true if there are no objects of type$P$. Source: Lecture 00, Slide 42. Victory Chain A victory chain in a tournament is a way of lining up the players so that every player beats the player that comes after them. Source: Lecture 04. Slide 40. ## W ## X XOR Operator The exclusive or (called XOR for short), is a logical operator, denoted$\bigoplus\$,that operates on two bits and returns 0 if they are the same and 1 if they are different.

Source: Lecture 01, Slide 48.