Appendix E Notation
The following table defines the notation used in this book. Page numbers or references refer to the first appearance of each symbol.
Symbol | Description | Location |
---|---|---|
\(x \in A\) | \(x\) is an element of \(A\) | Paragraph |
\(x \notin A\) | \(x\) is not an element of \(A\) | Paragraph |
\(\lvert A \rvert \) | The number of elements in a finite set \(A\text{.}\) | Definition 1.1.2 |
\(A \subseteq B\) | \(A\) is a subset of \(B\text{.}\) | Definition 1.1.3 |
\(\emptyset\) | the empty set | Paragraph |
\(\{\:\}\) | the empty set | Paragraph |
\(A \cap B\) | The intersection of \(A\) and \(B\text{.}\) | Definition 1.2.1 |
\(A \cup B\) | The union of \(A\) and \(B\text{.}\) | Definition 1.2.4 |
\(B - A\) | The complement of \(A\) relative to \(B\) | Definition 1.2.10 |
\(A^c\) | The complement of set \(A\) relative to the universe. | Definition 1.2.10 |
\(A\oplus B\) | The symmetric difference of \(A\) and \(B\text{.}\) | Definition 1.2.15 |
\(A \times B\) | The cartesian product of \(A\) with \(B\text{.}\) | Definition 1.3.1 |
\(\mathcal{P}(A)\) | The power set of \(A\text{,}\) the set of all subsets of \(A\text{.}\) | Definition 1.3.3 |
\(n!\) | \(n\) factorial, the product of the first \(n\) positive integers | Definition 2.2.5 |
\(\binom{n}{k}\) | \(n\) choose \(k\text{,}\) the number of \(k\) element subsets of an \(n\) element set. | Definition 2.4.3 |
\(p \land q\) | the conjunction, \(p \textrm{ and } q\) | Definition 3.1.3 |
\(p \lor q\) | the disjunction, \(p \textrm{ or } q\) | Definition 3.1.4 |
\(\neg p\) | the negation of \(p\text{,}\) “not \(p\)” | Definition 3.1.5 |
\(p \to q\) | The conditional proposition If \(p\) then \(q\text{.}\) | Definition 3.1.6 |
\(p \leftrightarrow q\) | The biconditional proposition \(p\) if and only if \(q\) | Definition 3.1.12 |
\(1\) | symbol for a tautology | Definition 3.3.2 |
\(0\) | symbol for a contradiction | Definition 3.3.4 |
\(r \iff s\) | \(r\) is logically equivalent to \(s\) | Definition 3.3.6 |
\(r \Rightarrow s\) | \(r\) implies \(s\) | Definition 3.3.11 |
\(p \mid q\) | the Sheffer Stroke of \(p\) and \(q\) | Definition 3.3.14 |
\(\blacksquare\) | Symbol that denotes the end of a proof. Can be replaced with QED | Paragraph |
\(T_p\) | the truth set of \(p\) | Definition 3.6.3 |
\((\exists n)_U(p(n))\) | The statement that \(p(n)\) is true for at least one value of \(n\) | Definition 3.8.1 |
\((\forall n)_U(p(n))\) | The statement that \(p(n)\) is always true. | Definition 3.8.3 |
\(\pmb{0}_{m\times n}\) | the \(m\) by \(n\) zero matrix | Item |
\(I_{n}\) | The \(n \times n\) identity matrix | Definition 5.2.4 |
\(A^{-1}\) | \(A\) inverse, the multiplicative inverse of \(A\) | Definition 5.2.5 |
\(\det A\textrm{ or }\lvert A \rvert\) | The determinant of \(A\text{,}\) 2 by 2 case | Definition 5.2.7 |
\(a \mid b\) | \(a\) divides \(b\text{,}\) or \(a\) divides evenly into \(b\) | Definition 6.1.5 |
\(x s y\) | \(x\) is related to \(y\) through the relation \(s\) | Paragraph |
\(r s\) | the composition of relation \(r\) with relation \(s\) | Definition 6.1.9 |
\([a]\) | The equivalence class of a | Definition 6.3.13 |
\(A/r\) | Partition of \(A\) with respect to an equivalence relation \(r\) | Definition 6.3.13 |
\(a \equiv_n b\) | \(a\) is congruent to \(b\) modulo \(n\) | Definition 6.3.15 |
\(a \equiv b (\textrm{mod } n)\) | \(a\) is congruent to \(b\) modulo \(n\) | Definition 6.3.15 |
\(r^+\) | The transitive closure of \(r\) | Definition 6.5.1 |
\(f:A \rightarrow B\) | A function, \(f\text{,}\) from \(A\) into \(B\) | Definition 7.1.1 |
\(B^A\) | The set of all functions from \(A\) into \(B\) | Definition 7.1.4 |
\(f(a)\) | The image of \(a\) under \(f\) | Definition 7.1.6 |
\(f(X)\) | Range of function \(f:X \rightarrow Y\) | Definition 7.1.7 |
\(\chi_S\) | Characteristic function of the set \(S\) | Exercise 7.1.5.4 |
\(\lvert A \rvert = n\) | \(A\) has cardinality \(n\) | Definition 7.2.7 |
\((g \circ f)(x) = g(f(x))\) | The composition of \(g\) with \(f\) | Definition 7.3.2 |
\(f \circ f = f^2\) | the “square” of a function. | Definition 7.3.5 |
\(i \textrm{ or } i_A\) | The identity function (on a set \(A\)) | Definition 7.3.8 |
\(f^{-1}\) | The inverse of function \(f\) read “\(f\) inverse” | Definition 7.3.11 |
\(log_b a\) | Logarithm, base \(b\) of \(a\) | Definition 8.4.4 |
\(\) | Definition 8.5.1 | |
\(S\uparrow\) | \(S\) pop | Definition 8.5.3 |
\(S\downarrow\) | \(S\) push | Definition 8.5.3 |
\(S*T\) | Convolution of sequences \(S\) and \(T\) | Definition 8.5.3 |
\(S\uparrow p\) | Multiple pop operation on \(S\) | Definition 8.5.6 |
\(S\downarrow p\) | Multiple push operation on \(S\) | Definition 8.5.6 |
\(K_n\) | A complete undirected graph with \(n\) vertices | Definition 9.1.10 |
\(deg(v), indeg(v), outdeg(v)\) | degree, indegree and outdegree of vertex \(v\) | Definition 9.1.30 |
\(e(v)\) | The eccentricity of a vertex | Paragraph |
\(d(G)\) | The diameter of graph \(G\) | Paragraph |
\(r(G)\) | The radius of graph \(G\) | Paragraph |
\(C(G)\) | The center of graph \(G\) | Paragraph |
\(Q_n\) | the \(n\)-cube | Definition 9.4.17 |
\(V(f)\) | The value of flow \(f\) | Definition 9.5.21 |
\(P_n\) | a path graph of length \(n\) | Definition 9.6.4 |
\(\chi(G)\) | the chromatic number of \(G\) | Definition 9.6.15 |
\(C_n\) | A cycle with \(n\) edges. | Definition 10.1.1 |
\(*\) | generic symbol for a binary operation | Definition 11.1.1 |
\(string1 + string2\) | The concatenation of \(string1\) and \(string2\) | Item a |
\([G;*]\) | a group with elements \(G\) and binary operation \(*\) | Definition 11.2.3 |
\(\gcd(a,b)\) | the greatest common divisor of \(a\) and \(b\) | Definition 11.4.4 |
\(a +_n b\) | the mod \(n\) sum of \(a\) and \(b\) | Definition 11.4.12 |
\(a \times_n b\) | the mod \(n\) product of \(a\) and \(b\) | Definition 11.4.13 |
\(\mathbb{Z}_n\) | The Additive Group of Integer Modulo \(n\) | Definition 11.4.17 |
\(\mathbb{U}_n\) | The Multiplicative Group of Integer Modulo \(n\) | Definition 11.4.18 |
\(W \leq V\) | \(W\) is a subsystem of \(V\) | Definition 11.5.1 |
\(\langle a \rangle\) | the cyclic subgroup generated by \(a\) | Definition 11.5.6 |
\(ord(a)\) | Order of a | Definition 11.5.9 |
\(V_1\times V_2 \times \cdots \times V_n\) | The direct product of algebraic structures \(V_1, V_2, \dots , V_n \) | Definition 11.6.1 |
\(G_1 \times G_2\) | The direct product of groups \(G_1\) and \(G_2\) | Definition 11.6.3 |
\(G_1 \cong G_2\) | \(G_1\) is isomorphic to \(G_2\) | Definition 11.7.9 |
\(\) | Definition 12.3.6 | |
\(dim(V)\) | The dimension of vector space \(V\) | Definition 12.3.18 |
\(\pmb{0}\) | least element in a poset | Definition 13.1.7 |
\(\pmb{1}\) | greatest element in a poset | Definition 13.1.7 |
\(D_n\) | the set of divisors of integer \(n\) | Definition 13.1.9 |
\(a \lor b\) | the join, or least upper bound of \(a\) and \(b\) | Definition 13.2.1 |
\(a \land b\) | the meet, or greatest lower bound of \(a\) and \(b\) | Definition 13.2.1 |
\([L;\lor,\land]\) | A lattice with domain having meet and join operations | Definition 13.2.2 |
\(\bar{a}\) | The complement of lattice element \(a\) | Definition 13.3.6 |
\([B; \lor , \land, \bar{\hspace{5 mm}}]\) | a boolean algebra with operations join, meet and complementation | Definition 13.3.8 |
\(\) | Definition 13.3.12 | |
\(M_{\delta_1 \delta_2 \cdots \delta_k}\) | the minterm generated by \(x_1, x_2, \ldots , x_k\text{,}\) where \(y_i=x_i\) if \(\delta_i = 1\) and \(y_i=\bar{x_i}\) if \(\delta_i = 0\) | Definition 13.6.3 |
\(A^*\) | The set of all strings over an alphabet \(A\) | Definition 14.2.1 |
\(A^n\) | The set of all strings of length \(n\) over an alphabet \(A\) | Definition 14.2.1 |
\(\lambda\) | The empty string | Definition 14.2.1 |
\(s_1+s_2\) | The concatenation of strings \(s_1\) and \(s_2\) | Definition 14.2.4 |
\(L(G)\) | Language created by phrase structure grammar \(G\) | Definition 14.2.15 |
\((S, X, Z, w, t)\) | A finite-state machine with states \(S\text{,}\) input alphabet \(X\text{,}\) output alphabet \(X\text{,}\) and output function \(w\) and next-state function \(t\) | Definition 14.3.1 |
\(m(M)\) | The machine of monoid \(M\) | Definition 14.5.1 |
\(\) | Definition 15.1.1 | |
\(a*H, H*a\) | the left and right cosets generated by \(a\) | Definition 15.2.2 |
\(G/H\) | The factor group G mod H. | Definition 15.2.20 |
\(S_A\) | The group of permutations of the set \(A\) | Definition 15.3.5 |
\(S_n\) | The group of permutations on a set with \(n\) elements | Definition 15.3.5 |
\(A_n\) | The Alternating Group | Definition 15.3.18 |
\(\mathcal{D}_n\) | The \(n\)th dihedral group | Definition 15.3.26 |
\(H \triangleleft G\) | \(H\) is a normal subgroup of \(G\) | Definition 15.4.5 |
\(ker \theta\) | the kernel of homomorphism \(\theta\) | Definition 15.4.19 |
\(d_H(a,b)\) | Hamming distance between \(a\) and \(b\) | Definition 15.5.3 |
\([R; +, \cdot]\) | a ring with domain \(R\) and operations \(+\) and \(\cdot\) | Definition 16.1.1 |
\(U(R)\) | the set of units of a ring \(R\) | Definition 16.1.10 |
\(\) | Definition 16.1.13 | |
\(\) | Definition 16.1.20 | |
\(D\) | a generic integral domain | Definition 16.1.23 |
\(\textrm{deg }f(x)\) | the degree of polynomial \(f(x)\) | Definition 16.3.1 |
\(R[x]\) | the set of all polynomials in \(x\) over \(R\) | Definition 16.3.1 |
\(R[[x]]\) | the set of all powers series in \(R\) | Definition 16.5.1 |
\(\grave x, \acute x\) | pre and post values of a variable \(x\) | Definition A.2.1 |
\(M(A)_{i,j}\) | The \(i, j\) minor of \(A\) | Definition C.1.2 |
\(C(A)_{i,j}\) | The \(i, j\) cofactor of \(A\) | Definition C.1.4 |
\(\det(A) or \lvert A \rvert\) | The determinant of \(A\) | Definition C.1.6 |