Q:

Enderton's A mathematical introduction to logic: Question about $n$-tuples in the lemma

I am reading A Mathematical Introduction to Logic by Herbert B. Enderton.
The following is an excerpt and my question pertains to the lemma below, but I provided additional information preceding the lemma, so that it appears in context.

We define $n$-tuples recursively by
$$\big<x_1, \dotsc, x_{n+1}\big> = \big<\big<x_1, \dotsc, x_n\big>, \, x_{n+1}\big>$$
for $n>1$. [...] define also $\big<x\big> = x$; the preceeding equation then holds also for $n=1$.
$S$ is a finite sequence (or string) of members of $A$ iff for some positive integer $n$, we have $S = \big<x_1, \dotsc, x_n\big>$ where each $x_i \in A$.
The segment of the finite sequence $S$ is a finite sequence
$$\big<x_k, x_{k+1}, \dotsc, x_{m-1}, x_m\big> \enspace \textrm{where} \enspace 1 \leq k \leq m \leq n$$
If $\big<x_1, \dotsc, x_m \big> = \big<y_1, \dotsc, y_n\big>$, then it does not in general follow that $m = n$. But we claim that $m$ and $n$ can be unequal only if soe $x_i$ iss itself a finite sequence of $y_j$'s, or the other way around.
Lemma 0A Assume that $\big<x_1, \dotsc, x_m\big> = \big<y_1, \dotsc, y_m, \dotsc, y_{m+k}\big>$. Then $x_1 = \big<y_1, \, \dotsc \, , y_{k+1} \big>$.
PROOF. We use induction on $m$. If $m=1$, the conclusion is immediate. For the inductive step, assume that $\big<x_1, \dotsc, x_m, \, x_{m+1}\big> = \big<y_1, \, \dotsc \,, y_{m+k}, \, y_{m+k+1}\big>$. Then the first components of this ordered pair must be equal: $\big<x_1, \, \dotsc \, , x_m\big> = \big<y_1, \, \dotsc \, , y_{m+k}\big>$. Now apply the inductive hypothesis.

Quetsions.

How are $k$ and $m+k$ related to each other in the lemma? Initially, I thought they satisfied the inequality $1\leq k \leq m \leq n$ provided in the definition of a segment above, but I want to make sure.

Honestly, I don't understand what the lemma is claiming or what makes it useful. Would someone explain to me what this lemma means?

I've been thinking about this for a couple of days, and would like some instruction.
Thanks.

A:

For Question 1, the answer is that both $k$ and $m$ must be positive, but are otherwise unrelated; $n$ does not appear in the lemma, but in the paragraph preceding it, we have $n = m+k$.
I don't have my copy of Enderton handy to check where the lemma is used; most likely to build a solid foundation for proofs involving tuples.
Here's an illustration, though.  The lemma claims that if $\langle x, 3, 4\rangle$ is equal to $\langle 1, 2, 3, 4\rangle$, then $\langle x \rangle = \langle 1, 2 \rangle$.  This is because according to the recursive definition
$$\langle 1, 2, 3, 4 \rangle = \langle\langle\langle\langle 1 \rangle, 2 \rangle, 3 \rangle, 4 \rangle \enspace,$$
and likewise, $\langle 1, 2\rangle = \langle\langle 1 \rangle, 2 \rangle$.

EDIT: Having now taken a look at the book, here's a refined reading.  In Chapter 0, our author introduces the important idea that sets can be used to define other mathematical concepts.  Right before talking about tuples, Enderton shows the standard way to define ordered pairs in terms of sets, namely $\langle x, y\rangle = \{\{x\}, \{x,y\}\}$.  (There's a good, extensive discussion of this definition in this answer.)  He then defines tuples in terms of ordered pairs and hence in terms of sets.
If we apply the two definitions to an ordered triple, we get:
$$ \langle x, y, z \rangle = \langle \langle x,y \rangle, z \rangle = \{\{\{x\},\{x,y\}\}, \{\{\{x\},\{x,y\}\},z\}\} \enspace. $$
Looking at what we got, we may wonder whether we can work with this definition, that is, whether it is a proper formalization of the intuitive notion of tuple.  In particular, Enderton observes that two tuples of different length may represent the same set.  Is that a problem?  Lemma 0A shows that the ambiguity is of a limited nature and not damaging.
It is true that every triple is also a pair---it's an unavoidable consequence of the recursive definition of tuple---but if two sequences of different length correspond to the same set, it is precisely because in one case we have decided to stop disassembling the sequence earlier than in the other case and declared a prefix of the sequence just an element of the set.
So, if $\langle 1, 2, 3 \rangle$ is defined as $\langle \langle 1 ,2 \rangle, 3 \rangle$, inevitably it is equal to $\langle x, 3 \rangle$ for $x = \langle 1, 2 \rangle$, but that does not bother us in the least, and we can now use tuples, knowing that they are well defined in terms of sets.

As @JeanMarie points out, there are similarities between the tuples of this discussion and LISP's lists.  Another, perhaps slightly closer, example comes from the definition of recursive datatypes in provers like Z3 (and others).  I say that it is slightly closer, because those recursive definitions are made for the explicit purpose to prove properties of programs.

