AFTD Auto-Formalizing Theoretical Domains

isSemilinearSet_rel_comp

theoremverified

For any two semilinear binary relations s₁, s₂ on ℕ × ℕ, their relational composition { p | ∃ m, (p.1, m) ∈ s₁ ∧ (m, p.2) ∈ s₂ } is a semilinear set.

Statement

theorem isSemilinearSet_rel_comp {s₁ s₂ : Set ((ℕ × ℕ) × (ℕ × ℕ))} (h₁ : IsSemilinearSet s₁) (h₂ : IsSemilinearSet s₂) : IsSemilinearSet { p : (ℕ × ℕ) × (ℕ × ℕ) | ∃ m : ℕ × ℕ, (p.1, m) ∈ s₁ ∧ (m, p.2) ∈ s₂ }
Source
step towards op_359_symmetric_two_counter_reachability_semilinear
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The relational composition of two semilinear relations is expressed as the projection π₁₃ of the intersection of their preimages under π₁₂ and π₂₃ on triples. Because the projections are additive monoid homomorphisms, the set is obtained from the original semilinear sets by closure under preimages, intersection, and image under additive homomorphisms, and is therefore semilinear.

  1. Define the coordinate projections π₁₂, π₂₃, and π₁₃ as additive monoid homomorphisms.

    We define three projections from (ℕ × ℕ)³ to (ℕ × ℕ)²: π₁₂(x, y, z) = (x, y), π₂₃(x, y, z) = (y, z), and π₁₃(x, y, z) = (x, z). Each preserves addition and zero definitionally.

    lines 3–15

      open Set in
      let pi12 : ((ℕ × ℕ) × (ℕ × ℕ) × (ℕ × ℕ)) →+ ((ℕ × ℕ) × (ℕ × ℕ)) :=
        { toFun := fun (x, y, _) => (x, y)
          map_zero' := rfl
          map_add' := fun _ _ => rfl }
      let pi23 : ((ℕ × ℕ) × (ℕ × ℕ) × (ℕ × ℕ)) →+ ((ℕ × ℕ) × (ℕ × ℕ)) :=
        { toFun := fun (_, y, z) => (y, z)
          map_zero' := rfl
          map_add' := fun _ _ => rfl }
      let pi13 : ((ℕ × ℕ) × (ℕ × ℕ) × (ℕ × ℕ)) →+ ((ℕ × ℕ) × (ℕ × ℕ)) :=
        { toFun := fun (x, _, z) => (x, z)
          map_zero' := rfl
          map_add' := fun _ _ => rfl }
  2. Formulate the characterization of relational composition as π₁₃ '' (π₁₂ ⁻¹' s₁ ∩ π₂₃ ⁻¹' s₂) and simplify set memberships.

    By extensionality on p, we must show that p is in the composition if and only if there exists a triple mapped to p by π₁₃ whose projections lie in s₁ and s₂. We unfold the definitions of image, intersection, and preimage.

    lines 16–20

    uses mem_image, mem_inter_iff, mem_preimage

      have heq : { p : (ℕ × ℕ) × (ℕ × ℕ) | ∃ m : ℕ × ℕ, (p.1, m) ∈ s₁ ∧ (m, p.2) ∈ s₂ } =
          pi13 '' (pi12 ⁻¹' s₁ ∩ pi23 ⁻¹' s₂) := by
        ext p
        simp only [mem_image, mem_inter_iff, mem_preimage]
        constructor
  3. Show the forward inclusion: any pair in the relational composition belongs to π₁₃ '' (π₁₂ ⁻¹' s₁ ∩ π₂₃ ⁻¹' s₂).

    Given an intermediate element m such that (p.1, m) ∈ s₁ and (m, p.2) ∈ s₂, the triple (p.1, m, p.2) satisfies the preimage conditions and projects via π₁₃ back to p.

    lines 21–22

    uses Prod.ext

        · rintro ⟨m, h1, h2⟩
          exact ⟨(p.1, m, p.2), ⟨h1, h2⟩, Prod.ext rfl rfl⟩
  4. Show the reverse inclusion: any element of π₁₃ '' (π₁₂ ⁻¹' s₁ ∩ π₂₃ ⁻¹' s₂) belongs to the relational composition.

    Given a triple (x, y, z) with (x, y) ∈ s₁ and (y, z) ∈ s₂, its projection (x, z) satisfies the composition condition with witness m = y.

    lines 23–24

        · rintro ⟨⟨x, y, z⟩, ⟨h1, h2⟩, rfl⟩
          exact ⟨y, h1, h2⟩
  5. Conclude that the relational composition is semilinear.

    Rewriting the relational composition with the proved set equality, it is the image under the additive homomorphism π₁₃ of the intersection of the preimages of s₁ and s₂ under π₁₂ and π₂₃. Since semilinear sets are closed under preimages of additive homomorphisms, binary intersection, and additive homomorphism images, the result follows.

    lines 25–26

    uses IsSemilinearSet.image

      rw [heq]
      exact ((h₁.preimage pi12).inter (h₂.preimage pi23)).image pi13
Prod.ext
Two pairs are equal if and only if their first components are equal and their second components are equal.
mem_image
An element y is in the image f '' s if and only if there is an x in s with f x = y.
mem_inter_iff
An element x is in the intersection of a and b if and only if x is in a and x is in b.
mem_preimage
An element a is in the preimage f ⁻¹' s if and only if f a is in s.
IsSemilinearSet.image
The image of a semilinear set under an additive monoid homomorphism is semilinear.

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

/-- The relational composition of two semilinear binary relations on ℕ × ℕ is semilinear. -/theorem isSemilinearSet_rel_comp {s₁ s₂ : Set ((ℕ × ℕ) × (ℕ × ℕ))} (h₁ : IsSemilinearSet s₁) (h₂ : IsSemilinearSet s₂) : IsSemilinearSet { p : (ℕ × ℕ) × (ℕ × ℕ) | ∃ m : ℕ × ℕ, (p.1, m) ∈ s₁ ∧ (m, p.2) ∈ s₂ } := by  open Set in  let pi12 : ((ℕ × ℕ) × (ℕ × ℕ) × (ℕ × ℕ)) →+ ((ℕ × ℕ) × (ℕ × ℕ)) :=    { toFun := fun (x, y, _) => (x, y)      map_zero' := rfl      map_add' := fun _ _ => rfl }  let pi23 : ((ℕ × ℕ) × (ℕ × ℕ) × (ℕ × ℕ)) →+ ((ℕ × ℕ) × (ℕ × ℕ)) :=    { toFun := fun (_, y, z) => (y, z)      map_zero' := rfl      map_add' := fun _ _ => rfl }  let pi13 : ((ℕ × ℕ) × (ℕ × ℕ) × (ℕ × ℕ)) →+ ((ℕ × ℕ) × (ℕ × ℕ)) :=    { toFun := fun (x, _, z) => (x, z)      map_zero' := rfl      map_add' := fun _ _ => rfl }  have heq : { p : (ℕ × ℕ) × (ℕ × ℕ) | ∃ m : ℕ × ℕ, (p.1, m) ∈ s₁ ∧ (m, p.2) ∈ s₂ } =      pi13 '' (pi12 ⁻¹' s₁ ∩ pi23 ⁻¹' s₂) := by    ext p    simp only [mem_image, mem_inter_iff, mem_preimage]    constructor    · rintro ⟨m, h1, h2⟩      exact ⟨(p.1, m, p.2), ⟨h1, h2⟩, Prod.ext rfl rfl⟩    · rintro ⟨⟨x, y, z⟩, ⟨h1, h2⟩, rfl⟩      exact ⟨y, h1, h2⟩  rw [heq]  exact ((h₁.preimage pi12).inter (h₂.preimage pi23)).image pi13
See it in the graphDiscuss this resultChallenge it