Euclid proved that there are infinitely many primes. His proof doesn't exactly use induction but it is close. Rewrite the proof to use proof by induction.
let be an exhaustive list of prime numbers where k is an integer greater than 0
consider has cardinality k
Therefore but not in
by the PMI there are infinitely many prime numbers