-- Mathlib/Data/Finset/Max.lean
theorem induction_on_max_value [DecidableEq ι] (f : ι → α) {p : Finset ι → Prop} (s : Finset ι)
    (h0 : p ∅) (step : ∀ a s, a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)) : p s

Proof state:
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
s : Finset ι
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
⊢ p s

Tactic:
induction' s using Finset.strongInductionOn with s ihs

Result:
case a
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
⊢ p s

Proof state:
case a
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
⊢ p s

Tactic:
rcases (s.image f).eq_empty_or_nonempty with (hne | hne)

Result:
case a.inl
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : image f s = ∅
⊢ p s

case a.inr
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
⊢ p s

Proof state:
case a.inr
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
H : ∃ a ∈ s, f a = (image f s).max' hne
⊢ p s

Tactic:
rcases H with ⟨a, has, hfa⟩

Result:
case a.inr.intro.intro
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
a : ι
has : a ∈ s
hfa : f a = (image f s).max' hne
⊢ p s

Proof state:
case a.inr.intro.intro
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
a : ι
has : a ∈ s
hfa : f a = (image f s).max' hne
⊢ p s

Tactic:
rw [← insert_erase has]

Result:
case a.inr.intro.intro
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
a : ι
has : a ∈ s
hfa : f a = (image f s).max' hne
⊢ p (insert a (s.erase a))

Proof state:
case a.inr.intro.intro
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
a : ι
has : a ∈ s
hfa : f a = (image f s).max' hne
x : ι
hx : x ∈ s.erase a
⊢ f x ≤ f a

Tactic:
rw [hfa]

Result:
case a.inr.intro.intro
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
a : ι
has : a ∈ s
hfa : f a = (image f s).max' hne
x : ι
hx : x ∈ s.erase a
⊢ f x ≤ (image f s).max' hne

Proof state:
case a.inr.intro.intro
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
a : ι
has : a ∈ s
hfa : f a = (image f s).max' hne
⊢ p (insert a (s.erase a))

Tactic:
refine step _ _ (not_mem_erase a s) (fun x hx => ?_) (ihs _ <| erase_ssubset has)

Result:
case a.inr.intro.intro
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
a : ι
has : a ∈ s
hfa : f a = (image f s).max' hne
x : ι
hx : x ∈ s.erase a
⊢ f x ≤ f a

Proof state:
case a.inr.intro.intro
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
a : ι
has : a ∈ s
hfa : f a = (image f s).max' hne
x : ι
hx : x ∈ s.erase a
⊢ f x ≤ (image f s).max' hne

Tactic:
exact le_max' _ _ (mem_image_of_mem _ <| mem_of_mem_erase hx)

Result:
no goals

Proof state:
case a.inr
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
⊢ p s

Tactic:
have H : (s.image f).max' hne ∈ s.image f := max'_mem (s.image f) hne

Result:
case a.inr
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
H : (image f s).max' hne ∈ image f s
⊢ p s

Proof state:
case a.inl
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : image f s = ∅
⊢ p s

Tactic:
simp only [image_eq_empty] at hne

Result:
case a.inl
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : s = ∅
⊢ p s

Proof state:
case a.inr
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
H : (image f s).max' hne ∈ image f s
⊢ p s

Tactic:
simp only [mem_image, exists_prop] at H

Result:
case a.inr
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : (image f s).Nonempty
H : ∃ a ∈ s, f a = (image f s).max' hne
⊢ p s

Proof state:
case a.inl
α : Type u_2
ι : Type u_5
inst✝¹ : LinearOrder α
inst✝ : DecidableEq ι
f : ι → α
p : Finset ι → Prop
h0 : p ∅
step : ∀ (a : ι) (s : Finset ι), a ∉ s → (∀ x ∈ s, f x ≤ f a) → p s → p (insert a s)
s : Finset ι
ihs : ∀ t ⊂ s, p t
hne : s = ∅
⊢ p s

Tactic:
simp only [hne, h0]

Result:
no goals