Enderton ' s una introducción matemática a la lógica: pregunta sobre $n$-tuplas en el lema

Question

Estoy leyendo Un Matemático Introducción a la Lógica por Herbert B. Enderton. El siguiente es un extracto y mi pregunta se refiere al lema de abajo, pero me proporcionó información adicional anterior el lema, por lo que aparece en el contexto.

Definimos $n$-tuplas de forma recursiva por

$$\big<x_1, \dotsc, x_{n+1}\big> = \big<\big<x_1, \dotsc, x_n\big>, \, x_{n+1}\big>$$

para $n>1$. [...] también definen $\big<x\big> = x$; la anterior ecuación, entonces tiene también para $n=1$.

$S$ es una secuencia finita (o cadena) de los miembros de $A$ fib para algún entero positivo $n$, $S = \big<x_1, \dotsc, x_n\big>$ donde cada una de las $x_i \in A$.

El segmento de la secuencia finita $S$ es una secuencia finita

$$\big<x_k, x_{k+1}, \dotsc, x_{m-1}, x_m\big> \enspace \textrm{where} \enspace 1 \leq k \leq m \leq n$$

Si $\big<x_1, \dotsc, x_m \big> = \big<y_1, \dotsc, y_n\big>$, no en general que siga $m = n$. Pero pretendemos que $m$ $n$ puede ser desigual sólo si soe $x_i$ iss en sí una secuencia finita de $y_j$'s, o la otra manera alrededor.

Lema 0A Asumir que $\big<x_1, \dotsc, x_m\big> = \big<y_1, \dotsc, y_m, \dotsc, y_{m+k}\big>$. A continuación,$x_1 = \big<y_1, \, \dotsc \, , y_{k+1} \big>$.

PRUEBA. Utilizamos la inducción en $m$. Si $m=1$, la conclusión es inmediata. Para el paso inductivo, supongamos que $\big<x_1, \dotsc, x_m, \, x_{m+1}\big> = \big<y_1, \, \dotsc \,, y_{m+k}, \, y_{m+k+1}\big>$. A continuación, los primeros componentes de este par ordenado debe ser igual: $\big<x_1, \, \dotsc \, , x_m\big> = \big<y_1, \, \dotsc \, , y_{m+k}\big>$. Ahora aplicar la hipótesis inductiva.

Quetsions.

1. ¿Cómo se $k$ $m+k$ relacionados unos con otros en el lema? Inicialmente, pensé que satisfacen la desigualdad $1\leq k \leq m \leq n$, siempre que en la definición de un segmento superior, pero quiero asegurarme.

2. Honestamente, no entiendo lo que el lema es que dicen o lo que la hace útil. Alguien que me explique lo que este lema significa?

He estado pensando en esto por un par de días, y le gustaría un poco de instrucción.

Gracias.

Answer 1

Para la Pregunta 1, la respuesta es que tanto $k$ $m$ debe ser positivo, pero no están relacionados; $n$ no aparece en el lema, pero en el párrafo precedente, tenemos $n = m+k$.

No tengo mi copia de Enderton práctico para comprobar donde el lema es utilizado; más probable es que para construir una base sólida para las pruebas que implican tuplas.

Aquí hay un ejemplo, aunque. El lema afirma que si $\langle x, 3, 4\rangle$ es igual a$\langle 1, 2, 3, 4\rangle$,$\langle x \rangle = \langle 1, 2 \rangle$. Esto es porque de acuerdo a la definición recursiva

$$\langle 1, 2, 3, 4 \rangle = \langle\langle\langle\langle 1 \rangle, 2 \rangle, 3 \rangle, 4 \rangle \enspace,$$

y de la misma manera, $\langle 1, 2\rangle = \langle\langle 1 \rangle, 2 \rangle$.

---

EDIT: después de Haber echado un vistazo al libro, he aquí una refinada de la lectura. En el Capítulo 0, nuestro autor introduce la importante idea de que los juegos pueden ser utilizados para definir otros conceptos matemáticos. A la derecha, antes de hablar acerca de tuplas, Enderton muestra la manera estándar de definir ordenó pares en términos de conjuntos, a saber,$\langle x, y\rangle = \{\{x\}, \{x,y\}\}$. (Hay una buena, amplia discusión de esta definición en esta respuesta.) Se define entonces tuplas en términos de pares ordenados y, por tanto, en términos de conjuntos.

Si aplicamos las dos definiciones para una ordenada triple, obtenemos:

$$ \langle x, y, z \rangle = \langle \langle x,y \rangle, z \rangle = \{\{\{x\},\{x,y\}\}, \{\{\{x\},\{x,y\}\},z\}\} \enspace. $$

Mirar lo que tenemos, nos preguntamos si podemos trabajar con esta definición, que es, si es una adecuada formalización de la idea intuitiva de la tupla. En particular, Enderton observa que dos tuplas de diferente longitud puede representar el mismo conjunto. Es eso un problema? Lema 0A muestra que la ambigüedad es de una naturaleza limitada y no dañar.

Es cierto que cada triple es también una par---es una consecuencia inevitable de la definición recursiva de la tupla---pero si dos secuencias de diferente longitud corresponden al mismo conjunto, es precisamente porque en uno de los casos que han decidido dejar de desmontaje de la secuencia antes que en el otro caso y declaró un prefijo de la secuencia sólo un elemento del conjunto.

Por lo tanto, si $\langle 1, 2, 3 \rangle$ se define como $\langle \langle 1 ,2 \rangle, 3 \rangle$, inevitablemente, es igual a$\langle x, 3 \rangle$$x = \langle 1, 2 \rangle$, pero eso no nos molesta en lo más mínimo, y ahora podemos usar tuplas, sabiendo que ellos están bien definidos en términos de conjuntos.

---

Como @JeanMarie señala, existen similitudes entre las tuplas de esta discusión y de LISP listas. Otro, tal vez un poco más cerca, el ejemplo viene de la definición de tipos de datos recursivos en provers como Z3 (y otros). Yo digo que es un poco más cerca, porque esas definiciones recursivas son hechas para el propósito explícito para demostrar las propiedades de los programas.

Answer 2

Algunos comentarios generales:

Enderton quiere describir las cadenas de símbolos de algún alfabeto de símbolos $A$. Una característica deseable es que la cadena ser el único descomponible por lo que si escribimos $\langle x_1 , \cdots , x_m \rangle = \langle y_1 , \cdots , y_n \rangle$,$x_i,y_j \in A$, luego tenemos a $m=n$$x_k = y_k$.

Enderton elegir para definir $n$-tuplas ($n \ge 2$) en términos de pares ordenados (definida en términos de Kuratowski de la representación). Una consecuencia de esta elección es que los hay cierta ambigüedad si no restringimos el alfabeto $A$. El propósito de Lema 0A es mostrar que la ambigüedad puede ser "resuelto" por la restricción de la alfabeto $A$. (Vea nota 5 en la Sección 1.1 de este libro).

Para ilustrar; la definición de una triple como $\langle x_1 ,x_2, x_3 \rangle = \langle \langle x_1 ,x_2 \rangle, x_3 \rangle$ introduce una ambigüedad en el sentido de que $\langle \langle 1 ,2 \rangle, 3 \rangle$ $2$- tupla de objetos de $\langle 1 ,2 \rangle, 3 $ o $3$-tupla de objetos de $1, 2, 3$. La ambigüedad desaparece si, por ejemplo, sabemos que $A \subset \mathbb{N}$.

Enderton podría haber elegido para representar las cadenas de otras maneras, pero cada esquema viene con su propio equipaje.

Respecto Lema 0A:

Tenemos $m \ge 1$$k \ge 0$. En las representaciones dadas, hay en menos como muchos '$y_i$'s, ya que hay" $x_j$'s, y el lema sólo a los estados que el 'flojo' es tomado por $x_1$.

Implícito en el Lema 0A es el hecho de que $x_2 = y_{2+k},..., x_m = y_{m+k}$ (al $m \ge 2$).

La utilidad de la lema es que si nos restringimos el alfabeto $A$, de modo que no elemento es una secuencia finita de otros elementos, entonces podemos ver que si $\langle x_1 , \cdots , x_m \rangle = \langle y_1 , \cdots , y_n \rangle$,$x_i,y_j \in A$, luego tenemos a $m=n$$x_k = y_k$. Este sigue debido a que nos han $x_1 = \langle y_1 , \cdots , y_{k+1} \rangle$, a continuación, debemos tener $k = 0$$y_1 = x_1$.