Theory of the map function:
Definition and characterization:The map function is the typical higher-order function used in functional programming. As a higher-order function the starting point of the map function is a function $f : A \to B$. In order to analyze its properties, we will fix a number $n$ which is the size of the tuples it is applied to. \[ map_{f,n} : A^n \to B^n \] If we define $P$ to be the equivalence relation associated to $f$, then equivalence with respect to the map function $map_{f,n}$ is the equivalence relation naturally defined on Cartesian powers $P^n$. The theory of this equivalence relation $P^n$ and its position in the lattice of equivalence relations will play a central role in the theory of the map function.
Lattice-theoretic decompositions:
As a starting point, we will decompose the equivalence relation $P^n$ in the lattice of equivalence relations, so that we can build up equivalence conditions from simpler foundations. There are natural meet and join decompositions of $P^n$.
- The meet decomposition is the same as the meet decomposition for any tuple-producing function. The equivalence relations $=_{f \circ first}$, $=_{f \circ second}$, ... together produce all the information produced by $map_{f,n}$.
- The join decomposition is produced by all equivalence relations which are the meet of all the different accessor functions except for a single one which has $f$ applied to it.
Inverse images:
A subset of $B^n$ is an n-ary relation on $B$. The inverse image of map applied to an n-relation of fixed arity, will be an n-ary relation of $A^n$ which is $P^n$-complete. The importance of $P^n$ therefore reveals itself in the theory of inverse images. \[ map_{f,n}^{-1}(R) \] Given any function, the family of inverse images of the function will be a partition topology of $P$-closed sets. Therefore, the family of all inverse images of $map_{f,n}$ will consist of all $P^n$-closed sets. A set $S$ is $P^n$ closed if for any element $x$ then the entire equivalence class containing $x$ is contained in $S$.
Relational equivalence:
Suppose that we have an n-ary relation and we want to know if it is $P^n$-closed with respect to some equivalence relation $P$. Throughout this discussion, we have been talking about the equivalence relation $P$ associated to any function. If we consider a function as a single-valued binary relation then this is equivalent to being $(P,second)$-closed. In other words, $P$-equal elements are replaceable in the first slot. The dual concept is being $(first,P)$-closed.
There is an alternative expression of the condition of being $(P,second)$ closed. Two elements are replaceable in the first slot if they have the same out neighbours, therefore for any binary relation $(P,second)$ closure is determined by out-neighbour equality. Dually, $(first,P)$ is determined by in-neighbour equality. The lattice-theoretic join decomposition comes into play here, as $P^2$-equality is simply the combination of in-neighbour equality and out-neighbour equality. This produces the natural $P^2$ equality associated to any binary relation.
For example, in a preorder its $P^2$ equivalence relation is determined by its symmetric components. In a symmetric, reflexive binary relation $P^2$ equality is determined by adjacency equality, and so on. In general, for any n-ary relation $P^n$ equality can be determined if all $P$ equal members are replaceable in slots of members of the relation.
Inflation and deflation of relations:
Standard terminology refers to the condensation of preorders, but now we have described the inverse process. Therefore, there are really two opposite processes: the inflation and deflation of relations. We can inflate relations with the inverse image of the map function $map_{f,n}^{-1}$ and we can deflate/condense relations by the images of the map function $map_{f,n}$ by projecting relationally equal elements to some representation of their equivalence class.
Any subclass closed family of relations defined by forbidden edge patterns, will not be preserved by inflation. Therefore, if a relation is single valued, inverse single valued, antisymmetric, antitransitive, or any related condition an inflated version of it may not be. Inflating partial orders therefore only has to lose the antisymmetric condition to get an inflated preorder. In general, we can inflate relations by adding more equal versions of elements and deflate them by condensing equal elements into single ones.
Relational structures:
Monotone maps:The inverse image of the map function gives us a structures that partial orders are preserved in. We can therefore now define structure preserving maps of partial orders:
Definition. a mapping $f : (A,R) \to (B,S)$ is a monotone map if $R \subseteq map_{f,2}^{-1}(S)$.
Monotone maps can therefore be understood by the inclusion relations among preorders. If we have a monotone map then the input structure $R$ is preserved in the induced superstructure $map_{f,2}^{-1}(S)$.
Example. the lattice of finite sets is contained in the total preorder of sets preordered by cardinality. All finite sets have larger cardinality then their subsets, so this is a subrelation. But it is also a larger relation, because in the cardinality preordering {0,1} is less then {3,4,5} even though it is clearly not a subset. Therefore, the inflated preorder contains strictly more elements. This is the inclusion of relations induced by the monotone map from finite sets to their cardinalities.
Relations and algebra:
It is not hard to see the classical definition of homomorphisms of semigroups and related algebraic structures is a special case of the relational definition. A semigroup homomorphism from $(S, \circ)$ to $(T,*)$ is expressed as: \[ f(a \circ b) = f(a)*f(b) \] If we expressed $\circ$ and $*$ as single-valued ternary relations this homomorphism can be recast as a structure preserving map of ternary relations: \[ \circ \subseteq map_{f,3}^{-1}(*) \] While this doesn't reveal anything new about semigroups, using the relational approach we can define structure preserving maps from semigroups to hypersemigroups. This allows us to relate the most important hypersemigroups to the semigroups that can be embedded in them.
Partial structural preservation:
Euler's totient function is one of the most important functions in all mathematics. Among other things, Euler's totient function defines the number of generators of the cyclic group. It therefore, solves the problem of iteration equality in semigroups. Euler's totient function has the property: \[ gcd(a,b) = 1 \implies \varphi(ab) = \varphi(a)\varphi(b) \] Therefore, the totient function preserves multiplication in the special case that two numbers are coprime. This suggests that there are some important cases where partial structures are preserved. We can get the exact structure preserved through intersection of a structure with its induced superstructure: \[ * \cap map_{\varphi,3}^{-1}(*) \] This produces a single-valued ternary relation that has at least coprime integers in its domain. In the case of the function from finite sets and union to cardinalities and sum, the only case the operation is preserved is when the two sets are disjoint. The intersection therefore consists solely of the ternary relation of disjoint sets and their union.
Universal relational theory:
A relational structure can be defined by a family of relations over a set. Algebraic structures in universal algebra can be cast to this form using single-valued relation. Then a structure preserving map can be defined by: \[ R \subseteq map_{f,n}^{-1}(S) \] The superstructure that preserves the previous structure is defined by the family of induced superstructures of each of the relations. The structural ordering is then defined by the product order of the inclusion order of all the different relations.
Topology and pseudometrics:
Pseudometrics:Pseudometrics on a set are naturally associated with a partial order on them in the standard manner orderings are defined on function spaces. We therefore, have the following characterization of short maps: \[ d_Y \circ map_{f,2} \subseteq d_X \] Let $P$ be the equivalence relation naturally associated with the function $f$. Then the induced structure $d_Y \circ map_{f,2}$ is an inflated version of the pseudometric $d_Y$ in the sense that $P^2$ is an equivalence subrelation of its kernel. Due to the backwardness of the ordering, the structural ordering on pseudometrics is the inverse pointwise ordering.
Topology:
Open maps are naturally associated to any topological space in a similar manner that structure-preserving maps are associated to relations. The open map preserving superstructure is defined by the family of image-open sets.
Definition. Given a map from topological spaces $(S,\tau_1)$ to $(T,\tau_2)$ then the family of all image-open sets consists of all subsets of $S$ whose image is in $\tau_2$
This allows us to define the preserving superstructures of open maps, but these are not the most common maps we use in topology despite the apparent naturality of their definition. To deal with continuous maps, we need to define the family of all inverse images of open sets in the output topology.
Definition. Given a map from topological spaces $(S,\tau_1)$ to $(T,\tau_2)$ then the family of all inverses images $F$ of open sets of $\tau_2$ is defined by $\{ A \in \mathcal{P}(S): \exists O \in \tau_2 : A = f^{-1}(O) \}$.
A continuous map is then defined to be one for which $F \subseteq \tau_1$. To compensate for the backwardness of this definition, we can define the induced structure to exist in inverse ordering of sets. Then $F$ is clearly the superstructure that preserves structures under continuous maps.
Structural orderings:
We can now associate structural orderings to the various kinds of structure-preserving maps. These various kinds of maps then preserve the structure of their elements in the structural ordering.| Mapping type | Structural ordering |
|---|---|
| Monotone maps | Inclusion of binary relations |
| Semigroup homomorphisms | Inclusion of ternary relations |
| Relation homomorphisms | Inclusion of n-ary relations |
| Nonexpanding metric maps | Inverse pointwise ordering of metrics |
| Open maps | Inclusion ordering |
| Continuous maps | Inverse inclusion ordering |
| Combined structures | Product ordering of each structure |
An example of the combined ordering is monoid homomorphisms, these preserve both a unary relation consisting of their identity element and a single valued ternary relation. Therefore, their superstructures contain parent unary relations and ternary relations. Topological groups then preserve both their monoid structure and their continuous order, producing a product order of a unary relation, a ternary relation, and an inverse inclusion ordering. Linear maps induce a parent ternary relation and a family of parent binary relations for each action of the structure, ordered by the product ordering, etc.
Categories are generalized posets. Given any category we have discussed so far, we can create a morphism to morphism mapping from the category to a structural ordering represented as a thin category. This takes any structure preserving map and assigns to an ordered pair consisting of the child structure and the parent structure it is preserved in. In other words, structure preserving maps are like edges in structural orderings with additional information. Categories in general can be formed from any kind of order-respecting mapping. Both monotone and extensive mappings, which satisfy a simpler condition, form categories.
No comments:
Post a Comment