8. Glossary#

antisymmetric#: A binary relation $\mathcal{R}$ on a set $A$ is antisymmetric if and only if, for every $a,b \in A$, $(a,b) \in \mathcal{R}$ and $(b,a) \in \mathcal{R}$ $\rightarrow$ $a=b$.
bijective#: A function is bijective if it is both injective and surjective.
binary relation#: Let $A$ and $B$ be sets. A binary relation from $A$ to $B$ is a subset of $A \times B$. A binary relation on $A$ is a subset of $A \times A$.
binary tree height#: The height of a rooted binary tree $T$, denoted $h(T)$, is the maximal length of any simple path in the tree with the root as one of its endpoints.
bipartite graph#: A bipartite graph is a graph $G = (V,E)$ whose vertices can be partitioned into two disjoint sets $V_1$ and $V_2$ such that every edge in $E$ has one endpoint int $V_1$ and one endpoint in $V_2$.
bound variable#: A variable which has been bound to a specific value or bound to a specific range of values through quantifiers.
cardinality#: The cardinality of a finite set is the number of distinct elements contained in the set. For a set $A$ its cardinality is denoted $|A|$. Two sets $A$ and $B$ have the same cardinality if there exists a bijection between them. When this is the case, we write $|A| = |B|$
Cartesian product#: The Cartesian product of two sets $A$ and $B$ is the set of all pairs $(a,b)$ where $a \in A$ and $b \in B$. The Cartesian product is denoted $A \times B$.
clique#: For a graph $G = (V,E)$ a clique is an induced subgraph of $G$ that is complete.
codomain#: When a binary relation from set $A$ to set $B$ is a function, we call $B$ the codomain of the function.
combination#: An $r-$combination is an unordered arrangement of $r$ elements of a set. An $r$-combination of a set is a subset with $r$ elements.
comparable#: In a partially ordered set $(A, \preceq)$, two elements $x, y$ are *comparable$ if $x \preceq y$ or $y \preceq x$. If both $x \not\preceq y$ and $y \not\preceq x$, then $x$ and $y$ are said to be incomparable.
complete bipartite graph#: A complete bipartite graph is a bipartite graph whose vertices can be partitioned into two sets $V_1$ and $V_2$ and there is an edge for every vertex in $V_1$ to every vertex in $V_2$. Where $|V_1| = m$ and $|V_2| = n$, The complete bipartite graph is denoted $K_{m,n}$.
complete graph#: A complete graph is a graph where every one of its vertices is adjacent to every other vertex. A complete graph of order $n$ is denoted $K_n$.
composition#: Given a function $f: B \rightarrow C$ and a function $g: A\rightarrow B$, the composition of $f$ and $g$ is the function $f \circ g: A \rightarrow C$ defined as $(f \circ g)(a) = f(g(a))$.
congruence class#: The congruence class modulo $m$ of an integer $x$ is the set of all integers congruent to $x$ modulo $m$.
congruent#: Two integers $a$ and $b$ are congruent modulo a positive integer $m$ if $m$ divides $a - b$.
conjecture#: A conjecture is a formal statement that is likely to be true, but has not yet been proved to be true. Once proven to be true, it may become a formal theorem or lemma.
connected#: Two vertices $u, v$ in a graph are connected if there exists a path from $u$ to $v$. Otherwise, $u$ and $v$ are said to be disconnected. A graph is connected if every pair of vertices in the graph is connected.
connected component#: An induced subgraph $H = (W,F)$ of a graph $G = (V,E)$ is a connected component if $H$ is a connected graph and adding any other vertex $v \in V \setminus W$ would make $H$ disconnected.
consistent#: A set of propositional formulas is consistent if is an assignment of truth values to the variables so that every proposition is simultaneously true.
contingency#: A propositional formula that is neither a tautology nor a contradiction is a contingency.
contradiction#: A propositional formula that is always false, for every possible truth assignment, is a contradiction.
corollary#: A corollary is a special case of a theorem, lemma, or proposition. It follows directly from a theorem and is not typically proved explicitly. Corollaries are stated to show an “important result” or “important implication” of of a theorem.
countably infinite#: A set $A$ is countably infinite if $|A| = |\mathbb{N}|$.
cover#: Let $a,b$ be elements of a set $A$ and $(A, \preceq)$ be a poset. The element $b$ covers $a$ if $a \preceq b$ and there does not exist another element $c \in A$ such that both $a \preceq c$ and $c \preceq b$.
cycle graph#: A cycle graph is a graph with exactly one cycle. The cycle graph of order $n$ is denoted $C_n$.
directed acycling graph#
DAG#: A directed acyclic graph (DAG) is a directed graph with no directed cycles.
directed graph#: A directed graph is a pair $(V,E)$ consisting of a non-empty set of vertices $V$ and a set of directed edges $E$ with $E \subseteq V \times V$.
directed path#: A directed path (or simply path) of a directed graph $G = (V,E)$ is a sequence of vertices $(v_n)$ where $(v_i, v_{i+1}) \in E$ for for $1 \leq i < n$.
disjoint sets#: Sets $A$ and $B$ are said to be disjoint if $A \cap B = \varnothing$.
divisible#: If $a$ and $b$ are integers, with $a \neq 0$, we say $a$ divides $b$ if there exists an integer $q$ such that $b = aq$. When $a$ divides $b$ we write $a \,|\, b$.
domain#: When a binary relation from set $A$ to set $B$ is a function, we call $A$ the domain of the function.
domain of definition#: The set of all preimages of a partial function.
domain of discourse#
universal set#
universe#: The set of objects over which certain variables range. That is, the set from which an object can be substituted for a variable.
empty set#: The empty set is the unique set containing no elements. It is denoted by $\varnothing$.
equally-likely#: In a finite sample space $S$, if all outcomes are equally likely, then the probability of an event $E$ occurring is $p(E) = |E| / |S|$.
equivalence class#: Let $\sim$ denote an equivalence relation on a set $A$. Then, for an element $a \in A$, the equivalence class of $a$ is the set $\{b \in A \ |\ b \sim a\}$.
equivalence relation#: A binary relation $\mathcal{R}$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive.
Euler circuit#: An Euler circuit is a circuit in a connected undirected graph which includes every edge exactly once.
Euler path#: An Euler path is a path in an undirected graph which includes every edge exactly once.
event#: An event is a subset of a sample space.
existential quantifier#
$\exists$#: “There exists”, “For some”, “There is a”, “There is at least one”. An existential quantifier asserts that a predicate is true for at least one value in the domain.
experiment#: An experiment is a procedure which yields a particular outcome from a set of possible outcomes.
finite set#: A set $A$ is finite if its cardinality is a natural number $n$. That is, $|A| < |\mathbb{N}|$.
free variable#: A variable which is not bound.
genealized pigeon hole principle#: If $N$ objects are placed into $k$ boxes, then there is at least one box containing $\lceil N/k \rceil$ or more objects.
graph#
simple graph#: A graph is a pair $(V,E)$ consisting of a non-empty set of vertices $V$ and a set of edges $E$. $E$ is a subset of the set $\{ \{u,v\} \ |\ u,v \in V\}$.
greatest common divisor#: For two non-zero integers $a$ and $b$, $d$ is the greatest common divisor of $a$ and $b$ if $d \mid a$, $d \mid b$, and any other common divisor of $a$ and $b$ also divides $d$.
Hamilton circuit#: A Hamilton circuit is a simple circuit in a connected undirected graph which passes through every vertex other than the starting and ending vertex exactly once.
Hamilton path#: A Hamilton path is a simple path in a connected undirected graph visits every vertex exactly one.
in-degree#: The in-degree of a vertex $v$ in a directed graph is the number of edges which terminate at $v$. It is denoted $deg^-(v)$.
injective#: A function is injective if every element in the range of the function has a unique preimage. That is, for a function $f : A \rightarrow B$, $\forall a_1, a_2 \in A, a_1 \neq a_2 \rightarrow f(a_1) \neq f(a_2)$.
intersection#
set intersection#: The intersection of two sets $A$ and $B$ is the set of elements which are members of both $A$ and $B$. The intersection of $A$ and $B$ is denoted $A \cap B$.
inverse function#: Given a bijection $f$ from set $A$ to set $B$, then the inverse of $f$, denoted $f^{-1}$ is a function from $B$ to $A$ defined as $f^{-1}(b) = a \leftrightarrow f(a) = b$.
isomorphic graphs#: Two simple graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a bijection function $f$ from $V_1$ to $V_2$ with the property that two vertices $v_1, u_1 \in V_1$ are adjacent in $G_1$ if and only if $f(v_1)$ and $f(u_1)$ are adjacent in $G_2$.
least common multiple#: The least common multiple of two positive integers $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$.
lemma#: A lemma is a formal statement that can be shown to be true, and is used as part of the proof of another theorem. It is a “helper theorem”.
loop invariant#: A loop invariant is a property of a program that is true before and after each iteration of a loop.
maximal#: An element $m$ of a set $A$ with a partial order $\preceq$ is maximal if for any $a \in A$ such that $m \preceq a$, then $m = a$.
maximal clique#: A maximal clique of $G = (V,E)$ is a clique that cannot be made larger by including any other adjacent vertex of $V$.
maximum#: An element $m$ of a set $A$ with a partial order $\preceq$ is maximum if $a \preceq m$ for all $a \in A$.
minimal#: An element $m$ of a set $A$ with a partial order $\preceq$ is minimal if for any $a \in A$ such that $a \preceq m$, then $m = a$.
minimum#: An element $m$ of a set $A$ with a partial order $\preceq$ is minimum if $m \preceq a$ for all $a \in A$.
monotonic function#: A function is monotonic if it is either non-increasing or non-decreasing. A function is strictly monotonic if it is either strictly non-increasing or strictly non-decreasing.
neighbourhood#: The neighbourhood of a vertex $v$ of a graph $G = (V,E)$ is the set of all vertices adjacent to $v$ in $G$.
non-decreasing#: A function $f: \mathbb{R} \rightarrow \mathbb{R}$ is non-decreasing if for all $x,y \in \mathbb{R}$, $x \leq y \rightarrow f(x) \leq f(y)$. A strictly non-decreasing or strictly increasing function has $x < y \rightarrow f(x) < f(y)$.
non-increasing#: A function $f: \mathbb{R} \rightarrow \mathbb{R}$ is non-increasing if for all $x,y \in \mathbb{R}$, $x \leq y \rightarrow f(x) \geq f(y)$. A strictly non-increasing or strictly decreasing function has $x < y \rightarrow f(x) > f(y)$.
open formula#: A formula which has at least one free variable.
order of a graph#: A graph $G = (V,E)$ of order $n$ has $|V| = n$.
out-degree#: The out-degree of a vertex $v$ in a directed graph is the number of edges which start at $v$. It is denoted $deg^+(v)$.
partial function#: A binary relation $\mathcal{R}$ form $A$ to $B$ is a partial function if it is univalent.
partial order#: A binary relation $\mathcal{R}$ on a set $A$ is a partial order if it is reflexive, antisymmetric, and transitive.
partially ordered set#
poset#: A partially ordered set or poset is a set $A$ along with a partial order on that set; a poset is a tuple $(A,\preceq)$.
partition#: A partition of a set $A$ is a collection of disjoint subsets of $A$ such that their union is all of $A$.
path#: A path of a simple graph $G = (V,E)$ is a sequence of vertices $(v_n)$ where an edge exists between $v_i$ and $v_{i+1}$ for $1 \leq i < n$.
permutation#: A permutation of a set of objects is an ordered arrangement of those objects. An ordered arrangement of $r$ objects is a called an $r$-permutation.
pigeon hole principle#: Let $k$ be a positive integer. If there are more than $k$ objects to be placed into $k$ boxes, then at least one box contains two or more objects.
planar graph#: A planar graph is a graph that can be drawn with no overlapping edges.
power set#: The power set of a set $A$ is the set of all possible subsets of $A$. The power set of $A$ is denoted by $\mathcal{P}(A)$.
predicate#: A symbol which represents a property or relation. Often, the statement or relation itself is called a predicate.
predicate Logic#: A logic system extending propositional logic to include predicates, quantifiers, and variables.
prime#: An integer $p > 1$ is prime if the only divisors of $p$ are $1$ and $p$.
product rule#: Given two choices, $n$ possibilities for the first, and $m$ possibilities for the second, then there are a total of $n \times m$ different combinations of choices.
proof#: A proof is a precise, formal, and valid argument which establishes the truth of a statement.
proposition#: A proposition is a formal statement that can be shown to be true, but the importance of this fact is less than that of a theorem.
proposition (logic)#: A declarative sentence or statement has a truth value. It is a statement which is either true of false.
propositional formula#: A syntactic formula which combines propositions into a compound statement via connectives. Propositional formulas have a truth value, unlike propositional functions which have one or more free variables.
propositional function#: A function formed by a predicate and one or more variables. A proposition is obtained by applying particular values to the variables or by bounding the variables by logical quantifiers,
propositional logic#: A logic system dealing with propositions, relations between propositions, and the construction of arguments based on propositions.
quantifier#: An operator that specifies how many objects in a domain of discourse satisfy an open formula. Examples include the universal quantifier and existential quantifier.
range#: The range of a function $f : A \rightarrow B$ is the set of all images of $f$ under $A$. It is denoted by $f(A)$.
rational number#: A number $n$ is rational if there exists integers $p$ and $q$ such that $n = \frac{p}{q}$ and $q \neq 0$.
recurrence relation#: A recurrence relation for a sequence $(a_n)$ is an equation definition $a_n$ in terms of one of more of the previous terms in the sequence.
recursive definition#: A recursive definition of a set defines elements of the set in terms of other elements in the set.
reflexive#: A binary relation $\mathcal{R}$ on a set $A$ is reflexive if and only if, for every $a \in A$, $(a,a) \in \mathcal{R}$.
relatively prime#: Two integers are relatively prime if their greatest common divisor is $1$. We call two such integers co-prime.
rooted subtree#: Given a non-root vertex $v$ of a rooted tree, the subtree rooted at $v$ is the subgraph rooted at $v$ and induced by $v$ and all its descendants.
rooted tree#: A rooted tree is a tree in which one of the vertices has been designated as the root.
sample space#: The sample space of an experiment is the set of all possible outcomes.
satisfiable#: A propositional formula is satisfiable if its truth value can be true under some truth assignment. If every possible truth assignment makes the formula have false as its truth value, that formula is said to be unsatisfiable.
sequence#: A sequence is a function from the subset of the integers, typically $\mathbb{N}$, to a set $S$.
singleton#: A singleton is a set with cardinality one. That is, it is a set with exactly one member.
string#: A string is a finite sequence of symbols from a finite set of symbols called the alphabet.
strongly connected component#: An induced subgraph $H = (W,F)$ of a directed graph $G = (V,E)$ is a strongly connected component if $H$ is a strongly connected directed graph and adding any other vertex $v \in V \setminus W$ would make $H$ not strongly connected.
subgraph#
proper subgraph#: A subgraph of a graph $G = (V,E)$ is another graph $(W,F)$ such that $W \subseteq V$ and $F \subseteq E$. A proper subgraph of $G$ if $W \subsetneq V$.
subset#: A set $A$ is a subset of the set $B$, written $A \subseteq B$, if every member of $A$ is also a member of $B$.
sum rule#: Given a choice, where one can either choose from a group of $n$ or a group of $m$ possibilities, then there are a total of $n + m$ different choices.
surjective#: A function is surjective if its codomain and range are equal. That is, for a function $f : A \rightarrow B$, $\forall\ b \in B \exists\ a \in A$ such that $f(a) = b$.
symmetric#: A binary relation $\mathcal{R}$ on a set $A$ is symmetric if and only if, for every $a,b \in A$, $(a,b) \in \mathcal{R} \rightarrow (b,a) \in \mathcal{R}$.
tautology#: A propositional formula that is always true, for every possible truth assignment, is a tautology.
theorem#: A theorem is a formal statement that can be shown to be true. It establishes a truth from which other theorems can be proved, or algorithms constructed.
total#: A binary relation $\mathcal{R}$ from $A$ to $B$ is total if, for every element $a \in A$, there exists an element $b \in B$ such that $(a,b) \in \mathcal{R}$.
total order#: A total order is a partial order $\preceq$ on a set $A$ where, for any two elements $a,b \in A$, $a \preceq b$ or $b \preceq a$.
totally ordered set#: A totally ordered set is a set $A$ along with a total order $\preceq$ on that set; a totally ordered set is a tuple $(A,\preceq)$.
transitive#: A binary relation $\mathcal{R}$ on a set $A$ is transitive if and only if, for every $a,b,c \in A$, $(a,b) \in \mathcal{R}$ and $(b,c) \in \mathcal{R}$ $\rightarrow$ $(a,c) \in \mathcal{R}$.
tree#: A tree is a simple connected graph with no cycles.
trivial proof#: A proof that the statement $p \rightarrow q$ is true due to the fact that $q$ is always true.
truth assignment#: A truth assignment is the assignment of a truth value (true or false) to a propositional variable. Equally, it is the replacement of a propositional variable with a truth value.
tuple#: A tuple is a finite ordered sequence of elements (from a set). An $n$-tuple is a tuple with $n$ elements.
uncountably infinite#: A set $A$ is uncountably infinite if $|A| > |\mathbb{N}|$.
underlying graph#: Given a directed graph $G = (V,E)$, its underlying graph is the undirected graph obtained by replacing every directed edge with an undirected edge.
union#
set union#: The union of two sets $A$ and $B$ is the set of elements which are members of $A$ or members of $B$, or members of both. The union of $A$ and $B$ is denoted $A \cup B$.
univalent#: A binary relation $\mathcal{R}$ from $A$ to $B$ is univalent or right-unique if, for every $a \in A$, and for every $b,c \in B$ we have: $(a,b) \in \mathcal{R} \land (a,c) \in \mathcal{R} \rightarrow b = c$
universal quantifier#
$\forall$#: “For all”, “For any”, “Given any”. A universal quantifier asserts that a predicate is true for any and every value in the domain.
vacuous proof#: A proof that the statement $p \rightarrow q$ is true due to the fact that $p$ is always false.
variable#: A symbol which is used as a placeholder for a mathematical object. The set of mathematical objects that can be used in place of a variable is limited by its domain.
weakly connected component#: A weakly connected component of a directed graph is the directed subgraph induced by a connected component of its underlying graph.
well-ordered#: A set is well-ordered is every one of its non-empty subsets has a least element.
well-ordering principle#: The well-ordering principle states that every non-empty subset of the positive integers has a least element.
wheel graph#: A wheel graph is a cycle graph in which one extra vertex has been added which connects to every other vertex in the cycle. The wheel graph of order $n$ is denoted $W_n$.