bipartite_poset_is_partial_order
If A and B are disjoint subsets of α, then for any simple graph H on α, the relation bipartite_poset_le H A B is a partial order on α.
Statement
theorem bipartite_poset_is_partial_order {α : Type*} (H : SimpleGraph α) (A B : Set α) (hdisj : Disjoint A B) : IsPartialOrder α (bipartite_poset_le H A B)
- Source
- arXiv:2610.24774, Section 4.1
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- bipartite_poset_leFor a graph H on α and subsets A, B of α, the height-2 order relation associated to H with bipartition (A, B) has x ≤ y if and only if x =…
- Used by 1
- bipartite_subgraph_poset_dimension_pow_lower_boundLet V be a finite type with decidable equality, G a simple graph on V with decidable adjacency, and A, B subsets of V covering V such that…
Read back from the Lean
For any type α, any simple graph H on α, and any two disjoint sets A, B : Set α, the relation on α that relates x to y if and only if x = y or (x ∈ A, y ∈ B, and x is adjacent to y in H) is a partial order on α.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes that the relation is a partial order by verifying reflexivity, transitivity, and antisymmetry. Reflexivity is immediate because every element is equal to itself, satisfying the diagonal part of the relation. Transitivity and antisymmetry hold because any non-trivial step requires moving from A to B; composing two non-trivial steps or having steps in both directions would require an intermediate element to belong to both A and B, which is impossible since A and B are disjoint.
The relation is reflexive.
For any vertex x, the equality x = x holds trivially, which satisfies the first disjunct in the definition of the bipartite poset relation.
uses
Std.Refl.mk,Or.inlhave hrefl : Std.Refl (bipartite_poset_le H A B) := by refine Std.Refl.mk ?_ intro x exact Or.inl rfl
The relation is transitive.
Suppose x ≤ y and y ≤ z. By definition of the relation, either x = y or (x ∈ A, y ∈ B, and x is adjacent to y in H). If x = y, then x ≤ z reduces to y ≤ z, which holds by assumption. If x ≠ y, we inspect y ≤ z: if y = z, then x ≤ z reduces to x ≤ y; if y ≠ z, we would have y ∈ A as well as y ∈ B, which contradicts the disjointness of A and B. Ex falso quodlibet eliminates this impossible branch.
uses
IsTrans.mk,Or.inr,False.elim,Set.disjoint_left.mphave htrans : IsTrans α (bipartite_poset_le H A B) := by refine IsTrans.mk ?_ intro x y z hxy hyz rw [bipartite_poset_le] at hxy hyz ⊢ rcases hxy with rfl | ⟨hxA, hyB, hxyadj⟩ · exact hyz · rcases hyz with rfl | ⟨hyA, hzB, hyzadj⟩ · exact Or.inr ⟨hxA, hyB, hxyadj⟩ · exact False.elim ((Set.disjoint_left.mp hdisj) hyA hyB)
The relation is antisymmetric.
Suppose x ≤ y and y ≤ x. If x = y, the claim is immediate. If x ≠ y, the first inequality gives x ∈ A and y ∈ B. Considering y ≤ x, if y = x then x = y by symmetry; otherwise, y ∈ A and x ∈ B, which implies y ∈ A ∩ B. Since A and B are disjoint, this is a contradiction, completing the antisymmetry check.
uses
Std.Antisymm.mk,False.elim,Set.disjoint_left.mphave hanti : Std.Antisymm (bipartite_poset_le H A B) := by refine Std.Antisymm.mk ?_ intro x y hxy hyx rw [bipartite_poset_le] at hxy hyx rcases hxy with rfl | ⟨hxA, hyB, hxyadj⟩ · rfl · rcases hyx with hEq | ⟨hyA, hxB, hyxadj⟩ · exact hEq.symm · exact False.elim ((Set.disjoint_left.mp hdisj) hyA hyB)
The relation is a partial order.
Reflexivity and transitivity assemble into a preorder, which together with antisymmetry shows that the relation is a partial order.
uses
IsPartialOrder.mk,IsPreorder.mkexact @IsPartialOrder.mk α (bipartite_poset_le H A B) (@IsPreorder.mk α (bipartite_poset_le H A B) hrefl htrans) hanti
Std.Refl.mk- A relation is reflexive if every element is related to itself.
Or.inl- A disjunction holds if its left disjunct holds.
IsTrans.mk- A relation is transitive if a ≤ b and b ≤ c imply a ≤ c for all elements.
Or.inr- A disjunction holds if its right disjunct holds.
False.elim- From a contradiction (falsehood), any proposition follows.
Set.disjoint_left.mp- If two sets are disjoint, an element of the first set cannot belong to the second set.
Std.Antisymm.mk- A relation is antisymmetric if a ≤ b and b ≤ a imply a = b for all elements.
IsPreorder.mk- A relation that is both reflexive and transitive forms a preorder.
IsPartialOrder.mk- A preorder that is also antisymmetric forms a partial order.
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.
/-- The relation bipartite_poset_le is a partial order whenever A and B are disjoint. -/theorem bipartite_poset_is_partial_order {α : Type*} (H : SimpleGraph α) (A B : Set α) (hdisj : Disjoint A B) : IsPartialOrder α (bipartite_poset_le H A B) := by have hrefl : Std.Refl (bipartite_poset_le H A B) := by refine Std.Refl.mk ?_ intro x exact Or.inl rfl have htrans : IsTrans α (bipartite_poset_le H A B) := by refine IsTrans.mk ?_ intro x y z hxy hyz rw [bipartite_poset_le] at hxy hyz ⊢ rcases hxy with rfl | ⟨hxA, hyB, hxyadj⟩ · exact hyz · rcases hyz with rfl | ⟨hyA, hzB, hyzadj⟩ · exact Or.inr ⟨hxA, hyB, hxyadj⟩ · exact False.elim ((Set.disjoint_left.mp hdisj) hyA hyB) have hanti : Std.Antisymm (bipartite_poset_le H A B) := by refine Std.Antisymm.mk ?_ intro x y hxy hyx rw [bipartite_poset_le] at hxy hyx rcases hxy with rfl | ⟨hxA, hyB, hxyadj⟩ · rfl · rcases hyx with hEq | ⟨hyA, hxB, hyxadj⟩ · exact hEq.symm · exact False.elim ((Set.disjoint_left.mp hdisj) hyA hyB) exact @IsPartialOrder.mk α (bipartite_poset_le H A B) (@IsPreorder.mk α (bipartite_poset_le H A B) hrefl htrans) hanti