poset_hypomorphic_card_reconstructible
Hypomorphic finite ordered sets have the same cardinality.
Statement
theorem poset_hypomorphic_card_reconstructible (P Q : Type) [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q] (h : poset_hypomorphic P Q) : Fintype.card P = Fintype.card Q
- Source
- step towards poset_height_one_reconstructible
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- poset_hypomorphicTwo ordered sets P and Q are hypomorphic (have the same deck) when there is a bijection σ : P → Q such that for every x the…
The proof, explained
In this formalization, two posets P and Q are defined to be hypomorphic if there exists a bijection σ : P ≃ Q whose point-deleted subposets are isomorphic. The proof simply unpacks this bijection σ from the hypomorphism hypothesis and applies the standard lemma that bijective finite types have identical cardinalities.
There exists a bijection σ : P ≃ Q between the underlying types.
By definition, `poset_hypomorphic P Q` asserts the existence of a bijection σ : P ≃ Q whose point-deleted subposets are pairwise order-isomorphic. We unpack this existential hypothesis to obtain the bijection σ, discarding the isomorphism condition on the cards since it is not needed.
obtain ⟨σ, -⟩ := hThe cardinalities of P and Q are equal.
Since σ is a bijection between the finite types P and Q, their cardinalities must be equal by `Fintype.card_congr`.
uses
Fintype.card_congrexact Fintype.card_congr σ
Fintype.card_congr- If two finite types are in bijection, they have the same cardinality.
- In reconstruction theory, two structures are typically defined to be hypomorphic if they have the same multiset of isomorphism classes of one-element-deleted cards. Here, `poset_hypomorphic` is defined with an explicit bijection σ : P ≃ Q already built into its definition. Consequently, cardinality reconstruction is trivialized to extracting this bijection, bypassing the standard combinatorial counting argument.
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.
/-- Finite ordered sets with the same deck have the same number of elements. -/theorem poset_hypomorphic_card_reconstructible (P Q : Type) [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q] (h : poset_hypomorphic P Q) : Fintype.card P = Fintype.card Q := by obtain ⟨σ, -⟩ := h exact Fintype.card_congr σ