Glossary

Last updated
Save as PDF

Page ID: 87143

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Example and Directions
Words (or words that have the same definition)	The definition is case sensitive	(Optional) Image to display with the definition [Not displayed in Glossary, only in pop-up on pages]	(Optional) Caption for Image	(Optional) External or Internal Link	(Optional) Source for Definition
(Eg. "Genetic, Hereditary, DNA ...")	(Eg. "Relating to genes or heredity")		The infamous double helix	https://bio.libretexts.org/	CC-BY-SA; Delmar Larsen

Glossary Entries
Word(s)	Definition	Image	Caption	Link	Source
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
Complete graph	A graph in which every pair of vertices is adjacent
Complement of a set	Let U be the universal set. A^c ={x in U, x is not in A}
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: ⪯ is reflexive : a⪯a∀a∈L ⪯ is antisymmetric : a⪯b and a≠b⇒b⋠a∀a,b∈L ⪯ is transitive : a⪯b and b⪯c⇒a⪯c∀a,b,c∈L The set together with the relation (L,⪯) is called a poset.
Principle of Mathematical Induction	A technique of proof whereby If T is a subset of N such that 1∈T, and For every k∈N, if k∈T, then (k+1)∈T. Then T=N.
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.
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
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
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