Infinitude of primes
From Automated Assistance for Formal Reasoning
We want to show that there are infinitely many primes. We will argue this by assuming the opposite and deriving a contradiction.
[edit] Argument
We introduce a finite set
of all primes, and its product
.
Introduce
.
Assume for all
, if
is prime then
.
Assume
is a finite set,
is non-empty, and
.
Assume
.
The above notation for the product of a subset of
has equivalent alternatives.
Assert
.
Assert
.
We now demonstrate that the above assumptions allow us to derive a contradiction.
Assert
.
Assert for any
,
- if
is a prime factor of
then
is not a factor of
,
is prime,
,
is a factor of
,
- there is a contradiction.