AFTD Auto-Formalizing Theoretical Domains

poset_order_iso_of_injective_order_homs

theoremverified

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

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.

  1. 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|.

    lines 6–9

    uses le_antisymm, Fintype.card_le_of_injective

      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
  2. 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.

    lines 10–13

    uses Fintype.bijective_iff_injective_and_card, Equiv.ofBijective

      have hfb : Function.Bijective f := by
        rw [Fintype.bijective_iff_injective_and_card]
        exact ⟨hf, hcard⟩
      let ef : X ≃ Y := Equiv.ofBijective f hfb
  3. 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.

    lines 14–25

    uses Fintype.bijective_iff_injective_and_card, Equiv.ofBijective

      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
  4. 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).

    lines 26–35

    uses orderOf_pos, Nat.succ_le_of_lt, pow_succ, Nat.sub_add_cancel, pow_orderOf_eq_one

      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
  5. 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.

    lines 36–39

    uses congrFun, congrArg, Equiv.Perm.mul_apply

      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
  6. 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.

    lines 40–45

    uses Equiv.Perm.coe_pow

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

    lines 46–51

      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
  8. 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.

    lines 52–59

    uses RelIso.mk

      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
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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it