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

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

12 Julio, 2023, 11:12 pm
Respuesta #160

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Los casos complicados ocurren cuando el primer signo es \(\kappa\) ó \(\rho\).

Sea \(n\) el orden del funtor \(f\).
En el primer caso, hay únicos funtores \(f_0,f_1,...,f_m\), tales que

\[f\equiv \kappa f_0f_1...f_m.\]

El orden de \(f_0\) es \(m\) y el de las demás \(f_j\) es \(n\).

[...]


El problema de esa demostración es que en toda ella has fijado una sucesión \( f_1,\ldots, f_{\color{red}m} \), y lo que has probado es que esa sucesión asigna una única función a cada funtor, pero en principio un mismo funtor puede definirse a partir de sucesiones distintas, y no veo que hayas probado que, aunque consideres otra sucesión, la función asociada al último funtor (común a ambas) será la misma en los dos casos.

En realidad, dos sucesiones sólo pueden diferir en el orden en que aparecen las funciones o en que contengan funciones inútiles, que no se usan al final en el cálculo de la última función, pero cuesta más probar eso que argumentar la unicidad como lo he hecho yo o, una alternativa que tal vez te guste más, apelando a la unicidad de la estructura de un funtor que ya has dado por demostrada.


Bueno, si de verdad has encontrado un error en mi demostración,
no tengo problemas en corregirlo.

Pero no sé si estamos diciendo lo mismo.

Primero, un leve detalle:
he he corregido en rojo el índice,
porque yo pongo \(f_m\) cuando vos dijiste \(f_n\).

Lo que yo creo haber probado unos cuantos posts antes
es que, dada una cadena de signos de ARP,
con la suerte de ser un funtor, cuyo orden indico con \(n\),
y en particular cuyo signo inicial es \(\kappa\),
entonces existen únicas cadenas de ARP \(f_0,f_1,...,f_m\),
que además también tienen la "suerte" de ser funtores,
tal que \(f_0\) tiene orden \(m\), y tal que \(f_1,...,f_m\), tienen orden \(n\).

Como esa descomposición en subfuntores es única,
la notación que yo uso para ellos es algo específico de ese funtor \(f\),
y el orden en que aparecen está unívocamente determinado.
La hipótesis de inducción hace que no sólo esos funtores sean únicos,
sino que ahora también, por ser cadenas de longitud más corta,
cada una tenga asociada una única función recursiva
\(F_0=\beta(f_0),F_1=\beta(f_1),...\), etc.

En ese caso, no estoy denotando con \(f_j\) exactamente el mismo "speech"
que usás en tu definición de funtor,
en la que hay una sucesión \(f_1,...,f_r\),
y en la que es cierto que se puede cambiar el orden,
y que puede haber algunos funtores que no se utilizan.

Por la manera en que yo he trabajado,
no se trata de una "sucesión" de funtores que construyen el funtor desde cero,
sino sólo de una "lista" (ordenada) de subcadenas,
que uso para descomponer el funtor \(f\) en subcadenas-funtores,
unívocamente determinados.

Eso implicaría, digo yo, que no haya otra opción
para la selección de la función recursiva \(F\) denotada por \(f\).

12 Julio, 2023, 11:23 pm
Respuesta #161

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Bueno, si de verdad has encontrado un error en mi demostración,
no tengo problemas en corregirlo.

Tienes razón. Disculpa. He pensado en mi notación al leer la tuya. Nada que objetar a tu demostración.

13 Julio, 2023, 12:39 pm
Respuesta #162

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Ya volví de vacaciones y puedo retomar el hilo ;D

Como siempre, primero las erratillas:

Sumas finitas Si \( t(x_1,\ldots, x_n) \) es un término cuyas variables estén entre las indicadas, definimos un funtor de rango \( n \) mediante las ecuaciones:

\( \begin{eqnarray*}
\sum\limits_{i<\color{red}0}t(x_1,\ldots, x_{n-1},i)&=&0\\
\sum\limits_{i<x+1}t(x_1,\ldots, x_{n-1},i)&=&\sum\limits_{i<x}t(x_1,\ldots, x_{n-1},i)+t(x_1,\ldots, x_{n-1},x).
\end{eqnarray*}
 \)

Escribiremos también:

\( \sum\limits_{i\leq x}t(x_1,\ldots, x_{n-1},i) {\color{red} \equiv}\sum\limits_{i< x+1}t(x_1,\ldots, x_{n-1},i). \)

Empezamos considerando el funtor dado por las ecuaciones

\( \begin{eqnarray*}
F(x, d, 0)&=&\left<c(x, d), r(x, d)\right>_{\color{red} \infty},\\
F(x, d,i+1)&=&\left<c(F(x, d, i)_0,d),r(F(x, d, i)_0,d)\right>_{\color{red} \infty}\color{red},
\end{eqnarray*} \)

donde \( c \) y \( r \) son los funtores que calculan el cociente y el resto de la división euclídea. Definimos

Teorema Si \( d\geq 2 \), todo número natural \( x\neq 0 \) admite el desarrollo decimal reducido en base \( d \)

\( x=x[d]_{(d)}=\sum\limits_{i\leq n_d(x)}x_i[d]\cdot d^i\color{red}. \)

Además, si \( x=s_{(d)} \) es otro desarrollo decimal en base \( d \), entonces \( \ell(s)> n_d(x) \), y, para todo \( i<\ell(s) \), se cumple que

\( s_i=\cases{x_i[d]&si $i\leq n_d(x)$,\cr 0&si $i>n_d(x)$.} \)

En particular, \( x \) admite un único desarrollo decimal reducido.

Demostración


[...]

Para probar la unicidad partimos de una sucesión \( s>0 \) arbitraria tal que \( \forall i<\ell(s)\, s_i<d \) y vamos a probar por inducción que, para todo \( k< \ell(s) \), se cumple

\( (s_{(d)})^*_k[d]= \sum\limits_{i<\ell(s)\dot{-} {\color{red} (k+1) }}s_{i+{\color{red}(k+1)}}d^i\land \forall i\leq k\,(s_{(d)})_i[d]=s_i. \)

Para \( k=0 \) tenemos que

\( s_{(d)}=\sum\limits_{i<\ell(s)}\!\!s_i\cdot d^i=\sum\limits_{i<\ell(s)\dot{-} 1}\!\!\!\!s_{i+1}\cdot d^{i+1}+s_0=d\cdot \sum\limits_{i<\ell(s)\dot{-} 1}\!\!\!s_{i+1}\cdot d^i+s_0,
 \)

luego por la unicidad de la división euclídea concluimos que \( {\color{red} (s_{(d)})}_0[d]=s_0 \) y

[...]
[cerrar]

Así pues, ahora podemos definir las cifras decimales

\( 1 \equiv S0,\quad 2 \equiv S1, \quad 3 \equiv S2, \quad 4 \equiv S3, \quad 5 \equiv S4, \)

\( 6 \equiv S5,\quad 7 \equiv S6,\quad 8 \equiv S7,\quad 9 \equiv S8 \)

y convenir en que todo numeral, como \( 1\,314 \), ha de interpretarse como

\( \left<4, 1, 3, 1\right>_{{\color{red}(}S9{\color{red})}}. \)

En particular, \( S9=10 \) y \( \left<4, 1, 3, 1\right>_{{\color{red}(}10{\color{red})}}=1\cdot 10^3+3\cdot 10^2+1\cdot 10+4 \).

Ahora, lo siguiente no lo entiendo bien:

La unicidad de los desarrollos decimales puede expresarse así:

Teorema \( d\geq 2\land \forall i<x+y\ x_i[d]=y_i[d]\rightarrow x=y \).

No llego a ver porque este teorema (de ARP) expresa la unicidad del desarrollo en base \( d \).

Un saludo.

EDITO:

También, aquí:

Sumas finitas Si \( t(x_1,\ldots, x_n) \) es un término cuyas variables estén entre las indicadas, definimos un funtor de rango \( n \) mediante las ecuaciones:

\( \begin{eqnarray*}
\sum\limits_{i<{\color{red}0}}t(x_1,\ldots, x_{n-1},i)&=&0\\
\sum\limits_{i<x+1}t(x_1,\ldots, x_{n-1},i)&=&\sum\limits_{i<x}t(x_1,\ldots, x_{n-1},i)+t(x_1,\ldots, x_{n-1},x).
\end{eqnarray*}
 \)

Lo que he marcado en rojo es un cero, y no una \( x \) como ponía, ¿no?

13 Julio, 2023, 01:11 pm
Respuesta #163

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ya volví de vacaciones y puedo retomar el hilo ;D

Espero que te lo hayas pasado bien.   :)

Como siempre, primero las erratillas:

Teorema Si \( d\geq 2 \), todo número natural \( x\neq 0 \) admite el desarrollo decimal reducido en base \( d \)

\( x=x[d]_{(d)}=\sum\limits_{i\leq n_d(x)}x_i[d]\cdot d^i\color{red}. \)

Además, si \( x=s_{(d)} \) es otro desarrollo decimal en base \( d \), entonces \( \ell(s)> n_d(x) \), y, para todo \( i<\ell(s) \), se cumple que

\( s_i=\cases{x_i[d]&si $i\leq n_d(x)$,\cr 0&si $i>n_d(x)$.} \)

En particular, \( x \) admite un único desarrollo decimal reducido.

Aquí no has marcado nada en rojo, y he comparado con el original por si habías cambiado algo sin marcarlo, y no he visto nada, y tampoco veo nada que pueda estar mal. ???

Ahora, lo siguiente no lo entiendo bien:

La unicidad de los desarrollos decimales puede expresarse así:

Teorema \( d\geq 2\land \forall i<x+y\ x_i[d]=y_i[d]\rightarrow x=y \).

No llego a ver porque este teorema (de ARP) expresa la unicidad del desarrollo en base \( d \).

He cambiado la frase. Me refería a que un número está unívocamente determinado por su desarrollo decimal, pero, en efecto, eso no es la unicidad del desarrollo decimal.

Bueno, después de todo esto tan sabido y tan aburrido, es posible que en el próximo mensaje ARP te vuelva a sorprender.

14 Julio, 2023, 03:46 pm
Respuesta #164

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Ya volví de vacaciones y puedo retomar el hilo ;D

Espero que te lo hayas pasado bien.   :)

Pues la verdad es que sí. A veces hace falta desconectar un poco de todo :)

Como siempre, primero las erratillas:

Teorema Si \( d\geq 2 \), todo número natural \( x\neq 0 \) admite el desarrollo decimal reducido en base \( d \)

\( x=x[d]_{(d)}=\sum\limits_{i\leq n_d(x)}x_i[d]\cdot d^i\color{red}. \)

Además, si \( x=s_{(d)} \) es otro desarrollo decimal en base \( d \), entonces \( \ell(s)> n_d(x) \), y, para todo \( i<\ell(s) \), se cumple que

\( s_i=\cases{x_i[d]&si $i\leq n_d(x)$,\cr 0&si $i>n_d(x)$.} \)

En particular, \( x \) admite un único desarrollo decimal reducido.

Aquí no has marcado nada en rojo, y he comparado con el original por si habías cambiado algo sin marcarlo, y no he visto nada, y tampoco veo nada que pueda estar mal. ???

Espero que no me odies, pero es simplemente en la segunda línea que había una coma donde iba un punto :P

He cambiado la frase. Me refería a que un número está unívocamente determinado por su desarrollo decimal, pero, en efecto, eso no es la unicidad del desarrollo decimal.

Vale, ahora si está claro.

Vamos ahora con la nueva respuesta que, efectivamente, me ha sorprendido bastante :aplauso:

El hecho de que cada número natural esté determinado por su desarrollo decimal en una base dada (en este caso por su desarrollo binario) implica claramente lo que en teoría de conjuntos se llama axioma de extensionalidad:

\( \forall u\in x\, u\in y\land \forall u\in y\, u\in x\rightarrow x=y. \)

La demostración sería algo de la forma siguiente, ¿no?

Es fácil demostrar la fórmula \( i \leq z \rightarrow x_i[2]=y_i[2] \), pues si \( x_i[2]=1 \) entonces \( i \in x \) y por hipótesis \( i \in y \), con lo que \( y_i[2]=1 \); y si fuera \( x_i[2]=0 \) por reducción al absurdo se llega igualmente a que \( y_i[2]=0 \). Por tanto, podemos concluir que \( \forall u \leq z\, x_u[2]=y_u[2] \), luego en particular \( \forall u < x+y\, x_u[2]=y_u[2] \) y el último teorema del mensaje anterior implica que \( x=y \).

y así se cumple claramente lo que en teoría de conjuntos se conoce como axioma de especificación:

Notemos que en el teorema anterior podemos cambiar \( u<k \) por \( u\in k \), entendiendo que

\( \{u\in k\mid \alpha(u,x_1,\ldots, x_n)\} {\color{red}\equiv}\{u<k\mid u\in k\land \alpha(u, x_1,\ldots , x_n)\}. \)

A partir de aquí ya podemos definir fácilmente todos los conceptos conjuntistas básicos:

[...]

\( \begin{eqnarray*}
x\times y&\equiv&\{w<\left<x,y\right>_{\color{red} \infty}\mid \exists u\in x\exists v\in y\, w=\left<u, v\right>_{\color{red} \infty}\}.
\end{eqnarray*} \)

En la definición de \( \mathcal Px \), notemos que \( y\subset x\rightarrow y_i[2]\leq x_i[2] \), de donde \( y\leq x \). Observemos también que

\( x\neq \emptyset\rightarrow (u\in \bigcap x\leftrightarrow \color{red} \forall v\in x\, u\in v), \)

Nota: Pares ordenados Con la definición que hemos dado de producto cartesiano \( x\times y \) se cumple que

\( w\in x\times y\leftrightarrow \exists u\in x\exists v\in y\ w = \left<u, v\right>_{\color{red} \infty}. \)

Para definir subconjuntos de productos cartesianos es útil introducir la notación siguiente:

\( \{\left<u, v\right>_{\color{red} \infty}\in x\times y\mid \alpha(u, v, x, y, x_1,\ldots, x_n)\}\equiv \)

\( \{w\in x\times y\mid \exists u\in x\exists v\in y(w = \left<u, v\right>_{\color{red} \infty}\land \alpha(u, v, x, y, x_1,\ldots, x_n))\}. \)

El mínimo y el máximo de un conjunto pueden definirse así:

\( \min x=\mu u\leq x(u\in x),\qquad \max x = x\dot{-} \mu u\leq x(x\dot{-} u\in x), \)

de modo que
\( x\neq \emptyset\rightarrow (\min x\in x\land \forall  u\in x\, \min x\leq u), \)

\( x\neq \emptyset\rightarrow (\max x\in x\land {\color{blue}\forall  u\in x\, u\leq \max x}). \)

No veo del todo claro lo marcado en azul.

Veamos ahora que es posible definir conjuntos sin tener a priori una cota para sus elementos eludiendo la exigencia del teorema de especificación:

Si fijamos un término \( t(x, x_1,\ldots, x_n) \), podemos definir el funtor

\( \begin{eqnarray*}
F_t(x_1,\ldots, x_n, y,0)&=&0,\\
F_t(x_1,\ldots, x_n,y,x+1)&=&F_{\color{red} t}(x_1,\ldots, x_n,{\color{red}y,x})\cup \{t(x, x_1,\ldots, x_n)\}\cdot\chi[x\in y],
\end{eqnarray*} \)
y a su vez

\( \{t(u, x_1,\ldots, x_n)\mid u\in y\} {\color{red} \equiv} F_t(x_1,\ldots, x_n, y,y). \)

Demostración
Omitiendo los parámetros, supongamos que

\( z\in \{t(u)\mid u\in y\} {\color{red} \equiv}F_t(y, y). \)

[...]

Recíprocamente, supongamos que \( \exists u\in y\, z=t(u) \) y tomemos \( \color{blue} x\equiv\mu u\in y\, z=t(u). \)

[...]

luego podemos concluir que \( z\in F_t(y, y){\color{red} \equiv}\{t(u)\mid u\in y\} \).
[cerrar]

Lo que he marcado en azul es porque cuando has introducido los cuantificadores restringidos a la propiedad de pertenencia no has introducido también el mínimo, y estaría bien incluirlo, ¿no?

Por ejemplo, ahora podemos definir

\( \textstyle \bigcup\limits_{u\in y}t(u, x_1, \ldots, x_n) {\color{red} \equiv} \bigcup\{t(u, x_1,\ldots, x_n)\mid u\in y\}, \)

\( \textstyle \bigcap\limits_{u\in y}t(u, x_1, \ldots, x_n) {\color{red} \equiv} \bigcap\{t(u, x_1,\ldots, x_n)\mid u\in y\}, \)

de modo que

\( \textstyle v\in \bigcup\limits_{u\in y}t(u, x_1, \ldots, x_n) \leftrightarrow \exists u\in y\, v\in {\color{red}t}(u, x_1,\ldots, x_n),
 \)

\( \textstyle y\neq \emptyset\rightarrow ( v\in \bigcap\limits_{u\in y}t(u, x_1, \ldots, x_n) \leftrightarrow \forall  u\in y\, v\in {\color{red}t}(u, x_1,\ldots, x_n)). \)

Aplicaciones Aunque las definiciones siguientes tienen sentido para cualquier conjunto \( f \) (es decir, para cualquier número natural \( f \)), sólo tienen interés cuando \( f \) es un conjunto de pares ordenados. En tal caso, el dominio de \( f \) es el conjunto de todas las primeras componentes de los pares ordenados de \( f \) y el rango es el conjunto de todas sus segundas componentes:

\( \mathcal D f \equiv \{u<f\mid \exists v< f\, \left<u, v\right>_{\color{red} \infty}\in f\}, \)

\( \mathcal R f \equiv \{v<f\mid \exists u< f\, \left<u, v\right>_{\color{red} \infty}\in f\}. \)

Diremos que \( f \) es una aplicación de un conjunto \( x \) en un conjunto \( y \) si cumple:

\( f: x\longrightarrow y\equiv f\subset x\times y\land \forall u\in {\color{red} x}\exists! v\in y\,\left<u,v\right>_{\color{red} \infty}\in f. \)

Así, si definimos
\( f(u)\equiv \mu v\in \mathcal Rf\ \left<u, v\right>_{\color{red} \infty}\in f, \)

tenemos que
\( f:x\longrightarrow y\land u\in x\rightarrow f(u)\in y\land \left<u, f(u)\right>_{\color{red} \infty}\in f, \)

y también que
\( f: x\longrightarrow y\land \left<u, v\right>_{\color{red} \infty}\in f\rightarrow v = f(u). \)

En resumen, en ARP se pueden demostrar todos los axiomas de ZFC salvo el axioma de infinitud (al contrario, en el mensaje siguiente veremos que en ARP se demuestra que todo conjunto es finito). No hemos mencionado el axioma de elección pero es inmediato a partir del hecho de que hemos visto cómo asociar a cada conjunto no vacío su mínimo elemento (respecto al orden usual de los números naturales).

También el de regularidad, que no se menciona en el mensaje, ¿no?

Basta también considerar el mínimo del propio conjunto \( x \) y es claro que \( \min x \in x \) y que \( \min x \cap x = \emptyset \) (porque si \( v \in \min x \), en particular, \( v < \min x \) y no puede ser entonces \( v \in x \)).

Por último, ahora se me plantea una cuestión:

En el hilo de respuestas sobre los ordinales me comentaste que lo que se puede demostrar en AP es (esencialmente) aquello que pueda demostrarse en ZFC cambiando el axioma de infinitud por aquel que dice que todo conjunto es finito, pero ahora también hemos visto (a falta de lo último que comentas que se verá en la siguiente respuesta) que esto es válido para ARP. Por tanto, ¿qué diferencia a ARP de AP? He de suponer que AP es más fuerte, ¿pero donde radica la diferencia respecto a aquello que se pueda probar y que no? ¿Hay algún resultado sencillo de ver que pueda probarse en AP, pero no en ARP? ¿Todo lo que puede probarse en ARP se puede probar en AP?

Un saludo.

EDITO:

Aquí:

Sumas finitas Si \( t(x_1,\ldots, x_n) \) es un término cuyas variables estén entre las indicadas, definimos un funtor de rango \( n \) mediante las ecuaciones:

\( \begin{eqnarray*}
\sum\limits_{i<{\color{red}0}}t(x_1,\ldots, x_{n-1},i)&=&0\\
\sum\limits_{i<x+1}t(x_1,\ldots, x_{n-1},i)&=&\sum\limits_{i<x}t(x_1,\ldots, x_{n-1},i)+t(x_1,\ldots, x_{n-1},x).
\end{eqnarray*}
 \)

Lo que he marcado en rojo es un cero, y no una \( x \) como ponía, ¿no?

14 Julio, 2023, 05:04 pm
Respuesta #165

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Espero que no me odies, pero es simplemente en la segunda línea que había una coma donde iba un punto :P

 >:(   Y yo que pensaba que ya habías saciado tu rencor...

La demostración sería algo de la forma siguiente, ¿no?

Es fácil demostrar la fórmula \( i \leq z \rightarrow x_i[2]=y_i[2] \), pues si \( x_i[2]=1 \) entonces \( i \in x \) y por hipótesis \( i \in y \), con lo que \( y_i[2]=1 \); y si fuera \( x_i[2]=0 \) por reducción al absurdo se llega igualmente a que \( y_i[2]=0 \). Por tanto, podemos concluir que \( \forall u \leq z\, x_u[2]=y_u[2] \), luego en particular \( \forall u < x+y\, x_u[2]=y_u[2] \) y el último teorema del mensaje anterior implica que \( x=y \).

Eso es. La idea subyacente es que si dos conjuntos tienen los mismos elementos, entonces, como números naturales, tienen las mismas cifras binarias, luego son iguales.

Notemos que en el teorema anterior podemos cambiar \( u<k \) por \( u\in k \), entendiendo que

\( \{u\in k\mid \alpha(u,x_1,\ldots, x_n)\} {\color{red}\equiv}\{u<k\mid u\in k\land \alpha(u, x_1,\ldots , x_n)\}. \)

He hecho el cambio que sugieres, pero no he hecho lo mismo con otros similares que propones. Te explico la diferencia:

Cuando defines un funtor por recursión, está claro que no puedes poner identidades en la definición, porque lo que estamos dando son los dos axiomas que definen la recursión. En cambio, cuando definimos un funtor por composición, podemos poner indistintamente \( \equiv \) o \( = \). En el primer caso la definición se interpreta como un cambio de notación, mientras que en el segundo se interpreta como la definición de un nuevo funtor por composición. En muchos casos la diferencia es meramente subjetiva. Ahora bien, en el ejemplo precedente me parece que lo natural es considerar que ambos miembros son el mismo funtor nombrado de dos formas distintas, mientras que, por ejemplo, aquí:

\( \{t(u, x_1,\ldots, x_n)\mid u\in y\} {\color{red} \equiv} F_t(x_1,\ldots, x_n, y,y). \)

me parece más natural entender que el miembro izquierdo es el funtor definido por composición del funtor \( F_t \) y varias proyecciones. Por supuesto, un \( \equiv \) también tendría sentido, pero me parece preferible usar el igualador siempre que tenga sentido. Lo mismo se aplica aquí:

Por ejemplo, ahora podemos definir

\( \textstyle \bigcup\limits_{u\in y}t(u, x_1, \ldots, x_n) {\color{red} \equiv} \bigcup\{t(u, x_1,\ldots, x_n)\mid u\in y\}, \)

\( \textstyle \bigcap\limits_{u\in y}t(u, x_1, \ldots, x_n) {\color{red} \equiv} \bigcap\{t(u, x_1,\ldots, x_n)\mid u\in y\}, \)

donde el miembro izquierdo puede verse como la composición del funtor \( \bigcup \) o \( \bigcap \) y el funtor (asociado a \( t \)) que define los conjuntos por reemplazo.

El mínimo y el máximo de un conjunto pueden definirse así:

\( \min x=\mu u\leq x(u\in x),\qquad \max x = x\dot{-} \mu u\leq x(x\dot{-} u\in x), \)

de modo que
\( x\neq \emptyset\rightarrow (\min x\in x\land \forall  u\in x\, \min x\leq u), \)

\( x\neq \emptyset\rightarrow (\max x\in x\land {\color{blue}\forall  u\in x\, u\leq \max x}). \)

No veo del todo claro lo marcado en azul.

Si \( u\in x \), llama \( v \equiv x\dot{-}u \), de modo que \( u = x\dot{-}v\in x \), luego \( \mu u\leq x(x\dot{-}u \in x)\leq v = x\dot{-}u \), luego \( u\leq \max x \), ¿no?

Lo que he marcado en azul es porque cuando has introducido los cuantificadores restringidos a la propiedad de pertenencia no has introducido también el mínimo, y estaría bien incluirlo, ¿no?

Cierto. Ya lo he incluido.

He puesto todos los infinitos que has marcado en los pares ordenados, pero hace ya tiempo que debería haber dicho que podemos omitirlos, puesto que no empleamos más n-tuplas que las de la forma \( \left<\right>_\infty \), pero me sabe mal dejar de ponerlos así, fuera de plazo.

También el de regularidad, que no se menciona en el mensaje, ¿no?

Basta también considerar el mínimo del propio conjunto \( x \) y es claro que \( \min x \in x \) y que \( \min x \cap x = \emptyset \) (porque si \( v \in \min x \), en particular, \( v < \min x \) y no puede ser entonces \( v \in x \)).

En efecto, no lo he mencionado por no suponer al lector familiarizado con un axioma técnico como ése.

Por último, ahora se me plantea una cuestión:

En el hilo de respuestas sobre los ordinales me comentaste que lo que se puede demostrar en AP es (esencialmente) aquello que pueda demostrarse en ZFC cambiando el axioma de infinitud por aquel que dice que todo conjunto es finito, pero ahora también hemos visto (a falta de lo último que comentas que se verá en la siguiente respuesta) que esto es válido para ARP. Por tanto, ¿qué diferencia a ARP de AP? He de suponer que AP es más fuerte, ¿pero donde radica la diferencia respecto a aquello que se pueda probar y que no? ¿Hay algún resultado sencillo de ver que pueda probarse en AP, pero no en ARP? ¿Todo lo que puede probarse en ARP se puede probar en AP?

Muy buena pregunta. Pero la respuesta es que no, ARP es mucho más débil que AP, y también es más débil que ZFC sin el axioma de infinitud. He puesto un último párrafo en el mensaje explicando el motivo, pero lo repito aquí: el axioma de especificación en ARP sólo vale para fórmulas de ARP, es decir, con cuantificadores acotados, mientras que en ZFC puedes usar fórmulas con cuantificadores arbitrarios. En el caso del axioma de reemplazo, en ZFC vale para fórmulas arbitrarias, mientras que en ARP vale para términos de ARP, que son más restrictivos. Más aún, el lenguaje formal de ZFC te permite considerar fórmulas con cuantificadores arbitrarios, y el lenguaje de ARP no.

Si comparas directamente ARP con AP, las comparación se ve más clara en términos del principio de inducción: en AP puedes razonar por inducción sobre cualquier fórmula, con todos los cuantificadores que quieras, mientras que en ARP sólo puedes considerar fórmulas con cuantificadores acotados.

Ya he corregido también la errata del mensaje previo que has añadido a última hora. No se te escapa una. Muchas gracias una vez más por tu atenta lectura.

15 Julio, 2023, 09:42 am
Respuesta #166

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola de nuevo.

>:(   Y yo que pensaba que ya habías saciado tu rencor...

Soy insaciable >:D

Eso es. La idea subyacente es que si dos conjuntos tienen los mismos elementos, entonces, como números naturales, tienen las mismas cifras binarias, luego son iguales.

Claro, porque al final, con la definición que se ha dado, los elementos de un conjunto en ARP no son más que las posiciones en su expresión en binario que valen \( 1 \), ¿no?

Me resulta muy curioso como en una teoría de conjuntos los números naturales son "conjuntos" (pues todo lo es) y ahora en ARP hablamos de conjuntos que, realmente, son números naturales (pues en esencia, todo término en ARP es un número natural).

Respecto a la diferencia entre usar el igualador y la identidad me ha quedado claro. Mi problema es que aun no me acostumbro del todo a que en ARP términos y funtores sean esencialmente lo mismo y por tanto, cuando por ejemplo veo la definición de la unión (que la pusiste con una identidad), no caigo al momento que es un término, pero que también define un funtor. Espero que no se me vuelva a olvidar ::)

Si \( u\in x \), llama \( v \equiv x\dot{-}u \), de modo que \( u = x\dot{-}v\in x \), luego \( \mu u\leq x(x\dot{-}u \in x)\leq v = x\dot{-}u \), luego \( u\leq \max x \), ¿no?

Cierto. Me cegó el no usar una propiedad no demostrada de la resta truncada, pero que resulta muy fácil de demostrar.

He puesto todos los infinitos que has marcado en los pares ordenados, pero hace ya tiempo que debería haber dicho que podemos omitirlos, puesto que no empleamos más n-tuplas que las de la forma \( \left<\right>_\infty \), pero me sabe mal dejar de ponerlos así, fuera de plazo.

Ya lo imaginaba, pero como no estaba mencionado en ningún lugar que dejáramos de usar el infinito, pues yo lo comento a ver si así consigo saciar mi rencor :laugh:

Muy buena pregunta. Pero la respuesta es que no, ARP es mucho más débil que AP, y también es más débil que ZFC sin el axioma de infinitud. He puesto un último párrafo en el mensaje explicando el motivo, pero lo repito aquí: el axioma de especificación en ARP sólo vale para fórmulas de ARP, es decir, con cuantificadores acotados, mientras que en ZFC puedes usar fórmulas con cuantificadores arbitrarios. En el caso del axioma de reemplazo, en ZFC vale para fórmulas arbitrarias, mientras que en ARP vale para términos de ARP, que son más restrictivos. Más aún, el lenguaje formal de ZFC te permite considerar fórmulas con cuantificadores arbitrarios, y el lenguaje de ARP no.

Si comparas directamente ARP con AP, las comparación se ve más clara en términos del principio de inducción: en AP puedes razonar por inducción sobre cualquier fórmula, con todos los cuantificadores que quieras, mientras que en ARP sólo puedes considerar fórmulas con cuantificadores acotados.

Claro, claro. Estaba tan metido en la lógica de ARP que se me había olvidado por completo que en la lógica de primer orden puedes utilizar tantos cuantificadores como quieras sin ningún problema :laugh:

Además, que es cierto que la versión de reemplazo que se ha probado sería (viéndolo en ZFC) únicamente para fórmulas de la forma \( \psi(u,z) \equiv z=t(u,x_1, \cdots, x_n) \), ¿no?

Un saludo.

15 Julio, 2023, 01:40 pm
Respuesta #167

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Claro, claro. Estaba tan metido en la lógica de ARP que se me había olvidado por completo que en la lógica de primer orden puedes utilizar tantos cuantificadores como quieras sin ningún problema :laugh:

En realidad lo esencial es que en ARP están truncados el principio de inducción, por una parte, y los teoremas de especificación y reemplazo, por otra (a fórmulas sin cuantificadores no acotados y a términos de ARP, respectivamente). El hecho de que la lógica de ARP no admita cuantificadores generales es secundario, porque podemos considerar una teoría de primer orden usual ARP' sobre un lenguaje con los funtores de ARP de modo que los teoremas de ARP coincidan con los teoremas de ARP' que no tienen cuantificadores no acotados. Así tienes una teoría en la que puedes trabajar sin restricciones lógicas, pero de modo que si demuestras un teorema sin cuantificadores no acotados, puedes estar seguro de que es un teorema de ARP. Aun así, esta teoría es más débil que AP o que ZFC sin el axioma de infinitud, porque sigues teniendo restringidos los principios de inducción o de especificación o reemplazo.

Además, que es cierto que la versión de reemplazo que se ha probado sería (viéndolo en ZFC) únicamente para fórmulas de la forma \( \psi(u,z) \equiv z=t(u,x_1, \cdots, x_n) \), ¿no?

Sí, pero esto es más delicado de comparar con el auténtico ZFC. El problema es que en ARP no puedes enunciar el reemplazo en términos de fórmulas arbitrarias \( \psi(u, z) \) tales que para cada \( z \) existe un único \( u \), etc., porque no podemos decir "existe un único \( u \)".

El caso es que, desde el punto de vista de ZFC, los casos particulares de reemplazo que tienes disponibles en ARP son los correspondientes a fórmulas de tipo \( \psi(u,z) \equiv z=t(u,x_1, \cdots, x_n) \) donde \( t \) es un término definible en ARP. Eso tiene una caracterizació aritmética, pero no es obvia.

15 Julio, 2023, 09:56 pm
Respuesta #168

argentinator

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

El problema es que un objetivo fundamental en la lógica formal es independizar el lenguaje formal de su posible significado.

Y bueno, ¿pero nadie se cuestionó jamás el por qué insisitir con ese objetivo?

Citar
Se trata de definir un lenguaje formal que pueda usar un formalista radical para demostrar cosas sin tener en cuenta para nada que los funtores denotan funciones recursivas primitivas.
Más gráficamente, para que podamos decir que \( \mathcal L_{\rm arp} \) es realmente un lenguaje formal de pleno derecho, es esencial que un formalista radical pueda entender lo que es \( \mathcal L_{\rm arp} \) (en particular, qué son los funtores de \( \mathcal L_{\rm arp} \) ) sin necesidad de leer nada escrito en rojo en el hilo, sin necesidad de que entienda (o quiera admitir) que los funtores están pensados para denotar funciones. Si agrupas la definición de los funtores con la definición de las funciones recursivas primitivas estás obligando a un formalista radical que  quiera entender (formalistarradicalmente) la definición de funtor a tragarse una buena píldora semántica.

No he hecho semejante mescolanza,
al menos no en un grado tan extremo.

Si te fijás bien, en el punto 4 de mi lista lo que digo es que el lenguaje de ARP
lo dejo tal cual estaba, o sea, queda definido en forma independiente.

Lo que hice fue definir la semántica de una manera diferente,
con la ayuda del lenguaje formal,
que es algo distinto a haber definido previamente las funciones.

Pero aparte, lo que digo es que, en cierto modo,
en el fondo estás haciendo algo muy similar
al definir primero a las funciones por separado,
porque si bien no estás usando el lenguaje formal de ARP,
en cambio estás usando letras y subíndices,
en el lenguaje castellano "extendido",
porque a las funciones recursivas primitivas
no te queda más remedio que "denotarlas" de algún modo.

Lo que digo es que,
ya que no se puede evitar denotar las funciones recursivas primitivas,
ya sea en español, o como semántica de ARP,
me ahorro un paso,
y uso directamente el lenguaje ARP para construir las funciones recursivas primitivas,
lo cual de paso ya reflejará la estructura recursiva que se pretende obtener.

En cuanto a las "píldoras semánticas",
yo creo que ya la misma palabra "semántica" es la píldora más grande y difícil de tragar de todas.
Una vez tragado eso, queda todo un mundo de "semántica sin sintaxis" que se puede explorar por sí solo,
o sea, objetos metamatemáticos que andan por ahí, sacados del aire.
Y no sólo eso, sino que se abre la puerta también a todo tipo de tratamientos y relaciones entre distintos lenguajes formales y estructuras semánticas,
los cuales no tienen por qué coincidir con lo que los primeros lógicos se plantearon.

Dicho de otro modo. Smullyan tendrá que tragarse las consecuencias de su propia píldora.

Citar
El hecho de que los funtores denotan funciones sirve para entender qué hacemos y por qué lo hacemos, pero el objetivo de la lógica formal es que se pueda trabajar con ARP olvidando que sus fórmulas significan algo. Una cosa es que des una definición formal e inmediatamente después la interpretes semánticamente, pero juntar en la misma definición la sintaxis con la semántica es ocultar un hecho fundamental: que la sintaxis está pensada para que funcione independientemente de la semántica.

Aunque mi producto final no tiene ese aspecto de mezcla extrema entre sintaxis y semántica, como ya he explicado,
lo cierto es que lo he intentado,
y no veo cuál sea el problema en pretender intentar hacer cosas así,
después de todo no hay reglas que lo impidan.

Pero bueno. No insistiré con eso, así no caigo en un off-topic, al cual encima no sé si aportaré gran cosa.


15 Julio, 2023, 11:19 pm
Respuesta #169

Carlos Ivorra

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

El problema es que un objetivo fundamental en la lógica formal es independizar el lenguaje formal de su posible significado.

Y bueno, ¿pero nadie se cuestionó jamás el por qué insisitir con ese objetivo?

Sí, eso tiene una respuesta muy clara: si la lógica formal tiene un importancia en la fundamentación de las matemáticas y no es una mera teoría poco conocida más entre muchas especialidades de la matemática, se debe a que para fundamentar la teoría de conjuntos es necesario diseñar un lenguaje formal y unas reglas de razonamiento formal que no se apoyen en el concepto general de "conjunto", ya que nadie puede decir con exactitud qué son esos objetos llamados "conjuntos" de los que se supone que hablan los matemáticos.

La lógica formal sirve para que los matemáticos a los que les intentan apretar las tuercas pidiendo que aclaren de qué cosas hablan cuando hacen matemáticas, puedan responder: No tengo ni idea de qué son los conjuntos, pero parto de la base de que cumplen estos axiomas (los de ZFC, por ejemplo). Y para que eso sea "lícito" es necesario que los axiomas de ZFC y las reglas de razonamiento de ZFC, que distinguen qué es un razonamiento correcto y qué no, puedan definirse sin hacer referencia a esos conjuntos de los que queremos hablar sin ser capaces de decir lo que son exactamente.

Claro, si hablamos de una teoría formal pensada para hablar de números naturales, no tenemos ese problema, porque sí que sabemos exactamente qué son los números naturales, por lo que podemos mezclar como queramos sintaxis y semántica sin caer en ningún círculo vicioso. De hecho, el problema de la fundamentación de la teoría de conjuntos es que obliga a definir ZFC sin hacer referencia a los conjuntos abstractos de los que habla ZFC, pero eso no significa que no podamos (y, de hecho, necesitamos) hacer referencia a algunos conceptos elementales, como son los números naturales y algunos conjuntos concretos (finitos o, a lo sumo, numerables). En el caso de una teoría como ARP, o la Aritmética de Peano, la poca semántica necesaria para construir la sintaxis está tan cerca de la totalidad de la semántica asociada a la teoría que la distinción se hace más difusa, pero creo que no está de más enfatizar que para construir ARP hace falta entender muy poco sobre los números naturales, y que con ese poco se puede construir una teoría formal capaz de regular completamente el razonamiento lógico finitista (en el caso de ARP) y el razonamiento de la aritmética elemental (en el caso de AP).

En resumen: la importancia de distinguir entre semántica y sintaxis no reside en el estudio de ARP o AP, sino en el uso de la lógica para fundamentar teorías mucho más abstractas, como ZFC, o una axiomática para el análisis no estándar, etc.

Citar
Se trata de definir un lenguaje formal que pueda usar un formalista radical para demostrar cosas sin tener en cuenta para nada que los funtores denotan funciones recursivas primitivas.
Más gráficamente, para que podamos decir que \( \mathcal L_{\rm arp} \) es realmente un lenguaje formal de pleno derecho, es esencial que un formalista radical pueda entender lo que es \( \mathcal L_{\rm arp} \) (en particular, qué son los funtores de \( \mathcal L_{\rm arp} \) ) sin necesidad de leer nada escrito en rojo en el hilo, sin necesidad de que entienda (o quiera admitir) que los funtores están pensados para denotar funciones. Si agrupas la definición de los funtores con la definición de las funciones recursivas primitivas estás obligando a un formalista radical que  quiera entender (formalistarradicalmente) la definición de funtor a tragarse una buena píldora semántica.

No he hecho semejante mescolanza,
al menos no en un grado tan extremo.

Si te fijás bien, en el punto 4 de mi lista lo que digo es que el lenguaje de ARP
lo dejo tal cual estaba, o sea, queda definido en forma independiente.

Lo que hice fue definir la semántica de una manera diferente,
con la ayuda del lenguaje formal,
que es algo distinto a haber definido previamente las funciones.

Ah. Yo me quedé como idea principal lo primero que decías:

Citar
Tal vez podría hacerse todo al mismo tiempo, más o menos así:

Y por eso te previne del inconveniente que supone hacer todo al mismo tiempo. Si lo que querías decir es que primero defines el lenguaje formal de ARP y luego las funciones recursivas primitivas usando el lenguaje formal de ARP, eso es distinto.

Por otro lado, a veces me da la impresión de que interpretas mis palabras como si te estuviera diciendo "hacer eso así está mal", cuando si trato de insistir en algo es en que en este contexto no se puede decir "así está bien" o "así está mal" mientras esté claro que lo que digas es verdad.

Aun suponiendo que pretendieras definir al mismo tiempo los funtores de ARP y las funciones recursivas primitivas, ni yo ni nadie te podría decir "eso está mal", "eso no se hace así". Si lo que haces está bien articulado y al final de tu exposición queda perfectamente claro qué es un funtor de ARP y qué es una función recursiva primitiva, entonces lo que haces está bien.

Lo máximo que yo aspiraba a decirte es que no es buena idea que un lector tenga que asimilar lo que es una función recursiva primitiva a la vez que asimila lo que es un funtor de ARP, porque es un hecho "profundo" que conviene explicitar que los funtores de ARP pueden definirse sin hacer referencia para nada a funciones recursivas primitivas. Y, aun así, si hicieras eso, lo que harías "no estaría mal", sino que sólo te digo que así estarías ocultando un hecho notable de ARP que merece la pena destacar.

Si lo que te propones es definir primero los funtores de ARP y luego las funciones recursivas primitivas, obviamente, tampoco te puedo decir "eso está mal". Sólo te diré que, personalmente, me parece más razonable decir: aquí están estas funciones, y ahora vamos a construir un lenguaje para hablar de ellas, pero eso ya es cuestión de gustos.

Pero aparte, lo que digo es que, en cierto modo,
en el fondo estás haciendo algo muy similar
al definir primero a las funciones por separado,
porque si bien no estás usando el lenguaje formal de ARP,
en cambio estás usando letras y subíndices,
en el lenguaje castellano "extendido",
porque a las funciones recursivas primitivas
no te queda más remedio que "denotarlas" de algún modo.

Cierto. La matemática informal es siempre muy similar a la matemática formal, igual que una mano es siempre muy similar a un guante diseñado para calzarla.

Lo que digo es que,
ya que no se puede evitar denotar las funciones recursivas primitivas,
ya sea en español, o como semántica de ARP,
me ahorro un paso,
y uso directamente el lenguaje ARP para construir las funciones recursivas primitivas,
lo cual de paso ya reflejará la estructura recursiva que se pretende obtener.

Bien. No veo inconveniente alguno en hacerlo así. De hecho, yo estoy escribiendo el hilo como a mí me parece más natural, pero no dudo de que con muchas de las alternativas que planteas podrías escribir una exposición alternativa que sería, como mínimo, tan válida como la que estoy haciendo yo, y no veo por qué no podría ser mejor en muchos aspectos y contener ideas interesantes. Si no lo ves un trabajo excesivo, yo te animaría a hacerlo. Por lo pronto, ayudaría a distinguir qué cosas no te gustan de la lógica porque son como son y no te gusta cómo son y qué cosas no te gustan porque te gustarían más expuestas con otro estilo. Si el segundo caso fuera el 100% sería una excelente noticia.

Por otro lado, te digo que no comparto tu filosofía del "ahorro". Siempre tratas de "evitar todo lo evitable", como diciendo "si no hay más remedio, lo hago, pero cuanto menos, mejor". Lo ideal sería que llegaras a convencerte de que no hay nada malo, o peligroso o qué sé yo, por hablar y razonar informalmente: si no es así, si algo está mal, está mal tanto si lo haces una vez, como si lo haces mil veces, mientras que si algo no está mal, ni está mal hacerlo una vez ni está mal hacerlo mil veces. No creo que el principio de "vale, pero no hay que abusar", que puede tener sentido con el consumo de alcohol y otras cosas de la vida, tenga sentido en este contexto. No hay unos máximos de informalidad recomendados por la OMS.

En cuanto a las "píldoras semánticas",
yo creo que ya la misma palabra "semántica" es la píldora más grande y difícil de tragar de todas.
Una vez tragado eso, queda todo un mundo de "semántica sin sintaxis" que se puede explorar por sí solo,
o sea, objetos metamatemáticos que andan por ahí, sacados del aire.

Sí, ya sé que piensas eso, como también sabrás que en eso discrepamos. Me temo que rebatirte eso sería repetir cosas que ya hemos discutido muchas veces. En efecto, yo no veo ningún inconveniente en razonar sobre números naturales o funciones recursivas primitivas sin necesidad de ningún lenguaje formal y sin necesidad de describir a priori las reglas de razonamiento válidas, igual que la gente razona sobre partidas de ajedrez o sobre cualquier cosa cotidiana que tenga algo de contenido matemático sin necesidad de ninguna teoría formal.

Y no sólo eso, sino que se abre la puerta también a todo tipo de tratamientos y relaciones entre distintos lenguajes formales y estructuras semánticas,
los cuales no tienen por qué coincidir con lo que los primeros lógicos se plantearon.

Aquí no identifico en qué estás pensando.

Dicho de otro modo. Smullyan tendrá que tragarse las consecuencias de su propia píldora.

Tampoco sé qué quieres decir con esto.

Citar
El hecho de que los funtores denotan funciones sirve para entender qué hacemos y por qué lo hacemos, pero el objetivo de la lógica formal es que se pueda trabajar con ARP olvidando que sus fórmulas significan algo. Una cosa es que des una definición formal e inmediatamente después la interpretes semánticamente, pero juntar en la misma definición la sintaxis con la semántica es ocultar un hecho fundamental: que la sintaxis está pensada para que funcione independientemente de la semántica.

Aunque mi producto final no tiene ese aspecto de mezcla extrema entre sintaxis y semántica, como ya he explicado,

Vale. Me resulta difícil hacerme una idea de en qué piensas concretamente (es decir, "cuál es el producto final") a partir de un esbozo como el que habías dado. Incluso con las aclaraciones que has hecho, todavía no estoy seguro de si lo que planteabas es definir primero los funtores y luego las funciones recursivas primitivas usando los funtores, o si hablabas de hacer las dos cosas al mismo tiempo, pero alegando que está claro que así se ve igualmente que los funtores están definidos independientemente de las funciones.

lo cierto es que lo he intentado,
y no veo cuál sea el problema en pretender intentar hacer cosas así,
después de todo no hay reglas que lo impidan.

Ciertamente, no hay reglas que impidan nada, con tal de que uno pueda afirmar que todo lo que vas diciendo es verdad. Y no estoy seguro de entender a qué te refieres con "lo he intentado". ¿Quieres decir que has intentado mezclar de forma extrema sintaxis y semántica? ¿O sólo que has intentado mezclarlas, pero no de forma extrema?

Una mezcla de sintaxis y semántica en una teoría aritmética es imprescindible, pues definir un lenguaje formal requiere un poco de aritmética, pero no mucha. Pero no está de más destacar que la construcción de ARP no requiere saber nada sobre funciones recursivas primitivas.