isSemilinearSet_rel_comp
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.
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.
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 }
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.
uses
mem_image,mem_inter_iff,mem_preimagehave 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
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.
uses
Prod.ext· rintro ⟨m, h1, h2⟩ exact ⟨(p.1, m, p.2), ⟨h1, h2⟩, Prod.ext rfl rfl⟩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.
· rintro ⟨⟨x, y, z⟩, ⟨h1, h2⟩, rfl⟩ exact ⟨y, h1, h2⟩
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.
uses
IsSemilinearSet.imagerw [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
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 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