AFTD Auto-Formalizing Theoretical Domains

rigid_sequence_tensor_product_mem_coord

theoremverified

Let n and m be natural numbers, t a natural number, and for each i in Fin t let S(i) be a sequence in Multiset (G(i)). If x is an element of the rigid sequence tensor product of S with parameters n and m, then for every coordinate j in Fin t, x(j) belongs to the sequence S(j).

Statement

lemma rigid_sequence_tensor_product_mem_coord {n m t : ℕ} {G : Fin t → Type*}
    [∀ i, DecidableEq (G i)] (S : (i : Fin t) → Multiset (G i))
    (x : (i : Fin t) → G i) (hx : x ∈ rigid_sequence_tensor_product n m S)
    (j : Fin t) : x j ∈ S j
Source
arXiv:2610.35819 Definition 4.2
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • rigid_sequence_tensor_productGiven natural numbers n and m, a natural number t, a family of types G(i) with decidable equality for each i in Fin t, and a sequence S(i)…
Used by 1

Read back from the Lean

For any natural numbers $n$, $m$, and $t$, any family of types $G_i$ (for $i : \mathrm{Fin}\ t$) with decidable equality, any family of multisets $S_i$ over $G_i$ (for $i : \mathrm{Fin}\ t$), and any element $x : \prod_{i : \mathrm{Fin}\ t} G_i$: if $x$ belongs to the multiset $\mathrm{rigid\_sequence\_tensor\_product}(n, m, S)$, then for every coordinate index $j : \mathrm{Fin}\ t$, the $j$-th component $x(j)$ belongs to the multiset $S_j$.

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 rigid sequence tensor product is defined as a sum of replicated copies of tuples drawn from the Cartesian product of the underlying sets of the sequences S(i). Since x belongs to this sum, it must belong to one of the summand multisets, which forces x to equal the tuple being replicated. Consequently, x lies in the Cartesian product of the support sets of the S(i), meaning that every coordinate x(j) belongs to S(j).

  1. There exists a tuple s in the product ∏ i, (S i).toFinset such that x belongs to the multiset of replications of s.

    By definition, the rigid sequence tensor product is formed as a multiset sum over all tuples s in the product ∏ i, (S i).toFinset of replicated copies of s. By Multiset.mem_sum.mp, membership of x in this sum yields a specific tuple s in the product whose replicated multiset contains x.

    lines 6–7

    uses Multiset.mem_sum.mp

      unfold rigid_sequence_tensor_product at hx
      rcases Multiset.mem_sum.mp hx with ⟨s, hs, hx_in⟩
  2. x = s, and hence x belongs to ∏ i, (S i).toFinset.

    Since x belongs to a multiset formed entirely of copies of s, Multiset.eq_of_mem_replicate implies x = s. Substituting x for s carries over the property that x belongs to ∏ i, (S i).toFinset.

    lines 8–9

    uses Multiset.eq_of_mem_replicate

      have hx_eq : x = s := Multiset.eq_of_mem_replicate hx_in
      subst hx_eq
  3. x j ∈ S j

    By Fintype.mem_piFinset, membership in the product means that each coordinate x(j) belongs to (S j).toFinset. Applying Multiset.mem_toFinset.mp translates membership in the support finset back to membership in the multiset S(j).

    lines 10–11

    uses Fintype.mem_piFinset, Multiset.mem_toFinset.mp

      rw [Fintype.mem_piFinset] at hs
      exact Multiset.mem_toFinset.mp (hs j)
Multiset.mem_sum.mp
If an element belongs to a multiset sum over a finite index set, it must belong to one of the summand multisets.
Multiset.eq_of_mem_replicate
Any element belonging to a multiset of replicated copies of an element a is equal to a.
Fintype.mem_piFinset
A tuple belongs to the Cartesian product of finite sets if and only if each coordinate belongs to the corresponding factor set.
Multiset.mem_toFinset.mp
If an element belongs to the set of distinct elements of a multiset, it belongs to the multiset.

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

/-- Every coordinate of a tuple in the tensor product belongs to the corresponding factor sequence. -/lemma rigid_sequence_tensor_product_mem_coord {n m t : ℕ} {G : Fin t → Type*}    [∀ i, DecidableEq (G i)] (S : (i : Fin t) → Multiset (G i))    (x : (i : Fin t) → G i) (hx : x ∈ rigid_sequence_tensor_product n m S)    (j : Fin t) : x j ∈ S j := by  unfold rigid_sequence_tensor_product at hx  rcases Multiset.mem_sum.mp hx with ⟨s, hs, hx_in⟩  have hx_eq : x = s := Multiset.eq_of_mem_replicate hx_in  subst hx_eq  rw [Fintype.mem_piFinset] at hs  exact Multiset.mem_toFinset.mp (hs j)
See it in the graphDiscuss this resultChallenge it