¿Cómo podría demostrarlo un intuicionista?

Question

Mi pregunta se refiere a la prueba de lo siguiente: Sea $a,b,n \in \mathbb{N}$ . Si $n \neq 1$ y $n$ divide ambos $a$ y $b$ entonces $b$ es un número compuesto o $b$ divide $a$ . Mi prueba:

Supongamos que $b$ no es compuesto. Entonces $b$ es primo. Como $n \neq 1$ y $n$ divide $b$ Debemos tener $n = b$ . Así, $b$ divide $a$ .

Esta prueba tiene la forma $(P \wedge \neg R) \to Q$ . Si utilizáramos la lógica normal de primer orden, podría concluir $P \to (Q \vee R)$ . Pero, utilizando la lógica intuicionista, no puedo concluir lo que había que demostrar. ¿Cómo llevarías a cabo esta prueba en lógica intuicionista?

Answer 1

En general, cuando se trabaja en matemáticas constructivas, la estrategia para demostrar $Q \lor R$ es demostrar $Q$ o para demostrar $R$ . En este caso, el mero hecho de saber de forma abstracta que "hay un $n \not = 1$ que divide a ambos $a$ y $b$ " no le dice directamente si $b$ es compuesto o si $b$ divide $a$ . Por lo tanto, necesitará más información para llegar a una prueba constructiva.

Si sabes más que el hecho de que hay es tal $n$ y realmente conoces el valor de $n$ Eso ayudaría. En particular, si pudiera decir si su valor de $n$ es igual a $b$ entonces se puede saber qué lado de la disyunción se mantiene. Así que podríamos utilizar el hecho $(\forall k)[k = b \lor k \not = b]$ para terminar la prueba constructiva.

Muchos sistemas constructivos del mundo real incluyen hechos adicionales como el de los números naturales, que no serían ciertos para otros objetos. En particular, muchos sistemas constructivos demuestran la sentencia $(\forall n,m \in \mathbb{N})[n = m \lor n \not = m]$ que dice que los números naturales tienen igualdad decidible. La motivación para aceptar esto en los sistemas constructivos es que, dados dos (términos para) números naturales concretos, podríamos en principio examinarlos para ver si son iguales. Este no es el caso de otros objetos, como los números reales, para los que la igualdad no es decidible. El hecho de que la igualdad de los números naturales sea decidible es demostrable, en muchos sistemas de matemática constructiva, a partir de axiomas de inducción que ya están incluidos.

Con un poco de trabajo, estos sistemas constructivos demuestran que cada número natural es compuesto o no compuesto. Y, con ese hecho extra, el resto de la prueba original se realiza constructivamente. Esto puede estar fuera del alcance de una clase de introducción a las pruebas, pero es una forma en que un constructivista podría demostrar el resultado.

Answer 2

Para añadir algunos detalles a la respuesta de Carl...

Asumiendo que su sistema incluye la inducción completa, su sistema puede probar que cualquier fórmula aritmética acotada es decidible (es decir, $P \lor \lnot P$ es demostrable para estos). Las fórmulas aritméticas acotadas son las que se construyen a partir de fórmulas atómicas ( $s = t$ y $s \leq t$ para los términos $s,t$ ) utilizando conectivos lógicos ( ${\land},{\lor},{\to},{\lnot}$ ) y cuantificadores limitados $\forall x \leq t\ldots$ y $\exists x \leq t\ldots$ donde $t$ es un término aritmético en el que el símbolo variable $x$ no se produce. La prueba de que tales fórmulas son decidibles se basa en el hecho de que, suponiendo $\forall x(P(x) \lor \lnot P(x))$ se puede demostrar por inducción en $y$ que $\forall x \leq y P(x)$ y $\exists x \leq y P(x)$ también son decidibles.

Estas fórmulas incluyen muchas nociones aritméticas elementales en (esencialmente) sus formas naturales: $$\begin{aligned} x \mid y \quad&\equiv\quad \exists z \leq y(xz = y)\\ \operatorname{Prime}(x) \quad&\equiv\quad x\geq 2 \land \forall y \leq x\forall z \leq x(yz = x \to y = x \lor z = x)\\ \operatorname{Composite}(x) \quad&\equiv\quad \exists y \leq x(y \neq 1 \land y \neq x \land y \mid x) \end{aligned}$$

Aunque $\lnot P \to Q$ no implica $P \lor Q$ intuitivamente, la hipótesis adicional de que $P$ es decidible ( $P \lor \lnot P$ ) nos permite llegar a esta conclusión utilizando únicamente un razonamiento intuitivo. Suponiendo que $P$ inmediatamente derivamos $P \lor Q$ . Suponiendo que $\lnot P$ y $\lnot P \to Q$ concluimos que $Q$ y por lo tanto $P \lor Q$ . Así, $$(P \lor \lnot P) \to (\lnot P \to Q) \to (P \lor Q)$$ es intuitivamente válida. Por lo tanto, el $(\lnot P \to Q) \to (P \lor Q)$ es demostrable intuitivamente siempre que $P$ es un enunciado aritmético acotado.

Answer 3

La pregunta era sobre el intuicionismo específicamente, no sobre alguna variante del constructivismo, ni sobre alguna formalización particular del intuicionismo (no creo que un intuicionista reconozca ninguna formalización particular como completa o incluso significativa).

Su declaración no es de la forma $$P \to (Q \vee R).$$ Es de la forma $$(\forall n)\Big(P(n) \to \big(Q(n) \vee R(n)\big)\Big).$$ (La cuantificación aquí es sobre números naturales).

Para demostrar esto intuitivamente, no necesitamos necesariamente una prueba de $(\forall n)(P(n) \to Q(n))$ o una prueba de $(\forall n)(P(n) \to R(n)).$ Lo que necesitamos es una forma constructiva de encontrar, para cada número natural $n,$ ya sea una prueba para ese específico $n$ de $P(\underline{n}) \to Q(\underline{n})$ o una prueba para ese específico $n$ de $P(\underline{n}) \to R(\underline{n}),$ donde $\underline{n}$ es el número que representa $n.$

En general, para demostrar intuitivamente que $(\forall n)S(n),$ necesitamos una forma constructiva de encontrar, para cada número natural $n,$ una prueba de $S(\underline{n})$ para ese específico $n.$

En su ejemplo, está claro que uno puede determinar intuitivamente si $b$ es compuesto o primo (basta con comprobar todos los factores posibles entre $2$ y $b-1\text{)}.$ Si $b$ es compuesto, tenemos inmediatamente una prueba de que " $b$ es compuesto o $(b \mid a)\text{."}$ Si $b$ es primo, entonces como se nos da que $n\ne 1\,\wedge\,(n\mid a)\,\wedge\,(n\mid b),$ podemos concluir que $n=b,$ así que $b\mid a,$ y de nuevo tenemos una prueba de $\text{"}b$ es compuesto o $(b \mid a)\text{."}$

Así que tenemos un método intuitivamente aceptable, dado cualquier $a, b, \text{ and }n$ tal que $n\ne 1$ y $n$ divide ambos $a$ y $b$ de encontrar una prueba de que $"\!\underline{b}$ es un número compuesto o $\underline{b}$ divide $\underline{a}\!",$ que es exactamente lo que se necesita.

Ahora, hay ultrafinistas que podrían discutir el hecho de que cada número natural $\gt 1$ es primo o compuesto, pero los intuicionistas no tendrían ningún problema con esa afirmación.

Answer 4

Preguntas cómo un matemático constructivo demostraría el teorema. Tal y como lo has hecho tú. Sólo tenemos que comprobar que cada número es compuesto o primo, ver más abajo. Pero Carl Mummert dio la "prueba del libro", que es constructiva:

Teorema: Si $n \neq 1$ y $n$ divide ambos $a$ y $b$ entonces $b$ es compuesto o $b$ divide $a$ .

Prueba constructiva (Carl Mummert). O bien $n = b$ o $n \neq b$ . Si $n = b$ entonces $b$ divide $a$ . Si $n \neq b$ entonces $b$ tiene un divisor no trivial y es compuesto. QED.

---

Aquí está su prueba, elaborada con un poco más de detalle.

Prueba constructiva. Si $n$ no es compuesto, entonces es primo por el siguiente lema. Porque $n$ divide $b$ se deduce que $b = n$ Por lo tanto $b$ divide $a$ . QED.

Lema: Un número $n > 1$ es compuesto o primo. es compuesto iosr epirtihmeer. compuesto o primo.

Prueba constructiva. Tengamos cuidado con el significado de las palabras aquí. Por compuesto nos referimos a "un producto de dos números, cada uno de los cuales es diferente de $1$ ". Por prime nos referimos a "un número $p > 1$ cuyos únicos divisores son $1$ y $p$ ". Como todo número es divisible por $1$ y a sí mismo, la primalidad equivale a "un número $p > 1$ tal que no tiene ningún divisor entre $2$ y $p-1$ ."

Supongamos que $\phi$ es un predicado decidible sobre números naturales, es decir, tenemos $\forall k \in \mathbb{N} \,.\, \phi(k) \lor \lnot\phi(k)$ . Entonces también los predicados $\forall k \leq n \,.\, \phi(k)$ y $\exists k \leq n \,.\, \phi(k)$ son decidibles. (Ejercicio, demostrar por inducción en $n$ .) Usando esto podemos demostrar:

1. Dado $n$ y $k$ es decidible si $k$ divide $n$ .
2. Dado $n$ es decidible si hay $k$ tal que $2 \leq k < n$ y $k$ divide $n$ .

Pero la segunda afirmación dice que es decidible si $n$ es compuesto. Para terminar la prueba necesitamos demostrar que un número $n > 1$ que no es compuesto es primo. Supongamos que $n > 1$ no es compuesto. Considere cualquier $k$ tal que $2 < k < n$ . O bien $k$ divide $n$ o no lo hace. Pero no puede dividir $n$ o bien $n$ sería compuesto. Por lo tanto, $n$ es primo. QED.