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

0-9

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

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:

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.