Modelos de aritmética sucesora

Question

Modelos de aritmética sucesora

lógica
Matemáticas
teoría de modelos
axiomas de peano

Nagase

Considere la teoría $\text{Th}(\mathbb{N}, S, 0)$ , que sabemos que está axiomatizado por los siguientes axiomas:

$\forall x (S(x) \neq 0)$
$\forall x \forall y (S(x) = S(y) \rightarrow x=y)$
$\forall x (x \neq 0 \rightarrow \exists y (x=S(y))$

más el esquema del axioma:

$\forall x (S^n(x) \neq x)$ para cada $n \in \mathbb{N}$ (dónde $S^n(x)$ es la aplicación de $S$ $n$ veces a $x$ ).

Ahora bien, es bien sabido que los modelos de esta teoría son exactamente aquellos que tienen la forma $\mathbb{N} + \lambda \cdot \mathbb{Z}$ , dónde $\lambda$ es un cardinal finito o infinito. Mi pregunta es acerca de cómo probar esto. No es difícil mostrar que cualquier estructura de esta forma es un modelo para la teoría, pero ¿qué ocurre a la inversa, es decir, que cualquier modelo de la teoría tiene esta forma?

Ahora bien, es claro que cualquier modelo de esta teoría consistirá en un segmento inicial que es una copia de $\mathbb{N}$ . Mi pensamiento fue entonces definir una relación de equivalencia $x \equiv y$ si hay $n$ tal que $S^n(x)=y$ , y luego demuestre que las clases de equivalencia serán todas de la forma $\mathbb{N}$ o $\mathbb{Z}$ . ¿Está esto en la dirección correcta?

Además, como nota al margen, solo para verificar, pero el $1$ -los tipos de esta teoría están todos aislados por una fórmula de la forma $S^n(0)=x$ , o bien el tipo único no aislado $\{S^n(0) \neq x \; | \; n \in \mathbb{N}\}$ , ¿correcto?

noah schweber

Su relación de equivalencia propuesta tiene la idea correcta pero en realidad no funciona: no es simétrica. Sin embargo, una vez que arreglas eso, tienes la idea correcta.

Nagase

@NoahSchweber - ¡Cierto, por supuesto! Quieres decir que debería poner en el lado derecho "hay

n

$n$ tal que o bien

S^{n} (x) = y

$S^n(x) = y$ o

S^{n} (y) = x

$S^n(y) = x$ , ¿bien? ¿Puedes publicar tu comentario como respuesta?

Primo Petri

Dices: los modelos de esta teoría son exactamente aquellos que tienen la forma ℕ+𝜆⋅ℤ. ¿Qué pasa con los modelos de la forma ℕ+ℚ⋅ℤ?

Nagase

@PrimoPetri - Desde

| Q | = ℵ_{0}

$|\mathbb{Q}|=\aleph_0$ , son de tipo

N + ℵ_{0} \cdot Z

$\mathbb{N} + \aleph_0 \cdot \mathbb{Z}$ . No creo que la aritmética sucesora pueda distinguir entre el tipo de orden de las copias de

Z

$\mathbb{Z}$ (es decir, la forma en que

Z

$\mathbb{Z}$ s están ordenados entre ellos).

Dan Christensen

¿No es (4) redundante? ¿No está ese "retroceder en bucle" prohibido por (1) y (2)?

Nagase

@DanChristensen - No, no son redundantes. Considere un modelo

M

$\mathcal{M}$ que consiste en

N

$\mathbb{N}$ y un solo elemento, digamos

a

$a$ , no en

N

$\mathbb{N}$ . Definir

S

$S$ como el sucesor como de costumbre

N

$\mathbb{N}$ y establecer

S (a) = a

$S(a)=a$ . Entonces

M

$\mathcal{M}$ satisface 1-3, pero no satisface 4 para

n = 1

$n=1$ .

Dan Christensen

Gracias. Entonces, ¿por qué no usar simplemente el principio más natural de la inducción y evitar construir el

S^{n} (x)

$S^n(x)$ ¿función?

Nagase

@DanChristensen: puede usar un esquema de inducción, similar al que tiene con PA de primer orden (pero restringido a fórmulas que contienen solo la función sucesora, por supuesto). Esto dará otro conjunto infinito de axiomas para la teoría. Pero encuentro más fácil analizar los modelos de la teoría usando este esquema particular.

Dan Christensen

Creo que necesitarías inducción para probar la existencia de la

S^{n} (x)

$S^n(x)$ función. Solo para aclarar, ¿es el caso de que

S^{0} (x) = x, S^{1} (x) = S (x), S^{2} (x) = S (S (x))

$S^0(x)=x, ~S^1(x) = S(x), ~S^2(x)=S(S(x))$ , ¿etcétera? Entonces

S^{n} (x) = x + n

$S^n(x)=x+n$ .

Nagase

@DanChristensen - No hay "

S^{n}

$S^n$ función. El idioma oficial contiene sólo

S

$S$ . solo uso

S^{n}

$S^n$ como una abreviatura para aplicar la función

n

$n$ veces a un término. A1

_{1}

$_1$ es

\forall x (S (x) \neq x)

$\forall x (S(x) \neq x)$ , A2

_{2}

$_2$ es

\forall x (S (S (x)) \neq x)

$\forall x (S(S(x)) \neq x)$ , etc., de modo que ninguno de los axiomas en realidad contiene

S^{n}

$S^n$ .

Dan Christensen

En PA de segundo orden (en el lenguaje de la teoría de conjuntos), se puede probar formalmente la existencia de tal función a partir de los Axiomas de Peano. Entiendo que no puede hacer eso en PA de primer orden.

Respuestas (1)

Modelos de aritmética sucesora

Su relación de equivalencia propuesta tiene la idea correcta pero en realidad no funciona: no es simétrica. Sin embargo, una vez que arreglas eso, tienes la idea correcta.
@NoahSchweber - ¡Cierto, por supuesto! Quieres decir que debería poner en el lado derecho "hay $n$ tal que o bien $S^n(x) = y$ o $S^n(y) = x$ , ¿bien? ¿Puedes publicar tu comentario como respuesta?
Dices: los modelos de esta teoría son exactamente aquellos que tienen la forma ℕ+𝜆⋅ℤ. ¿Qué pasa con los modelos de la forma ℕ+ℚ⋅ℤ?
@PrimoPetri - Desde $|\mathbb{Q}|=\aleph_0$ , son de tipo $\mathbb{N} + \aleph_0 \cdot \mathbb{Z}$ . No creo que la aritmética sucesora pueda distinguir entre el tipo de orden de las copias de $\mathbb{Z}$ (es decir, la forma en que $\mathbb{Z}$ s están ordenados entre ellos).
¿No es (4) redundante? ¿No está ese "retroceder en bucle" prohibido por (1) y (2)?
@DanChristensen - No, no son redundantes. Considere un modelo $\mathcal{M}$ que consiste en $\mathbb{N}$ y un solo elemento, digamos $a$ , no en $\mathbb{N}$ . Definir $S$ como el sucesor como de costumbre $\mathbb{N}$ y establecer $S(a)=a$ . Entonces $\mathcal{M}$ satisface 1-3, pero no satisface 4 para $n=1$ .
Gracias. Entonces, ¿por qué no usar simplemente el principio más natural de la inducción y evitar construir el $S^n(x)$ ¿función?
@DanChristensen: puede usar un esquema de inducción, similar al que tiene con PA de primer orden (pero restringido a fórmulas que contienen solo la función sucesora, por supuesto). Esto dará otro conjunto infinito de axiomas para la teoría. Pero encuentro más fácil analizar los modelos de la teoría usando este esquema particular.
Creo que necesitarías inducción para probar la existencia de la $S^n(x)$ función. Solo para aclarar, ¿es el caso de que $S^0(x)=x, ~S^1(x) = S(x), ~S^2(x)=S(S(x))$ , ¿etcétera? Entonces $S^n(x)=x+n$ .
@DanChristensen - No hay " $S^n$ función. El idioma oficial contiene sólo $S$ . solo uso $S^n$ como una abreviatura para aplicar la función $n$ veces a un término. A1 $_1$ es $\forall x (S(x) \neq x)$ , A2 $_2$ es $\forall x (S(S(x)) \neq x)$ , etc., de modo que ninguno de los axiomas en realidad contiene $S^n$ .
En PA de segundo orden (en el lenguaje de la teoría de conjuntos), se puede probar formalmente la existencia de tal función a partir de los Axiomas de Peano. Entiendo que no puede hacer eso en PA de primer orden.

noah schweber · Answer 1

Tienes la idea correcta, pero necesita un ajuste: la relación de "distancia finita" es lo que quieres, pero no es lo que has escrito (lo que has escrito no es simétrico). Colocar $x\sim y$ iff o bien hay algo finito $n$ tal que $S^n(x)=y$ o hay algo finito $n$ tal que $S^n(y)=x$ (Tenga en cuenta que esta es solo la "métrica de gráfico" habitual).

Ahora, las observaciones clave son que en cualquier modelo de aritmética sucesora hay exactamente un elemento sin predecesor y la función sucesora es inyectiva. Estos dos hechos implican rápidamente que cualquier modelo de aritmética sucesora consta exactamente de una $\sim$ -clase de "tipo $\mathbb{N}$ "y todos los demás $\sim$ -las clases (si las hay) tienen "tipo $\mathbb{Z}$ ."

(Puede ser útil pensar en lo que prueba la aritmética sucesora sobre la relación de "distancia uno" $x=S(y)\vee y=S(x)$ ; en mi experiencia, esto es un poco más fácil de conceptualizar, aunque no estoy seguro de por qué).

Modelos de aritmética sucesora

Nagase

noah schweber

Nagase

Primo Petri

Nagase

Dan Christensen

Nagase

Dan Christensen

Nagase

Dan Christensen

Nagase

Dan Christensen

Respuestas (1)

noah schweber

¿Existe un modelo no estándar de la aritmética de Peano donde cualquier elemento tiene solo un número finito de divisores primos?

¿Todos los modelos de aritmética peano se describen utilizando lógica de primer orden no estándar?

¿Una pregunta sobre el teorema de Tennebaum?

¿Existe un modelo natural de la Aritmética de Peano donde falla el teorema de Goodstein?

¿Son los números naturales estándar un modelo destacado de PA?

¿Se puede probar en Peano Arithmetic el hecho de que NBG sin elección es una extensión conservadora de ZF?

La aritmética sucesora no es finitamente axiomatizable

¿Cuánta aritmética podemos encontrar definiblemente en los surrealistas?

¿Pueden dos modelos diferentes de aritmética tener puntos de vista no comparables de la aritmética peano?

¿Es la teoría de los lenguajes formales regulares finitamente axiomatizable?