Glossary

Antisymmetric | A relation R on a set A is an antisymmetric relation provided that for all x,y∈Ax, if x R y and y R x, then x=y.

Biconditional | P if and only if Q

Bijection | A function f:A -> B such that f is both an injection and a surjection

Bipartite graph | A graph for which it is possible to divide the vertices into two disjoint sets such that there are no edges between any two vertices in the same set

Boolean algebra | a lattice that contains a least element and a greatest element and that is both complemented and distributive. The notation [B;∨,∧,¯] is used to denote the boolean algebra with operations join, meet and complementation.

Cardinality | The number of elements in a set

Chromatic number | The minimum number of colors required in a proper vertex coloring of the graph

Complement of a set | Let U be the universal set. A^c ={x in U, x is not in A}

Complete graph | A graph in which every pair of vertices is adjacent

Conditional Statement | If P then Q. P is the antecedent (hypothesis) and Q is the consequent (conclusion)

Congruent | Two integers are congruent mod n (n a positive integer) if the integers leave the same remainder upon division by n

Conjecture | a guess in mathematics

Conjunction | P and Q

Contrapositive | Of the conditional, if not Q then not P, logically equivalent to if P then Q

Converse | Of the conditional, if Q then P

Countably infinite | A set that can be put into one-to-one correspondence with the set of natural numbers

Cyclic group | Group G is cyclic if there exists a∈G such that the cyclic subgroup generated by a, ⟨a⟩ equals all of G. That is, G={na|n∈Z} in which case a is called a generator of G. The reader should note that additive notation is used for G

Digraph | A directed graph

Direct Proof | Argument that is based on "If P then Q" and "P" implies Q

Disjunction | P and Q

Division algorithm | Let m and d be integers with d>0. Then, there exists unique integers q and r with 0<=r < d such that m = dq+r

Equivalence class |
For each a∈A, the equivalence class of aa determined by ∼ is the subset of A, denoted by [a], consisting of all the elements of A that are equivalent to a

Equivalence relation | A relation that is reflexive, symmetric and transitive

Euclidean algorithm | Let a and b be integers with a≠0 and b>0. Then gcd(a, b) is the only natural number d such that (a) d divides a and d divides b, and
(b) if k is an integer that divides both a and b, then k divides d

Euler circuit | An Euler path which starts and stops at the same vertex

Euler path | A walk which uses each edge exactly once

Existential operator | There exists

Formal Language | If A is an alphabet, a formal language over A is a subset of A^∗.

Graph | an ordered pair G=(V,E) consisting of a nonempty set V (called the vertices) and a set E (called the edges) of two-element subsets of V

Greatest common divisor |
The largest natural number that divides both a and b is called the greatest common divisor of a and b

Hasse diagram | an illustration of a poset

Homomorphism | Let [G;∗] and [G′;⋄]be groups. θ:G→G′ is a homomorphism if θ(x∗y)=θ(x)⋄θ(y) for all x,y∈G

Indirect Proof | Argument based upon the contrapositive

Injection | A function f:A->B is an injection, if for every a and b in the domain of f, f(a)=f(b) implies a = b.

Intersection of two sets | Let U be the universal set. A intersect B = {x in U, x is in A and x is in B}

Inverse | Of the conditional, if not P then not Q

Isomorphism |
between two graphs G1 and G2 is a bijection f:V1→V2 between the vertices of the graphs such that if {a,b} is an edge in G1 then {f(a),f(b)} is an edge in G2

Lattice | a poset (L,⪯)for which every pair of elements has a greatest lower bound and least upper bound

Logical equivalence | Two expressions are logically equivalent provided that they have the same truth value for all possible combinations of truth values for all variables appearing in the two expressions

Monoid | a set M together with a binary operation ∗∗ with the properties

• ∗∗ is associative: ∀a,b,c∈M, (a∗b)∗c=a∗(b∗c) and
• ∗∗ has an identity in M:M: ∃e∈Msuch that ∀a∈M, a∗e=e∗a=a

Negation | not P

Partial order | Let ⪯⪯ be a relation on a set L.L. We say that ⪯⪯ is a partial ordering on LL if it is reflexive , antisymmetric , and transitive . That is:

1. ⪯ is reflexive : a⪯a∀a∈L
2. ⪯ is antisymmetric : a⪯b and a≠b⇒b⋠a∀a,b∈L
3. ⪯ is transitive : a⪯b and b⪯c⇒a⪯c∀a,b,c∈L

Principle of Mathematical Induction | A technique of proof whereby If T is a subset of N such that

1. 1∈T, and
2. For every k∈N, if k∈T, then (k+1)∈T.

Proof by Contradiction | Given "If P then Q" assume "P and not Q" to arrive at "P and not P"

Reflexive |
The relation R is reflexive on A provided that for each x∈A, x R x or, equivalently, (x,x)∈R

Relation | Let A and B be sets. A relation R from the set A to the set B is a subset of A×B

Set | A well-defined collection of objects

Statement | a declarative sentence that is either true or false but not both

String |
A string of length n, n⩾1 over alphabet A is a sequence of nn letters from A: a₁a₂…a_n. The set of all strings over A is A^*.

Subgraph | We say that G1=(V1,E1) is a subgraph of G2=(V2,E2) provided V1⊆V2 and E1⊆E2

Surjection | A function f:A ->B is a surjection if for every b in B there exists an a in A such that f(a)=b.

Symmetric | The relation R is symmetric provided that for every x,y∈A, if x R y, then y R x or, equivalently, for every x,y∈Ax, if (x,y)∈R, then (y,x)∈R

Symmetric group |
Let A be a nonempty set . The set of all permutations on A with the operation of function composition is called the symmetric group on A, denoted S_A.

The Well-Ordering Principle | for the natural numbers states that any nonempty set of natural numbers must contain a least element equivalent to the Principle of Mathematical Induction

Transitive | The relation R is transitive provided that for every x,y,z∈A, if x R y and y R z, then x R z or, equivalently, for every x,y,z∈A, if (x,y)∈R and (y,z)∈R, then (x,z)∈R

Tree | A (connected) graph with no cycles. (A non-connected graph with no cycles is called a forest.) The vertices in a tree with degree 1 are called leaves

Truth table | a summary of all the truth values of a statement

Uncountably infinite | An infinite set for which there does not exist a one to one correspondence with the natural numbers

Union of two sets | Let U be the universal set. A U B ={x in U, such that x is in A or x is in B}

Universal operator | For all or for every

Vertex coloring | An assignment of colors to each of the vertices of a graph. A vertex coloring is proper if adjacent vertices are always colored differently