Autor Tema: Comentarios a "La Aritmética Recursiva Primitiva"

0 Usuarios y 1 Visitante están viendo este tema.

16 Julio, 2023, 04:40 pm
Respuesta #180

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ese conjunto \(Z^*\) existe, y es "intuitivo". Mmmmmm.

Dos cosas:

1) Pareces asociar "intuitivo" con "sencillo" o "fácil de visualizar", cuando no tiene nada que ver. Tu definición deja claro cuáles son los elementos del conjunto \( Z^* \), y no hay duda de que un conjunto dado, o está en \( Z^* \) o no lo está. Por eso es un conjunto intuitivamente bien definido, sin que importe que la definición es un galimatías que hace muy difícil operar con ella en la práctica.

El conjunto de todos los teoremas de ZFC es un conjunto intuitivamente bien definido, aunque no exista un criterio que nos permita saber en cualquier caso si una fórmula dada está o no en dicho conjunto. No podemos ver una fórmula y decir: "claramente es un teorema de ZFC" o "claramente no lo es". Es mucho más difícil establecer si determinadas fórmulas son o no teoremas de ZFC que determinar si un cierto conjunto está o no en tu conjunto \( Z^* \), y eso no afecta en nada a si está intuitivamente bien definido o no. Nadie puede decir que ve intuitivamente si una fórmula dada es o no un teorema de ZFC y eso no quita para que el conjunto de los teoremas de ZFC esté intuitivamente bien definido, pues no hay duda de lo que significa ser un teorema de ZFC.

2) No estoy muy seguro de qué quieres ilustrar con este ejemplo, pero mi conjetura es que cuestionas que podamos razonar intuitivamente con seguridad porque sería muy difícil hacerlo con el conjunto \( Z^* \). Si es eso, caes una vez más en la falacia del "o todo o nada". Los límites de lo "intuitivamente bien definido" son difusos. No creo que tu \( Z^* \) esté cerca de esos límites, pero, aunque así fuera, ¿qué importaría? La cuestión no es si podemos razonar intuitivamente sobre cualquier cosa que en principio uno podría considerar razonable (como \( Z^* \)), sino si podemos razonar intuitivamente con los objetos con los que razonamos intuitivamente.

Aun suponiendo que hubiera problemas insalvables para razonar intuitivamente con tu \( Z^* \) (cosa que dudo), ¿en qué afectaría eso a la posibilidad de justificar intuitivamente los hechos que estoy enunciando y razonando en el hilo sobre ARP? ¿Acaso el hecho de que puedas considerar dudoso que podamos decir algo intuitivamente sobre \( Z^* \) implica que pueda ser dudosa cualquier cosa que estamos diciendo sobre los términos y las fórmulas de ARP, sobre la verdad o falsedad de una fórmula de ARP, etc.?

Es como si dices: Nunca podremos estar seguros de cuáles son las soluciones (enteras, por ejemplo) de la ecuación \( x^2= 1 \) porque hay otras ecuaciones más complicadas de las que no sabemos si tienen o no soluciones enteras. ¿Qué tiene que ver que otros casos sean más complicados a la hora de juzgar si entendemos bien o no un caso sencillo?

Toda la construcción que estamos viendo de ARP es como resolver \( x^2 = 1 \), un problema que podemos analizar intuitivamente y entender perfectamente lo que hacemos. Tu dices: "pero no podemos razonar así porque en otros casos mucho más complicados no sabríamos qué hacer", y yo te digo: ¿y qué? Cuando nos encontremos con un caso así, ya veremos qué hacemos, pero mientras no tengamos problemas en abarcar y entender lo que estamos haciendo, ¿qué importa que si intentáramos hacer otras cosas nos encontraríamos con problemas?

Si quieres entender ARP, tu problema es ver si algo de lo que estamos diciendo sobre ARP es dudoso o si está claro que todo lo que decimos es verdad. No (te) ayuda en nada que te preocupes por si estudiando otra cosa que no es ARP podrías encontrarte con problemas tal vez insalvables. Es como si me dices que no puedes estudiar ARP porque te preocupa que Putin pueda provocar una guerra nuclear. Yo no te digo que no hagas bien en preocuparte por eso. Sólo te digo que eso no afecta en nada a si ARP está bien o está mal.

16 Julio, 2023, 05:41 pm
Respuesta #181

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Saber si es consistente o no, es como que hay que pararse por fuera del mundo de las demostraciones habituales y ver si hay alguna zona sin zanjar, ¿no?

No sé a qué te refieres con "el mundo de las demostraciones habituales" ni con "alguna zona sin zanjar".

Creo que mezclé los conceptos, pero me refiero a que si sólo miramos la teoría de lógica de primer lógica por dentro, no tiene contradicciones. Hay que alejar la vista para empezar a observar que existe una mínima probabilidad de que las matemáticas se caigan a pedazos. Una analogía sería que voy caminando por la calle y mi campo de visión es una losa de distancia. A la primera que cruce la calle sin ver alrededor me atropella un auto. En mi mundo todo estaba bien porque iba empeñado en sólo ver una losa de distancia, pero un agente externo (un auto en este caso) hizo que me destroce a pedazos.

Si ZFC es contradictorio, entonces todo se puede demostrar en ZFC. Si ZFC es consistente, entonces obviamente hay afirmaciones que no se pueden probar con los axiomas de ZFC. Por ejemplo, \( 2+2 = 5 \). Pero probablemente quieres preguntar por afirmaciones que no se pueden demostrar ni refutar a partir de los axiomas de ZFC.

Claro. \( 2+2=4 \) y no \( 5 \), luego \( 2+2=5 \) es falso y, en general, cualquier \( x\neq4 \) hace que \( 2+2=x \) sea falso.

El teorema de incompletitud de Gödel afirma que en cualquier teoría axiomática razonable (en particular, consistente) que permita demostrar los hechos más elementales sobre los números naturales hay afirmaciones no demostrables ni refutables. Más aún, algunas de estas afirmaciones dicen simplemente que cierto polinomio de varias variables no tiene soluciones enteras (de la ecuación que resulta de igualarlo a cero).

Esto se aplica a ZFC: existen polinomios de varias variables, con coeficientes enteros, tales que la existencia de una solución entera de la ecuación que resulta de igualarlos a cero equivale a que ZFC es contradictorio. Por lo tanto, si ZFC es consistente, la ecuación no tiene soluciones enteras, pero no es posible demostrarlo en ZFC.

Pero, aparte de esto, las afirmaciones no demostrables ni refutables en ZFC (supuesto que sea consistente) son como setas. Están por todas partes. Una de las más famosas es \( 2^{\aleph_0} = \aleph_1 \) (la hipótesis del continuo), pero hay muchísimas más, en la teoría de conjuntos propiamente dicha, en análisis, en álgebra, en topología, etc.

https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC

No entiendo muy bien a qué viene lo de los polinomios de varias variables. Nunca lo había leído en el foro.

Saludos

16 Julio, 2023, 05:46 pm
Respuesta #182

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Yo no estoy de acuerdo conque los axiomas te aseguran que el método de contradicción funcione
No sé a cuáles axiomas te referís.

Los Axiomas de la Lógica son una cosa, y los de ZFC se añaden aparte.

No hay manera de saber si una lista de axiomas es contradictoria o no,
hasta el día que te encuentres una contradicción.
Eso ocurrió con el postulado de las paralelas de Euclides,
el cual la gente intentó probar por contradicción durante siglos,
sin nunca lograrlo.

Si puedo elegir los axiomas como yo quiero,
puedo poner contradicciones, y la teoría no sirve.
Si pongo por axioma que \(\emptyset \in \emptyset\),
puedo hacerlo, pero junto a los demás axiomas me va a dar una contradicción en ZFC.
Cuando uno comienza a quitar los axiomas que son obviamente contradictorios,
los que quedan, ¿son contradictorios?

Es que estamos de acuerdo en que la elección de unos axiomas no significa que nos hayamos librado de contradicciones. Estamos de acuerdo en que siempre puede darse el caso de encontrar una contradicción.

A lo que voy es que:

(...) Porque no sabemos si ZFC es consistente o contradictoria. Más aún, no puede existir una prueba "convincente" de que ZFC es consistente. Si tuviéramos una definición "robusta" de conjunto, lo que tendríamos sería un modelo de ZFC, y entonces podríamos asegurar que ZFC es consistente, pero, como no la tenemos (ni podemos tenerla) entonces está abierta la posibilidad de que ZFC sea contradictorio.

Saludos

16 Julio, 2023, 05:51 pm
Respuesta #183

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No entiendo muy bien a qué viene lo de los polinomios de varias variables. Nunca lo había leído en el foro.

Imagina que te pregunto: ¿existen números enteros que cumplen esto?

\( x^4yx+3xy^3z-2xz+7z^3-6yz+z^4=0 \)

No sé si será fácil encontrarlos porque he puesto lo que se me ha ido ocurriendo al tun tun, pero lo que te digo es que puedes cambiar este polinomio que me acabo de inventar por otro cuidadosamente elegido de modo que la existencia de números enteros que cumplan la ecuación correspondiente es equivalente a que ZFC es contradictorio. Por lo tanto, si ZFC es consistente, hay una ecuación con la misma pinta que la anterior (pero más sofisticada) que no tiene soluciones enteras, pero es imposible demostrar que no las tiene.

17 Julio, 2023, 12:52 am
Respuesta #184

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino

Definiciones de funtores

La definición del funtor \( c \) es la fórmula: \( c(x)=0 \).

Si en vez de \(x\) ponemos cualquier otra variable,
debiera ser igualmente válida.

¿Se arregla con la regla de inferencia \(S_1 \)?

Citar
La definición de un funtor \( f\equiv \kappa(h, g_1,\ldots, g_m) \), donde \( h \) es \( m \)-ádico y los \( g_i \) son \( n \)-ádicos es

\( f(x_1,\ldots, x_m) = h(g_1(x_1, \ldots, x_n), \ldots, g_m(x_1,\ldots, x_n)) \)

Acá entiendo que se establece lo siguiente:

\[=\kappa h g_1...g_m \; x_1...x_n \quad \kappa h g_1 x_1...x_n \; ... \; g_m x_1...x_n.\]

Por otra parte, del lado izquierdo creo que tu última variable debiera ser \(x_n\) en vez de \(x_m\).

Citar
Para expresar formalmente el significado de los signos \( 0 \) y \( S \) formulamos un caso particular del principio de inducción:

\( (I_0)\ \begin{array}{ccc}
s_1(0)=s_2(0)&s_1(Sx)=h(x, s_1(x))&s_2(Sx)=h(x,s_2(x))\\
\hline
&s_1(x)=s_2(x)
\end{array}
 \)

Las premisas afirman que dos términos \( s_1(x) \) y \( s_2(x) \) toman el mismo valor para \( x=0 \) y que el valor que toman en \( Sx \) puede obtenerse en ambos casos a partir de \( x \) y del valor que toman en \( x \) mediante un mismo cálculo, expresado en el término \( h(x, y) \). La conclusión es que los dos términos coinciden para todo valor de \( x \). Es obvio entonces que si las premisas son verdaderas la conclusión también tiene que serlo, pero vamos a probarlo explícitamente:

No sé si entiendo qué tipo de funtor es \(h\).
¿Es un funtor del tipo \(\rho\), de orden \(1\)?



Citar
Una demostración en ARP es una deducción sin premisas. Una fórmula \( \alpha \) es un teorema de ARP si existe una demostración en ARP cuya última línea sea \( \alpha \). Lo expresaremos así: \( \mathop{\vdash}\limits_{\rm ARP}\alpha \).

Cuando se dice "una deducción sin premisas",
¿quiere decir que se toman los axiomas como "premisas" en forma implícita?


17 Julio, 2023, 01:23 am
Respuesta #185

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal

Definiciones de funtores

La definición del funtor \( c \) es la fórmula: \( c(x)=0 \).

Si en vez de \(x\) ponemos cualquier otra variable,
debiera ser igualmente válida.

¿Se arregla con la regla de inferencia \(S_1 \)?

Que también sea cierta la fórmula con otra variable no significa que tengamos que tomarla como axioma. Basta con que sea un teorema. Puedes elegir entre tomar como axiomas todas las fórmulas del tipo indicado para elecciones arbitrarias de las variables o sólo para una elección en concreto. Eso no altera el conjunto de los teoremas de ARP. Está explicado al final de la respuesta #6.

Citar
La definición de un funtor \( f\equiv \kappa(h, g_1,\ldots, g_m) \), donde \( h \) es \( m \)-ádico y los \( g_i \) son \( n \)-ádicos es

\( f(x_1,\ldots, x_m) = h(g_1(x_1, \ldots, x_n), \ldots, g_m(x_1,\ldots, x_n)) \)

Acá entiendo que se establece lo siguiente:

\[=\kappa h g_1...g_m \; x_1...x_n \quad \kappa h g_1 x_1...x_n \; ... \; g_m x_1...x_n.\]

Por otra parte, del lado izquierdo creo que tu última variable debiera ser \(x_n\) en vez de \(x_m\).

Sí. Había una errata. Ya la he corregido, gracias. En efecto, puedes escribir la fórmula con el criterio básico de enumerar sus signos en orden o usando los convenios de notación que facilitan la lectura. Es lo mismo (pero, a la larga, lo segundo es aconsejable).

Citar
Para expresar formalmente el significado de los signos \( 0 \) y \( S \) formulamos un caso particular del principio de inducción:

\( (I_0)\ \begin{array}{ccc}
s_1(0)=s_2(0)&s_1(Sx)=h(x, s_1(x))&s_2(Sx)=h(x,s_2(x))\\
\hline
&s_1(x)=s_2(x)
\end{array}
 \)

Las premisas afirman que dos términos \( s_1(x) \) y \( s_2(x) \) toman el mismo valor para \( x=0 \) y que el valor que toman en \( Sx \) puede obtenerse en ambos casos a partir de \( x \) y del valor que toman en \( x \) mediante un mismo cálculo, expresado en el término \( h(x, y) \). La conclusión es que los dos términos coinciden para todo valor de \( x \). Es obvio entonces que si las premisas son verdaderas la conclusión también tiene que serlo, pero vamos a probarlo explícitamente:

No sé si entiendo qué tipo de funtor es \(h\).
¿Es un funtor del tipo \(\rho\), de orden \(1\)?

No, no, en todas las reglas de inferencia, \( s, s_1, s_2, t, t_1, t_2, t_3, h \) son términos cualesquiera. En este caso, tenemos un término \( h \) cuyas variables pueden ser cualesquiera, pero escribimos \( h(x, y) \) sin que ello obligue siquiera a que las variables \( x, y \) estén en \( h \). La notación sirve únicamente para indicar que cuando escribimos \( h(x, s_1(x)) \) nos referimos a

\( h(x, s_1(x))\equiv S_y^{s_1}h \)

y a su vez, \( s_1 \) es un término cualquiera que puede tener las variables que sean, pero escribimos \( s_1(x) \) para indicar que \( s_1(Sx) \equiv S_x^{Sx}s_1 \).

A ver si así te gusta más: la regla \( I_0 \) afirma que

\( (I_0)\ \begin{array}{ccc}
S_x^0s_1=S_x^0s_2&S_x^{Sx}s_1=S_y^{s_1}h&S_x^{Sx}s_2=S_y^{s_2}h\\
\hline
&s_1=s_2
\end{array}
 \)

donde \( s_1, s_2, h \) son términos cualesquiera de ARP, con las variables que sean. La idea es que \( s_1 \) y \( s_2 \) contengan la variable \( x \) y que \( h \) contenga las variables \( x, y \), pero, aunque no se dé el caso, la regla vale trivialmente.

Me temo que hay una coincidencia de notación entre el operador sustitución \( S \) y el funtor sucesor \( S \). Eso se debe a que cuando escribo en LaTeX para mí uso otra fuente para la sustitución, pero eso se pierde cuando escribo en el foro, pero el contexto distingue claramente los dos casos (la sustitución va seguida de un subíndice y un superíndice, y el funtor siguiente no).

Si no te quedan claros los convenios de notación, insiste en ello, porque es algo fundamental para seguir el texto.

Citar
Una demostración en ARP es una deducción sin premisas. Una fórmula \( \alpha \) es un teorema de ARP si existe una demostración en ARP cuya última línea sea \( \alpha \). Lo expresaremos así: \( \mathop{\vdash}\limits_{\rm ARP}\alpha \).

Cuando se dice "una deducción sin premisas",
¿quiere decir que se toman los axiomas como "premisas" en forma implícita?

Premisas son fórmulas que se incluyen en una deducción aunque no sean axiomas. Los axiomas no cuentan como premisas. Una deducción sin premisas es una deducción en las que cada línea es un axioma o consecuencia de otras líneas anteriores.

Más precisamente, en la definición de deducción se dice que cada fórmula de una deducción puede ser un axioma, una premisa o una consecuencia de líneas anteriores. Aunque quites las premisas, te siguen quedando los axiomas.

17 Julio, 2023, 06:10 pm
Respuesta #186

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Gracias por las aclaraciones.

Citar
Me temo que hay una coincidencia de notación entre el operador sustitución S y el funtor sucesor S. Eso se debe a que cuando escribo en LaTeX para mí uso otra fuente para la sustitución, pero eso se pierde cuando escribo en el foro, pero el contexto distingue claramente los dos casos (la sustitución va seguida de un subíndice y un superíndice, y el funtor siguiente no).

Sí, es molesto, pero se entiende.

Citar
Una deducción sin premisas es una deducción en las que cada línea es un axioma o consecuencia de otras líneas anteriores.

Perfecto. Eso quería decir.


A ver si así te gusta más: la regla \( I_0 \) afirma que

\( (I_0)\ \begin{array}{ccc}
S_x^0s_1=S_x^0s_2&S_x^{Sx}s_1=S_y^{s_1}h&S_x^{Sx}s_2=S_y^{s_2}h\\
\hline
&s_1=s_2
\end{array}
 \)

donde \( s_1, s_2, h \) son términos cualesquiera de ARP, con las variables que sean. La idea es que \( s_1 \) y \( s_2 \) contengan la variable \( x \) y que \( h \) contenga las variables \( x, y \), pero, aunque no se dé el caso, la regla vale trivialmente.
 

Sí, ahí quedó más claro.



17 Julio, 2023, 06:44 pm
Respuesta #187

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
En lo que sigue necesito estar seguro de algo:


Como siempre, vamos a aplicar el teorema sobre sustituciones, por lo que es mejor expresar la regla de inducción explicitando las sustituciones, así:

\( (I_0)\ \begin{array}{ccc}
S_x^0s_1=S_x^0s_2&S_x^{Sx}s_1=S_y^{s_1}h&S_x^{Sx}s_2=S_y^{s_2}h\\
\hline
&s_1=s_2
\end{array}
 \)

Suponemos que las premisas son verdaderas y tenemos que probar que lo es la conclusión. Fijamos una valoración \( v \), de modo que tenemos que probar que:

\( N(s_1)[v] = N(s_2)[v] \).

Para ello demostraremos, por inducción sobre \( n \), que se cumple

\( N(s_1)[v_x^n] = N(s_2)[v_x^n] \).

En particular, para \( n = v(x) \) tenemos que \( v_x^n \) es la propia valoración \( v \), y tenemos la conclusión deseada. La primera premisa nos da que

\( N(S_x^0s_1)[v]=N(S_x^0s_2)[v], \)

que por el teorema de la sustitución equivale a

\( N(s_1)[v_x^0] = N(s_2)[v_x^0]. \)

Ahora supongamos que la conclusión es correcta para \( v_x^n \), es decir, que

\( N(s_1)[v_x^n] = N(s_2)[v_x^n] \).

La segunda premisa nos da que

\( N(S_x^{Sx}s_1)[v_x^n] = N(S_y^{s_1}h)[v_x^n], \)

lo que equivale a

\( N(s_1)[v_x^{N(Sx)[v_x^n]}] = N(h)[v_{x,y}^{n,N(s_1)[v_x^n]}], \)

pero \( N(Sx)[v_x^n] = N(x)[v_x^n]+1 = v_x^n(x)+1 = n+1 \), luego tenemos que

\( N(s_1)[v_x^{n+1}] = N(h)[v_{x,y}^{n,N(s_1)[v_x^n]}]. \)

Igualmente, partiendo de la tercera premisa llegamos a que

\( N(s_2)[v_x^{n+1}] = N(h)[v_{x,y}^{n,N(s_2)[v_x^n]}]. \)

Teniendo en cuenta la hipótesis de inducción, resulta que

\( N(s_1)[v_x^{n+1}] = N(s_2)[v_x^{n+1}] \),

lo que termina la prueba.

Antes has definido \(N\) como el número natural denotado por un determinado término,
para una valoración \(v\).

¿Tengo que entender que cada vez que aparece \(N()\), tengo que hacer el cálculo respecto a la valoración que figura entre corchetes a la derecha, o hay que suponer que \(N\) se refiere a una \(v\) prefijada al principio de la demostración?

Hay varias valoraciones distintas a lo largo de la demostración,
y siempre se usa la misma letra \(N\).

Si dice \(N(t)[v]\), entiende que \(N\) depende de \(v\) (uno podría escribir \(N_v\)),
pero si dice \(N(t)[v_x^n]\), por ejemplo,
no sé si \(N\) es \(N_v\) o \(N_{v_x^n}\).


17 Julio, 2023, 09:26 pm
Respuesta #188

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Antes has definido \(N\) como el número natural denotado por un determinado término,
para una valoración \(v\).

No he definido \( N \). He definido \( N(t)[v] \). Todo eso (junto) es el nombre del número natural denotado por \( t \) respecto a la valoración \( v \). Cada vez que veas \( N(t)[v] \) has de entender que la valoración es la \( v \) que ves.

pero si dice \(N(t)[v_x^n]\), por ejemplo,
no sé si \(N\) es \(N_v\) o \(N_{v_x^n}\).

\( N(t)[v_x^n] \) es el número natural denotado por \( t \) respecto de la valoración \( v_x^n \).

17 Julio, 2023, 10:08 pm
Respuesta #189

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Antes has definido \(N\) como el número natural denotado por un determinado término,
para una valoración \(v\).

No he definido \( N \). He definido \( N(t)[v] \). Todo eso (junto) es el nombre del número natural denotado por \( t \) respecto a la valoración \( v \). Cada vez que veas \( N(t)[v] \) has de entender que la valoración es la \( v \) que ves.


Bueno, pero entonces, ¿es necesaria esa letra \(N\)?

Igual ya no importa, porque ya entendí la notación.

En cuanto a las valoraciones, a ver si entiendo bien un detalle.
Entiendo que lo siguiente vale:

\[N(t)[v_{x,x}^{a,b}] = N(t)[v_x^b],\]

para cualesquiera naturales \(a,b\).