AFTD Auto-Formalizing Theoretical Domains

pattern_contains

def

A list of natural numbers π pattern-contains a list of natural numbers τ if some sublist s of π has the same length as τ and satisfies s[i] < s[j] ↔ τ[i] < τ[j] for all indices i, j.

Statement

def pattern_contains (π τ : List ℕ) : Prop
Defined in
arXiv:2610.37940 Section 2
Verified
31 Oct 2026
Axioms
none listed

Read back from the Lean

For two lists of natural numbers π and τ, pattern_contains π τ asserts that there exists a list of natural numbers s such that: 1. s is a sublist (subsequence) of π (s.Sublist π); 2. the length of s equals the length of τ (with equality proof h : s.length = τ.length); and 3. for all indices i, j : Fin s.length, the i-th element of s is strictly less than the j-th element of s if and only if the i-th element of τ (cast via h to index into τ) is strictly less than the j-th element of τ.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Pattern containment on lists of natural numbers. -/
def pattern_contains (π τ : List ℕ) : Prop := ∃ s : List ℕ, s.Sublist π ∧ ∃ h : s.length = τ.length,
    ∀ (i j : Fin s.length), s[i] < s[j] ↔ τ[i.cast h] < τ[j.cast h]
See it in the graphDiscuss this resultChallenge it