¿Qué es un ejemplo de una prueba por contraejemplo mínimo?

Question

Estaba leyendo acerca de la prueba mediante el descenso infinito, y la prueba por un mínimo de contraejemplo. Mi comprensión es que asumimos la existencia de algunos de los más pequeños contraejemplo $A$ que refuta algunos proposición $P$, a continuación, vaya a mostrar que hay algunos de los más pequeños contraejemplo a esta que me parece como una mezcla de infinito descenso y la inversa de la prueba por contradicción'.

Mi pregunta es, ¿cómo podemos saber que podría haber algún contraejemplo? Además, hay ejemplos de esto?

Answer 1

Consideremos, por ejemplo, la declaración: todos los $n\in\mathbb{N}\setminus\{1\}$ se puede escribir como un producto de números primos (incluyendo el caso en el que hay un único número primo que aparecen sólo una vez). Supongamos lo contrario. Entonces habría un menor $n\in\mathbb{N}\setminus\{1\}$ que no sería posible la expresa como un producto de números primos. En particular, esto implica que $n$ no puede ser un número primo. Desde $n$ es también no $1$, puede ser escrito como $a\times b$, donde $a,b\in\{2,3,\ldots,n-1\}$. Pero, puesto que el $n$ es el más pequeño de contraejemplo, ni $a$ ni $b$ son contraejemplos y, por lo tanto, de ellos se puede escribir como un producto de números primos. Pero, a continuación, $n(=a\times b)$ puede ser escrita de tal manera demasiado.

Answer 2

Tal prueba con frecuencia va de la siguiente manera.

• Supongamos por contradicción que existe un contraejemplo a $P$ dentro de algunas conjunto ordenado $X$.
• Considerar la (ciertamente no vacío) conjunto de todos los $X$ cuales son contraejemplos a $P$. Este conjunto tiene al menos un elemento (que es lo que significa ser un bien de orden), así que...
• Considere el más pequeño contraejemplo.
• Demostrar que se puede encontrar una pequeña contraejemplo.
• La contradicción, por lo que no puede haber sido cualquier contraejemplos a $P$ , después de todo.
• Por lo tanto, $P$ es cierto.

Answer 3

Asumir la $\sqrt{2}$ es racional, entonces existen números enteros $(a,b)$ tal que $\sqrt{2}=a/b$ e $a$ es el número más pequeño con esta propiedad, pero entonces nos encontramos con que $a/2, b/2$ también son números enteros con esta propiedad. Así que hay un pequeño ejemplo.

Yo creo que esto debe ser el ejemplo a la gente son los más familiarizados con el y es una especie de infinito descenso pesar de que a menudo no se refieren a ella como tal.

Answer 4

Un ejemplo fundamental en la teoría de números es el descenso (Euclidiana) de la división con resto (o, equivalentemente, por la resta repetida), como en el siguiente resultado básico.

Lema $\ \ $ Deje $\,S\,$ ser un conjunto no vacío de enteros positivos que es cerrado bajo la resta $> 0,\,$ es decir, para todos los $ \,n,m\in S, \,$ $ \ n > m\ \Rightarrow\ n-m\, \in\, S.\,$ , a Continuación, al menos $ \:\ell\in S\,$ divide cada elemento de a$\, S.$

Prueba de ${\bf\ 1}\,\ $ Si no hay un mínimo de nonmultiple $ \,n\in S,\,$ contra $ \,n-\ell \in S\,$ es un nonmultiple de $ \,\ell.$

Prueba de ${\bf\ 2}\, \,\ \ S\,$ cerrado bajo la resta $ \,\Rightarrow\,S\,$ cerrado bajo resto (mod), cuando es $\ne 0,$ ya que el mod es simplemente resta repetida, es decir, $ \ a\bmod\ b\, =\, a - k b\, =\, a\!-\!b\!-\!b\!-\cdots\! -\!b.\,$ por lo Tanto $ \,n\in S\,$ $\Rightarrow$ $ \, (n\bmod \ell) = 0,\,$ otra cosa es en $\, S\,$ y menor que $ \,\ell,\,$ contra minimality de $ \,\ell.$

Comentario $\ $ , En pocas palabras, dos aplicaciones de la inducción producen los siguientes inferencias

$\begin{eqnarray}\rm S\ closed\ under\ {\bf subtraction} &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\ &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$

Este rendimientos de Bezout del MCD de identidad: el conjunto de $ \,S\,$ de los enteros de la forma $ \,a_1\,x_1 + \cdots + a_n x_n,\ x_i\in \mathbb Z,\,$ es cerrado bajo la resta tan Lema $\Rightarrow$ cada positivos $ \,k\in S\,$ es divisible por $ \,d = $ menos positivos $ \in S.\,$ por lo Tanto $ \,a_i\in S$ $\,\Rightarrow\,$ $ d\mid a_i,\,$ es decir $ \,d\,$ es un común divisor de todos los $ \,a_i,\,$ necesariamente el más grande , porque la $ \ c\mid a_i$ $\Rightarrow$ $ \,c\mid d = a_!\,x_1\!+\!\cdots\!+\!a_nx_n$ $\Rightarrow$ $ \,c\le d.\,$ Cuando se interpreta de manera constructiva, esto produce que el algoritmo de Euclides extendido por el mcd.