Autor Tema: Enumeración de las fórmulas de PROP

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

08 Febrero, 2013, 12:33 am
Leído 2193 veces

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Para demostrar el siguiente teorema

Cada conjunto consistente \( \Gamma \) se encuentra incluido en algún conjunto \( \Gamma^* \) consistente maximal.

necesito construir una enumeración para las fórmulas de \( \text{PROP} \). Eso en el libro está como ejercicio, pero no se me ocurre nada por ahora. Dice:

Citar
Find an effective way of enumerating all propositions (hint: consider sets \( \Gamma_n \) of all propositions of rank \( \leq n \) with atoms \( p_0,\dots,p_n \)).

¿A qué se está refiriendo?

O sea, hay que construir explícitamente una biyección \( f:\mathbb{N}\longrightarrow \text{PROP} \) donde \( \text{PROP} \) es el definido en este hilo.

Muchas gracias.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

08 Febrero, 2013, 01:39 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,075
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Entiendes la definición de \( \Gamma_n \)? Se trata del conjunto de todas las fórmulas en las que a lo sumo aparecen los átomos \( p_0,\ldots, p_n \) y que resultan de aplicar a lo sumo \( n \) reglas de construcción.

Por ejemplo, \( \Gamma_0 = \{p_0, \bot\} \),

\( \Gamma_1 = \{p_0, p_1, \bot, p_0\land p_0, p_1\land p_1, \)\(  p_0\land p_1,p_1\land p_0,p_0\land \bot, p_1\land \bot, \bot\land p_0,\bot\land p_1,\bot\land \bot,\ldots\} \)

Se trata de probar que cada \( \Gamma_n \) es finito, que toda fórmula está en un \( \Gamma_n \) y que \( \Gamma_n\subset \Gamma_{n+1} \).

Entonces, puedes biyectar \( \Gamma_0 \) con \( \{0,1\} \), luego puedes biyectar \( \Gamma_1\setminus \Gamma_0 \) con los números naturales \( 2, 3, \ldots, k_1 \), hasta cierto \( k_1 \), luego puedes biyectar \( \Gamma_2\setminus \Gamma_1 \) con \( k_1+1,\ldots, k_2 \), y uniendo todas estas biyecciones tienes una biyección entre fórmulas y números naturales.

Puedes dar un criterio explícito para elegir cada fragmento de biyección, y entonces tienes definida explícitamente la biyección completa.

No obstante, yo creo que hay una forma más sencilla de hacerlo: asocia a cada signo de PROP un número natural. Por ejemplo

\( n(\land)=0 \), \( n(\lor)=1 \), \( n(\rightarrow)=2 \), \( n(\lnot)=3 \), \( n(\leftrightarrow)=4 \), \( n(\bot)=5 \), \( n(()=6 \), \( n())=7 \), \( n(p_0)=8 \), \( n(p_1)=9 \), etc.

Cada fórmula \( \phi \) de PROP es una sucesión finita de signos, digamos \( s_0,\ldots, s_n \). Asígnale el número natural \( g(\phi) = p_0^{n(s_0)}\cdots p_n^{n(s_n)} \), donde \( p_i \) es la sucesión de los primos.

De este modo tienes una aplicación inyectiva del conjunto de fórmulas de PROP en los números naturales. Para hacerla biyectiva asigna el \( 0 \) a la fórmula \( \phi_0 \)  tal que \( g(\phi_0) \) es el menor posible, asigna el \( 1 \) a la fórmula \( \phi_1 \) tal que  \( g(\phi_1) \) es el menor posible después de  \( g(\phi_0) \), etc.

08 Febrero, 2013, 06:01 am
Respuesta #2

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
¿Entiendes la definición de \( \Gamma_n \)?

No, no la entendía hasta que leí tu explicación:

Se trata del conjunto de todas las fórmulas en las que a lo sumo aparecen los átomos \( p_0,\ldots, p_n \) y que resultan de aplicar a lo sumo \( n \) reglas de construcción.

Por ejemplo, \( \Gamma_0 = \{p_0, \bot\} \),

\( \Gamma_1 = \{p_0, p_1, \bot, p_0\land p_0, p_1\land p_1, \)\(  p_0\land p_1,p_1\land p_0,p_0\land \bot, p_1\land \bot, \bot\land p_0,\bot\land p_1,\bot\land \bot,\ldots\} \)

Se trata de probar que cada \( \Gamma_n \) es finito, que toda fórmula está en un \( \Gamma_n \) y que \( \Gamma_n\subset \Gamma_{n+1} \).

Que \( \Gamma_n\subset \Gamma_{n+1} \) es inmediato a partir de la definición de los \( \Gamma_n \), ¿no? Respecto a que son finitos, lo más fácil creo que es hacerlo por inducción en \( n \). En el paso inductivo se tendría que \( |\Gamma_{n+1}|=|\Gamma_n|+4(|\Gamma_n|+1)^2+(|\Gamma_n|+1) \) pero como \( |\Gamma_n|<\infty \) por hipótesis de inducción, también \( |\Gamma_{n+1}|<\infty \). El razonamiento anterior deja planteada al mismo tiempo una relación de recurrencia (con condición inicial \( |\Gamma_0|=2 \)) cuya solución (aportada por Wolfram Alpha) es \( |\Gamma_n|=\dfrac{13^{2^n}-5}{4} \). Igual no tiene mucho interés práctico esta fórmula (salvo que permite determinar explícitamente los naturales \( k_1,k_2,\dots \)).

Lo que no veo claro es cómo probar que toda proposición está en un \( \Gamma_n \).

Entonces, puedes biyectar \( \Gamma_0 \) con \( \{0,1\} \), luego puedes biyectar \( \Gamma_1\setminus \Gamma_0 \) con los números naturales \( 2, 3, \ldots, k_1 \), hasta cierto \( k_1 \), luego puedes biyectar \( \Gamma_2\setminus \Gamma_1 \) con \( k_1+1,\ldots, k_2 \), y uniendo todas estas biyecciones tienes una biyección entre fórmulas y números naturales.

Puedes dar un criterio explícito para elegir cada fragmento de biyección, y entonces tienes definida explícitamente la biyección completa.

Comprendo  :).

No obstante, yo creo que hay una forma más sencilla de hacerlo: asocia a cada signo de PROP un número natural. Por ejemplo

\( n(\land)=0 \), \( n(\lor)=1 \), \( n(\rightarrow)=2 \), \( n(\lnot)=3 \), \( n(\leftrightarrow)=4 \), \( n(\bot)=5 \), \( n(()=6 \), \( n())=7 \), \( n(p_0)=8 \), \( n(p_1)=9 \), etc.

Cada fórmula \( \phi \) de PROP es una sucesión finita de signos, digamos \( s_0,\ldots, s_n \). Asígnale el número natural \( g(\phi) = p_0^{n(s_0)}\cdots p_n^{n(s_n)} \), donde \( p_i \) es la sucesión de los primos.

De este modo tienes una aplicación inyectiva del conjunto de fórmulas de PROP en los números naturales. Para hacerla biyectiva asigna el \( 0 \) a la fórmula \( \phi_0 \)  tal que \( g(\phi_0) \) es el menor posible, asigna el \( 1 \) a la fórmula \( \phi_1 \) tal que  \( g(\phi_1) \) es el menor posible después de  \( g(\phi_0) \), etc.

Respecto a esto:  :o. Ciertamente, es mucho más simple que lo que se sugiere en el libro. Voy a resolverlo así.

Muchísimas gracias, Carlos.

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

08 Febrero, 2013, 10:50 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 9,075
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Que \( \Gamma_n\subset \Gamma_{n+1} \) es inmediato a partir de la definición de los \( \Gamma_n \), ¿no?

Sí.

Respecto a que son finitos, lo más fácil creo que es hacerlo por inducción en \( n \). En el paso inductivo se tendría que \( |\Gamma_{n+1}|=|\Gamma_n|+4(|\Gamma_n|+1)^2+(|\Gamma_n|+1) \)

¿No sería \( |\Gamma_n|+1 \) al principio? Porque aparece la fórmula \( p_{n+1} \).

Lo que no veo claro es cómo probar que toda proposición está en un \( \Gamma_n \).

¿No ves la idea o no ves la forma de probarlo? La idea es que, si \( \phi \) es una fórmula cualquiera, puedes tomar el máximo \( m \) tal que \( p_m \) aparece en \( \phi \) y, por otra parte, el mínimo \( m' \) tal que   \( \phi \) puede definirse por una sucesión de fórmulas de longitud \( m' \). Entonces, si \( n \) es el máximo de \( m \) y \( m' \), tienes que \( \phi \) está en \( \Gamma_n \).

Respecto a esto:  :o. Ciertamente, es mucho más simple que lo que se sugiere en el libro. Voy a resolverlo así.

Si, está bien que digas  :o, pero quede claro que la idea no es mía. Es de Gödel. Lo que he hecho ha sido definirte una numeración de Gödel para las fórmulas de PROP. Es una técnica estándar en lógica.

08 Febrero, 2013, 01:02 pm
Respuesta #4

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
¿No sería \( |\Gamma_n|+1 \) al principio? Porque aparece la fórmula \( p_{n+1} \).

Sí, precisamente entraba ahora para corregir ese detalle. Y efectivamente, la proposición que no había tenido en cuenta fue \( p_{n+1} \). Lo raro es que no la conté en el primer sumando pero sí en el último, al contar las mismas fórmulas (las de \( \Gamma_n\cup \{p_{n+1}\} \)) negadas.

Lo que no veo claro es cómo probar que toda proposición está en un \( \Gamma_n \).

¿No ves la idea o no ves la forma de probarlo?

En realidad no veía ni una cosa ni la otra. Con esto:

La idea es que, si \( \phi \) es una fórmula cualquiera, puedes tomar el máximo \( m \) tal que \( p_m \) aparece en \( \phi \) y, por otra parte, el mínimo \( m' \) tal que \( \phi \) puede definirse por una sucesión de fórmulas de longitud \( m' \). Entonces, si \( n \) es el máximo de \( m \) y \( m' \), tienes que \( \phi \) está en \( \Gamma_n \).

ya lo tengo claro.

Si, está bien que digas  :o, pero quede claro que la idea no es mía. Es de Gödel. Lo que he hecho ha sido definirte una numeración de Gödel para las fórmulas de PROP. Es una técnica estándar en lógica.

No sabía. Pero ahora (con la mente más despejada) le encuentro un "defecto" (o una desventaja) que no le encontré ayer. Creo que esa enumeración tiene importancia teórica, pero no práctica. Porque si no, ¿cómo vamos a determinar a qué fórmula le corresponde el \( n \)-ésimo lugar? Por ejemplo, la primer fórmula de acuerdo a esa enumeración creo que va a ser \( \varphi_0=\bot \). Pero ya para calcular \( \varphi_1 \) en principio, habría varios candidatos y no es evidente saber cuál es.

En ese sentido, con el procedimiento que indicaste con los \( \Gamma_n \) y dando un criterio explícito para cada fragmento de biyección (de \( \Gamma_{n+1}\setminus \Gamma_n \) en \( \{k_n+1,k_n+2,\dots,k_{n+1}\} \)), uno puede ir numerando las fórmulas casi sin ningún esfuerzo.

Muchas gracias.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

08 Febrero, 2013, 02:16 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,075
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Sí, precisamente entraba ahora para corregir ese detalle. Y efectivamente, la proposición que no había tenido en cuenta fue \( p_{n+1} \). Lo raro es que no la conté en el primer sumando pero sí en el último, al contar las mismas fórmulas (las de \( \Gamma_n\cup \{p_{n+1}\} \)) negadas.

Me acabo de dar cuenta de que tus cuentas (incluso con esta corrección) no se corresponden exactamente con la definición de \( \Gamma_n \) (aunque serían válidas para una definición ligeramente distinta que también permitiría obtener el resultado). El problema es que al incorporar \( p_{n+1} \) de la forma en que lo haces, en \( \Gamma_{n+1} \) no estás contando todas las fórmulas que contienen a \( p_{n+1} \) pero se construyen en más de un paso. Por ejemplo, no estás contando \( (p_{n+1}\land p_{n+1})\rightarrow p_{n+1} \), porque ésta no se obtiene en un paso de  \( \Gamma_n\cup \{p_{n+1}\} \).

Pero ahora (con la mente más despejada) le encuentro un "defecto" (o una desventaja) que no le encontré ayer. Creo que esa enumeración tiene importancia teórica, pero no práctica. Porque si no, ¿cómo vamos a determinar a qué fórmula le corresponde el \( n \)-ésimo lugar? Por ejemplo, la primer fórmula de acuerdo a esa enumeración creo que va a ser \( \varphi_0=\bot \). Pero ya para calcular \( \varphi_1 \) en principio, habría varios candidatos y no es evidente saber cuál es.

Ante todo, me acabo de dar cuenta de un pequeño error también en mis cuentas. Habría que poner

\( g(\phi) = p_0^{n(s_0)+1}\cdots p_n^{n(s_n)+1} \)

porque los exponentes 0 dan lugar a ambigüedades.

Hay un algoritmo (aunque no sea muy práctico). Observa que si tomas un número \( N \), siempre puedes saber si codifica una fórmula o no. Sólo tienes que descomponerlo en primos \( N = p_0^{n_0}\cdots p_k^{n_k} \) y comprobar si los signos codificados por \( n_0, \ldots, n_k \) forman o no una fórmula de PROP.

Teniendo esto en cuenta, puedes tomar el 2 y comprobar que codifica a \( \bot \), luego tomar el 3 y ver que no codifica a nada, y luego ver qué pasa con el 4, y luego con el 5, y así vamos obteniendo las fórmulas de PROP en el orden correcto.

En ese sentido, con el procedimiento que indicaste con los \( \Gamma_n \) y dando un criterio explícito para cada fragmento de biyección (de \( \Gamma_{n+1}\setminus \Gamma_n \) en \( \{k_n+1,k_n+2,\dots,k_{n+1}\} \)), uno puede ir numerando las fórmulas casi sin ningún esfuerzo.

Sí, algo más práctico puede ser. De todos modos, si quieres la enumeración para demostrar el teorema que indicas en tu primer mensaje, sucede que la demostración no es constructiva, por lo que tener una enumeración explícita fácilmente computable no ayuda en gran cosa. Luego tienes que decidir si incluyes o no una fórmula en el conjunto \( \Gamma^* \) en función de si al hacerlo conservas o no la consistencia, y eso no puede en general decidirse por algoritmo alguno, así que en ese punto pierdes la "efectividad" de la demostración.

08 Febrero, 2013, 05:06 pm
Respuesta #6

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Me acabo de dar cuenta de que tus cuentas (incluso con esta corrección) no se corresponden exactamente con la definición de \( \Gamma_n \) (aunque serían válidas para una definición ligeramente distinta que también permitiría obtener el resultado). El problema es que al incorporar \( p_{n+1} \) de la forma en que lo haces, en \( \Gamma_{n+1} \) no estás contando todas las fórmulas que contienen a \( p_{n+1} \) pero se construyen en más de un paso. Por ejemplo, no estás contando \( (p_{n+1}\land p_{n+1})\rightarrow p_{n+1} \), porque ésta no se obtiene en un paso de  \( \Gamma_n\cup \{p_{n+1}\} \).

Tienes razón  :-[. Es que intuitivamente entendí a los \( \Gamma_n \) de manera recursiva. Voy a llamar \( \overline{\Gamma}_n \) a los que yo creí que eran los \( \Gamma_n \). Entonces mi cabeza razonó:

\( \left\{\begin{array}{ll}
\overline{\Gamma}_0=\{\bot,p_0\}\\
\\
\displaystyle \overline{\Gamma}_{n+1}=\Big(\overline{\Gamma}_n\cup\{p_{n+1}\}\Big)\cup\Big(\bigcup_{\varphi,\psi\in \overline{\Gamma}_n\cup\{p_{n+1}\}}\{(\varphi\square\psi)\}\Big)\cup\Big(\bigcup_{\varphi\in \overline{\Gamma}_n\cup\{p_{n+1}\}}\{(\lnot\varphi)\}\Big)
\end{array}\right. \)

Pero estoy de acuerdo en que no son los \( \Gamma_n \) sino otra sucesión de conjuntos diferente. Cuando dices que mis cuentas "serían válidas para una definición ligeramente distinta que también permitiría obtener el resultado", ¿te refieres a mi definición de los \( \overline{\Gamma}_n \)? Creo que esta definición no sirve porque habría fórmulas en \( \text{PROP} \) que no están en ningún \( \overline{\Gamma}_n \).

Ante todo, me acabo de dar cuenta de un pequeño error también en mis cuentas. Habría que poner

\( g(\phi) = p_0^{n(s_0)+1}\cdots p_n^{n(s_n)+1} \)

porque los exponentes 0 dan lugar a ambigüedades.

¿Por qué habría ambigüedades? Creo que viene por el lado de que dado un número natural \( N \), uno no puede saber la cadena de símbolos que codifica. El problema está en que, si por ejemplo \( N=2 \), se tiene que \( 2=2^13^05^07^0\cdots \) y se estaría representando una cadena infinita. Aún así, la función \( g \) estaría bien definida (la "ambigüedad" estaría en la imposibilidad de determinar \( g^{-1} \)).

Hay un algoritmo (aunque no sea muy práctico). Observa que si tomas un número \( N \), siempre puedes saber si codifica una fórmula o no. Sólo tienes que descomponerlo en primos \( N = p_0^{n_0}\cdots p_k^{n_k} \) y comprobar si los signos codificados por \( n_0, \ldots, n_k \) forman o no una fórmula de PROP.

Teniendo esto en cuenta, puedes tomar el 2 y comprobar que codifica a \( \bot \), luego tomar el 3 y ver que no codifica a nada, y luego ver qué pasa con el 4, y luego con el 5, y así vamos obteniendo las fórmulas de PROP en el orden correcto.

Es verdad. Creo que hay algunas erratas, pero está muy claro de todas formas. El 2 no codificaría a \( \bot \), el número 2 (que es \( 2^{0+1} \)), codificaría a la cadena formada únicamente por \( \wedge \) (ya que \( n(\wedge)=0 \)), que no es una fórmula de \( \text{PROP} \). Además aquí me parece que lo correcto hubiese sido:

Sólo tienes que descomponerlo en primos \( N = p_0^{n_0}\cdots p_k^{n_k} \) y comprobar si los signos codificados por \( n_0{\red -1}, \ldots, n_k{\red -1} \) forman o no una fórmula de PROP.

En ese sentido, con el procedimiento que indicaste con los \( \Gamma_n \) y dando un criterio explícito para cada fragmento de biyección (de \( \Gamma_{n+1}\setminus \Gamma_n \) en \( \{k_n+1,k_n+2,\dots,k_{n+1}\} \)), uno puede ir numerando las fórmulas casi sin ningún esfuerzo.

Sí, algo más práctico puede ser. De todos modos, si quieres la enumeración para demostrar el teorema que indicas en tu primer mensaje, sucede que la demostración no es constructiva, por lo que tener una enumeración explícita fácilmente computable no ayuda en gran cosa. Luego tienes que decidir si incluyes o no una fórmula en el conjunto \( \Gamma^* \) en función de si al hacerlo conservas o no la consistencia, y eso no puede en general decidirse por algoritmo alguno, así que en ese punto pierdes la "efectividad" de la demostración.

Tienes razón. El esfuerzo en conseguir una enumeración explícita para las fórmulas proposicionales es en vano si se quiere una demostración constructiva de ese teorema. No obstante, se me ocurre que podría tener interés en sí misma...

Muchas gracias por toda tu ayuda.

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

08 Febrero, 2013, 05:33 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 9,075
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero estoy de acuerdo en que no son los \( \Gamma_n \) sino otra sucesión de conjuntos diferente. Cuando dices que mis cuentas "serían válidas para una definición ligeramente distinta que también permitiría obtener el resultado", ¿te refieres a mi definición de los \( \overline{\Gamma}_n \)? Creo que esta definición no sirve porque habría fórmulas en \( \text{PROP} \) que no están en ningún \( \overline{\Gamma}_n \).

Sí que sirve. Sólo que una fórmula puede aparecer un poco más tarde: si una fórmula contiene hasta \( p_n \) y se construye en \( m \) pasos aparecerá en el conjunto de orden \( n+m \).

¿Por qué habría ambigüedades? Creo que viene por el lado de que dado un número natural \( N \), uno no puede saber la cadena de símbolos que codifica. El problema está en que, si por ejemplo \( N=2 \), se tiene que \( 2=2^13^05^07^0\cdots \) y se estaría representando una cadena infinita. Aún así, la función \( g \) estaría bien definida (la "ambigüedad" estaría en la imposibilidad de determinar \( g^{-1} \)).

Sí, a eso me refería, a que no sería biyectiva, y queremos una biyección. Estaba pensando en que sería ambiguo hablar de la cadena codificada por tal número, pues no sabríamos si es una o la que resulta de ponerle un \( \land \) detrás, claro que como una fórmula no puede acabar en \( \land \) la restricción al conjunto de fórmulas sí que sería biyectiva, pero es más sencillo si sumas uno a los exponentes.

Es verdad. Creo que hay algunas erratas, pero está muy claro de todas formas.

Sí, todas las rectificaciones que haces son ciertas. Disculpa.

Tienes razón. El esfuerzo en conseguir una enumeración explícita para las fórmulas proposicionales es en vano si se quiere una demostración constructiva de ese teorema. No obstante, se me ocurre que podría tener interés en sí misma...

No te digo que no.

08 Febrero, 2013, 06:17 pm
Respuesta #8

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Sí que sirve. Sólo que una fórmula puede aparecer un poco más tarde: si una fórmula contiene hasta \( p_n \) y se construye en \( m \) pasos aparecerá en el conjunto de orden \( n+m \).

¿Y cómo se demostraría eso? Disculpa que te haga tantas preguntas, pero ya que definí al conjunto de los \( \overline{\Gamma}_n \) y sirve para el propósito que quería (que yo pensé que no servía), quisiera saber cómo continuar por ese camino. Además de las tres cosas que se debían probar, a saber

1) \( \overline{\Gamma}_{n}\subset \overline{\Gamma}_{n+1} \)

2) Toda fórmula proposicional está en un \( \overline{\Gamma}_{n} \)

3) \( \overline{\Gamma}_{n} \) es finito para todo \( n \)

1) es inmediato a partir de la definición recursiva que di de los \( \overline{\Gamma}_{n} \), en 3) ahora sí vale la fórmula que yo había dado de \( |\overline{\Gamma}_{n+1}|=(|\overline{\Gamma}_{n}|+1)+4(|\overline{\Gamma}_{n}|+1)^2+(|\overline{\Gamma}_{n}|+1) \) y 2) sería la parte que me faltaría demostrar. Luego sí continúo como indicaste:

Entonces, puedes biyectar \( \Gamma_0 \) con \( \{0,1\} \), luego puedes biyectar \( \Gamma_1\setminus \Gamma_0 \) con los números naturales \( 2, 3, \ldots, k_1 \), hasta cierto \( k_1 \), luego puedes biyectar \( \Gamma_2\setminus \Gamma_1 \) con \( k_1+1,\ldots, k_2 \), y uniendo todas estas biyecciones tienes una biyección entre fórmulas y números naturales.

Puedes dar un criterio explícito para elegir cada fragmento de biyección, y entonces tienes definida explícitamente la biyección completa.

Muchas gracias.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

08 Febrero, 2013, 06:26 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 9,075
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Considera una sucesión \( \alpha_0,\ldots, \alpha_m \) que defina a una fórmula \( \phi=\alpha_m \) y demuestra por inducción que \( \alpha_i\in \bar \Gamma_{n+i} \), donde \( n \) es el máximo natural tal que \( p_n \) aparece en la sucesión.

08 Febrero, 2013, 06:34 pm
Respuesta #10

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Considera una sucesión \( \alpha_0,\ldots, \alpha_m \) que defina a una fórmula \( \phi=\alpha_m \) y demuestra por inducción que \( \alpha_i\in \bar \Gamma_{n+i} \), donde \( n \) es el máximo natural tal que \( p_n \) aparece en la sucesión.

Gracias. Queda "concluido" este hilo  :laugh:.

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

09 Febrero, 2013, 12:51 am
Respuesta #11

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Al momento de pasar en limpio el ejercicio, me doy cuenta de que algo que dije está mal así que me rectifico en este post.

(...), en 3) ahora sí vale la fórmula que yo había dado de \( |\overline{\Gamma}_{n+1}|=(|\overline{\Gamma}_{n}|+1)+4(|\overline{\Gamma}_{n}|+1)^2+(|\overline{\Gamma}_{n}|+1) \)

\( \left\{\begin{array}{ll}
\overline{\Gamma}_0=\{\bot,p_0\}\\
\\
\displaystyle \overline{\Gamma}_{n+1}=\Big(\overline{\Gamma}_n\cup\{p_{n+1}\}\Big)\cup\Big(\bigcup_{\varphi,\psi\in \overline{\Gamma}_n\cup\{p_{n+1}\}}\{(\varphi\square\psi)\}\Big)\cup\Big(\bigcup_{\varphi\in \overline{\Gamma}_n\cup\{p_{n+1}\}}\{(\lnot\varphi)\}\Big)
\end{array}\right. \)

Ciertamente,

\( \displaystyle\overline{\Gamma}_n\cup\{p_{n+1}\} \)

tiene \( |\overline{\Gamma}_n|+1 \) elementos,

\( \displaystyle\bigcup_{\varphi,\psi\in \overline{\Gamma}_n\cup\{p_{n+1}\}}\{(\varphi\square\psi)\} \)

tiene cardinal \( (|\Gamma_n|+1)^2 \) y

\( \displaystyle \bigcup_{\varphi\in \overline{\Gamma}_n\cup\{p_{n+1}\}}\{(\lnot\varphi)\} \)

\( |\overline{\Gamma}_n|+1 \). Pero en general, si \( n\geq 2 \) estos tres conjuntos no son disjuntos por lo cual, en realidad lo que vale para todo \( n \) es:

\( |\overline{\Gamma}_{n+1}|\leq (|\overline{\Gamma}_{n}|+1)+4(|\overline{\Gamma}_{n}|+1)^2+(|\overline{\Gamma}_{n}|+1) \)

Esta desigualdad también sirve para probar la finitud de los \( \Gamma_n \) (en el paso inductivo no es necesario conocer explicítamente el número de elementos de \( \overline{\Gamma}_{n+1} \) en términos del número de elementos de \( \overline{\Gamma}_n \), sino que basta con hallar una cota superior).

Estuve pensando un rato en otra expresión para la cual sí se tenga la igualdad, pero no veo nada claro (de todas maneras, no es necesario para nuestro propósito).

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

09 Febrero, 2013, 12:58 am
Respuesta #12

Carlos Ivorra

  • Administrador
  • Mensajes: 9,075
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pues tienes razón. ¡Estamos finos hoy!   ::)

09 Febrero, 2013, 04:35 pm
Respuesta #13

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Estuve pensando un rato en otra expresión para la cual sí se tenga la igualdad, pero no veo nada claro (de todas maneras, no es necesario para nuestro propósito).

Acaba de ocurrírseme lo siguiente (por si a alguien llegara a interesarle). Redefinimos los \( \overline{\Gamma}_n \) así:

\( \left\{\begin{array}{ll}
\overline{\Gamma}_0=\{\bot,p_0\}\\
\\
\displaystyle \overline{\Gamma}_1=\{\bot,p_0,p_1\}\cup\Big(\bigcup_{\varphi,\psi\in \{\bot,p_0,p_1\}}\{(\varphi\square\psi)\}\Big)\cup \{(\lnot \bot),(\lnot p_0),(\lnot p_1)\}\\
\\
\displaystyle \overline{\Gamma}_{n+2}=\Big(\overline{\Gamma}_{n+1}\cup\{p_{n+2}\}\Big)\cup\Big(\bigcup_{\varphi,\psi\in \overline{\Gamma}_{n+1}\cup\{p_{n+2}\}}\{(\varphi\square\psi)\}\;\setminus\;\bigcup_{\varphi,\psi\in \overline{\Gamma}_n}\{(\varphi\square\psi)\}\Big)\cup\Big(\bigcup_{\varphi\in \overline{\Gamma}_{n+1}\setminus\overline{\Gamma}_n\cup\{p_{n+2}\}}\{(\lnot\varphi)\}\Big)
\end{array}\right. \)

Ahora sí creo que la unión es disjunta, y se tendría que:

\( \\
|\overline{\Gamma}_0|=2\\
|\overline{\Gamma}_1|=3+4\cdot 3^2+3=42\\
|\overline{\Gamma}_{n+2}|=(|\overline{\Gamma}_{n+1}|+1)+4(|\overline{\Gamma}_{n+1}|+1)^2-4|\overline{\Gamma}_n|^2+(|\overline{\Gamma}_{n+1}|-|\overline{\Gamma}_n|+1)
 \)
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print