Teorema de Fraïsse en "Un curso de teoría de modelos" de Bruno Poizat

Question

En el libro "A course in model theory" de Bruno Poizat, no entendí el lema utilizado para demostrar la segunda parte del teorema que afirma que " $p$ -son finitas para $n$ -tuplas donde $n$ es fijo". La parte que no entendía era cómo la fórmula dada $$C(n,p+1)\leq 2^{C(n+1,p)}$$ se dedujo del hecho:

En otras palabras, el $(p+1)$ -clase de equivalencia de un $n$ -está determinada por el conjunto de todas las $p$ -clases de equivalencia de $(n+1)$ -tuplas obtenidas añadiéndole un elemento.

Answer 1

Dice Poizat:

Dos $n$ -Las tuplas son $(p+1)$ -equivalente si cada vez que añado un elemento en un lado, puedo responder con un elemento en el otro lado de un tipo tal que tenga $p$ -equivalencia.

Así que la situación se reduce a esto:

Supongamos que tenemos un conjunto $X$ y, para cualquier número entero $p\geq 0$ y $n\geq 1$ tenemos una relación de equivalencia $\sim_{p,n}$ en $X^n$ de forma que se cumplan las siguientes condiciones:

1. Para todos $n\geq 1$ , $\sim_{0,n}$ tiene un número finito de clases.

2. Para todos $n\geq 1$ si $\bar{a},\bar{b}\in X^n$ entonces $\bar{a}\sim_{p+1,n}\bar{b}$ sólo si

   • para cualquier $a'\in X$ hay un $b'\in X$ tal que $\bar{a}a'\sim_{p,n+1}\bar{b}b'$ y
   • para cualquier $b'\in X$ hay $a'\in X$ tal que $\bar{a}a'\sim_{p,n+1}\bar{b}b'$ .

Aquí $\bar{a}a'$ denota el $(n+1)$ -tupla en $X^{n+1}$ obtenido concatenando $a'$ al final de $\bar{a}$ (y análogamente para $\bar{b}b'$ ). Obsérvese que la condición (2) transcribe precisamente la cita de Poizat más arriba.

Ahora, dado $p\geq 0$ y $n\geq 1$ define $C(p,n)$ es la cardinalidad del conjunto de $\sim_{p,n}$ -clases sobre $X^n$ . El objetivo es demostrar que $C(p,n)$ es finito para todo $n$ y la prueba procede por inducción en $p$ . El caso base $p=0$ es precisamente la condición (1) anterior. Por tanto, fija $p$ y asumir $C(p,n)$ es finito para todo $n$ . La reivindicación principal es:

Reclamación. Para todos $n\geq 1$ , $C(p+1,n)\leq 2^{C(p,n+1)}$ .

Prueba. Fijar $n\geq 1$ y que $k=C(p,n+1)$ . Vamos a demostrar que el número de $\sim_{p+1,n}$ -clases es como máximo $2^k$ utilizando la condición (2) para exhibir una función inyectiva desde el conjunto de todas las $\sim_{p+1,n}$ -al conjunto de todos los subconjuntos de $\{1,\ldots,k\}$ .

Sea $\bar{a}_1,\ldots,\bar{a}_k\in X^{n+1}$ sea un conjunto completo de representantes de la relación de equivalencia $\sim_{p,n+1}$ (así cualquier $(n+1)$ -tupla en $X^{n+1}$ es equivalente a $\bar{a}_i$ para algunos $1\leq i\leq k$ ). Dado un $n$ -tupla $\bar{a}\in X^n$ defina el conjunto $$ I_{\bar{a}}=\{1\leq i\leq n:\bar{a}_i\sim_{p,n+1}\bar{a}a'\text{ for some }a'\in X\}. $$ (En otras palabras, $I_{\bar{a}}$ es el conjunto de índices $i$ tal que $\bar{a}_i$ es $\sim_{p,n+1}$ -equivalente a un $(n+1)$ -obtenida añadiendo un elemento de $X$ hasta el final de $\bar{a}$ .)

Supongamos que tenemos dos $n$ -tuplas $\bar{a},\bar{b}\in X^n$ . Entonces la condición (2) anterior dice exactamente: $$ \bar{a}\sim_{p+1,n}\bar{b}\text{ if and only if }I_{\bar{a}}=I_{\bar{b}}.~(\ast) $$ (Si no estás seguro, te animo a que escribas los detalles).

Así que $S$ sea el conjunto de todos los $\sim_{p+1,n}$ -y que $P$ sea el conjunto de todos los subconjuntos de $\{1,2,\ldots,k\}$ . Entonces, por $(\ast)$ tenemos una función inyectiva bien definida $f\colon S\to P$ tal que, dada una $\sim_{p+1,n}$ -clase $c\in P$ , $f(c)$ se define como $I_{\bar{a}}$ donde $\bar{a}$ es un elemento arbitrario de la clase $c$ . Desde $P$ tiene cardinalidad $2^k$ tenemos $|S|\leq 2^k$ que es lo que queríamos demostrar.