Editing Partially ordered set (section)

== Mappings between partially ordered sets ==
{{multiple image
| align = right
| direction = horizontal
| total_width = 580
| image1 = Monotonic but nonhomomorphic map between lattices.gif
| caption1 = '''Fig. 7a''' Order-preserving, but not order-reflecting (since {{nowrap|''f''(''u'') ≼ ''f''(''v'')}}, but not u {{small|<math>\leq</math>}} v) map.
| image2 = Birkhoff120.svg
| caption2 = '''Fig. 7b''' Order isomorphism between the divisors of 120 (partially ordered by divisibility) and the divisor-closed subsets of {{nowrap|{{mset|2, 3, 4, 5, 8}}}} (partially ordered by set inclusion)
}}
Given two partially ordered sets {{math|1=(''S'', ≤)}} and {{math|(''T'', ≼)}}, a function <math>f : S \to T</math> is called '''[[order-preserving]]''', or '''[[Monotonic function#In order theory|monotone]]''', or '''isotone''', if for all <math>x, y \in S,</math> <math>x \leq y</math> implies {{math|1=''f''(''x'') ≼ ''f''(''y'')}}.
If {{math|1=(''U'', ≲)}} is also a partially ordered set, and both <math>f : S \to T</math> and <math>g : T \to U</math> are order-preserving, their [[Function composition|composition]] <math>g \circ f : S \to U</math> is order-preserving, too.
A function <math>f : S \to T</math> is called '''order-reflecting''' if for all <math>x, y \in S,</math>  {{math|1=''f''(''x'') ≼ ''f''(''y'')}} implies <math>x \leq y.</math>
If {{mvar|f}} is both order-preserving and order-reflecting, then it is called an '''[[order-embedding]]''' of {{math|1=(''S'', ≤)}} into {{math|1=(''T'', ≼)}}.
In the latter case, {{mvar|f}} is necessarily [[injective]], since <math>f(x) = f(y)</math> implies <math>x \leq y \text{ and } y \leq x</math> and in turn <math>x = y</math> according to the antisymmetry of <math>\leq.</math> If an order-embedding between two posets ''S'' and ''T'' exists, one says that ''S'' can be '''embedded''' into ''T''. If an order-embedding <math>f : S \to T</math> is [[bijective]], it is called an '''[[order isomorphism]]''', and the partial orders {{math|1=(''S'', ≤)}} and {{math|1=(''T'', ≼)}} are said to be '''isomorphic'''. Isomorphic orders have structurally similar [[Hasse diagram]]s (see Fig.&nbsp;7a). It can be shown that if order-preserving maps <math>f : S \to T</math> and <math>g : T \to U</math> exist such that <math>g \circ f</math> and <math>f \circ g</math> yields the [[identity function]] on ''S'' and ''T'', respectively, then ''S'' and ''T'' are order-isomorphic.{{sfnp|Davey|Priestley|2002|pp=23–24}}

For example, a mapping <math>f : \N \to \mathbb{P}(\N)</math> from the set of natural numbers (ordered by divisibility) to the [[power set]] of natural numbers (ordered by set inclusion) can be defined by taking each number to the set of its [[prime divisor]]s. It is order-preserving: if {{mvar|x}} divides {{mvar|y}}, then each prime divisor of {{mvar|x}} is also a prime divisor of {{mvar|y}}. However, it is neither injective (since it maps both 12 and 6 to <math>\{2, 3\}</math>) nor order-reflecting (since 12 does not divide 6). Taking instead each number to the set of its [[prime power]] divisors defines a map <math>g : \N \to \mathbb{P}(\N)</math> that is order-preserving, order-reflecting, and hence an order-embedding. It is not an order-isomorphism (since it, for instance, does not map any number to the set <math>\{4\}</math>), but it can be made one by [[Injective function#Injections may be made invertible|restricting its codomain]] to <math>g(\N).</math> Fig.&nbsp;7b shows a subset of <math>\N</math> and its isomorphic image under {{mvar|g}}. The construction of such an order-isomorphism into a power set can be generalized to a wide class of partial orders, called [[distributive lattice]]s; see ''[[Birkhoff's representation theorem]]''.