6.4: Expresar relaciones en una estructura

Template:MathJaxZach

Una fórmula de uso principal que se puede poner a es expresar propiedades y relaciones en una estructura\(\Struct M\) en términos de las primitivas del lenguaje\(\Lang L\) de\(\Struct M\). Con esto nos referimos a lo siguiente: el dominio de\(\Struct M\) es un conjunto de objetos. Los símbolos constantes, símbolos de función y símbolos de predicado son interpretados\(\Struct M\) por algunos objetos en\(\Domain M\), funciones sobre\(\Domain M\), y relaciones sobre\(\Domain M\). Por ejemplo, si\(\Obj A^2_0\) está en\(\Lang L\), entonces le\(\Struct M\) asigna una relación\(R = \Assign{ {\Obj A^2_0} }{M}\). Entonces la fórmula\(\Atom{\Obj A^2_0}{\Obj v_1, \Obj v_2}\) expresa esa misma relación, en el siguiente sentido: si una asignación variable se\(s\) mapea\(\Obj v_1\) hacia\(a \in \Domain{M}\) y\(\Obj v_2\) hacia\(b \in \Domain M\), entonces\[Rab \quad\text{ iff}\quad \Sat[,s]{M}{\Atom{\Obj A^2_0}{\Obj v_1, \Obj v_2}}.\nonumber\] Tenga en cuenta que aquí tenemos que involucrar asignaciones de variables: no podemos simplemente decir “\(Rab\)iff\(\Sat{M}{\Atom{\Obj A^2_0}{a, b}}\)” porque\(a\) y no\(b\) son símbolos de nuestro lenguaje: son elementos de\(\Domain{M}\).

Como no solo tenemos fórmulas atómicas, sino que podemos combinarlas usando las conectivas lógicas y los cuantificadores, fórmulas más complejas pueden definir otras relaciones en las que no están directamente integradas\(\Struct M\). Nos interesa cómo hacer eso, y específicamente, qué relaciones podemos definir en una estructura.

Definición\(\PageIndex{1}\)

Que\(A(\Obj v_1,\dots, \Obj v_n)\) sea una fórmula de\(\Lang L\) en la que solo\(\Obj v_1\),...,\(\Obj v_n\) ocurran libres, y dejen de\(\Struct M\) ser una estructura para\(\Lang L\). \(A(\Obj v_1,\dots, \Obj v_n)\)expresa la relación\(R \subseteq \Domain M^n\) iff\[Ra_1\dots a_n \quad\text{ iff}\quad \Sat[,s]{M}{\Atom{A}{\Obj v_1,\dots, \Obj v_n}}\nonumber\] para cualquier asignación de variable\(s\) con\(s(\Obj v_i) = a_i\) (\(i = 1, \dots, n\)).

Ejemplo\(\PageIndex{1}\)

En el modelo estándar de aritmética\(\Struct N\), la fórmula\(\Obj v_1 < \Obj v_2 \lor \eq[\Obj v_1][\Obj v_2]\) expresa la\(\le\) relación sobre\(\Nat\). La fórmula\(\eq[\Obj v_2][\Obj v_1']\) expresa la relación sucesora, es decir, la relación\(R \subseteq \Nat^2\) donde se\(Rnm\) sostiene si\(m\) es el sucesor de\(n\). La fórmula\(\eq[\Obj v_1][\Obj v_2']\) expresa la relación predecesora. Las fórmulas\(\lexists{\Obj v_3}{(\eqN[\Obj v_3][\Obj 0] \land \eq[\Obj v_2][(\Obj v_1 + \Obj v_3)])}\) y\(\lexists{\Obj v_3}{\eq[(\Obj v_1 + {\Obj v_3}')][v_2]}\) ambas expresan la\(\Obj <\) relación. Esto significa que el símbolo de predicado\(<\) es realmente superfluo en el lenguaje de la aritmética; se puede definir.

Esta idea no solo es interesante en estructuras específicas, sino generalmente siempre que usamos un lenguaje para describir un modelo o modelos pretendidos, es decir, cuando consideramos teorías. Estas teorías a menudo solo contienen algunos símbolos predicados como símbolos básicos, pero en el dominio se utilizan para describir a menudo muchas otras relaciones juegan un papel importante. Si estas otras relaciones pueden ser expresadas sistemáticamente por las relaciones que interpretan los símbolos predicados básicos de la lengua, decimos que podemos definirlos en el lenguaje.

Problema\(\PageIndex{1}\)

Encuentra fórmulas en las\(\Lang L_A\) que definan las siguientes relaciones:

1. \(n\)está entre\(i\) y\(j\);

2. \(n\)divide uniformemente\(m\) (es decir,\(m\) es un múltiplo de\(n\));

3. \(n\)es un número primo (es decir, ningún número que no sea\(1\) y\(n\) se divide uniformemente\(n\)).

Problema\(\PageIndex{2}\)

Supongamos que la fórmula\(A(\Obj v_1, \Obj v_2)\) expresa la relación\(R \subseteq \Domain M^2\) en una estructura\(\Struct M\). Encuentra fórmulas que expresen las siguientes relaciones:

1. la inversa\(R^{-1}\) de\(R\);

2. el producto relativo\(R \mid R\);

¿Se puede encontrar una manera de expresar\(R^+\), el cierre transitivo de\(R\)?

Problema\(\PageIndex{3}\)

\(\Lang{L}\)Sea el lenguaje que contiene\(<\) solo un símbolo de predicado de 2 lugares (no hay otros símbolos constantes, símbolos de función o símbolos de predicado, excepto por supuesto\(\eq[][]\)). Que\(\Struct{N}\) sea la estructura tal que\(\Domain{N} = \Nat\), y\(\Assign{<}{N} = \Setabs{\tuple{n,m}}{n < m}\). Demostrar lo siguiente:

1. \(\{ 0 \}\)es definible en\(\Struct{N}\);

2. \(\{ 1 \}\)es definible en\(\Struct{N}\);

3. \(\{ 2 \}\)es definible en\(\Struct{N}\);

4. para cada uno\(n \in \Nat\), el conjunto\(\{ n \}\) es definible en\(\Struct{N}\);

5. cada subconjunto finito de\(\Domain{N}\) es definible en\(\Struct{N}\);

6. cada subconjunto cofinito de\(\Domain{N}\) es definible en\(\Struct{N}\) (donde\(X \subseteq \Nat\) es cofinito iff\(\Nat \setminus X\) es finito).