# User:Richard Pinch/sandbox

## Contents

# Eulerian number

A combinatorial counting function for the number of descents in a permutation. Here we take a permutation $(a_1,\ldots,a_n)$ of $(1,\ldots,n)$ and count as a *descent* any $i$ such that $a_i > a_{i+1}$. We let
$$
\left\langle{ n \atop k }\right\rangle
$$
denote the number of permutations on $n$ elements with $k$ descents. It satisfies the recurrence relation
$$
\left\langle{ n \atop k }\right\rangle = (n-k) \left\langle{ n-1 \atop k-1 }\right\rangle + (k+1) \left\langle{ n-1 \atop k }\right\rangle
$$

The *Eulerian polynomial* is the generating function
$$
S_n(t) = \sum_{k=0}^n \left\langle{ n \atop k }\right\rangle t^k \ .
$$
The recurrence relation may be written as
$$
S_{n+1}(t) = (1+nt) S_n(t) + t(1-t)S'_n(t) \ .
$$

The Eulerian numbers appear in a related context. We define an *excedance* of a permutation to be the number of $i$ such that $a(i) > i$ (*weak* if $a_i \ge i$). Then the number of permutations with $k$ excendances is equal to the number with $k+1$ weak excedances, and is in turn equal to $\left\langle{ n \atop k }\right\rangle$.

#### References

- T. Kyle Petersen
*Eulerian Numbers*Birkhäuser (2015) ISBN 1-4939-3091-5 Zbl 06467929 - Richard P. Stanley
*Enumerative combinatorics***I**Wadsworth & Brooks/Cole (1986) ISBN 0-534-06546-5 0608.05001 Zbl 0608.05001

# Lattice valuation

A function $\nu$ on a lattice $L$ with values in a ring $R$ satisfying $$ \nu(x \wedge y) + \nu(x \vee y) = \nu(x) + \nu(y) \ . $$

#### References

- Rota, Gian-Carlo (with P. Doubilet, C. Greene, D. Kahaner, A: Odlyzko and R. Stanley)
*Finite operator calculus*Academic Press (1975) ISBN 0-12-596650-4 Zbl 0328.05007

# Series-parallel graph

A class of graphs 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.

## 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 Zbl 0919.05001

# 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 sets, $F : \mathcal{P}A \rightarrow \mathcal{P}B$ and $G : \mathcal{P}B \rightarrow \mathcal{P}A$ by
$$
F(U) = \{ b \in B : aRb\ \text{for all}\ a \in U \}
$$
and
$$
G(V) = \{ a \in A : aRb\ \text{for all}\ b \in V \} \ .
$$

Make $\mathcal{P}A$, $\mathcal{P}B$ partially ordered sets 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 operators.

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 $$ \bigwedge_{i \in I} (U_i,V_i) = \left({ \bigcap_{i\in I} U_i, FG\left({ \bigcup_{i \in I} V_i }\right) }\right) $$ and $$ \bigvee_{i \in I} (U_i,V_i) = \left({ GF\left({ \bigcup_{i \in I} U_i }\right), \bigcap_{i\in I} V_i }\right) \ . $$

Every complete lattice $L$ arises in this way: indeed, $L = \mathfrak{B}(L,L,{\le})$.

## References

- Birkhoff, Garrett
*Lattice theory*American Mathematical Society (1940) 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 Zbl 1002.06001

# 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:
$$
x \wedge \bigvee \{ y \in Y \} = \bigvee \{ x \wedge y : y \in Y \} \ .
$$

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 $$ \bigwedge \{ S \} = \mathrm{Int}\left({ \bigcap \{ S \} }\right) $$ where $\mathrm{Int}$ denotes the interior.

#### References

[1] | Steven Vickers Topology via Logic Cambridge Tracts in Theoretical Computer Science 5 Cambridge University Press (1989) ISBN 0-521-36062-5 Zbl 0668.54001 |

[2] | Jonathan S. Golan Semirings and their Applications Springer (2013) ISBN 9401593337 |

# 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 specialisation order is just the original order ${\le}$ on $X$.

#### References

- Johnstone, Peter T.
*Stone spaces*Cambridge Studies in Advanced Mathematics**3**Cambridge University Press(1986) Zbl 0586.54001

# 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
$$
x^n = x \cdot x \cdot \cdots \cdot x\ \ \ (n\,\text{times})
$$
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 associative, $x \cdot (y \cdot z) = (x \cdot y) \cdot z$. In this case we have $$ x^{m+n} = x^m \cdot x^n \ . $$

If the operation is also commutative then we have $$ (x \cdot y)^n = x^n \cdot y^n \ . $$

We may extend the definition to non-positive integer powers by defining $x^0 = 1$ and $$ x^{-n} = \frac{1}{x^n} $$ 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.

### 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 and logarithm functions which allow the alternative definition $$ x^y = \exp(y \log x) \ . $$ Here the exponential function may be regarded as $\exp(x) = e^x$ where $e$ is the base of natural logarithms.

### Complex numbers

Exponentiation of complex numbers with non-integer exponents may be defined using the complex exponential function and logarithm. The exponential function is analytic and defined on the whole complex plane: the logarithmic function requires a choice of 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)$.

### 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
$$
x^{n+1} = x \star (x^n)
$$
and
$$
x^{n+1} = (x^n) \star x
$$
respectively. A binary operation is power associative if the powers of a single element form an associative subsystem, so that exponentiation is well-defined.

# Logarithm

The operation inverse to exponentiation.

Over the fields of real or complex numbers, 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.

*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)$.

#### 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 Zbl 0901.06012

# 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 numbers are the real numbers, the field of complex numbers $\mathbf{C}$, the skew-field of quaternions, the non-associative algebra of octonions.

#### References

- Springer, Tonny A.; Veldkamp, Ferdinand D.
*Octonions, Jordan algebras and exceptional groups*. Springer Monographs in Mathematics. Springer (2000) ISBN 3-540-66337-1 Zbl 1087.17001

# 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 numbers, quaternions 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 $$ (a_1,a_2) \cdot (b_1,b_2) = (a_1b_1 - d b_2 a_2^* , a_1^*b_2 + b_1a_2) \ . $$ The algebra $A_1$ has an involution $(x_1,x_2) \mapsto (x_1^*,-x_2)$.

# 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
$$
\partial_i(x_j) = \delta_{ij} \ ,
$$
$$
\partial_i(1) = 0 \ ,
$$
$$
\partial_i(uv) = u \partial_i(v) + \partial_i(u) v \ .
$$
It follows that
$$
\partial_i(x_i^{-1}) = - x_i^{-1} \ .
$$

The maps extend to derivations 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.

#### References

- Thomas Jech,
*Set Theory*, Perspectives in Mathematical Logic, Third Millennium Edition, revised and expanded. Springer (2007) ISBN 3-540-44761-X

**How to Cite This Entry:**

Richard Pinch/sandbox.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox&oldid=42809