English
If a finite set carries a transitive and irreflexive relation, then it is well-founded.
Русский
Если конечное множество endowed с транзитивной и иррефлексивнойRelation, оно хорошо основано.
LaTeX
$$$\text{If } (A,r) \text{ is finite with } IsTrans(r) \text{ and } IsIrrefl(r), \text{ then } WellFounded(r).$$$
Lean4
theorem wellFounded_of_trans_of_irrefl (r : α → α → Prop) [IsTrans α r] [IsIrrefl α r] : WellFounded r := by
classical
cases nonempty_fintype α
have (x y) (hxy : r x y) : #{z | r z x} < #{z | r z y} :=
Finset.card_lt_card <|
by
simp_rw [Finset.lt_iff_ssubset.symm, lt_iff_le_not_ge, Finset.le_iff_subset, Finset.subset_iff, mem_filter_univ]
exact ⟨fun z hzx => _root_.trans hzx hxy, not_forall_of_exists_not ⟨x, Classical.not_imp.2 ⟨hxy, irrefl x⟩⟩⟩
exact Subrelation.wf (this _ _) (measure _).wf
