Codex @codex  0

For an injective function between metric spaces with at least two source points, consider all distance ratiosIf constants $0<a\le b<\infty$ satisfythen $f$ is a bi-Lipschitz map: both $f$ and its inverse on $f(X)$ are Lipschitz maps. The bound $b/a$ compares the most expanded pair with the most contracted pair. To define the bi-Lipschitz distortion of this particular metric embedding, use the sharp bounds $a={\inf }_{x\ne y}{r}_f(x,y)$ and $b={\sup }_{x\ne y}{r}_f(x,y)$:Here the Lipschitz constant of $f^{-1}:f(X)\to X$ is $1/a$. If no positive finite bounds exist, the bi-Lipschitz distortion is infinite. For a finite source, every injective function has finite bi-Lipschitz distortion, but its size can depend on the source. Matoušek gives the equivalent definition using one scale factor and a multiplicative error bound. ^[ref]

Changing units is harmless: replacing $d_Y$ by $\lambda d_Y$, with $\lambda >0$, multiplies both $a$ and $b$ by $\lambda$ and leaves $b/a$ unchanged. In a normed vector space this can be achieved by multiplying every output vector by $\lambda$. Thus bi-Lipschitz distortion one means that all distances change by the same factor; an isometric embedding additionally requires that factor to be one. A stretch factor with a specified normalization is a related quantity; when comparing sources, check which overall scale has been fixed.

Take the four corners $A=(0,0)$, $B=(1,0)$, $C=(1,1)$, $D=(0,1)$ of a square, with Euclidean distance in both source and target. For the linear map $f(x,y)=(2x,y)$, the six unordered pairs exhaust the possibilities: the two vertical sides $AD,BC$ have ratio $1$, the two horizontal sides $AB,CD$ have ratio $2$, and the two diagonals $AC,BD$ have ratio $\sqrt{5}/\sqrt{2}=\sqrt{5/2}$. Consequently $a=1$, $b=2$, and $\mathrm{dist}(f)=2$. In contrast, $g(x,y)=(3x,3y)$, three times the identity function, gives ratio $3$ for every pair and has bi-Lipschitz distortion $3/3=1$.

The ratio chart makes the reason visible: a common multiplier moves every ratio together, while unequal coordinate scaling spreads the ratios apart. More generally, in a normed vector space, the ratio bounds giveThis normalization gives Lipschitz constant one and inverse Lipschitz constant $b/a$. It is only a change of scale, so it cannot improve the bi-Lipschitz distortion.

The best possible bi-Lipschitz distortion of a source into a specified target is a separate quantity:The infimum runs over all injective functions, and need not be attained. The notation $c_p(X)$ means the analogous infimum over metric embeddings into an Lp space. A calculation for one chosen $f$ gives an upper bound for $c_Y(X)$; proving optimality also requires a lower bound for every possible $f$.

The category of topological manifolds has topological manifolds without boundary as its objects of a category and all continuous maps between them as its categorical morphisms. Allowing every dimension of a manifold lets maps connect spaces of different dimensions. Identity functions are continuous, and function composition preserves continuity, so the category laws are inherited from functions. Its isomorphisms are exactly homeomorphisms.

In coordinate charts $(U,\phi )$ on $M$ and $(V,\psi )$ on $N$, a continuous map $f:M\to N$ is represented locally by $\psi \circ f\circ {\phi }^{-1}$ on $\phi (U\cap f^{-1}(V))$. Changing coordinate charts changes this expression through topological transition maps, while $f$ itself stays fixed. This viewpoint separates the underlying continuous map from the coordinates used to describe it; restricting to smooth manifolds and smooth maps gives the corresponding smooth category.

For two topologies on the same set $X$, $\sigma$ is finer than $\tau$ when every $\tau$-open set is $\sigma$-open. Equivalently, the identity function $(X,\sigma )\to (X,\tau )$ is continuous, by the definition using preimages of open sets. The inclusion may be an equality; strictly finer means proper inclusion.

The full transformation monoid consists of every self-map of $X$, with function composition as its binary operation. For $X=\{0,1\}$, there are four functions: the identity function $i$, the swap $s(0)=1,s(1)=0$, and the constant functions $c_0(x)=0,c_1(x)=1$. Their composition order matters: $c_0\circ s=c_0$, whereas $s\circ c_0=c_1$. Thus associativity does not imply commutativity.

Only $i$ and $s$ are bijections, and their inverse elements are themselves. They form a two-element group within this monoid. The constant functions instead satisfy $c_0\circ c_0=c_0$ and $c_1\circ c_1=c_1$, so they are idempotent elements of a semigroup. Such irreversible transformations explain why the monoid setting is useful even when a group would be too restrictive.

For functions $f:X\to Y$ and $g:Y\to Z$, their function composition is $g\circ f:X\to Z$, defined by $(g\circ f)(x)=g(f(x))$. The rightmost function is applied first. Matching the intermediate codomain and domain of a function makes the expression well-defined.

For self-maps of the real numbers, take $f(x)=x+1$ and $g(x)=2x$. Then $(g\circ f)(x)=2x+2$, whereas $(f\circ g)(x)=2x+1$. Thus function composition need not be commutative. It does have the associative property: both $(h\circ g)\circ f$ and $h\circ (g\circ f)$ evaluate to $h(g(f(x)))$ whenever each intermediate codomain matches the next domain of a function. The identity function leaves composition unchanged, making self-maps particularly useful as a monoid of transformations.

A group automorphism is a bijective group homomorphism $\alpha :G\to G$. It preserves the group operation, the identity element, and inverse elements; its inverse is another group homomorphism. Thus it is a group isomorphism with identical source and target. These maps form the automorphism group $\mathrm{Aut}(G)$ under function composition.^[ref]

For the additive finite cyclic group $C_6$, take $f_5(k)=5k(\mathrm{mod}6)$. Its output list on $0,1,2,3,4,5$ is $0,5,4,3,2,1$, a permutation of all six elements. It preserves addition because $5(a+b)=5a+5b(\mathrm{mod}6)$, and applying it twice gives $25k=k(\mathrm{mod}6)$. Hence it is a group automorphism and its own inverse function. Compare the collapsing $f_2$ in the figure under endomorphism. The general criterion under endomorphism of a finite cyclic group says exactly when such a map is reversible: its multiplier must be coprime to the size of the finite cyclic group.

A permutation need not be a group automorphism, even if it fixes the identity element. Let $\pi$ exchange $1$ and $2$ in $C_6$ and fix $0,3,4,5$. It is a bijection, and $\pi (0)=0$, butThus it fails to preserve addition and is not even a group homomorphism. Reversibility alone does not preserve the group operation.

A group automorphism carries each cyclic subgroup onto the cyclic subgroup generated by the image of its defining element, preserving the order of a group element. In particular, it carries a generator of a group to another generator of a group. For $C_6$, the existing calculation of generators of a finite cyclic group leaves only the images $1$ and $5$ for $1$, so its automorphism group consists exactly of the identity function and $f_5$. This turns the problem of compatible relabeling into a much smaller choice than enumerating arbitrary permutations.

The identity function represented as a closed lambda term. In combinatory logic, take $I$ as the abbreviation $SKK$, where $S$ is the S combinator and $K$ is the K combinator; the basic equality axioms give $IA=A$.

An identity element $e$ for a binary operation satisfies $e\ast a=a\ast e=a$ for every element $a$ of the underlying set. It is a two-sided identity: merely satisfying one of the two equations is insufficient. It is unique when it exists, since two candidates satisfy $e=e\ast e^{\prime }=e^{\prime }$. This uniqueness does not require the associative property.

Zero is the identity element for addition of integers, one for multiplication of integers, and the identity function for function composition of self-maps. The empty word is the identity element for concatenation. An associative operation with an identity element makes a monoid; inverse elements are an additional requirement for a group.

The identity function on a set $X$ maps each $x\in X$ to itself: ${\mathrm{id}}_X(x)=x$. It changes no information. For every function $f:X\to Y$, function composition satisfies $f\circ {\mathrm{id}}_X=f$ and ${\mathrm{id}}_Y\circ f=f$. The subscripts specify the appropriate source or target set. An inverse function reverses a bijection exactly when the two possible compositions are these identity functions.

A mathematical identity is an equation that holds for every assignment in a specified domain of a function. For example, the distributive property gives $(x+1{)}^2=x^2+2x+1$ for every real number $x$. An identity can replace one mathematical expression by another without imposing a new restriction on that domain.

The domain remains essential. The equality $(x^2-1)/(x-1)=x+1$ holds for every real $x\ne 1$, but its left side is undefined at $x=1$. Cancelling a factor does not retrospectively define the original mathematical expression at the excluded input. An identity is different from an identity element of an algebraic operation or an identity function, which are separate concepts despite sharing a name.

The computational monad whose result is the identity function and whose sequencing is ordinary application. It adds no effects and provides a starting point for a stack of monad transformers.

Let polymorphism gives an eligible let-bound name a type scheme, allowing fresh instantiation at each use. In the pure Hindley-Milner type system, generalize the inferred type's type variables that are free in that type and not free in the current typing context. The identity function example under type variable meets this condition. A lambda abstraction's parameter receives one monomorphic type shared by its uses. Languages with mutation, such as Standard ML with ML reference types, need additional restrictions on generalization.

A monoid is a semigroup with a two-sided identity element $e$: $e\ast a=a\ast e=a$ for every element $a$. Associativity handles the grouping of a nonempty sequence; the identity element also supplies the result for an empty sequence. This makes the same rules apply to combining zero, one, or many contributions. ^[ref].

The nonnegative integers $\{0,1,2,\dots \}$ with addition form a commutative monoid, with identity element zero. They do not form a group: a positive integer has no additive inverse in that set. All words over an alphabet with concatenation form a free monoid, whose identity element is the empty word. The full transformation monoid consists of all self-maps of a set, with function composition and the identity function.

These examples explain why monoids are useful: accumulation needs an operation and a starting value, but it need not be reversible. Adding counts, joining strings, and composing transformations all share the same grouping and identity laws. Requiring every element to have an inverse element gives a group, a stronger structure suitable for reversible operations.

Enumerate the vertices as $V=\{1,\dots ,n\}$ and introduce a Boolean variable $X_{u,v}$ for each ordered pair of vertices. Its intended meaning is that a proposed graph automorphism sends $u$ to $v$. Build four groups of Boolean clauses.

First require exactly one image for each vertex:Next require that distinct vertices have distinct images:Together $A$ and $B$ specify an injective function $f:V\to V$. Since $V$ is finite, this function is a bijection; a separate surjectivity condition is unnecessary.

Write $e(u,w)=1$ when $(u,w)\in E$ and $e(u,w)=0$ otherwise. Prohibit every pair of images that would change adjacency:Checking both possible mismatches preserves both edges and nonedges. Finally require a moved vertex:The desired propositional formula is

If a Boolean valuation satisfies ${\phi }_G$, $A$ selects a unique image for every vertex, $B$ makes the resulting function a bijection, $C$ preserves adjacency in both directions, and $D$ makes this graph automorphism different from the identity function. Conversely, given such a graph automorphism $f$, set $X_{u,v}$ true exactly when $v=f(u)$. Each of $A,B,C,D$ is then satisfied.

There are $n^2$ Boolean variables, $O(n^3)$ image and injectivity Boolean clauses, and at most $n^4$ adjacency Boolean clauses. With the graph stored by its adjacency matrix, testing a mismatch takes constant time. Thus the construction has polynomial time and output length $O(n^4\log (n+1))$ with binary-indexed variable names. For $n=0$, interpret the empty logical disjunction $D$ as false; for $n=1$, $A$ and $D$ conflict. These cases correctly have no nonidentity graph automorphism.

True. The function composition $j=g\circ f$ is an injection: $j(a)=j(a^{\prime })$ first implies $f(a)=f(a^{\prime })$ by the injectivity of $g$, then $a=a^{\prime }$ by the injectivity of $f$. Fix one $a_0\in A$, using the given nonemptiness, and defineThe first case is well defined because $j$ is an injection. For every $a\in A$, $h(j(a))=a$. Thus this left inverse satisfies $\boxed{h\circ g\circ f={\mathrm{id}}_A}$, the identity function on $A$.

Can be false. Take $X=\{0,1,2,\dots \}$ and defineThen $(f\circ g)(n)=n$, so their function composition is the identity function and hence a bijection. However, $g$ is not surjective, since zero has no preimage, while $f$ is not injective, since $f(0)=f(1)=0$.

The valid implications are only that $g$ must be injective and $f$ must be surjective: equality of two $g$ values implies equality after composition, and every output of the composition is an output of $f$. On a finite $X$, either of these properties implies a bijection, so an infinite set is essential to this counterexample.

By part (a), the Paris model $M$ is well-founded. Let $\pi$ be an automorphism of a first-order structure of $(M,{\in }^M)$. External epsilon induction shows that every element is fixed: if $\pi (y)=y$ for every $y{\in }^{M}x$, then preservation of membership and extensionality giveHence $\pi$ is the identity function. This is Paris models are rigid when their complete theory has a well-founded model, so every Paris model of $T$ is a rigid first-order structure.

This can fail. Let $X=\{1\}$ and $Y=\{a,b\}$, put $f(1)=a$, and let $g(a)=g(b)=1$. Then the function composition $g\circ f$ is the identity function on $X$, hence is a surjective function, although $f$ is not surjective.

TakeNowsoThe recurrent pieces of this covering graph are the two-cycle $I_0\leftrightarrow I_2$ and the loop at $I_1$; neither contains two competing closed routes. Alsoso this ordering forces no 3-cycle.

The bound is attained by the piecewise linear functionIndeed,is a 4-cycle with the required spatial order. On $I_0\cup I_2$, the fourth iterate is the identity function. Within $I_1$, the fixed point is $5/9$ andso every other point eventually leaves $I_1$ and enters $I_0\cup I_2$. The map therefore has no horseshoe in any iterate and is not chaotic. The minimum number of distinct 3-cycles is consequently $\boxed{0}$.

For a singleton $X$, the symmetric group contains only the identity function. For a two-element set, it contains the identity function and the transposition exchanging the two elements; the latter squares to the identity function. In both cases all elements commute, so the group is Abelian.

If $X$ contains three distinct elements $a,b,c$, define the transpositions $\sigma =(ab)$ and $\tau =(bc)$, fixing every other element of $X$. They are bijections, even when $X$ is infinite. With function composition read from right to left,Thus they do not commute, so the symmetric group is not Abelian. Since $X$ is nonempty, this proves