User:Richard Pinch/sandbox

Rank of a partially ordered set

The maximum cardinality of a chain in a partially ordered set. If $(P,\le)$ is a partially ordered set then the rank of $b$ relative to $a$, where $a \le b$ is the rank of the interval $[a,b]$; if $P$ has a minimum element $0$, then the rank $\rho(x)$ of an element $x$ is the rank of $x$ relative to $0$. A chain $C$ in $P$ is maximal if it no proper superset of $C$ is a chain. If all maximal chains have the same cardinality, then $P$ is said to be graded by rank.

If the rank of each element of the poset $(P,\le)$ is finite, and there is a finite number $p_n$ of elements of rank $n$ (in particular, if $P$ is finite$) then the rank generating function of $P$ is the formal series '"`UNIQ-MathJax1-QINU`"' ===='"`UNIQ--h-1--QINU`"'References==== * Stanley, Richard P. ''Enumerative combinatorics'' '''I''' Wadsworth & Brooks/Cole (1986) ISBN 0-534-06546-5 [https://zbmath.org/?q=an%3A 0608.05001 Zbl 0608.05001] ='"`UNIQ--h-2--QINU`"'Jeffreys distance= A measure of the divergence between two [[probability distribution]]s, developed by H. Jeffreys. For probability distributions on a finite set of size $n$, given by $P = (p_1,\ldots,p_n)$ and $Q = (q_1,\ldots,q_n)$, the Jeffreys distance is '"`UNIQ-MathJax2-QINU`"' See also: [[Kullback–Leibler-type distance measures]]. ===='"`UNIQ--h-3--QINU`"'References==== * Jeffreys, Harold "An invariant form for the prior probability in estimation problems" ''Proc. R. Soc. Lond., Ser. A.'' '''186''' (1946) 453-461 [https://doi.org/10.1098/rspa.1946.0056 DOI 10.1098/rspa.1946.0056] [https://zbmath.org/?q=an%3A0063.03050 Zbl 0063.03050] ='"`UNIQ--h-4--QINU`"'Series-parallel graph= A class of [[graph]]s related to ideas from electrical networks. It is convenient to take "graph" to mean unoriented graph allowing loops and multiple edges. A two-terminal series-parallel graph $(G,h,t)$ has two distinguished vertices, ''source'' $h$ and ''sink'' $t$ (or "head and "tail"). The class is built recursively from the single edge $P_2 = ((\{h,t\}, \{ht\}), h,t)$ with $h$ as head and $t$ as tail, using the operations of series and parallel combination. It is assumed that the graphs to be combined have disjoint vertex sets. The series combination of $(G_1, h_1,t_1)$ and $(G_2, h_2,t_2)$ is the graph obtained by identifying $t_1$ with $h_2$ and taking $h_1$ as head and $t_2$ as tail. The parallel combination of $(G_1, h_1,t_1)$ and $(G_2, h_2,t_2)$ is the graph obtained by identifying $h_1$ with $h_2$ and $t_1$ with $t_2$ then taking $h_1=h_2$ as head and $t_1=t_2$ as tail. ... Series-parallel graphs are characterised by having no subgraph homeomorphic to $K_4$, the [[complete graph]] on $4$ vertices. =='"`UNIQ--h-5--QINU`"'References== * Andreas Brandstädt, Van Bang Le; Jeremy P. Spinrad, "Graph classes: a survey". SIAM Monographs on Discrete Mathematics and Applications '''3'''. Society for Industrial and Applied Mathematics (1999) ISBN 978-0-898714-32-6 [https://zbmath.org/?q=an%3A0919.05001 Zbl 0919.05001] ='"`UNIQ--h-6--QINU`"'Polarity= A correspondence derived from a [[binary relation]] between two sets, introduced by G. Birkhoff: a special case of a [[Galois correspondence]]. Let $R$ be a relation from $A$ to $B$, equivalently a subset of $A \times B$. Define ''polar'' maps between the [[power set]]s, $F : \mathcal{P}A \rightarrow \mathcal{P}B$ and $G : \mathcal{P}B \rightarrow \mathcal{P}A$ by '"`UNIQ-MathJax3-QINU`"' and '"`UNIQ-MathJax4-QINU`"' Make $\mathcal{P}A$, $\mathcal{P}B$ [[partially ordered set]]s by subset inclusion. Then $F$ and $G$ are order-reversing maps, and $FG$ and $GF$ are order-preserving (monotone). Indeed, $F$ and $G$ are quasi-inverse, that is, $FGF = F$ and $GFG = G$; hence $FG$ and $GF$ are [[closure operator]]s. The closed pairs $(U,V)$ with $V = F(U)$ and $U = G(V)$ may be ordered by $(U_1,V_1) \le (U_2,V_2) \Leftrightarrow U_1 \subseteq U_2 \Leftrightarrow V_1 \supseteq V_2$. This ordered set, denoted $\mathfrak{B}(A,B,R)$, is a [[complete lattice]] with '"`UNIQ-MathJax5-QINU`"' and '"`UNIQ-MathJax6-QINU`"' Every complete lattice $L$ arises in this way: indeed, $L = \mathfrak{B}(L,L,{\le})$. =='"`UNIQ--h-7--QINU`"'References== * Birkhoff, Garrett ''Lattice theory'' American Mathematical Society (1940) [https://zbmath.org/?q=an%3A0063.00402 Zbl 0063.00402] * Davey, B.A.; Priestley, H.A. ''Introduction to lattices and order'' (2nd ed.) Cambridge University Press (2002) ISBN 978-0-521-78451-1 [https://zbmath.org/?q=an%3A1002.06001 Zbl 1002.06001] ='"`UNIQ--h-8--QINU`"'Frame= A generalisation of the concept of topological space occurring in the theory of logic and computation. A ''frame'' is a [[complete lattice]] $(X,{\le})$ (a lattice with all meets and joins) satisfying the frame distributivity law, that binary meets distribute over arbitrary joins: '"`UNIQ-MathJax7-QINU`"' The powerset $\mathcal{P}(A)$ of a set $A$ forms a frame. If $(X,\mathfrak{T})$ is a [[topological space]], with $\mathfrak{T}$ the collection of open sets, then $\mathfrak{T}$ forms a subframe of $\mathcal{P}(X)$: it should be noted that whereas the join is set-theoretic union, the meet operation is given by '"`UNIQ-MathJax8-QINU`"' where $\mathrm{Int}$ denotes the [[interior]]. ===='"`UNIQ--h-9--QINU`"'References==== <table> <tr><td valign="top">[1]</td> <td valign="top"> Steven Vickers ''Topology via Logic'' Cambridge Tracts in Theoretical Computer Science '''5''' Cambridge University Press (1989) ISBN 0-521-36062-5 [https://zbmath.org/?q=an%3A0668.54001 Zbl 0668.54001] </td></tr> <tr><td valign="top">[2]</td> <td valign="top"> Jonathan S. Golan ''Semirings and their Applications'' Springer (2013) ISBN 9401593337</td></tr> </table> ='"`UNIQ--h-10--QINU`"'Alexandrov topology= ''on a [[partially ordered set]] $(X,{\le})$'' A topology which is discrete in the broad sense, that arbitrary unions and intersections of open sets are open. Define an upper set $U \subseteq X$ to be one for which $u \in U$ and $u \le x$ implies $x \in U$. The Alexandrov topology on $X$ is that for which all upper sets are open. The Alexandrov topology makes $X$ a [[T0 space]] and the [[Specialization of a point|specialisation]] order is just the original order ${\le}$ on $X$. ===='"`UNIQ--h-11--QINU`"'References==== * Johnstone, Peter T. ''Stone spaces'' Cambridge Studies in Advanced Mathematics '''3''' Cambridge University Press(1986) [https://zbmath.org/?q=an%3A0586.54001 Zbl 0586.54001] ='"`UNIQ--h-12--QINU`"'Exponentiation= The algebraic and analytic operations generalising the operation of repeated multiplication in number systems. For positive integer $n$, the operation $x \mapsto x^n$ may be defined on any system of numbers by repeated multiplication '"`UNIQ-MathJax9-QINU`"' where $\cdot$ denotes multiplication. The number $n$ is the ''exponent'' in this operation. The repeated operations may be carried out in any order provided that multiplication is [[associativity|associative]], $x \cdot (y \cdot z) = (x \cdot y) \cdot z$. In this case we have '"`UNIQ-MathJax10-QINU`"' If the operation is also [[commutativity|commutative]] then we have '"`UNIQ-MathJax11-QINU`"' We may extend the definition to non-positive integer powers by defining $x^0 = 1$ and '"`UNIQ-MathJax12-QINU`"' whenever this makes sense. We may extend the definition to rational number exponents by taking $x^{1/n}$ to be any number $y$ such that $y^n = x$: this may denote none, one or more than one number. ==='"`UNIQ--h-13--QINU`"'Positive real numbers=== Exponentiation of positive real numbers by rational exponents may be defined by taking $x^{1/n}$ to be the unique positive real solution of $y^n = x$: this always exists. We thus have $x^q$ well-defined for $x>0$ and any rational exponent $q$. Exponentiation preserves order: if $x > y$ then $x^q > y^q$ if $q > 0$ and $x^q < y^q$ if $q < 0$. We can now define exponentiation with real exponent $r$ by defining $x^r$ to be the limit of $x^{q_n}$ where $q_n$ is a sequence of rational numbers converging to $r$. There is always such a sequence, and the limit exists and does not depend on the chosen sequence. For positive real numbers there are mutually inverse [[exponential function, real|exponential]] and [[logarithmic function|logarithm]] functions which allow the alternative definition '"`UNIQ-MathJax13-QINU`"' Here the exponential function may be regarded as $\exp(x) = e^x$ where [[E-number|$e$]] is the base of natural logarithms. ==='"`UNIQ--h-14--QINU`"'Complex numbers=== Exponentiation of complex numbers with non-integer exponents may be defined using the complex [[exponential function]] and [[logarithmic function|logarithm]]. The exponential function is analytic and defined on the whole complex plane: the logarithmic function requires a choice of [[Branch of an analytic function|branch]], corresponding to a choice of the range of values for the [[argument]], to make it single-valued. Given such a choice, exponentiation may be defined as $z^w = \exp(w \log z)$. ==='"`UNIQ--h-15--QINU`"'General algebraic systems=== For a general (not necessarily associative) binary operation, it is necessary to define the order of operations. The left and right ''principal powers'' are defined inductively by '"`UNIQ-MathJax14-QINU`"' and '"`UNIQ-MathJax15-QINU`"' respectively. A binary operation is [[power associativity|power associative]] if the powers of a single element form an associative subsystem, so that exponentiation is well-defined. ='"`UNIQ--h-16--QINU`"'Logarithm= The operation inverse to [[exponentiation]]. Over the fields of [[Real number|real]] or [[complex number]]s, one speaks of the [[logarithm of a number]]. The [[logarithmic function]] is the complex analytic function inverse to the [[exponential function]]. In a finite Abelian group, the [[discrete logarithm]] is the inverse to exponentiation, with applications in [[cryptography]]. The [[Zech logarithm]] in a finite field is related to the discrete logarithm. ='"`UNIQ--h-17--QINU`"'''I''-semigroup= A topological semigroup defined on a totally ordered set. Let $I$ be a [[totally ordered set]] with minimum element $0$ and maximum element $1$, and equipped with the [[order topology]]; then $0$ acts as a zero (absorbing) element for the semigroup operation and $1$ acts as an identity (neutral) element. Although not required by the definition, it is the case that an ''I''-semigroup is commutative. Examples. The real interval $[0,1]$ under multiplication. The ''nil interval'' $[\frac12,1]$ with operation $x \circ y = \max(xy,\frac12)$. The ''min interval'' $[0,1]$ with operation $x \cdot y = \min(x,y)$. ===='"`UNIQ--h-18--QINU`"'References==== * Hofmann, K.H.; Lawson, J.D. "Linearly ordered semigroups: Historical origins and A. H. Clifford’s influence" ''in'' Hofmann, Karl H. (ed.) et al., ''Semigroup theory and its applications. Proceedings of the 1994 conference commemorating the work of Alfred H. Clifford'' London Math. Soc. Lecture Note Series '''231''' Cambridge University Press (1996) pp.15-39 [https://zbmath.org/?q=an%3A0901.06012 Zbl 0901.06012] ='"`UNIQ--h-19--QINU`"'Composition algebra= An algebra $A$ (not necessarily associative) over a field $K$ with a [[quadratic form]] $q$ taking values in $K$ which is multiplicative, $q(x\cdot y) = q(x) q(y)$. The composition algebras over the field $\mathbf{R}$ of [[real number]]s are the real numbers, the field of [[complex number]]s $\mathbf{C}$, the [[skew-field]] of [[quaternion]]s, the non-associative algebra of [[octonions]]. ===='"`UNIQ--h-20--QINU`"'References==== * Springer, Tonny A.; Veldkamp, Ferdinand D. ''Octonions, Jordan algebras and exceptional groups''. Springer Monographs in Mathematics. Springer (2000) ISBN 3-540-66337-1 [https://zbmath.org/?q=an%3A1087.17001 Zbl 1087.17001] ='"`UNIQ--h-21--QINU`"'Cayley–Dickson process= A construction of an algebra $A_1$ from an algebra $A$ with involution over a field $K$ which generalises the construction of the [[complex number]]s, [[quaternion]]s and [[octonion]]. Fix a parameter $d \in A$. As a set $A_1 = A \times A$ with addition defined by $(a_1,a_2) + (b_1,b_2) = (a_1+b_1, a_2+b_2)$ and multiplication by '"`UNIQ-MathJax16-QINU`"' The algebra $A_1$ has an involution $(x_1,x_2) \mapsto (x_1^*,-x_2)$. ='"`UNIQ--h-22--QINU`"'BCH code= A [[cyclic code]] over a finite field. Fix length $n$ and ground field $\mathbf{F}_q$ and a design distance parameter $\delta$. Let $\beta$ be a primitive $n$-th root of unity in a suitable extension of $\mathbf{F}_q$. The generator of the cyclic code is the least common multiple $g$ of the minimal polynomials (over $\mathbf{F}_q$) of the elements $\beta^1, \beta^2, \ldots, \beta^{\delta-1}$. The minimum distance of the BCH code generated by $g$ is at least $\delta$: this is the ''BCH bound''. As an example, let $q=2$ and $\beta$ be a primitive $7$-th root of unity in $\mathrm{F}_{8}$: we may take $\beta$ to satisfy the polynomial $x^3 + x + 1$. Choose $\delta = 3$. The minimal polynomial for $\beta^2$ is the same as that of $\beta$, so that the cyclic code is generated by the word $1101000$. This is in fact the Hamming [7,4] code. ===='"`UNIQ--h-23--QINU`"'References==== * Goldie, Charles M.; Pinch, Richard G.E. ''Communication theory'', London Mathematical Society Student Texts. '''20''' Cambridge University Press (1991) iSBN 0-521-40456-8 [https://zbmath.org/?q=an%3A0746.94001 Zbl 0746.94001] ='"`UNIQ--h-24--QINU`"'Leibniz algebra= An algebra over a field $K$ generalising the properties of a [[Lie algebra]]. A Leibniz algebra $L$ is a $K$-algebra with multiplication denoted by $[\cdot,\cdot]$ satisfying '"`UNIQ-MathJax17-QINU`"' Every Lie algebra is a Leibniz algebra, and a Leibniz algebra is a Lie aglebra if in addition $[x,x] = 0$. The free Leibniz algebra on a generating set $X$ may be defined as the quotient of the free non-associative algebra over $K$ (cf. [[Free algebra over a ring]]) by the ideal generated by all elements of the form $[ x, [y,z]] - [[x,y],z] + [[x,z],y] $. The standard Leibniz algebra on $X$ is obtained from the vector space $V = KX$ and forming the tensor module '"`UNIQ-MathJax18-QINU`"' with the multiplication '"`UNIQ-MathJax19-QINU`"' when $v \in V$ and '"`UNIQ-MathJax20-QINU`"' The standard algebra is then a presentation of the free algebra on $X$. ====References==== * Mikhalev, Alexander A.; Shpilrain, Vladimir; Yu, Jie-Tai, ''Combinatorial methods. Free groups, polynomials, and free algebras'', CMS Books in Mathematics '''19''' Springer (2004) ISBN 0-387-40562-3 [https://zbmath.org/?q=an%3A1039.16024 Zbl 1039.16024] =Free differential calculus= Let $F$ be a [[free group]] on a set of generators $X = \{x_i : i \in I \}$ and $R[F]$ the [[group ring]] of $F$ over a commutative unital ring $R$. The ''Fox derivative'' $\partial_i$ are maps from $F$ to $R[F]$ defined by '"`UNIQ-MathJax21-QINU`"' '"`UNIQ-MathJax22-QINU`"' '"`UNIQ-MathJax23-QINU`"' It follows that '"`UNIQ-MathJax24-QINU`"' The maps extend to [[derivation]]s on $R[F]$. ===References=== * D. L. Johnson, ''Presentations of Groups'', London Mathematical Society Student Texts '''15''' Cambridge University Press (1997) ISBN 0-521-58542-2 =Martin's axiom= An axiom of set theory. Let $(P,{<})$ be a [[partially ordered set]] satisfying the [[countable chain condition]] and $D$ a family of $\mathfrak{k}$ dense subsets of $P$ for $\mathfrak{k}$ a cardinal less than $2^{\aleph_0}$. Then $\text{MA}_{\mathfrak{k}}$ asserts that there is a $D$-generic filter on $P$. Martin's axiom $\text{MA}$ is the conjunction of $\text{MA}_{\mathfrak{k}}$ for all $\mathfrak{k} < 2^{\aleph_0}$. The case $\text{MA}_{\aleph_0}$ holds in [[ZFC]]. MA is a consequence of the [[Continuum hypothesis]] ($\text{CH}$) but $\text{MA} \wedge \text{CH}$ is consistent with ZFC if ZFC is consistent. ===='"`UNIQ--h-25--QINU`"'References==== * Thomas Jech, ''Set Theory'', Perspectives in Mathematical Logic, Third Millennium Edition, revised and expanded. Springer (2007) ISBN 3-540-44761-X ='"`UNIQ--h-26--QINU`"'Hurwitz zeta function= ''generalised zeta function'' An [[Dirichlet series]] related to the [[Riemann zeta function]] which may be used to exhibit properties of various [[Dirichlet L-function]]s. The Hurwitz zeta function $\zeta(\alpha,s)$ is defined for real $\alpha$, $0 < \alpha \le 1$ as '"`UNIQ-MathJax25-QINU`"' The series is convergent, and defines an analytic function, for $\Re s > 1$. The function possesses an [[analytic continuation]] to the whole $s$-plane except for a simple pole of residue 1 at $s=1$.

References

• Tom M. Apostol, "Introduction to Analytic Number Theory", Undergraduate Texts in Mathematics, Springer (1976) ISBN 0-387-90163-9 Zbl 0335.10001