This entire issue is somewhat similar to the distinction between proof by contrapositive and proof by contradiction, which I wrote about at http://math.stackexchange.com/a/705291/630https://math.stackexchange.com/a/705291/630
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
This entire issue is somewhat similar to the distinction between proof by contrapositive and proof by contradiction, which I wrote about at http://math.stackexchange.com/a/705291/630
This entire issue is somewhat similar to the distinction between proof by contrapositive and proof by contradiction, which I wrote about at https://math.stackexchange.com/a/705291/630
In constructive mathematics, they often redefine concepts that have "negative" definitions in ordinary mathematics. In particular, they would usually define "$X$ is infinite" to mean there is an infinite sequence of distinct members of $X$. This is a stronger statement, in a constructive setting, than "$X$ is not finite". In that setting, although proof 3 shows them that the set of primes is not finite, it does not show them that the set of primes is infinite. But the original direct proof (proof 12) does show them this, because proof 12 is also constructively valid (with appropriate axioms for number theory).
In constructive mathematics, they often redefine concepts that have "negative" definitions in ordinary mathematics. In particular, they would usually define "$X$ is infinite" to mean there is an infinite sequence of distinct members of $X$. This is a stronger statement, in a constructive setting, than "$X$ is not finite". In that setting, although proof 3 shows them that the set of primes is not finite, it does not show them that the set of primes is infinite. But the original direct proof (proof 1) does show them this, because proof 1 is also constructively valid (with appropriate axioms for number theory).
In constructive mathematics, they often redefine concepts that have "negative" definitions in ordinary mathematics. In particular, they would usually define "$X$ is infinite" to mean there is an infinite sequence of distinct members of $X$. This is a stronger statement, in a constructive setting, than "$X$ is not finite". In that setting, although proof 3 shows them that the set of primes is not finite, it does not show them that the set of primes is infinite. But the original direct proof (proof 2) does show them this, because proof 2 is also constructively valid (with appropriate axioms for number theory).
Proof 2 We inductively construct a sequence $p_1, p_2, \ldots$ of distinct primes. To start, let $p_1 = 2$. Now, for the "inductive set"step", assume we have constructed distinct primes $p_1, \ldots, p_n$. Form the number $q=p_1p_2\cdots p_n+1$. This number $q$ is greater than 1, so it must be divisible by some prime $p$. But the remainder of dividing $q$ by $p_i$ for any $i\leq n$ is 1, so $p$ cannot equal $p_i$ for any $i \leq n$. Thus we can take $p_{n+1} = p$. Continuing in this way, we can construct an infinite sequence $p_1, p_2, \ldots$ of distinct primes. In particular, this shows that there are infinitely many primes.
In constructive mathematics, they often redefine concepts that have "negative" definitions in ordinary mathematics. In particular, they would usually define "$X$ is infinite" to mean there is an infinite sequence of distinct members of $X$. This is a stronger statement, in a constructive setting, than "$X$ is not finite". In that setting, although proof 3 shows them that the set of primes is not finite, it does not show them that the set of primes is infinite. But the original direct proof (proof 1) does show them this, because the direct proof I wrote1 is also constructively valid (with appropriate axioms for number theory).
The fact that the proof is constructively valid is closely related to the fact that it gives an algorithm for enumerating an infinite set of primes. Even for mathematicians who are unworried about constructive math, that algorithm is likely to be of interest. A key intuition from logic is that these two topics (constructive provability and algorithms) are closely intertwined.
Proof 2 We inductively construct a sequence $p_1, p_2, \ldots$ of distinct primes. To start, let $p_1 = 2$. Now, for the "inductive set", assume we have constructed distinct primes $p_1, \ldots, p_n$. Form the number $q=p_1p_2\cdots p_n+1$. This number $q$ is greater than 1, so it must be divisible by some prime $p$. But the remainder of dividing $q$ by $p_i$ for any $i\leq n$ is 1, so $p$ cannot equal $p_i$ for any $i \leq n$. Thus we can take $p_{n+1} = p$. Continuing in this way, we can construct an infinite sequence $p_1, p_2, \ldots$ of distinct primes. In particular, this shows that there are infinitely many primes.
In constructive mathematics, they often redefine concepts that have "negative" definitions in ordinary mathematics. In particular, they would usually define "$X$ is infinite" to mean there is an infinite sequence of distinct members of $X$. This is a stronger statement, in a constructive setting, than "$X$ is not finite". In that setting, although proof 3 shows them that the set of primes is not finite, it does not show them that the set of primes is infinite. But the direct proof does show them this, because the direct proof I wrote is also constructively valid (with appropriate axioms for number theory).
The fact that the proof is constructively valid is closely related to the fact that it gives an algorithm for enumerating an infinite set of primes. Even for mathematicians who are unworried about constructive math, that algorithm is likely to be of interest.
Proof 2 We inductively construct a sequence $p_1, p_2, \ldots$ of distinct primes. To start, let $p_1 = 2$. Now, for the "inductive step", assume we have constructed distinct primes $p_1, \ldots, p_n$. Form the number $q=p_1p_2\cdots p_n+1$. This number $q$ is greater than 1, so it must be divisible by some prime $p$. But the remainder of dividing $q$ by $p_i$ for any $i\leq n$ is 1, so $p$ cannot equal $p_i$ for any $i \leq n$. Thus we can take $p_{n+1} = p$. Continuing in this way, we can construct an infinite sequence $p_1, p_2, \ldots$ of distinct primes. In particular, this shows that there are infinitely many primes.
In constructive mathematics, they often redefine concepts that have "negative" definitions in ordinary mathematics. In particular, they would usually define "$X$ is infinite" to mean there is an infinite sequence of distinct members of $X$. This is a stronger statement, in a constructive setting, than "$X$ is not finite". In that setting, although proof 3 shows them that the set of primes is not finite, it does not show them that the set of primes is infinite. But the original direct proof (proof 1) does show them this, because proof 1 is also constructively valid (with appropriate axioms for number theory).
The fact that the proof is constructively valid is closely related to the fact that it gives an algorithm for enumerating an infinite set of primes. Even for mathematicians who are unworried about constructive math, that algorithm is likely to be of interest. A key intuition from logic is that these two topics (constructive provability and algorithms) are closely intertwined.
Loading