Declaraciones de bicondicional con una dirección "fácil".

Question

Estaba leyendo a través de Lax del Análisis Funcional, cuando me topé con la siguiente declaración:

Teorema: X es una normativa espacio lineal sobre $\mathbb{R}$, $M$ un subconjunto acotado de $X$. Un punto de $z$ $X$ pertenece a la cerrada, convex hull $\breve{M}$ $M$ fib para todos los $l$ en $X'$, $$l(z) \leq S_M(l).$$

No tengo una pregunta acerca de este teorema, pero me gustaría usar como un ejemplo. Su prueba, al igual que muchos "si y sólo si" pruebas tiene una dirección (hacia adelante uno en este caso) que es bastante trivial y que es difícil. Esto se refleja en la longitud de las dos partes de Lax de la prueba. Estoy seguro de que hay mucho mejores ejemplos de esto.

Después de la lectura de este teorema, me acordé de un profesor que tuve no hace mucho tiempo que hizo una gran cosa acerca de estos asimétrica de las pruebas. Recuerdo que él nos preguntó, "Si dos estados son equivalentes, ¿por qué no debería ser igual de fácil para probar uno de los otros?" Él admitió que él no tenía una respuesta real, pero sugirió que tenía que ver con la psicología humana. Otras personas que he hablado han afirmado que, para algunos un gran genio, ambas direcciones sería de igual dificultad.

Mis preguntas son estas:

1. Esto es realmente un fenómeno interesante?
2. Si es así, ¿hay alguna forma de estado es menos "suave?"
3. ¿Tienes algún favorito entre los ejemplos de estos teoremas?
4. ¿Por qué es una dirección más fácil en estos casos?

Gracias y espero que esto no es demasiado vaga.

Answer 1

Yo no paso a lo esotérico o nivel psicológico aquí. Permítanme presentarles un ejemplo sencillo de dos, obviamente, equivalente declaraciones: $\forall x Rx$ mantiene si y sólo si $(\exists x Px \lor \forall x\neg Px)\rightarrow \forall x Rx$, por lo que $$\forall x Rx \leftrightarrow((\exists x Px \lor \forall x\neg Px)\rightarrow \forall x Rx)$$ es una tautología. Pero a ver qué pasa si queremos probar las dos direcciones en un secuente cálculo:

Dirección "$\rightarrow$"

Dirección "$\leftarrow$"

La esencia de la ejemplo: Sólo porque dos fórmulas de $\varphi$ $\psi$ son equivalentes, esto no significa que las pruebas de la lógica de verdad, pero de lo contrario, potencialmente sustancialmente diferentes fórmulas de $\varphi\rightarrow\psi$ $\psi\rightarrow\varphi$ son igual de duro. En el ejemplo, hemos tenido que en realidad la prueba de la premisa $\exists x Px \lor \forall x\neg Px$ "$\leftarrow$ " de la dirección, mientras que se podría tratar en el "$\rightarrow$" dirección como una caja negra.

También: La lógica de la equivalencia de las dos fórmulas no nos dice nada acerca de la complejidad de sus respectivas pruebas! Esta no es la psicología humana, sólo de cuestiones técnicas. Y un genio, probablemente se vería en las fórmulas y el estado: "oye, pero el segundo es más complejo que la prueba" ;)

Comentario: yo a usted no se siente cómodo con el secuente cálculo, respecto de la siguiente manera: En la izquierda-a-derecha dirección, usted puede aprovechar el hecho de que $\varphi\rightarrow(\psi\rightarrow\varphi)$ es siempre verdadera (proposicional tautología), independientemente de la verdad de $\psi$. Para $(\psi\rightarrow\varphi)\rightarrow\varphi$, usted tiene que demostrar $\psi$ en primer lugar, porque sólo entonces esto se convierte lógicamente verdaderas. Todo esto no es afectado por el hecho de que las fórmulas de los ejemplos de arriba son equivalentes, y que ambas direcciones son por lo tanto demostrable. Provability y la complejidad de las pruebas, son dos cosas diferentes.

Edit: Ahora específicamente para abordar sus preguntas -

1. Esto es realmente un fenómeno interesante?

Yo iba a votar por sí -, sino de la prueba de la teoría de la "técnica" punto de vista de un filosófica.

1. Si es así, ¿hay alguna forma de estado es menos "suave?"

Bien, usted podría frase hacia una investigación de las longitudes de las más cortas pruebas (en un sistema formal) para las dos direcciones de un bi-implicación.

1. ¿Tienes algún favorito entre los ejemplos de estos teoremas?

Uno de mis favoritos es la solidez y la integridad de una prueba formal del sistema para la lógica de primer orden: Un teorema es lógicamente verdadera si y sólo si es demostrable en el sistema.

1. ¿Por qué es una dirección más fácil en estos casos?

El "$\leftarrow$" dirección (solidez) es la más fácil, sólo tienes que hacer una inducción estructural sobre el cálculo. El "$\rightarrow$" dirección ((fuerte) integridad) es el complicado (y más interesante) uno; hechos interesantes como el teorema de compacidad seguir a partir de la existencia de tales completa de los sistemas de prueba.

Answer 2

Creo que muchos de los teoremas podría ser presentado de tal manera como para cumplir los requisitos, por ejemplo, $x^n+y^n=z^n$ tiene una solución en los enteros positivos si y sólo si $n\le2$; la de Riemann zeta función tiene un número infinito de ceros con parte real $s$ si y sólo si $s=1/2$ (OK, el "sólo si" la parte no puede ser un teorema todavía); hay una esporádica simple grupo de orden $n$ si y sólo si $n$ está en la lista siguiente [inserte aquí la lista de los pedidos de los esporádicos simple grupos], y así sucesivamente. Un ejemplo interesante es el del Ayuntamiento de Matrimonio Teorema, que le da una condición necesaria y suficiente para la existencia de ciertos emparejamientos. La "necesaria" la parte es trivial, el "suficiente" parte toma un poco de trabajo.