¿Se considera una prueba rigurosa que una propiedad no es cierto que un contraejemplo?

Question

Esta es mi pregunta de seguimiento a mi propia consulta anterior:

¿Cómo puedo algebraicamente demostrar que $2^n - 1$ no es siempre prime?

Casi la mitad de las respuestas dijo que me proporcionó mi propia prueba, dando el contraejemplo. Aunque, yo no estaba satisfecho a través de las respuestas a esas preguntas, ya que no proporcionan una visión completa de la situación y de cómo existen algebraicas factores.

Es refutar una afirmación algebraica necesariamente la misma que la introducción de un caso donde no es cierto? Estoy de acuerdo con el Nombre de la instrucción que se encuentra aquí, pero no estoy seguro de cómo contribuye a una rigurosa prueba algebraica.

Comentario: estoy de acuerdo en que no me pregunte por una prueba algebraica anterior, pero me hizo esperar un mejor prueba.

Answer 1

Las declaraciones que son relevantes aquí son llamados universal declaraciones (porque se relacionan con el cuantificador universal). Estas son las declaraciones de la forma "para todos los foos, declaración(foo) es verdadera." Muchas cosas se le pedirá demostrar en matemáticas son universales declaraciones, pero también estamos interesados en la no-universal declaraciones.

La negación de una declaración universal es un existencial de la declaración (porque se trata de un cuantificador existencial). Más precisamente, la negación de la declaración universal "para todos los foos, declaración(foo) es verdadera" es la declaración existencial "existe un foo tal que la declaración(foo) es falsa."

Refutar una declaración universal de los medios para demostrar su negación, que es una declaración existencial. Para probar una declaración existencial, es suficiente para dar un solo ejemplo. Esto es más o menos lo existencial declaración a los medios. Es decir, si quiero demostrar que existe un foo tal que la declaración(foo) es falso, todo lo que tengo que hacer es encontrar uno y se las muestro.

Answer 2

Sí, un solo contraejemplo es una prueba rigurosa que una afirmación es falsa. Uno a menudo puede decir más, por supuesto: es posible, por ejemplo, para exponer una clase entera de contraejemplos, o incluso para mostrar exactamente cuando la afirmación es verdadera y Cuándo es falso. Es posible demostrar que si las hipótesis se fortalecen ligeramente, el verdadero es afirmación. Pero para refutar la afirmación basta un contraejemplo.

Answer 3

Como una adición a las otras respuestas, quería señalar teoremas de la forma

Si $P(x)$, entonces el $Q(x)$

son afirmaciones universales generalmente implícitas del tipo "todos $x$, si $P(x)$, entonces el $Q(x)$".

Por lo tanto, para demostrar una implicación no es un teorema, basta para encontrar un contraejemplo: un solo objeto $x$ para que "si $P(x)$ y $Q(x)$" es no es cierto, que es equivalente a decir que "$P(x)$ es cierto pero $Q(x)$ es falso".

Answer 4

Generalmente las declaraciones de la forma "$2^n-1$ es siempre un primer" se traducen en «$\forall n\in\mathbb N: 2^n-1$ es una privilegiada».

Para mostrar que una declaración de la forma $\forall x\varphi(x)$ es falsa basta Mostrar un contraejemplo. Eso es que demostrar la negación de la declaración, que se traduce en $\exists x\lnot\varphi(x)$. Para demostrar que hay algún número con el % de propiedad $\lnot\varphi(x)$es bastante a uno que hace.