Theorem: C05S03.primes_infinite' (LeanCourse/MIL/C05_Elementary_Number_Theory/solutions/Solutions_S03_Infinitely_Many_Primes.lean)

State before:
⊢ ∀ (s : Finset ℕ), ∃ p, Nat.Prime p ∧ p ∉ s
Tactic:
intro s
State after:
s : Finset ℕ
⊢ ∃ p, Nat.Prime p ∧ p ∉ s

State before:
s : Finset ℕ
⊢ ∃ p, Nat.Prime p ∧ p ∉ s
Tactic:
by_contra h
State after:
s : Finset ℕ
h : ¬∃ p, Nat.Prime p ∧ p ∉ s
⊢ False

State before:
s : Finset ℕ
h : ¬∃ p, Nat.Prime p ∧ p ∉ s
⊢ False
Tactic:
push_neg  at h
State after:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
⊢ False

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
⊢ False
Tactic:
set s' := s.filter Nat.Prime with s'_def
State after:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
⊢ False

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
⊢ False
Tactic:
have mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ n.Prime := by
  intro n
  simp [s'_def]
  apply h
State after:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ False

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ False
Tactic:
have : 2 ≤ (∏ i in s', i) + 1 := by
  apply Nat.succ_le_succ
  apply Nat.succ_le_of_lt
  apply Finset.prod_pos
  intro n ns'
  apply (mem_s'.mp ns').pos
State after:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
⊢ False

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
⊢ False
Tactic:
rcases exists_prime_factor this with ⟨p, pp, pdvd⟩
State after:
case intro.intro
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
⊢ False

State before:
case intro.intro
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
⊢ False
Tactic:
have : p ∣ ∏ i in s', i := by
  apply dvd_prod_of_mem
  rw [mem_s']
  apply pp
State after:
case intro.intro
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝ : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this : p ∣ ∏ i in s', i
⊢ False

State before:
case intro.intro
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝ : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this : p ∣ ∏ i in s', i
⊢ False
Tactic:
have : p ∣ 1 := by
  convert Nat.dvd_sub' pdvd this
  simp
State after:
case intro.intro
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝¹ : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this✝ : p ∣ ∏ i in s', i
this : p ∣ 1
⊢ False

State before:
case intro.intro
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝¹ : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this✝ : p ∣ ∏ i in s', i
this : p ∣ 1
⊢ False
Tactic:
have := Nat.le_of_dvd zero_lt_one this
State after:
case intro.intro
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝² : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this✝¹ : p ∣ ∏ i in s', i
this✝ : p ∣ 1
this : p ≤ 1
⊢ False

State before:
case intro.intro
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝² : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this✝¹ : p ∣ ∏ i in s', i
this✝ : p ∣ 1
this : p ≤ 1
⊢ False
Tactic:
linarith [pp.two_le]
State after:
no goals

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
⊢ ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
Tactic:
intro n
State after:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
n : ℕ
⊢ n ∈ s' ↔ Nat.Prime n

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
n : ℕ
⊢ n ∈ s' ↔ Nat.Prime n
Tactic:
simp [s'_def]
State after:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
n : ℕ
⊢ Nat.Prime n → n ∈ s

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
n : ℕ
⊢ Nat.Prime n → n ∈ s
Tactic:
apply h
State after:
no goals

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ 2 ≤ ∏ i in s', i + 1
Tactic:
apply Nat.succ_le_succ
State after:
case a
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ 1 ≤ ∏ i in s', i

State before:
case a
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ 1 ≤ ∏ i in s', i
Tactic:
apply Nat.succ_le_of_lt
State after:
case a.h
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ 0 < ∏ i in s', i

State before:
case a.h
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ 0 < ∏ i in s', i
Tactic:
apply Finset.prod_pos
State after:
case a.h.h0
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ ∀ i ∈ s', 0 < i

State before:
case a.h.h0
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
⊢ ∀ i ∈ s', 0 < i
Tactic:
intro n ns'
State after:
case a.h.h0
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
n : ℕ
ns' : n ∈ s'
⊢ 0 < n

State before:
case a.h.h0
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
n : ℕ
ns' : n ∈ s'
⊢ 0 < n
Tactic:
apply (mem_s'.mp ns').pos
State after:
no goals

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
⊢ p ∣ ∏ i in s', i
Tactic:
apply dvd_prod_of_mem
State after:
case ha
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
⊢ p ∈ s'

State before:
case ha
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
⊢ p ∈ s'
Tactic:
rw [mem_s']
State after:
case ha
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
⊢ Nat.Prime p

State before:
case ha
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
⊢ Nat.Prime p
Tactic:
apply pp
State after:
no goals

State before:
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝ : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this : p ∣ ∏ i in s', i
⊢ p ∣ 1
Tactic:
convert Nat.dvd_sub' pdvd this
State after:
case h.e'_4
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝ : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this : p ∣ ∏ i in s', i
⊢ 1 = ∏ i in s', i + 1 - ∏ i in s', i

State before:
case h.e'_4
s : Finset ℕ
h : ∀ (p : ℕ), Nat.Prime p → p ∈ s
s' : Finset ℕ := filter Nat.Prime s
s'_def : s' = filter Nat.Prime s
mem_s' : ∀ {n : ℕ}, n ∈ s' ↔ Nat.Prime n
this✝ : 2 ≤ ∏ i in s', i + 1
p : ℕ
pp : Nat.Prime p
pdvd : p ∣ ∏ i in s', i + 1
this : p ∣ ∏ i in s', i
⊢ 1 = ∏ i in s', i + 1 - ∏ i in s', i
Tactic:
simp
State after:
no goals