Documentation

Mathlib.Data.Finset.PiInduction

Induction principles for ∀ i, Finset (α i) #

In this file we prove a few induction principles for functions Π i : ι, Finset (α i) defined on a finite type.

Tags #

finite set, finite type, induction, function

theorem Finset.induction_on_pi_of_choice {ι : Type u_1} {α : ιType u_2} [Finite ι] [DecidableEq ι] [(i : ι) → DecidableEq (α i)] (r : (i : ι) → α iFinset (α i)Prop) (H_ex : ∀ (i : ι) (s : Finset (α i)), s.Nonemptyxs, r i x (s.erase x)) {p : ((i : ι) → Finset (α i))Prop} (f : (i : ι) → Finset (α i)) (h0 : p fun (x : ι) => ) (step : ∀ (g : (i : ι) → Finset (α i)) (i : ι) (x : α i), r i x (g i)p gp (Function.update g i (insert x (g i)))) :
p f

General theorem for Finset.induction_on_pi-style induction principles.

theorem Finset.induction_on_pi {ι : Type u_1} {α : ιType u_2} [Finite ι] [DecidableEq ι] [(i : ι) → DecidableEq (α i)] {p : ((i : ι) → Finset (α i))Prop} (f : (i : ι) → Finset (α i)) (h0 : p fun (x : ι) => ) (step : ∀ (g : (i : ι) → Finset (α i)) (i : ι), xg i, p gp (Function.update g i (insert x (g i)))) :
p f

Given a predicate on functions ∀ i, Finset (α i) defined on a finite type, it is true on all maps provided that it is true on fun _ ↦ ∅ and for any function g : ∀ i, Finset (α i), an index i : ι, and x ∉ g i, p g implies p (update g i (insert x (g i))).

See also Finset.induction_on_pi_max and Finset.induction_on_pi_min for specialized versions that require ∀ i, LinearOrder (α i).

theorem Finset.induction_on_pi_max {ι : Type u_1} {α : ιType u_2} [Finite ι] [DecidableEq ι] [(i : ι) → DecidableEq (α i)] [(i : ι) → LinearOrder (α i)] {p : ((i : ι) → Finset (α i))Prop} (f : (i : ι) → Finset (α i)) (h0 : p fun (x : ι) => ) (step : ∀ (g : (i : ι) → Finset (α i)) (i : ι) (x : α i), (∀ yg i, y < x)p gp (Function.update g i (insert x (g i)))) :
p f

Given a predicate on functions ∀ i, Finset (α i) defined on a finite type, it is true on all maps provided that it is true on fun _ ↦ ∅ and for any function g : ∀ i, Finset (α i), an index i : ι, and an elementx : α i that is strictly greater than all elements of g i, p g implies p (update g i (insert x (g i))).

This lemma requires LinearOrder instances on all α i. See also Finset.induction_on_pi for a version that x ∉ g i instead of does not need∀ i, LinearOrder (α i)`.

theorem Finset.induction_on_pi_min {ι : Type u_1} {α : ιType u_2} [Finite ι] [DecidableEq ι] [(i : ι) → DecidableEq (α i)] [(i : ι) → LinearOrder (α i)] {p : ((i : ι) → Finset (α i))Prop} (f : (i : ι) → Finset (α i)) (h0 : p fun (x : ι) => ) (step : ∀ (g : (i : ι) → Finset (α i)) (i : ι) (x : α i), (∀ yg i, x < y)p gp (Function.update g i (insert x (g i)))) :
p f

Given a predicate on functions ∀ i, Finset (α i) defined on a finite type, it is true on all maps provided that it is true on fun _ ↦ ∅ and for any function g : ∀ i, Finset (α i), an index i : ι, and an elementx : α i that is strictly less than all elements of g i, p g implies p (update g i (insert x (g i))).

This lemma requires LinearOrder instances on all α i. See also Finset.induction_on_pi for a version that x ∉ g i instead of does not need∀ i, LinearOrder (α i)`.