¿Cuál es la definición formal preferida de "contraejemplo" como en: cero es un contraejemplo para "cada entero es positivo o negativo". ¿En qué parte de la literatura se define formalmente la noción de "contraejemplo"? ¿Y cuáles son los principales teoremas que involucran esta noción? ¿Y qué cuestiones relativas a ella permanecen abiertas?
Respuestas
¿Demasiados anuncios?
Oli
Puntos
89
Primero una broma: no sé qué es un contraejemplo, pero puedo reconocerlo cuando lo veo.
En un contexto de primer orden algo como lo siguiente comienza a capturar la noción. Dejemos que $T$ ser una teoría sobre el lenguaje $L$ . y dejar que $ \phi $ ser la sentencia $ \forall x_1 \dots\forall x_n \psi (x_1, \dots ,x_n)$ .
Luego un contraejemplo para $ \phi $ en el contexto $T$ es un modelo $M$ de $T$ y elementos $a_1, \dots ,a_n$ de $M$ de tal manera que $ \psi (a_1, \dots ,a_n)$ es falso en $M$ .
Una noción formal conexa es la de cuadros semánticos como se utiliza en los sistemas de deducción natural . Debido a su interés en la informática, hay una considerable literatura reciente.
Michael K Campbell
Puntos
260
Un contraejemplo es un caso especial de una reclamación general: un caso que muestra que la reclamación es falsa. Esto es en realidad sólo una cuestión de sentido común y lógica cotidiana que se aplica mucho más allá de las matemáticas. No suele considerarse como algo que necesite una definición formal. Una vez que se tiene un contraejemplo, se sabe que la afirmación general no es verdadera, y ese es el final.
user326210
Puntos
26
Se puede pensar en nuestro conocimiento de las matemáticas como dividido en (1) conocimiento sobre las matemáticas en sí mismas -teóricas de álgebra, análisis, teoría de números, topología, etc.- y (2) conocimiento sobre cómo hacer casos matemáticos-paradigmáticos, heurística para abordar un problema, contraejemplos, etc.
Los contraejemplos son parte de nuestro conocimiento de cómo hacer matemáticas. Si quisiera una definición formal, podría decir:
Si tienes una declaración como "Cada $X$ tiene la propiedad $P$ ", a contraejemplo porque la declaración es una $X$ que no tiene la propiedad $P$ .
Además, usted podría tener una buena razón para creer que cada $X$ tiene la propiedad $P$ :
- Si casi cada $X$ tiene la propiedad $P$ . Por ejemplo, "Cada número racional tiene un inverso multiplicador" es cierto en todos los casos excepto en el 0.
- Si antes estudiabas un caso especial en el que todo tenía la propiedad $P$ y ahora están estudiando un caso más general. Por ejemplo, "Cuadrar un número lo hace más grande" es cierto si sólo se miran los números naturales - pero si se extiende la vista a los números en $0<x<1$ la declaración es falsa.
- Si todos los ejemplos "prácticos" que has visto tienen la propiedad. Por ejemplo, "todas las funciones son continuas" no es ciertamente cierto. Pero si trabajas con problemas de cinemática práctica en física, puedes estar acostumbrado a que todas las funciones tengan esta propiedad.
Los contraejemplos son una de las formas más importantes de organizar nuestro conocimiento y agudizar nuestras intuiciones.
Ver también: Edwina Rissland escribió una disertación sobre la forma en que organizamos procedimentalmente nuestro conocimiento de cómo hacer matemáticas:
goblin
Puntos
21696
No sé si llamarías a esto una definición formal, pero un contraejemplo para $$ \forall (x \in X, y \in Y)P(x,y)$$ es básicamente una sustitución $(x:= x_0, y:= y_0)$ junto con una prueba de que $$(x:= x_0, y:= y_0) P(x,y) \rightarrow \bot. $$
Por cierto, podemos pensar en una sustitución como $(x:= x_0,y:= y_0)$ como si fuera un poco como una tupla ordenada, en este caso $(x_0,y_0)$ . La diferencia es que el "orden" se sustituye por un nombre para cada elemento individual; así que en este caso, $x_0$ está en el " $x$ "(en lugar de la primera posición) y $y_0$ está en el " $y$ "(en lugar de la segunda posición). Creo que los informáticos llaman a estas cosas registros que son vistos como elementos de "productos cartesianos con nombre" (alias "tipos de registro").
J Tim
Puntos
101
Para utilizar la prueba por contra-ejemplo, la declaración original tiene que ser de la forma
"Para todos los x, declaración $A_x$ es cierto". (1)
Así, mostrando que para algunos x, la declaración $A_x$ es falso, prueba que la declaración original es falsa. Una definición formal de un contra-ejemplo podría ser "un ejemplo que prueba que una declaración es falsa" o algo así. Esta es una forma rigurosa de prueba y no sé qué quiere decir con preguntas abiertas. Para algunos ejemplos, véase http://www.math.toronto.edu/writing/Counterexample.pdf .
También la siguiente técnica poof se denomina a veces contra-ejemplo:
- Tenemos que probar que la declaración S es verdadera
- Supongamos que S es falso
- Mostrar que esto lleva a algo que es falso
- Por lo tanto, S tiene que ser cierto
