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

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

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

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • 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,447
  • 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: 11,956
  • 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,447
  • 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