Pruebas usando tautologías

Digamos que quiero probar formalmente una declaración de la forma

pag q
Así que hago un poco de trabajo, algo de reorganización y, finalmente, llego a una declaración de la forma
pag pag
lo cual es una tautología, ya que esto es cierto para todos los valores de pag , pero también una verdad evidente. ¿He probado pag q ?


Alcanzando "Verdades Obvias"

En general, cuando se hacen pruebas, llegar a algo que es obviamente cierto "no es una prueba. Por ejemplo, si está demostrando que 2 es irracional, llegando 1 = 1 no ha probado nada. Pero en este caso he llegado a una tautología, ¿eso hace verdadera mi implicación original?

A mí esto me parece una contradicción, porque la tautología a la que he llegado es una verdad obvia, que es un gran "no-no" en la validación de pruebas.


Además, la convención de que llegar a algo como una "verdad obvia" no es una forma matemáticamente rigurosa de completar una demostración, ¿se extiende a todas las técnicas de demostración?

Por ejemplo, alcanzar una "verdad obvia" todavía no constituye una prueba para las siguientes técnicas de prueba:

  1. Pruebas directas
  2. Pruebas Indirectas (Pruebas por Contrapositiva)
  3. Prueba por contradicción
  4. Demostración por Inducción Matemática
  5. Pruebas Vacuas
  6. Pruebas triviales
  7. Prueba por casos

Última pregunta, en el ejemplo que he dado anteriormente, parece que comencé tratando de probar directamente pag q , pero cuando he llegado pag pag , ahora es una Prueba Trivial, ¿bajo cuál caería el ejemplo de prueba anterior que he dado? ¿Prueba directa o prueba trivial?


Algún contexto de fondo si es necesario:

Hice esta pregunta en respuesta a una pregunta anterior que hice, en el ϵ d definición de un límite, donde trato de probar un enunciado de la forma pag q al reducirlo a la forma pag pag , y sostengo que no es matemáticamente riguroso, ya que llegué a una verdad obvia, sin embargo, otro usuario argumenta que he probado formalmente lo que me propuse probar ya que llegué a una tautología, manipulando la implicación original: https: / /math.stackexchange.com/a/1745657/266135

Otra pregunta extremadamente relevante para llegar a "verdades obvias": ¿Es incorrecta esta prueba directa de una desigualdad?

Depende de como lo manipule pag q . si empiezas con pag q y llegar a pag pag , entonces eso podría no ser una prueba válida porque has mostrado ( pag q ) ( pag pag ) que no es lo mismo que ( pag pag ) ( pag q ) . Sin embargo, si usa solo equivalencias lógicas para obtener de pag q a pag pag , entonces has mostrado ( pag q ) ( pag pag ) lo que prueba que pag q es verdadero ya que es lógicamente equivalente a una declaración verdadera.
@NobleMushtak ¿Por qué no expandir su comentario en una respuesta, ya que esencialmente responde a la pregunta central de OP?
@Travis Lo haré, pero llevará un tiempo porque voy a volver a escribir las pruebas de ejemplo que dio. Hagen von Eitzen básicamente ya reescribió mi comentario.

Respuestas (2)

"Alcanzar una verdad obvia" (como pag pag Ro 1 = 1 ) es un método de prueba válido si los pasos utilizados para llegar a esta verdad obvia son transformadas de equivalencia. Es decir, si su argumento es como

A 1 es equivalente a A 2 , que es equivalente a A 3 , , que es equivalente a A norte , que es una tautología

entonces has probado A 1 . Sin embargo, debe tener cuidado de que ni un solo paso "es equivalente" resulte ser solo un paso "implica". Por otro lado, ni siquiera necesitamos la equivalencia, solo necesitamos una dirección: la inversa. Por lo tanto, a menudo es mejor escribir una prueba en la otra dirección:

Tenemos la tautología A norte . Esto implica A norte 1 . Esto implica A 3 . Esto implica A 2 . Esto implica A 1 , como se desee.

El de A 1 a A norte El método puede ser el más adecuado para descubrir una prueba, pero "a partir de A norte a A 1 " (que luego puede ser una prueba directa) es más adecuado para presentar una prueba (y al mismo tiempo para descubrir lagunas en la prueba porque se vuelve más fácil detectar pasos que no son equivalencias).

Además, esto se relaciona con la prueba directa de la desigualdad porque si miras la prueba, todos los pasos son correctos, pero la prueba está escrita al revés. Debería haber comenzado con 2 norte > norte y luego terminó con norte norte + 1 > norte norte + 2 .
@NobleMushtak En realidad, la prueba de desigualdad a la que se hace referencia es solo una secuencia de declaraciones no relacionadas " A 1 , A 2 , , A norte " sin ningún conector. Si hubiera habido algún conector (válido) como " " o "que es equivalente a lo siguiente al multiplicar ambos lados con el número positivo norte + 1 " o similar, habría sido una prueba y no solo una lista de afirmaciones aparentemente no relacionadas que no difieren estructuralmente de " norte norte + 1 > norte norte + 2 , me encanta el pastel de arándanos, 2 norte > norte "
Bueno, si hubiera escrito la prueba al revés y luego escrito el razonamiento detrás de todos sus pasos, su razonamiento habría sido correcto.
@NobleMushtak De hecho. " A 1 , A 2 "es mucho peor que" A 2 implica A 1 ", y lo mejor sería" A 2 implica A 1 porque ..."
@HagenvonEitzen Está bien, dado A k ( A i = A j = A norte = A k ) , ¿Sería eso una prueba?
@Perturbativo Si A i es cierto, entonces simplemente A i = A j = A norte = A k bastaría.
@HagenvonEitzen esencialmente estoy tratando de profundizar en la lógica detrás ϵ d pruebas Este artículo aquí: bobobobo.wordpress.com/2008/01/20/… lógicamente está haciendo exactamente lo que he explicado anteriormente comenzando con A k A metro , "elegir" un valor para A metro y comprobando si el valor elegido satisface A k A metro , reduciendo A k A metro a A k A k , ¿es eso matemáticamente riguroso?
@Perturbative No, su prueba también está al revés, pero su razonamiento es correcto. Lo estoy reescribiendo en mi respuesta ahora mismo.

Cuando está explorando y descubriendo cómo probar una declaración, quiere explorar tratando de reducir la conclusión a una declaración de la hipótesis. De esa manera, puedes ver cómo la conclusión se relaciona con la hipótesis y, a partir de esa conexión, escribir tu prueba.

Sin embargo, cuando estás escribiendo tu prueba, siempre comienzas desde la hipótesis hasta la conclusión. Eso tiene sentido: no puede asumir su conclusión y probar la hipótesis porque eso es simplemente al revés. El ϵ d artículo que leyó de hecho tenía un razonamiento correcto de por qué el límite era verdadero y entendió el significado de la ϵ d límite, pero no tenía una prueba real. Simplemente mostró que la declaración era verdadera al mostrar la conexión entre la hipótesis y la conclusión. En realidad, no probó cómo la hipótesis implica la conclusión, por lo que no fue una prueba real. Sin embargo, dada esta conexión, podemos crear nuestra propia prueba directa:

Para cualquier ϵ > 0 . Podemos elegir d = ϵ 3 tal que si 0 < | X 5 | < d , entonces | F ( X ) 3 | < ϵ . Ahora probaremos esto directamente. Empezamos con nuestra hipótesis:

0 < | X 5 | < ϵ 3

Esto es en realidad una instrucción AND: 0 < | X 5 | y | X 5 | < ϵ 3 . Sin embargo, realmente no necesitamos la primera declaración ya que F ( X ) todavía se define en X = 5 , así que podemos usar el segundo.

| X 5 | < ϵ 3

Multiplica ambos lados por 3 .

| 3 X 15 | < ϵ

3 X 15 = 3 X 3 12 = F ( X ) 3 , así que sustituye:

| F ( X ) 12 | < ϵ

Así, hemos demostrado que 0 < | X 5 | < ϵ 3 implica | F ( X ) 12 | < ϵ para todos ϵ > 0 , lo que significa que hemos probado el límite.


Fíjate cómo usamos las mismas ecuaciones y razonamientos que en el artículo, pero lo escribimos al revés. Podemos hacer lo mismo con la demostración de la desigualdad :

Empezamos con una verdad evidente:

2 > 1

Desde norte es positivo, podemos multiplicar ambos lados por norte :

2 norte > norte

Añadir ambos lados por norte 2 :

norte 2 + 2 norte > norte 2 + norte

Factoriza el lado izquierdo y multiplica el lado derecho por 1 = norte + 2 norte + 2 :

norte ( norte + 2 ) > ( norte 2 + norte ) ( norte + 2 ) norte + 2

Desde norte es positivo, también lo es norte + 2 , entonces podemos dividir ambos lados por norte + 2 :

norte > norte 2 + norte norte + 2

Multiplica el lado izquierdo por 1 = norte + 1 norte + 1 y factorizamos el lado derecho:

norte ( norte + 1 ) norte + 1 > norte ( norte + 1 ) norte + 2

Divide ambos lados por norte + 1 :

norte norte + 1 > norte norte + 2

Así, hemos mostrado norte norte + 1 > norte norte + 2 usando enunciados obvios, la hipótesis de norte > 0 , y las leyes de manipulación de desigualdades, por lo que debe ser cierto.

Observe cómo tengo las mismas desigualdades que la primera prueba, pero están escritas en el orden opuesto y he agregado mi razonamiento entre cada paso. La primera prueba simplemente muestra que la declaración es verdadera al llevarnos a la conexión, pero la prueba anterior es una prueba real, rigurosa y directa.