[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
s' : Finset ↑{x' | x' ≠ x}
⊢ card s' ≤ card (Finset.biUnion s' fun x' => erase (t ↑x') a)
[PROOFSTEP]
haveI := Classical.decEq ι
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
⊢ card s' ≤ card (Finset.biUnion s' fun x' => erase (t ↑x') a)
[PROOFSTEP]
specialize ha (s'.image fun z => z.1)
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha :
  Finset.Nonempty (image (fun z => ↑z) s') →
    image (fun z => ↑z) s' ≠ univ → card (image (fun z => ↑z) s') < card (Finset.biUnion (image (fun z => ↑z) s') t)
⊢ card s' ≤ card (Finset.biUnion s' fun x' => erase (t ↑x') a)
[PROOFSTEP]
rw [Nonempty.image_iff, Finset.card_image_of_injective s' Subtype.coe_injective] at ha
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
⊢ card s' ≤ card (Finset.biUnion s' fun x' => erase (t ↑x') a)
[PROOFSTEP]
by_cases he : s'.Nonempty
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
⊢ card s' ≤ card (Finset.biUnion s' fun x' => erase (t ↑x') a)
[PROOFSTEP]
have ha' : s'.card < (s'.biUnion fun x => t x).card :=
  by
  convert ha he fun h => by simpa [← h] using mem_univ x using 2
  ext x
  simp only [mem_image, mem_biUnion, exists_prop, SetCoe.exists, exists_and_right, exists_eq_right, Subtype.coe_mk]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
⊢ card s' < card (Finset.biUnion s' fun x_1 => t ↑x_1)
[PROOFSTEP]
convert ha he fun h => by simpa [← h] using mem_univ x using 2
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
h : image (fun z => ↑z) s' = univ
⊢ False
[PROOFSTEP]
simpa [← h] using mem_univ x
[GOAL]
case h.e'_4.h.e'_2
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
⊢ (Finset.biUnion s' fun x_1 => t ↑x_1) = Finset.biUnion (image (fun z => ↑z) s') t
[PROOFSTEP]
ext x
[GOAL]
case h.e'_4.h.e'_2.a
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x✝ : ι
a : α
s' : Finset ↑{x' | x' ≠ x✝}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
x : α
⊢ (x ∈ Finset.biUnion s' fun x => t ↑x) ↔ x ∈ Finset.biUnion (image (fun z => ↑z) s') t
[PROOFSTEP]
simp only [mem_image, mem_biUnion, exists_prop, SetCoe.exists, exists_and_right, exists_eq_right, Subtype.coe_mk]
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
ha' : card s' < card (Finset.biUnion s' fun x_1 => t ↑x_1)
⊢ card s' ≤ card (Finset.biUnion s' fun x' => erase (t ↑x') a)
[PROOFSTEP]
rw [← erase_biUnion]
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
ha' : card s' < card (Finset.biUnion s' fun x_1 => t ↑x_1)
⊢ card s' ≤ card (erase (Finset.biUnion s' fun x' => t ↑x') a)
[PROOFSTEP]
by_cases hb : a ∈ s'.biUnion fun x => t x
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
ha' : card s' < card (Finset.biUnion s' fun x_1 => t ↑x_1)
hb : a ∈ Finset.biUnion s' fun x_1 => t ↑x_1
⊢ card s' ≤ card (erase (Finset.biUnion s' fun x' => t ↑x') a)
[PROOFSTEP]
rw [card_erase_of_mem hb]
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
ha' : card s' < card (Finset.biUnion s' fun x_1 => t ↑x_1)
hb : a ∈ Finset.biUnion s' fun x_1 => t ↑x_1
⊢ card s' ≤ card (Finset.biUnion s' fun x_1 => t ↑x_1) - 1
[PROOFSTEP]
exact Nat.le_pred_of_lt ha'
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
ha' : card s' < card (Finset.biUnion s' fun x_1 => t ↑x_1)
hb : ¬a ∈ Finset.biUnion s' fun x_1 => t ↑x_1
⊢ card s' ≤ card (erase (Finset.biUnion s' fun x' => t ↑x') a)
[PROOFSTEP]
rw [erase_eq_of_not_mem hb]
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : Finset.Nonempty s'
ha' : card s' < card (Finset.biUnion s' fun x_1 => t ↑x_1)
hb : ¬a ∈ Finset.biUnion s' fun x_1 => t ↑x_1
⊢ card s' ≤ card (Finset.biUnion s' fun x_1 => t ↑x_1)
[PROOFSTEP]
exact Nat.le_of_lt ha'
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : ¬Finset.Nonempty s'
⊢ card s' ≤ card (Finset.biUnion s' fun x' => erase (t ↑x') a)
[PROOFSTEP]
rw [nonempty_iff_ne_empty, not_not] at he
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
s' : Finset ↑{x' | x' ≠ x}
this : DecidableEq ι
ha : Finset.Nonempty s' → image (fun z => ↑z) s' ≠ univ → card s' < card (Finset.biUnion (image (fun z => ↑z) s') t)
he : s' = ∅
⊢ card s' ≤ card (Finset.biUnion s' fun x' => erase (t ↑x') a)
[PROOFSTEP]
subst s'
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
x : ι
a : α
this : DecidableEq ι
ha : Finset.Nonempty ∅ → image (fun z => ↑z) ∅ ≠ univ → card ∅ < card (Finset.biUnion (image (fun z => ↑z) ∅) t)
⊢ card ∅ ≤ card (Finset.biUnion ∅ fun x' => erase (t ↑x') a)
[PROOFSTEP]
simp
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
haveI : Nonempty ι := Fintype.card_pos_iff.mp (hn.symm ▸ Nat.succ_pos _)
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this : Nonempty ι
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
haveI := Classical.decEq ι
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
let x := Classical.arbitrary ι
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
have tx_ne : (t x).Nonempty := by
  rw [← Finset.card_pos]
  calc
    0 < 1 := Nat.one_pos
    _ ≤ (Finset.biUnion { x } t).card := (ht { x })
    _ = (t x).card := by rw [Finset.singleton_biUnion]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
⊢ Finset.Nonempty (t x)
[PROOFSTEP]
rw [← Finset.card_pos]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
⊢ 0 < card (t x)
[PROOFSTEP]
calc
  0 < 1 := Nat.one_pos
  _ ≤ (Finset.biUnion { x } t).card := (ht { x })
  _ = (t x).card := by rw [Finset.singleton_biUnion]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
⊢ card (Finset.biUnion {x} t) = card (t x)
[PROOFSTEP]
rw [Finset.singleton_biUnion]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
tx_ne : Finset.Nonempty (t x)
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
choose y hy using tx_ne
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
let ι' := {x' : ι | x' ≠ x}
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
let t' : ι' → Finset α := fun x' => (t x').erase y
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
have card_ι' : Fintype.card ι' = n :=
  calc
    Fintype.card ι' = Fintype.card ι - 1 := Set.card_ne_eq _
    _ = n := by rw [hn, Nat.add_succ_sub_one, add_zero]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
⊢ Fintype.card ι - 1 = n
[PROOFSTEP]
rw [hn, Nat.add_succ_sub_one, add_zero]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
rcases ih t' card_ι'.le (hall_cond_of_erase y ha) with
  ⟨f', hfinj, hfr⟩
    -- Extend the resulting function.
[GOAL]
case intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
refine' ⟨fun z => if h : z = x then y else f' ⟨z, h⟩, _, _⟩
[GOAL]
case intro.intro.refine'_1
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
⊢ Function.Injective fun z => if h : z = x then y else f' { val := z, property := h }
[PROOFSTEP]
rintro z₁ z₂
[GOAL]
case intro.intro.refine'_1
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z₁ =
      (fun z => if h : z = x then y else f' { val := z, property := h }) z₂ →
    z₁ = z₂
[PROOFSTEP]
have key : ∀ {x}, y ≠ f' x := by
  intro x h
  simpa [← h] using hfr x
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
⊢ ∀ {x : ↑ι'}, y ≠ f' x
[PROOFSTEP]
intro x h
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x✝ : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x✝
ι' : Set ι := {x' | x' ≠ x✝}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
x : ↑ι'
h : y = f' x
⊢ False
[PROOFSTEP]
simpa [← h] using hfr x
[GOAL]
case intro.intro.refine'_1
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
key : ∀ {x : ↑ι'}, y ≠ f' x
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z₁ =
      (fun z => if h : z = x then y else f' { val := z, property := h }) z₂ →
    z₁ = z₂
[PROOFSTEP]
by_cases h₁ : z₁ = x
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
key : ∀ {x : ↑ι'}, y ≠ f' x
h₁ : z₁ = x
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z₁ =
      (fun z => if h : z = x then y else f' { val := z, property := h }) z₂ →
    z₁ = z₂
[PROOFSTEP]
by_cases h₂ : z₂ = x
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
key : ∀ {x : ↑ι'}, y ≠ f' x
h₁ : ¬z₁ = x
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z₁ =
      (fun z => if h : z = x then y else f' { val := z, property := h }) z₂ →
    z₁ = z₂
[PROOFSTEP]
by_cases h₂ : z₂ = x
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
key : ∀ {x : ↑ι'}, y ≠ f' x
h₁ : z₁ = x
h₂ : z₂ = x
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z₁ =
      (fun z => if h : z = x then y else f' { val := z, property := h }) z₂ →
    z₁ = z₂
[PROOFSTEP]
simp [h₁, h₂, hfinj.eq_iff, key, key.symm]
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
key : ∀ {x : ↑ι'}, y ≠ f' x
h₁ : z₁ = x
h₂ : ¬z₂ = x
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z₁ =
      (fun z => if h : z = x then y else f' { val := z, property := h }) z₂ →
    z₁ = z₂
[PROOFSTEP]
simp [h₁, h₂, hfinj.eq_iff, key, key.symm]
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
key : ∀ {x : ↑ι'}, y ≠ f' x
h₁ : ¬z₁ = x
h₂ : z₂ = x
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z₁ =
      (fun z => if h : z = x then y else f' { val := z, property := h }) z₂ →
    z₁ = z₂
[PROOFSTEP]
simp [h₁, h₂, hfinj.eq_iff, key, key.symm]
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z₁ z₂ : ι
key : ∀ {x : ↑ι'}, y ≠ f' x
h₁ : ¬z₁ = x
h₂ : ¬z₂ = x
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z₁ =
      (fun z => if h : z = x then y else f' { val := z, property := h }) z₂ →
    z₁ = z₂
[PROOFSTEP]
simp [h₁, h₂, hfinj.eq_iff, key, key.symm]
[GOAL]
case intro.intro.refine'_2
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
⊢ ∀ (x_1 : ι), (fun z => if h : z = x then y else f' { val := z, property := h }) x_1 ∈ t x_1
[PROOFSTEP]
intro z
[GOAL]
case intro.intro.refine'_2
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z : ι
⊢ (fun z => if h : z = x then y else f' { val := z, property := h }) z ∈ t z
[PROOFSTEP]
simp only [ne_eq, Set.mem_setOf_eq]
[GOAL]
case intro.intro.refine'_2
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z : ι
⊢ (if h : z = Classical.arbitrary ι then y else f' { val := z, property := h }) ∈ t z
[PROOFSTEP]
split_ifs with hz
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z : ι
hz : z = Classical.arbitrary ι
⊢ y ∈ t z
[PROOFSTEP]
rwa [hz]
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
hfr : ∀ (x : ↑ι'), f' x ∈ t' x
z : ι
hz : ¬z = Classical.arbitrary ι
⊢ f' { val := z, property := hz } ∈ t z
[PROOFSTEP]
specialize hfr ⟨z, hz⟩
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
z : ι
hz : ¬z = Classical.arbitrary ι
hfr : f' { val := z, property := hz } ∈ t' { val := z, property := hz }
⊢ f' { val := z, property := hz } ∈ t z
[PROOFSTEP]
rw [mem_erase] at hfr
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
ha : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
this✝ : Nonempty ι
this : DecidableEq ι
x : ι := Classical.arbitrary ι
y : α
hy : y ∈ t x
ι' : Set ι := {x' | x' ≠ x}
t' : ↑ι' → Finset α := fun x' => erase (t ↑x') y
card_ι' : Fintype.card ↑ι' = n
f' : ↑ι' → α
hfinj : Function.Injective f'
z : ι
hz : ¬z = Classical.arbitrary ι
hfr : f' { val := z, property := hz } ≠ y ∧ f' { val := z, property := hz } ∈ t ↑{ val := z, property := hz }
⊢ f' { val := z, property := hz } ∈ t z
[PROOFSTEP]
exact hfr.2
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑↑s
⊢ card s' ≤ card (Finset.biUnion s' fun a' => t ↑a')
[PROOFSTEP]
classical
rw [← card_image_of_injective s' Subtype.coe_injective]
convert ht (s'.image fun z => z.1) using 1
apply congr_arg
ext y
simp
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑↑s
⊢ card s' ≤ card (Finset.biUnion s' fun a' => t ↑a')
[PROOFSTEP]
rw [← card_image_of_injective s' Subtype.coe_injective]
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑↑s
⊢ card (image (fun a => ↑a) s') ≤ card (Finset.biUnion s' fun a' => t ↑a')
[PROOFSTEP]
convert ht (s'.image fun z => z.1) using 1
[GOAL]
case h.e'_4
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑↑s
⊢ card (Finset.biUnion s' fun a' => t ↑a') = card (Finset.biUnion (image (fun z => ↑z) s') t)
[PROOFSTEP]
apply congr_arg
[GOAL]
case h.e'_4.h
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑↑s
⊢ (Finset.biUnion s' fun a' => t ↑a') = Finset.biUnion (image (fun z => ↑z) s') t
[PROOFSTEP]
ext y
[GOAL]
case h.e'_4.h.a
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑↑s
y : α
⊢ (y ∈ Finset.biUnion s' fun a' => t ↑a') ↔ y ∈ Finset.biUnion (image (fun z => ↑z) s') t
[PROOFSTEP]
simp
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
⊢ card s' ≤ card (Finset.biUnion s' fun x' => t ↑x' \ Finset.biUnion s t)
[PROOFSTEP]
haveI := Classical.decEq ι
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this : DecidableEq ι
⊢ card s' ≤ card (Finset.biUnion s' fun x' => t ↑x' \ Finset.biUnion s t)
[PROOFSTEP]
have disj : Disjoint s (s'.image fun z => z.1) :=
  by
  simp only [disjoint_left, not_exists, mem_image, exists_prop, SetCoe.exists, exists_and_right, exists_eq_right,
    Subtype.coe_mk]
  intro x hx hc _
  exact absurd hx hc
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this : DecidableEq ι
⊢ Disjoint s (image (fun z => ↑z) s')
[PROOFSTEP]
simp only [disjoint_left, not_exists, mem_image, exists_prop, SetCoe.exists, exists_and_right, exists_eq_right,
  Subtype.coe_mk]
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this : DecidableEq ι
⊢ ∀ ⦃a : ι⦄, a ∈ s → ∀ (x : a ∈ (↑s)ᶜ), ¬{ val := a, property := (_ : a ∈ (↑s)ᶜ) } ∈ s'
[PROOFSTEP]
intro x hx hc _
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this : DecidableEq ι
x : ι
hx : x ∈ s
hc : x ∈ (↑s)ᶜ
a✝ : { val := x, property := (_ : x ∈ (↑s)ᶜ) } ∈ s'
⊢ False
[PROOFSTEP]
exact absurd hx hc
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
⊢ card s' ≤ card (Finset.biUnion s' fun x' => t ↑x' \ Finset.biUnion s t)
[PROOFSTEP]
have : s'.card = (s ∪ s'.image fun z => z.1).card - s.card := by
  simp [disj, card_image_of_injective _ Subtype.coe_injective]
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
⊢ card s' = card (s ∪ image (fun z => ↑z) s') - card s
[PROOFSTEP]
simp [disj, card_image_of_injective _ Subtype.coe_injective]
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
⊢ card s' ≤ card (Finset.biUnion s' fun x' => t ↑x' \ Finset.biUnion s t)
[PROOFSTEP]
rw [this, hus]
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
⊢ card (s ∪ image (fun z => ↑z) s') - card (Finset.biUnion s t) ≤
    card (Finset.biUnion s' fun x' => t ↑x' \ Finset.biUnion s t)
[PROOFSTEP]
refine' (tsub_le_tsub_right (ht _) _).trans _
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
⊢ card (Finset.biUnion (s ∪ image (fun z => ↑z) s') t) - card (Finset.biUnion s t) ≤
    card (Finset.biUnion s' fun x' => t ↑x' \ Finset.biUnion s t)
[PROOFSTEP]
rw [← card_sdiff]
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
⊢ card (Finset.biUnion (s ∪ image (fun z => ↑z) s') t \ Finset.biUnion s t) ≤
    card (Finset.biUnion s' fun x' => t ↑x' \ Finset.biUnion s t)
[PROOFSTEP]
refine' (card_le_of_subset _).trans le_rfl
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
⊢ Finset.biUnion (s ∪ image (fun z => ↑z) s') t \ Finset.biUnion s t ⊆
    Finset.biUnion s' fun x' => t ↑x' \ Finset.biUnion s t
[PROOFSTEP]
intro t
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝¹ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t✝ : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t✝)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t✝)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
t : α
⊢ t ∈ Finset.biUnion (s ∪ image (fun z => ↑z) s') t✝ \ Finset.biUnion s t✝ →
    t ∈ Finset.biUnion s' fun x' => t✝ ↑x' \ Finset.biUnion s t✝
[PROOFSTEP]
simp only [mem_biUnion, mem_sdiff, not_exists, mem_image, and_imp, mem_union, exists_and_right, exists_imp]
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝¹ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t✝ : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t✝)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t✝)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
t : α
⊢ ∀ (x : ι),
    (x ∈ s ∨ ∃ a, a ∈ s' ∧ ↑a = x) →
      t ∈ t✝ x → (∀ (x : ι), ¬(x ∈ s ∧ t ∈ t✝ x)) → ∃ a, a ∈ s' ∧ t ∈ t✝ ↑a ∧ ∀ (x : ι), ¬(x ∈ s ∧ t ∈ t✝ x)
[PROOFSTEP]
rintro x (hx | ⟨x', hx', rfl⟩) rat hs
[GOAL]
case inl
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝¹ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t✝ : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t✝)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t✝)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
t : α
x : ι
hx : x ∈ s
rat : t ∈ t✝ x
hs : ∀ (x : ι), ¬(x ∈ s ∧ t ∈ t✝ x)
⊢ ∃ a, a ∈ s' ∧ t ∈ t✝ ↑a ∧ ∀ (x : ι), ¬(x ∈ s ∧ t ∈ t✝ x)
[PROOFSTEP]
exact False.elim <| (hs x) <| And.intro hx rat
[GOAL]
case inr.intro.intro
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝¹ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t✝ : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t✝)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t✝)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
t : α
x' : ↑(↑s)ᶜ
hx' : x' ∈ s'
rat : t ∈ t✝ ↑x'
hs : ∀ (x : ι), ¬(x ∈ s ∧ t ∈ t✝ x)
⊢ ∃ a, a ∈ s' ∧ t ∈ t✝ ↑a ∧ ∀ (x : ι), ¬(x ∈ s ∧ t ∈ t✝ x)
[PROOFSTEP]
use x', hx', rat, hs
[GOAL]
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
⊢ Finset.biUnion s t ⊆ Finset.biUnion (s ∪ image (fun z => ↑z) s') t
[PROOFSTEP]
apply biUnion_subset_biUnion_of_subset_left
[GOAL]
case h
ι✝ : Type u
α : Type v
inst✝¹ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝ : Fintype ι✝
ι : Type u
t : ι → Finset α
s : Finset ι
hus : card s = card (Finset.biUnion s t)
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
s' : Finset ↑(↑s)ᶜ
this✝ : DecidableEq ι
disj : Disjoint s (image (fun z => ↑z) s')
this : card s' = card (s ∪ image (fun z => ↑z) s') - card s
⊢ s ⊆ s ∪ image (fun z => ↑z) s'
[PROOFSTEP]
apply subset_union_left
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
haveI := Classical.decEq ι
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = n + 1
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
rw [Nat.add_one] at hn
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
have card_ι'_le : Fintype.card s ≤ n := by
  apply Nat.le_of_lt_succ
  calc
    Fintype.card s = s.card := Fintype.card_coe _
    _ < Fintype.card ι := ((card_lt_iff_ne_univ _).mpr hns)
    _ = n.succ := hn
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
⊢ Fintype.card { x // x ∈ s } ≤ n
[PROOFSTEP]
apply Nat.le_of_lt_succ
[GOAL]
case a
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
⊢ Fintype.card { x // x ∈ s } < Nat.succ n
[PROOFSTEP]
calc
  Fintype.card s = s.card := Fintype.card_coe _
  _ < Fintype.card ι := ((card_lt_iff_ne_univ _).mpr hns)
  _ = n.succ := hn
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
let t' : s → Finset α := fun x' => t x'
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
rcases ih t' card_ι'_le (hall_cond_of_restrict ht) with
  ⟨f', hf', hsf'⟩
    -- Restrict to `sᶜ` in the domain and `(s.biUnion t)ᶜ` in the codomain.
[GOAL]
case intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
set ι'' := (s : Set ι)ᶜ
[GOAL]
case intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
let t'' : ι'' → Finset α := fun a'' => t a'' \ s.biUnion t
[GOAL]
case intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
have card_ι''_le : Fintype.card ι'' ≤ n :=
  by
  simp_rw [← Nat.lt_succ_iff, ← hn, ← Finset.coe_compl, coe_sort_coe]
  rwa [Fintype.card_coe, card_compl_lt_iff_nonempty]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
⊢ Fintype.card ↑ι'' ≤ n
[PROOFSTEP]
simp_rw [← Nat.lt_succ_iff, ← hn, ← Finset.coe_compl, coe_sort_coe]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
⊢ Fintype.card { x // x ∈ sᶜ } < Fintype.card ι
[PROOFSTEP]
rwa [Fintype.card_coe, card_compl_lt_iff_nonempty]
[GOAL]
case intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
rcases ih t'' card_ι''_le (hall_cond_of_compl hus ht) with
  ⟨f'', hf'', hsf''⟩
    -- Put them together
[GOAL]
case intro.intro.intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
have f'_mem_biUnion : ∀ (x') (hx' : x' ∈ s), f' ⟨x', hx'⟩ ∈ s.biUnion t :=
  by
  intro x' hx'
  rw [mem_biUnion]
  exact ⟨x', hx', hsf' _⟩
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
⊢ ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
[PROOFSTEP]
intro x' hx'
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
x' : ι
hx' : x' ∈ s
⊢ f' { val := x', property := hx' } ∈ Finset.biUnion s t
[PROOFSTEP]
rw [mem_biUnion]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
x' : ι
hx' : x' ∈ s
⊢ ∃ a, a ∈ s ∧ f' { val := x', property := hx' } ∈ t a
[PROOFSTEP]
exact ⟨x', hx', hsf' _⟩
[GOAL]
case intro.intro.intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
have f''_not_mem_biUnion : ∀ (x'') (hx'' : ¬x'' ∈ s), ¬f'' ⟨x'', hx''⟩ ∈ s.biUnion t :=
  by
  intro x'' hx''
  have h := hsf'' ⟨x'', hx''⟩
  rw [mem_sdiff] at h
  exact h.2
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
⊢ ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
[PROOFSTEP]
intro x'' hx''
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
x'' : ι
hx'' : ¬x'' ∈ s
⊢ ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
[PROOFSTEP]
have h := hsf'' ⟨x'', hx''⟩
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
x'' : ι
hx'' : ¬x'' ∈ s
h : f'' { val := x'', property := hx'' } ∈ t'' { val := x'', property := hx'' }
⊢ ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
[PROOFSTEP]
rw [mem_sdiff] at h
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
x'' : ι
hx'' : ¬x'' ∈ s
h :
  f'' { val := x'', property := hx'' } ∈ t ↑{ val := x'', property := hx'' } ∧
    ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
⊢ ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
[PROOFSTEP]
exact h.2
[GOAL]
case intro.intro.intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
have im_disj : ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s), f' ⟨x', hx'⟩ ≠ f'' ⟨x'', hx''⟩ :=
  by
  intro x x' hx' hx'' h
  apply f''_not_mem_biUnion x' hx''
  rw [← h]
  apply f'_mem_biUnion x
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
⊢ ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s),
    f' { val := x', property := hx' } ≠ f'' { val := x'', property := hx'' }
[PROOFSTEP]
intro x x' hx' hx'' h
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
x x' : ι
hx' : x ∈ s
hx'' : ¬x' ∈ s
h : f' { val := x, property := hx' } = f'' { val := x', property := hx'' }
⊢ False
[PROOFSTEP]
apply f''_not_mem_biUnion x' hx''
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
x x' : ι
hx' : x ∈ s
hx'' : ¬x' ∈ s
h : f' { val := x, property := hx' } = f'' { val := x', property := hx'' }
⊢ f'' { val := x', property := hx'' } ∈ Finset.biUnion s t
[PROOFSTEP]
rw [← h]
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
x x' : ι
hx' : x ∈ s
hx'' : ¬x' ∈ s
h : f' { val := x, property := hx' } = f'' { val := x', property := hx'' }
⊢ f' { val := x, property := hx' } ∈ Finset.biUnion s t
[PROOFSTEP]
apply f'_mem_biUnion x
[GOAL]
case intro.intro.intro.intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
im_disj :
  ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s),
    f' { val := x', property := hx' } ≠ f'' { val := x'', property := hx'' }
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
refine' ⟨fun x => if h : x ∈ s then f' ⟨x, h⟩ else f'' ⟨x, h⟩, _, _⟩
[GOAL]
case intro.intro.intro.intro.refine'_1
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
im_disj :
  ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s),
    f' { val := x', property := hx' } ≠ f'' { val := x'', property := hx'' }
⊢ Function.Injective fun x => if h : x ∈ s then f' { val := x, property := h } else f'' { val := x, property := h }
[PROOFSTEP]
refine' hf'.dite _ hf'' (@fun x x' => im_disj x x' _ _)
[GOAL]
case intro.intro.intro.intro.refine'_2
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
im_disj :
  ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s),
    f' { val := x', property := hx' } ≠ f'' { val := x'', property := hx'' }
⊢ ∀ (x : ι), (fun x => if h : x ∈ s then f' { val := x, property := h } else f'' { val := x, property := h }) x ∈ t x
[PROOFSTEP]
intro x
[GOAL]
case intro.intro.intro.intro.refine'_2
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
im_disj :
  ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s),
    f' { val := x', property := hx' } ≠ f'' { val := x'', property := hx'' }
x : ι
⊢ (fun x => if h : x ∈ s then f' { val := x, property := h } else f'' { val := x, property := h }) x ∈ t x
[PROOFSTEP]
simp only [of_eq_true]
[GOAL]
case intro.intro.intro.intro.refine'_2
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
im_disj :
  ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s),
    f' { val := x', property := hx' } ≠ f'' { val := x'', property := hx'' }
x : ι
⊢ (if h : x ∈ s then f' { val := x, property := h } else f'' { val := x, property := h }) ∈ t x
[PROOFSTEP]
split_ifs with h
[GOAL]
case pos
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
im_disj :
  ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s),
    f' { val := x', property := hx' } ≠ f'' { val := x'', property := hx'' }
x : ι
h : x ∈ s
⊢ f' { val := x, property := h } ∈ t x
[PROOFSTEP]
exact hsf' ⟨x, h⟩
[GOAL]
case neg
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Fintype ι
n : ℕ
hn : Fintype.card ι = Nat.succ n
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
ih :
  ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
hs : Finset.Nonempty s
hns : s ≠ univ
hus : card s = card (Finset.biUnion s t)
this : DecidableEq ι
card_ι'_le : Fintype.card { x // x ∈ s } ≤ n
t' : { x // x ∈ s } → Finset α := fun x' => t ↑x'
f' : { x // x ∈ s } → α
hf' : Function.Injective f'
hsf' : ∀ (x : { x // x ∈ s }), f' x ∈ t' x
ι'' : Set ι := (↑s)ᶜ
t'' : ↑ι'' → Finset α := fun a'' => t ↑a'' \ Finset.biUnion s t
card_ι''_le : Fintype.card ↑ι'' ≤ n
f'' : ↑ι'' → α
hf'' : Function.Injective f''
hsf'' : ∀ (x : ↑ι''), f'' x ∈ t'' x
f'_mem_biUnion : ∀ (x' : ι) (hx' : x' ∈ s), f' { val := x', property := hx' } ∈ Finset.biUnion s t
f''_not_mem_biUnion : ∀ (x'' : ι) (hx'' : ¬x'' ∈ s), ¬f'' { val := x'', property := hx'' } ∈ Finset.biUnion s t
im_disj :
  ∀ (x' x'' : ι) (hx' : x' ∈ s) (hx'' : ¬x'' ∈ s),
    f' { val := x', property := hx' } ≠ f'' { val := x'', property := hx'' }
x : ι
h : ¬x ∈ s
⊢ f'' { val := x, property := h } ∈ t x
[PROOFSTEP]
exact sdiff_subset _ _ (hsf'' ⟨x, h⟩)
[GOAL]
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
cases nonempty_fintype ι
[GOAL]
case intro
ι : Type u
α : Type v
inst✝¹ : DecidableEq α
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
induction' hn : Fintype.card ι using Nat.strong_induction_on with n ih generalizing ι
[GOAL]
case intro.h
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
n : ℕ
ih :
  ∀ (m : ℕ),
    m < n →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
hn : Fintype.card ι = n
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
rcases n with (_ | _)
[GOAL]
case intro.h.zero
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
ih :
  ∀ (m : ℕ),
    m < Nat.zero →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.zero
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
rw [Fintype.card_eq_zero_iff] at hn
[GOAL]
case intro.h.zero
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
ih :
  ∀ (m : ℕ),
    m < Nat.zero →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : IsEmpty ι
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
exact ⟨isEmptyElim, isEmptyElim, isEmptyElim⟩
[GOAL]
case intro.h.succ
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
n✝ : ℕ
ih :
  ∀ (m : ℕ),
    m < Nat.succ n✝ →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.succ n✝
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
have ih' :
  ∀ (ι' : Type u) [Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ _ →
      (∀ s' : Finset ι', s'.card ≤ (s'.biUnion t').card) → ∃ f : ι' → α, Function.Injective f ∧ ∀ x, f x ∈ t' x :=
  by
  intro ι' _ _ hι' ht'
  exact ih _ (Nat.lt_succ_of_le hι') ht' _ rfl
[GOAL]
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
n✝ : ℕ
ih :
  ∀ (m : ℕ),
    m < Nat.succ n✝ →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.succ n✝
⊢ ∀ (ι' : Type u) [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ ?m.46100 ι' t' →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
[PROOFSTEP]
intro ι' _ _ hι' ht'
[GOAL]
ι✝ : Type u
α : Type v
inst✝³ : DecidableEq α
t✝ : ι✝ → Finset α
inst✝² : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝¹ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
n✝ : ℕ
ih :
  ∀ (m : ℕ),
    m < Nat.succ n✝ →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.succ n✝
ι' : Type u
inst✝ : Fintype ι'
t'✝ : ι' → Finset α
hι' : Fintype.card ι' ≤ ?m.46100 ι' t'✝
ht' : ∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t'✝)
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t'✝ x
[PROOFSTEP]
exact ih _ (Nat.lt_succ_of_le hι') ht' _ rfl
[GOAL]
case intro.h.succ
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
n✝ : ℕ
ih :
  ∀ (m : ℕ),
    m < Nat.succ n✝ →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.succ n✝
ih' :
  ∀ (ι' : Type u) [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n✝ →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
by_cases h : ∀ s : Finset ι, s.Nonempty → s ≠ univ → s.card < (s.biUnion t).card
[GOAL]
case pos
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
n✝ : ℕ
ih :
  ∀ (m : ℕ),
    m < Nat.succ n✝ →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.succ n✝
ih' :
  ∀ (ι' : Type u) [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n✝ →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
h : ∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
refine' hall_hard_inductive_step_A hn ht (@fun ι' => ih' ι') h
[GOAL]
case neg
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
n✝ : ℕ
ih :
  ∀ (m : ℕ),
    m < Nat.succ n✝ →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.succ n✝
ih' :
  ∀ (ι' : Type u) [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n✝ →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
h : ¬∀ (s : Finset ι), Finset.Nonempty s → s ≠ univ → card s < card (Finset.biUnion s t)
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
push_neg at h
[GOAL]
case neg
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
n✝ : ℕ
ih :
  ∀ (m : ℕ),
    m < Nat.succ n✝ →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.succ n✝
ih' :
  ∀ (ι' : Type u) [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n✝ →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
h : ∃ s, Finset.Nonempty s ∧ s ≠ univ ∧ card (Finset.biUnion s t) ≤ card s
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
rcases h with ⟨s, sne, snu, sle⟩
[GOAL]
case neg.intro.intro.intro
ι✝ : Type u
α : Type v
inst✝² : DecidableEq α
t✝ : ι✝ → Finset α
inst✝¹ : Finite ι✝
ht✝ : ∀ (s : Finset ι✝), card s ≤ card (Finset.biUnion s t✝)
val✝¹ : Fintype ι✝
x✝ : ℕ
hn✝ : Fintype.card ι✝ = x✝
ι : Type u
t : ι → Finset α
inst✝ : Finite ι
ht : ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
val✝ : Fintype ι
n✝ : ℕ
ih :
  ∀ (m : ℕ),
    m < Nat.succ n✝ →
      ∀ {ι : Type u} {t : ι → Finset α} [inst : Finite ι],
        (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) →
          ∀ (val : Fintype ι), Fintype.card ι = m → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
hn : Fintype.card ι = Nat.succ n✝
ih' :
  ∀ (ι' : Type u) [inst : Fintype ι'] (t' : ι' → Finset α),
    Fintype.card ι' ≤ n✝ →
      (∀ (s' : Finset ι'), card s' ≤ card (Finset.biUnion s' t')) → ∃ f, Function.Injective f ∧ ∀ (x : ι'), f x ∈ t' x
s : Finset ι
sne : Finset.Nonempty s
snu : s ≠ univ
sle : card (Finset.biUnion s t) ≤ card s
⊢ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
exact hall_hard_inductive_step_B hn ht (@fun ι' => ih' ι') s sne snu (Nat.le_antisymm (ht _) sle)
[GOAL]
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
⊢ (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) ↔ ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
constructor
[GOAL]
case mp
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
⊢ (∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)) → ∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x
[PROOFSTEP]
exact HallMarriageTheorem.hall_hard_inductive
[GOAL]
case mpr
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
⊢ (∃ f, Function.Injective f ∧ ∀ (x : ι), f x ∈ t x) → ∀ (s : Finset ι), card s ≤ card (Finset.biUnion s t)
[PROOFSTEP]
rintro ⟨f, hf₁, hf₂⟩ s
[GOAL]
case mpr.intro.intro
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
f : ι → α
hf₁ : Function.Injective f
hf₂ : ∀ (x : ι), f x ∈ t x
s : Finset ι
⊢ card s ≤ card (Finset.biUnion s t)
[PROOFSTEP]
rw [← card_image_of_injective s hf₁]
[GOAL]
case mpr.intro.intro
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
f : ι → α
hf₁ : Function.Injective f
hf₂ : ∀ (x : ι), f x ∈ t x
s : Finset ι
⊢ card (image f s) ≤ card (Finset.biUnion s t)
[PROOFSTEP]
apply card_le_of_subset
[GOAL]
case mpr.intro.intro.a
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
f : ι → α
hf₁ : Function.Injective f
hf₂ : ∀ (x : ι), f x ∈ t x
s : Finset ι
⊢ image f s ⊆ Finset.biUnion s t
[PROOFSTEP]
intro
[GOAL]
case mpr.intro.intro.a
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
f : ι → α
hf₁ : Function.Injective f
hf₂ : ∀ (x : ι), f x ∈ t x
s : Finset ι
a✝ : α
⊢ a✝ ∈ image f s → a✝ ∈ Finset.biUnion s t
[PROOFSTEP]
rw [mem_image, mem_biUnion]
[GOAL]
case mpr.intro.intro.a
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
f : ι → α
hf₁ : Function.Injective f
hf₂ : ∀ (x : ι), f x ∈ t x
s : Finset ι
a✝ : α
⊢ (∃ a, a ∈ s ∧ f a = a✝) → ∃ a, a ∈ s ∧ a✝ ∈ t a
[PROOFSTEP]
rintro ⟨x, hx, rfl⟩
[GOAL]
case mpr.intro.intro.a.intro.intro
ι : Type u_1
α : Type u_2
inst✝¹ : Finite ι
inst✝ : DecidableEq α
t : ι → Finset α
f : ι → α
hf₁ : Function.Injective f
hf₂ : ∀ (x : ι), f x ∈ t x
s : Finset ι
x : ι
hx : x ∈ s
⊢ ∃ a, a ∈ s ∧ f x ∈ t a
[PROOFSTEP]
exact ⟨x, hx, hf₂ x⟩