2.8: Axiomas no lógicos

Cuando estamos tratando de probar teoremas en matemáticas, casi siempre hay axiomas adicionales, más allá del conjunto de axiomas lógicos\(\Lambda\), que utilizamos. Si estamos tratando de probar un teorema sobre los espacios vectoriales, los axiomas de los espacios vectoriales pueden ser útiles. Si estamos probando teoremas en un curso de análisis real, necesitamos tener axiomas sobre la estructura de los números reales. Estos axiomas adicionales a veces se enuncian explícitamente y a veces casi siempre están ahí. En esta sección damos un par de ejemplos de conjuntos de axiomas no lógicos que podríamos usar en deducciones por escrito.

Ejemplo 2.8.1. Para muchos de nosotros, el primer conjunto explícito de axiomas no lógicos que wee es en un curso sobre álgebra lineal. Para trabajar esos axiomas explícitamente, fijemos el lenguaje\(\mathcal{L}\) como que consiste en un símbolo de función binaria\(\oplus\), e infinitamente muchos símbolos de función unarios\(c \cdot\), uno para cada número real\(c\). (Sí, ese símbolo es “c-punto”.) Estos símbolos de función se utilizarán para representar las funciones de multiplicación escalar. También tendremos un símbolo constante, 0, para representar el vector cero del espacio vectorial. Aquí, entonces, es una manera de enumerar los axiomas no lógicos de un espacio vectorial:

1. \(\left( \forall x \right) \left( \forall y \right) x \oplus y = y \oplus x\)(la adición de vectores es conmutativa).
2. \(\left( \forall x \right) \left( \forall y \right) \left( \forall z \right) x \oplus \left( y \oplus z \right) = \left( x \oplus y \right) \oplus z\)(la adición de vectores es asociativa).
3. \(\left( \forall x \right) x \oplus 0 = x\).
4. \(\left( \forall x \right) \left( \exists y \right) x \oplus y = 0\).
5. \(\left( \forall x \right) 1 \cdot x = x\).
6. \(\left( \forall x \right) \left( c_1 c_2 \right) \cdot x = c_1 \cdot \left( c_2 \cdot x \right)\).
7. \(\left( \forall x \right) \left( \forall y \right) c \cdot \left( x \oplus y \right) = c \cdot x \oplus c \cdot y\).
8. \(\left( \forall x \right) \left( c_1 + c_2 \right) \cdot x = c_1 \cdot x \oplus c_2 \cdot x\).

Observe un par de cosas aquí: Hay infinitamente axiomas del hombre enumerados, ya que los últimos tres axiomas son realmente esquemas de axiomas, que consisten en un axioma para cada elección de\(c\),\(c_1\), y\(c_2\). Un esquema de axioma es una plantilla, diciendo que una fórmula está en el conjunto de axiomas si es de cierta forma. También note que he hecho trampa al usar el signo de adición para representar suma y yuxtaposición para representar multiplicación de números reales ya que el lenguaje\(\mathcal{L}\) no permite ese tipo de cosas. Ver Ejercicio 1.

Ejemplo 2.8.2. Escribiremos los axiomas para un orden lineal denso sin puntos finales. Nuestro lenguaje consiste en un solo símbolo de relación binaria,\(<\). Nuestros axiomas no lógicos son:

1. \(\left( \forall x \right) \left( \forall y \right) \left( x < y \lor x = y \lor y < x \right)\).
2. \(\left( \forall x \right) \left( \forall y \right) \left[ x = y \rightarrow \neg x < y \right]\).
3. \(\left( \forall x \right) \left( \forall y \right) \left( \forall z \right) \left[ \left( x < y \land y < z \right) \rightarrow x < z \right]\).
4. \(\left( \forall x \right) \left( \forall y \right) \left[ x < y \rightarrow \left( \left( \exists z \right) \left( x < z \land z < y \right) \right) \right]\).
5. \(\left( \forall x \right) \left( \exists y \right) \left( \exists z \right) \left( y < x \land x < z \right)\).

Los tres primeros axiomas garantizan que la relación denotada por\(<\) es un orden lineal, el cuarto axioma afirma que la relación es densa, y el axioma final asegura que no hay ningún elemento más pequeño y ningún elemento mayor.

Observe que en ambos ejemplos, el conjunto de axiomas involucrado es decidible: Dada una fórmula\(\phi\) que supuestamente es un axioma para espacios vectoriales o un axioma para órdenes lineales densos sin puntos finales, podríamos decidir si la fórmula era o no, de hecho, tal axioma. Y además, podríamos escribir un programa de computadora que pudiera decidir el tema por nosotros.

Ejemplo 2.8.3. Es momento de introducir una colección de axiomas no lógicos que serán de vital importancia para nosotros para el resto del libro. Trabajamos en el lenguaje de la teoría de números,

\[\mathcal { L } _ { N T } = \{ 0 , S , + , \cdot, E , < \}.\]

El conjunto de axiomas que llamaremos\(N\) es un conjunto mínimo de supuestos para describir una versión básica de las operaciones habituales sobre el conjunto de números naturales. Justo lo débiles que son estos axiomas se discutirá en el próximo capítulo. Estos axiomas, sin embargo, serán importantes para nosotros en los Capítulos 4, 5 y 6 precisamente porque son tan débiles.

Los axiomas de\(N\)

\[\begin{align} &1. \left( \forall x \right) \neg Sx = 0. \\ &2. \left( \forall x \right) \left( \forall y \right) \left[ Sx = Sy \rightarrow x = y \right]. \\ &3. \left( \forall x \right) x + 0 = x. \\ &4. \left( \forall x \right) \left( \forall y \right) x + Sy = S \left( x + y \right). \\ &5. \left( \forall x \right) x \cdot 0 = 0. \\ &6. \left( \forall x \right) \left( \forall y \right) x \cdot Sy = \left( x \cdot y \right) + x. \\ &7. \left( \forall x \right) xE0 = S0. \\ &8. \left( \forall x \right) \left( \forall y \right) xE \left( Sy \right) = \left( xEy \right) \cdot x. \\ &9. \left( \forall x \right) \neg x < 0. \\ &10. \left( \forall x \right) \left( \forall y \right) \left[ x < Sy \leftrightarrow \left( x < y \lor x = y \right) \right].\\ &11. \left( \forall x \right) \left( \forall y \right) \left[ \left( x < y \right) \lor \left( x = y \right) \lor \left( y < x \right) \right]. \end{align}\]

Si bien acabamos de afirmar que\(N\) es un conjunto débil de axiomas, demostremos que\(N\) es lo suficientemente fuerte como para probar algunos de los hechos básicos sobre las relaciones y funciones sobre los números naturales. Para la siguiente discusión, si\(a\) es un número natural, déjese\(\overline{a}\) ser el\(\mathcal{L}_{NT}\) -término\(SSS \cdots S0\) (\(S\)a's). Así\(\overline{a}\) es el término canónico de la lengua que se pretende hacer referencia al número natural\(a\).

Lema 2.8.4. Para números naturales\(a\) y\(b\):

1. Si\(a = b\), entonces\(N \vdash \overline{a} = \overline{b}\).
2. Si\(a \neq b\), entonces\(N \vdash \overline{a} \neq \overline{b}\).
3. Si\(a < b\), entonces\(N \vdash \overline{a} < \overline{b}\).
4. Si\(a \nless b\), entonces\(N \vdash \overline{a} \nless \overline{b}\).
5. \(N \vdash \overline{a} + \overline{b} = \overline{a + b}\)
6. \(N \vdash \overline{a} \cdot \overline{b} = \overline{a \cdot b}\)
7. \(N \vdash \overline{a} E \overline{b} = \overline{a^b}\)

Comprobante. Empecemos por (1), y trabajemos con bastante cuidado. Observe que el teorema está diciendo que si el número\(a\) es igual al número\(b\), entonces hay una deducción de los axiomas en\(N\) de la fórmula

\[SS \cdots S0 \: \left( aS \text{'s} \right) = SS \cdots S0 \: \left( bS \text{'s} \right).\]

Trabajamos por inducción en\(a\) (y\(b\), desde\(a = b\)). Entonces, primero asumamos eso\(a = b = 0\). Aquí está la deducción necesaria en\(N\):

\[\begin{array}{lr} \vdots & \text{Deduction of} \: \left( \forall x \right) x = x \: \text{(see Lemma 2.7.2)} \\ \left( \forall x \right) x = x & \\ \left( \forall x \right) x = x \rightarrow 0 = 0 & \text{(Q1)} \\ 0 = 0 & \text{(PC)} \end{array}\]

Ahora bien, ¿\(a = b\)y si\(a\) y\(b\) son mayores que 0? Entonces ciertamente\(a - 1\) y\(b - 1\) son iguales, y por la hipótesis inductiva hay una deducción de\(SS \cdots S0 \: \left( \left( a - 1 \right) S \text{'s} \right) = SS \cdots S0 \: \left( \left( b - 1 \right) S \text{'s} \right)\). Si seguimos esa deducción con un uso de axioma (E2):\(x = y \rightarrow Sx = Sy\), y luego (PC) nos da\(SS \cdots S0 \: \left( a S \text{'s} \right) = SS \cdots S0 \: \left( b S \text{'s} \right)\), según sea necesario. Escriba los detalles del fin de esta deducción. Es un poco más complicado de lo que hemos hecho sonar cuando en realidad tienes que usar (Q1) para hacer la sustitución. Esto termina el paso inductivo de la prueba, por lo que (1) se establece. (Alternativamente, se puede establecer (1) usando el axioma (E1) y varias aplicaciones de (E2), pero pensamos que debería ver la prueba inductiva para la práctica.)

Mirando a (2), supongamos que\(a \neq b\). Si uno de\(a\) o\(b\) es 0, entonces se\(\neg \overline{a} = \overline{b}\) desprende rápidamente del Axioma N1 y el hecho que\(N\) demuestra que\(=\) es una relación de equivalencia. Si ni\(a\) ni\(b\) es 0, procedemos por inducción en el menor de\(a\),\(b\). Ya que\(a - 1 \neq b - 1\), por la hipótesis inductiva,\(N \vdash \neg \overline{a - 1} = \overline{b - 1}\). Después por Axioma N2,\(N \vdash \neg S \overline{(a - 1)} = S \overline{(b -1)}\). En otras palabras\(N \vdash \neg \overline{a} = \overline{b}\),, as\(S \overline{(a - 1)}\) es tipográficamente equivalente a\(\overline{a}\) y\(S \overline{(b - 1)}\) es tipográficamente equivalente a\(\overline{b}\).

Para (3), utilizamos inducción en\(b\). Como\(a < b\), lo sabemos\(b \neq 0\) y lo sabemos\(a < b - 1\) o\(a = b - 1\). Entonces, ya sea

\[N \vdash \overline{a} < \overline{b - 1} \: \text{(by the inductive hypothesis)}\]

o

\[N \vdash \overline{a} = \overline{b - 1} \: \text{(by (1))}.\]

Entonces

\[N \vdash \left( \overline{a} < \overline{b - 1} \lor \overline{a} = \overline{b - 1} \right).\]

Pero luego por Axioma N10,\(N \vdash \overline{a} < S \overline{(b - 1)}\), que es exactamente lo mismo que\(N \vdash \overline{a} < \overline{b}\).

Ahora discutiremos (5), dejando (4), (6) y (7) a los ejercicios. Demostramos (5) por inducción en\(b\). Si\(b = 0\), entonces\(\overline{a + b} : \equiv \overline{a + 0} : \equiv \overline{a}\). Entonces Axioma N3 nos dice eso\(N \vdash \overline{a} + \overline{b} = \overline{a}\).

Para el paso inductivo, si\(b = c + 1\), entonces\(\overline{a} + \overline{b} : \equiv \overline{a} + S \left( \overline{c} \right)\). Entonces Axioma N4 nos dice que

\[N \vdash \overline{a} + \overline{b} = S \left( \overline{a} + \overline{c} \right).\]

Ya que\(N \vdash \overline{a} + \overline{c} = \overline{a + c}\) por la hipótesis inductiva, los axiomas de igualdad nos dicen eso\(N \vdash S \left( \overline{a} + \overline{c} \right) = S \overline{(a + c)}\). Pero\(S \overline{(a + c)}\) es\(\overline{a + c + 1}\), que es\(\overline{a + b}\). Ya que sabemos (por Teorema 2.7.1) que\(N \vdash\) “la igualdad es transitiva”,\(N \vdash \overline{a} + \overline{b} = \overline{a + b}\).

Ejercicios

1. Este problema se encuentra en la configuración del Ejemplo 2.8.1. Exactamente una de las dos afirmaciones siguientes está en la colección de axiomas no lógicos de ese ejemplo. Averiguar cuál es y por qué.
   (a)\(\left( \forall x \right) \left( 17 + 42 \right) \cdot x = 17 \cdot x \oplus 42 \cdot x\).
   b)\(\left( \forall x \right) 59 \cdot x = 17 \cdot x \oplus 42 \cdot x\).
   Ahora arregla la presentación de los axiomas para un espacio vectorial. Es posible que deba redefinir el idioma, o puede que pueda tomar lo que se presenta en el Ejemplo 2.8.1 y arreglarlo.
2. Para cada una de las siguientes estructuras, decida si satisface o no todos los axiomas del Ejemplo 2.8.2. Si la estructura no es un orden lineal denso sin puntos finales, señale cuál de los axiomas la estructura no satisface.
   a) La estructura\(\left( \mathbb{N}, < \right)\), los números naturales con la relación menor que habitual.
   b) La estructura\(\left( \mathbb{Z}, < \right)\), los enteros con la relación menor que habitual.
   c) La estructura\(\left( \mathbb{Q}, < \right)\), el conjunto de números racionales con la relación menor que habitual.
   d) La estructura\(\left( \mathbb{R}, < \right)\), los números reales con la relación menor que habitual.
   e) La estructura\(\left( \mathbb{C}, < \right)\), los números complejos con la relación\(<\) definida por:
   \[a + b i < c + d i \text { if } \text { and only } \text { if } \left( a ^ { 2 } + b ^ { 2 } \right) < \left( c ^ { 2 } + d ^ { 2 } \right).\]
3. Escribe los axiomas para la teoría de grupos. Si no conoces los axiomas de la teoría de grupos, ve a la biblioteca y echa un vistazo a cualquier libro con la frase “álgebra abstracta”, “álgebra moderna” o “teoría de grupos” en el título. Después revisa el índice bajo “grupo”. Especifique su idioma cuidadosamente y luego escribir los axiomas debería ser fácil.
4. En este ejercicio se le pide que escriba algunos de los axiomas de la teoría de conjuntos de Zermelo-Fraenkel, también conocida como ZF. El lenguaje de la teoría de conjuntos consiste en un solo símbolo de relación binaria\(\in\),, que se pretende representar la relación “es un elemento de”. Por lo que la fórmula\(x \in y\) generalmente se interpretará en el sentido de que el conjunto\(x\) es un elemento del conjunto\(y\). Aquí están las versiones en inglés de algunos de los axiomas de ZF. Escríbelos formalmente como oraciones en el lenguaje de la teoría de conjuntos.
   El Axioma de la Extensionalidad: Dos conjuntos son iguales si y solo si tienen los mismos elementos.
   El axioma del conjunto nulo: Hay un conjunto sin elementos.
   The Pair Set Axioma: Si\(a\) y\(b\) son conjuntos, entonces hay un conjunto cuyos únicos elementos son\(a\) y\(b\).
   El axioma de la unión: Si\(a\) es un conjunto, entonces hay un conjunto que consiste exactamente en los elementos de los elementos de\(a\). [Consulta: ¿Se puede entender por qué esto se llama el axioma de la unión? Escribe un ejemplo, donde\(a\) hay un conjunto de tres conjuntos y cada uno de esos tres conjuntos tiene dos elementos. ¿Cómo se ve el conjunto cuya existencia está garantizada por este axioma?]
   El Axioma del Conjunto de Poder: Si\(a\) es un conjunto, entonces hay un conjunto que consiste en todos los subconjuntos de\(a\). [Sugerencia: Para este axioma podría ser bueno definirlo\(\subseteq\) diciendo que\(x \subseteq y\) es taquigrafía (alguna fórmula agradable con\(x\) y\(y\) libre en el lenguaje de la teoría de conjuntos).]
5. Completar el comprobante de Lemma 2.8.4.
6. Lema 2.8.4 (2) establece que existe una deducción en\(N\) de la sentencia\(\neg \left( = S0SS0 \right)\). Encuentra una deducción en\(N\) de esta frase.
7. Este problema es solo para darte una pista de lo poco que podemos probar usando el sistema de axiomas\(N\). Supongamos que quisiéramos probarlo\(N \nvdash \neg x < x\). Tiene sentido (y es consecuencia del Teorema de la Solidez, Teorema 2.5.3) que una manera de hacerlo sería construir una\(\mathcal{L}_{NT}\) -estructura\(\mathfrak{A}\) en la que todos los axiomas de\(N\) son verdaderos pero no\(\left( \forall x \right) \neg x < x\) es cierto. Hazlo. Te sugerimos que tomes como tu universo el conjunto
   \[A = \{ 0,1,2,3 , \ldots \} \cup \{ a \},\]
   donde\(a\) está la letra\(a\) y no un número natural. Es necesario definir las funciones\(S^\mathfrak{A}\),\(+^\mathfrak{A}\), etc., y la relación\(<^\mathfrak{A}\). No hagas nada demasiado extraño para los números naturales, pero asegúrate de eso\(a <^\mathfrak{A} a\). Comprueba que los axiomas de\(N\) son verdaderos en la estructura\(\mathfrak{A}\), ¡y ya terminaste!
8. Utilizando más o menos la misma técnica que en el Ejercicio 7, muestran que\(N\) no prueba que la adición sea conmutativa.