poset_order_iso_of_injective_order_homs
Two finite posets with mutual injective order homomorphisms are order-isomorphic. The permutation g ∘ f on X has finite order k, so its inverse (g ∘ f)^{k-1} is order-preserving; hence f^{-1} = (g ∘ f)^{-1} ∘ g is order-preserving.
Statement
theorem poset_order_iso_of_injective_order_homs {X Y : Type*} [Fintype X] [Fintype Y] [PartialOrder X] [PartialOrder Y] (f : X →o Y) (g : Y →o X) (hf : Function.Injective f) (hg : Function.Injective g) : Nonempty (X ≃o Y)
- Source
- step towards poset_nonempty_order_iso_of_card_order_hom_eq_of_connected
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- poset_nonempty_order_iso_of_card_order_hom_eq_of_connectedLet X and Y be finite posets (possibly empty). If for every finite nonempty connected poset Z the number of order-preserving maps Z → X…
The proof, explained
Because X and Y are finite posets with mutual injections, their cardinalities are equal and f is a bijection. The composition e = g ∘ f is an order-preserving permutation of X and therefore has finite order n. Its inverse permutation p^(n - 1) is also order-preserving as an iterate of e, which implies that f reflects the ordering (f(a) ≤ f(b) implies a ≤ b). Combining bijectivity, order preservation, and order reflection proves that f is an order isomorphism between X and Y.
The posets X and Y have equal cardinality: |X| = |Y|.
Because f : X → Y and g : Y → X are both injective functions between finite types, we have |X| ≤ |Y| and |Y| ≤ |X| by Fintype.card_le_of_injective. Antisymmetry of ≤ (le_antisymm) then implies |X| = |Y|.
uses
le_antisymm,Fintype.card_le_of_injectivehave hcard : Fintype.card X = Fintype.card Y := by apply le_antisymm · exact Fintype.card_le_of_injective f hf · exact Fintype.card_le_of_injective g hg
The map f is bijective, defining a type equivalence ef : X ≃ Y.
An injective map between finite types of the same cardinality is bijective by Fintype.bijective_iff_injective_and_card. Applying this to f yields a set bijection ef : X ≃ Y via Equiv.ofBijective.
uses
Fintype.bijective_iff_injective_and_card,Equiv.ofBijectivehave hfb : Function.Bijective f := by rw [Fintype.bijective_iff_injective_and_card] exact ⟨hf, hcard⟩ let ef : X ≃ Y := Equiv.ofBijective f hfb
The composition e = g ∘ f is a monotone permutation of X.
The composite map e = g ∘ f is injective as the composition of two injective functions, hence bijective because X is finite (again by Fintype.bijective_iff_injective_and_card). It is packaged into a permutation p ∈ Equiv.Perm X with underlying function e. Furthermore, e is monotone because both f and g preserve the partial order.
uses
Fintype.bijective_iff_injective_and_card,Equiv.ofBijectivelet e : X → X := fun x => g (f x) have he_inj : Function.Injective e := by exact hg.comp hf have he_bij : Function.Bijective e := by rw [Fintype.bijective_iff_injective_and_card] exact ⟨he_inj, rfl⟩ let p : Equiv.Perm X := Equiv.ofBijective e he_bij have hp_e : (⇑p) = e := by ext x simp [p, e] have hp_mono : Monotone e := by exact g.monotone.comp f.monotone
The permutation p has finite positive order n, and p^(n - 1) * p = 1.
Because X is finite, the permutation group is finite, so n = orderOf p is strictly positive (orderOf_pos), meaning 1 ≤ n by Nat.succ_le_of_lt. Group exponent arithmetic gives p^(n - 1) * p = p^((n - 1) + 1) = p^n by pow_succ and Nat.sub_add_cancel, and p^n = 1 by definition of the order (pow_orderOf_eq_one).
uses
orderOf_pos,Nat.succ_le_of_lt,pow_succ,Nat.sub_add_cancel,pow_orderOf_eq_onelet n : ℕ := orderOf p have hn_pos : 0 < n := by dsimp [n] exact orderOf_pos p have hn1 : 1 ≤ n := Nat.succ_le_of_lt hn_pos have hp_pred : p ^ (n - 1) * p = 1 := by calc p ^ (n - 1) * p = p ^ ((n - 1) + 1) := (pow_succ p (n - 1)).symm _ = p ^ n := by rw [Nat.sub_add_cancel hn1] _ = 1 := pow_orderOf_eq_one p
p^(n - 1) is a left inverse of p: for every x ∈ X, (p^(n - 1))(p(x)) = x.
Evaluating both sides of the permutation equation p^(n - 1) * p = 1 at an element x using congrArg and congrFun, and simplifying the product via Equiv.Perm.mul_apply, shows that applying p^(n - 1) to p(x) returns x.
uses
congrFun,congrArg,Equiv.Perm.mul_applyhave hp_left_inv : ∀ x, (p ^ (n - 1)) (p x) = x := by intro x have := congrFun (congrArg (fun q : Equiv.Perm X => (q : X → X)) hp_pred) x simpa [Equiv.Perm.mul_apply] using this
The map x ↦ (p^(n - 1))(x) is monotone.
By Equiv.Perm.coe_pow, the permutation power p^(n - 1) acts on elements as the (n - 1)-fold iterate e^[n - 1] of the function e. Since e is monotone, any iterate of e is monotone.
uses
Equiv.Perm.coe_powhave hp_pred_mono : Monotone (fun x => (p ^ (n - 1)) x) := by rw [show (fun x => (p ^ (n - 1)) x) = e^[n - 1] by funext x rw [Equiv.Perm.coe_pow] simp [hp_e]] exact hp_mono.iterate (n - 1)
f reflects the order: f(a) ≤ f(b) implies a ≤ b for all a, b ∈ X.
Assume f(a) ≤ f(b). Applying the monotone map g gives e(a) ≤ e(b), which means p(a) ≤ p(b). Applying the monotone map p^(n - 1) gives (p^(n - 1))(p(a)) ≤ (p^(n - 1))(p(b)). Since p^(n - 1) is a left inverse of p, this simplifies directly to a ≤ b.
have hreflect : ∀ a b, f a ≤ f b → a ≤ b := by intro a b hab have h1 : e a ≤ e b := g.monotone hab have h1' : p a ≤ p b := by simpa [hp_e] using h1 have h2 : (p ^ (n - 1)) (p a) ≤ (p ^ (n - 1)) (p b) := hp_pred_mono h1' simpa [hp_left_inv] using h2
X and Y are order-isomorphic (Nonempty (X ≃o Y)).
Using RelIso.mk, the bijection ef : X ≃ Y is upgraded to an order isomorphism by showing ef(a) ≤ ef(b) ↔ a ≤ b for all a, b ∈ X. The forward implication is the order reflection established in the previous step, and the reverse implication is the monotonicity of f.
uses
RelIso.mkrefine ⟨RelIso.mk ef ?_⟩ intro a b constructor · intro h apply hreflect a b simpa [ef] using h · intro h simpa [ef] using f.monotone h
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Fintype.card_le_of_injective- An injective function between finite types implies that the cardinality of the domain is at most the cardinality of the codomain.
Fintype.bijective_iff_injective_and_card- A function between finite types of equal cardinality is bijective if and only if it is injective.
Equiv.ofBijective- A bijective function can be packaged into an equivalence (a bijection with computable inverse).
orderOf_pos- Every element of a finite cancellative monoid has strictly positive order.
Nat.succ_le_of_lt- For natural numbers, n < m implies n + 1 ≤ m.
pow_succ- In a monoid, a^(n + 1) = a^n * a.
Nat.sub_add_cancel- For natural numbers, if m ≤ n, then (n - m) + m = n.
pow_orderOf_eq_one- An element raised to the power of its order is the identity element 1.
congrFun- Equal functions take equal values at every input.
congrArg- Applying a function to equal arguments yields equal results.
Equiv.Perm.mul_apply- Multiplication of permutations acts by function composition: (f * g)(x) = f(g(x)).
Equiv.Perm.coe_pow- The action of the n-th power of a permutation on elements equals the n-fold function iterate of that permutation.
RelIso.mk- An equivalence between types that preserves and reflects a relation in both directions forms an isomorphism of relations.
- In Lean, the permutation inverse p⁻¹ is represented group-theoretically as p^(n - 1); connecting its action on elements to the (n - 1)-fold function iterate e^[n - 1] requires the lemma Equiv.Perm.coe_pow.
- The proof shows that f reflects the order (f(a) ≤ f(b) → a ≤ b), which combined with the monotonicity of f is what RelIso.mk needs to build an order isomorphism.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Two finite posets with mutual injective order homomorphisms are order-isomorphic (finite poset Cantor-Bernstein theorem). -/theorem poset_order_iso_of_injective_order_homs {X Y : Type*} [Fintype X] [Fintype Y] [PartialOrder X] [PartialOrder Y] (f : X →o Y) (g : Y →o X) (hf : Function.Injective f) (hg : Function.Injective g) : Nonempty (X ≃o Y) := by have hcard : Fintype.card X = Fintype.card Y := by apply le_antisymm · exact Fintype.card_le_of_injective f hf · exact Fintype.card_le_of_injective g hg have hfb : Function.Bijective f := by rw [Fintype.bijective_iff_injective_and_card] exact ⟨hf, hcard⟩ let ef : X ≃ Y := Equiv.ofBijective f hfb let e : X → X := fun x => g (f x) have he_inj : Function.Injective e := by exact hg.comp hf have he_bij : Function.Bijective e := by rw [Fintype.bijective_iff_injective_and_card] exact ⟨he_inj, rfl⟩ let p : Equiv.Perm X := Equiv.ofBijective e he_bij have hp_e : (⇑p) = e := by ext x simp [p, e] have hp_mono : Monotone e := by exact g.monotone.comp f.monotone let n : ℕ := orderOf p have hn_pos : 0 < n := by dsimp [n] exact orderOf_pos p have hn1 : 1 ≤ n := Nat.succ_le_of_lt hn_pos have hp_pred : p ^ (n - 1) * p = 1 := by calc p ^ (n - 1) * p = p ^ ((n - 1) + 1) := (pow_succ p (n - 1)).symm _ = p ^ n := by rw [Nat.sub_add_cancel hn1] _ = 1 := pow_orderOf_eq_one p have hp_left_inv : ∀ x, (p ^ (n - 1)) (p x) = x := by intro x have := congrFun (congrArg (fun q : Equiv.Perm X => (q : X → X)) hp_pred) x simpa [Equiv.Perm.mul_apply] using this have hp_pred_mono : Monotone (fun x => (p ^ (n - 1)) x) := by rw [show (fun x => (p ^ (n - 1)) x) = e^[n - 1] by funext x rw [Equiv.Perm.coe_pow] simp [hp_e]] exact hp_mono.iterate (n - 1) have hreflect : ∀ a b, f a ≤ f b → a ≤ b := by intro a b hab have h1 : e a ≤ e b := g.monotone hab have h1' : p a ≤ p b := by simpa [hp_e] using h1 have h2 : (p ^ (n - 1)) (p a) ≤ (p ^ (n - 1)) (p b) := hp_pred_mono h1' simpa [hp_left_inv] using h2 refine ⟨RelIso.mk ef ?_⟩ intro a b constructor · intro h apply hreflect a b simpa [ef] using h · intro h simpa [ef] using f.monotone h