Theorem: sb_surjective (MIL/C04_Sets_and_Functions/S03_The_Schroeder_Bernstein_Theorem.lean)

State before:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
⊢ Surjective (sbFun f g)
Tactic:
set A := sbSet f g with A_def
State after:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
⊢ Surjective (sbFun f g)

State before:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
⊢ Surjective (sbFun f g)
Tactic:
set h := sbFun f g with h_def
State after:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
⊢ Surjective h

State before:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
⊢ Surjective h
Tactic:
intro y
State after:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
⊢ ∃ a, h a = y

State before:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
⊢ ∃ a, h a = y
Tactic:
by_cases gyA : g y ∈ A
State after:
case pos
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : g y ∈ A
⊢ ∃ a, h a = y

case neg
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : g y ∉ A
⊢ ∃ a, h a = y

State before:
case neg
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : g y ∉ A
⊢ ∃ a, h a = y
Tactic:
use g y
State after:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : g y ∉ A
⊢ h (g y) = y

State before:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : g y ∉ A
⊢ h (g y) = y
Tactic:
simp only [h_def, sbFun, if_neg gyA]
State after:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : g y ∉ A
⊢ invFun g (g y) = y

State before:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : g y ∉ A
⊢ invFun g (g y) = y
Tactic:
apply leftInverse_invFun hg
State after:
no goals

State before:
case pos
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : g y ∈ A
⊢ ∃ a, h a = y
Tactic:
rw [A_def, sbSet, mem_iUnion] at gyA
State after:
case pos
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : ∃ i, g y ∈ sbAux f g i
⊢ ∃ a, h a = y

State before:
case pos
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
gyA : ∃ i, g y ∈ sbAux f g i
⊢ ∃ a, h a = y
Tactic:
rcases gyA with ⟨n, hn⟩
State after:
case pos.intro
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
hn : g y ∈ sbAux f g n
⊢ ∃ a, h a = y

State before:
case pos.intro
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
hn : g y ∈ sbAux f g n
⊢ ∃ a, h a = y
Tactic:
rcases n with _ | n
State after:
case pos.intro.zero
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
hn : g y ∈ sbAux f g 0
⊢ ∃ a, h a = y

case pos.intro.succ
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
hn : g y ∈ sbAux f g (n + 1)
⊢ ∃ a, h a = y

State before:
case pos.intro.succ
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
hn : g y ∈ sbAux f g (n + 1)
⊢ ∃ a, h a = y
Tactic:
simp [sbAux] at hn
State after:
case pos.intro.succ
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
hn : ∃ a ∈ sbAux f g n, g (f a) = g y
⊢ ∃ a, h a = y

State before:
case pos.intro.succ
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
hn : ∃ a ∈ sbAux f g n, g (f a) = g y
⊢ ∃ a, h a = y
Tactic:
rcases hn with ⟨x, xmem, hx⟩
State after:
case pos.intro.succ.intro.intro
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
⊢ ∃ a, h a = y

State before:
case pos.intro.succ.intro.intro
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
⊢ ∃ a, h a = y
Tactic:
use x
State after:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
⊢ h x = y

State before:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
⊢ h x = y
Tactic:
have : x ∈ A := by
  rw [A_def, sbSet, mem_iUnion]
  exact ⟨n, xmem⟩
State after:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
this : x ∈ A
⊢ h x = y

State before:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
this : x ∈ A
⊢ h x = y
Tactic:
simp only [h_def, sbFun, if_pos this]
State after:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
this : x ∈ A
⊢ f x = y

State before:
case h
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
this : x ∈ A
⊢ f x = y
Tactic:
exact hg hx
State after:
no goals

State before:
case pos.intro.zero
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
hn : g y ∈ sbAux f g 0
⊢ ∃ a, h a = y
Tactic:
simp [sbAux] at hn
State after:
no goals

State before:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
⊢ x ∈ A
Tactic:
rw [A_def, sbSet, mem_iUnion]
State after:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
⊢ ∃ i, x ∈ sbAux f g i

State before:
α : Type u_1
β : Type u_2
inst✝ : Nonempty β
f : α → β
g : β → α
hf : Injective f
hg : Injective g
A : Set α := sbSet f g
A_def : A = sbSet f g
h : α → β := sbFun f g
h_def : h = sbFun f g
y : β
n : ℕ
x : α
xmem : x ∈ sbAux f g n
hx : g (f x) = g y
⊢ ∃ i, x ∈ sbAux f g i
Tactic:
exact ⟨n, xmem⟩
State after:
no goals