# mathlibdocumentation

order.filter.lift

# Lift filters along filter and set functions

def filter.lift {α : Type u_1} {β : Type u_2} :
(set αfilter β)

A variant on bind using a function g taking a set instead of a member of α. This is essentially a push-forward along a function mapping each set to a filter.

Equations
theorem filter.has_basis.mem_lift_iff {α : Type u_1} {γ : Type u_3} {ι : Type u_2} {p : ι → Prop} {s : ι → set α} {f : filter α} (hf : f.has_basis p s) {β : ι → Type u_4} {pg : Π (i : ι), β i → Prop} {sg : Π (i : ι), β iset γ} {g : set α} (hg : ∀ (i : ι), (g (s i)).has_basis (pg i) (sg i)) (gm : monotone g) {s_1 : set γ} :
s_1 f.lift g ∃ (i : ι) (hi : p i) (x : β i) (hx : pg i x), sg i x s_1

If (p : ι → Prop, s : ι → set α) is a basis of a filter f, g is a monotone function set α → filter γ, and for each i, (pg : β i → Prop, sg : β i → set α) is a basis of the filter g (s i), then (λ (i : ι) (x : β i), p i ∧ pg i x, λ (i : ι) (x : β i), sg i x) is a basis of the filter f.lift g.

This basis is parametrized by i : ι and x : β i, so in order to formulate this fact using has_basis one has to use Σ i, β i as the index type, see filter.has_basis.lift. This lemma states the corresponding mem_iff statement without using a sigma type.

theorem filter.has_basis.lift {α : Type u_1} {γ : Type u_3} {ι : Type u_2} {p : ι → Prop} {s : ι → set α} {f : filter α} (hf : f.has_basis p s) {β : ι → Type u_4} {pg : Π (i : ι), β i → Prop} {sg : Π (i : ι), β iset γ} {g : set α} :
(∀ (i : ι), (g (s i)).has_basis (pg i) (sg i))(f.lift g).has_basis (λ (i : Σ (i : ι), β i), p i.fst pg i.fst i.snd) (λ (i : Σ (i : ι), β i), sg i.fst i.snd)

If (p : ι → Prop, s : ι → set α) is a basis of a filter f, g is a monotone function set α → filter γ, and for each i, (pg : β i → Prop, sg : β i → set α) is a basis of the filter g (s i), then (λ (i : ι) (x : β i), p i ∧ pg i x, λ (i : ι) (x : β i), sg i x) is a basis of the filter f.lift g.

This basis is parametrized by i : ι and x : β i, so in order to formulate this fact using has_basis one has to use Σ i, β i as the index type. See also filter.has_basis.mem_lift_iff for the corresponding mem_iff statement formulated without using a sigma type.

theorem filter.mem_lift_sets {α : Type u_1} {β : Type u_2} {f : filter α} {g : set α} (hg : monotone g) {s : set β} :
s f.lift g ∃ (t : set α) (H : t f), s g t

theorem filter.mem_lift {α : Type u_1} {β : Type u_2} {f : filter α} {g : set α} {s : set β} {t : set α} :
t fs g ts f.lift g

theorem filter.lift_le {α : Type u_1} {β : Type u_2} {f : filter α} {g : set α} {h : filter β} {s : set α} :
s fg s hf.lift g h

theorem filter.le_lift {α : Type u_1} {β : Type u_2} {f : filter α} {g : set α} {h : filter β} :
(∀ (s : set α), s fh g s)h f.lift g

theorem filter.lift_mono {α : Type u_1} {β : Type u_2} {f₁ f₂ : filter α} {g₁ g₂ : set α} :
f₁ f₂g₁ g₂f₁.lift g₁ f₂.lift g₂

theorem filter.lift_mono' {α : Type u_1} {β : Type u_2} {f : filter α} {g₁ g₂ : set α} :
(∀ (s : set α), s fg₁ s g₂ s)f.lift g₁ f.lift g₂

theorem filter.map_lift_eq {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : set α} {m : β → γ} :
(f.lift g) = f.lift g)

theorem filter.comap_lift_eq {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : set α} {m : γ → β} :
(f.lift g) = f.lift g)

theorem filter.comap_lift_eq2 {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {m : β → α} {g : set β} :
f).lift g = f.lift (g

theorem filter.map_lift_eq2 {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : set β} {m : α → β} :
f).lift g = f.lift (g

theorem filter.lift_comm {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : filter β} {h : set αset β} :
f.lift (λ (s : set α), g.lift (h s)) = g.lift (λ (t : set β), f.lift (λ (s : set α), h s t))

theorem filter.lift_assoc {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : set α} {h : set β} :
(f.lift g).lift h = f.lift (λ (s : set α), (g s).lift h)

theorem filter.lift_lift_same_le_lift {α : Type u_1} {β : Type u_2} {f : filter α} {g : set αset α} :
f.lift (λ (s : set α), f.lift (g s)) f.lift (λ (s : set α), g s s)

theorem filter.lift_lift_same_eq_lift {α : Type u_1} {β : Type u_2} {f : filter α} {g : set αset α} :
(∀ (s : set α), monotone (λ (t : set α), g s t))(∀ (t : set α), monotone (λ (s : set α), g s t))f.lift (λ (s : set α), f.lift (g s)) = f.lift (λ (s : set α), g s s)

theorem filter.lift_principal {α : Type u_1} {β : Type u_2} {g : set α} {s : set α} :
(𝓟 s).lift g = g s

theorem filter.monotone_lift {α : Type u_1} {β : Type u_2} {γ : Type u_3} [preorder γ] {f : γ → } {g : γ → set α} :
monotone (λ (c : γ), (f c).lift (g c))

theorem filter.lift_ne_bot_iff {α : Type u_1} {β : Type u_2} {f : filter α} {g : set α} :
((f.lift g).ne_bot ∀ (s : set α), s f(g s).ne_bot)

@[simp]
theorem filter.lift_const {α : Type u_1} {β : Type u_2} {f : filter α} {g : filter β} :
f.lift (λ (x : set α), g) = g

@[simp]
theorem filter.lift_inf {α : Type u_1} {β : Type u_2} {f : filter α} {g h : set α} :
f.lift (λ (x : set α), g x h x) = f.lift g f.lift h

@[simp]
theorem filter.lift_principal2 {α : Type u_1} {f : filter α} :
f.lift 𝓟 = f

theorem filter.lift_infi {α : Type u_1} {β : Type u_2} {ι : Sort u_4} {f : ι → } {g : set α} [hι : nonempty ι] :
(∀ {s t : set α}, g s g t = g (s t))((infi f).lift g = ⨅ (i : ι), (f i).lift g)

def filter.lift' {α : Type u_1} {β : Type u_2} :
(set αset β)

Specialize lift to functions set α → set β. This can be viewed as a generalization of map. This is essentially a push-forward along a function mapping each set to a set.

Equations
theorem filter.mem_lift' {α : Type u_1} {β : Type u_2} {f : filter α} {h : set αset β} {t : set α} :
t fh t f.lift' h

theorem filter.has_basis.lift' {α : Type u_1} {β : Type u_2} {f : filter α} {h : set αset β} {ι : Type u_3} {p : ι → Prop} {s : ι → set α} :
f.has_basis p s(f.lift' h).has_basis p (h s)

theorem filter.mem_lift'_sets {α : Type u_1} {β : Type u_2} {f : filter α} {h : set αset β} (hh : monotone h) {s : set β} :
s f.lift' h ∃ (t : set α) (H : t f), h t s

theorem filter.eventually_lift'_iff {α : Type u_1} {β : Type u_2} {f : filter α} {h : set αset β} (hh : monotone h) {p : β → Prop} :
(∀ᶠ (y : β) in f.lift' h, p y) ∃ (t : set α) (H : t f), ∀ (y : β), y h tp y

theorem filter.lift'_le {α : Type u_1} {β : Type u_2} {f : filter α} {g : set αset β} {h : filter β} {s : set α} :
s f𝓟 (g s) hf.lift' g h

theorem filter.lift'_mono {α : Type u_1} {β : Type u_2} {f₁ f₂ : filter α} {h₁ h₂ : set αset β} :
f₁ f₂h₁ h₂f₁.lift' h₁ f₂.lift' h₂

theorem filter.lift'_mono' {α : Type u_1} {β : Type u_2} {f : filter α} {h₁ h₂ : set αset β} :
(∀ (s : set α), s fh₁ s h₂ s)f.lift' h₁ f.lift' h₂

theorem filter.lift'_cong {α : Type u_1} {β : Type u_2} {f : filter α} {h₁ h₂ : set αset β} :
(∀ (s : set α), s fh₁ s = h₂ s)f.lift' h₁ = f.lift' h₂

theorem filter.map_lift'_eq {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {h : set αset β} {m : β → γ} :
(f.lift' h) = f.lift' h)

theorem filter.map_lift'_eq2 {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : set βset γ} {m : α → β} :
f).lift' g = f.lift' (g

theorem filter.comap_lift'_eq {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {h : set αset β} {m : γ → β} :
(f.lift' h) = f.lift' h)

theorem filter.comap_lift'_eq2 {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {m : β → α} {g : set βset γ} :
f).lift' g = f.lift' (g

theorem filter.lift'_principal {α : Type u_1} {β : Type u_2} {h : set αset β} {s : set α} :
(𝓟 s).lift' h = 𝓟 (h s)

theorem filter.lift'_pure {α : Type u_1} {β : Type u_2} {h : set αset β} {a : α} :
(pure a).lift' h = 𝓟 (h {a})

theorem filter.lift'_bot {α : Type u_1} {β : Type u_2} {h : set αset β} :
.lift' h = 𝓟 (h )

theorem filter.principal_le_lift' {α : Type u_1} {β : Type u_2} {f : filter α} {h : set αset β} {t : set β} :
(∀ (s : set α), s ft h s)𝓟 t f.lift' h

theorem filter.monotone_lift' {α : Type u_1} {β : Type u_2} {γ : Type u_3} [preorder γ] {f : γ → } {g : γ → set αset β} :
monotone (λ (c : γ), (f c).lift' (g c))

theorem filter.lift_lift'_assoc {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : set αset β} {h : set β} :
(f.lift' g).lift h = f.lift (λ (s : set α), h (g s))

theorem filter.lift'_lift'_assoc {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : set αset β} {h : set βset γ} :
(f.lift' g).lift' h = f.lift' (λ (s : set α), h (g s))

theorem filter.lift'_lift_assoc {α : Type u_1} {β : Type u_2} {γ : Type u_3} {f : filter α} {g : set α} {h : set βset γ} :
(f.lift g).lift' h = f.lift (λ (s : set α), (g s).lift' h)

theorem filter.lift_lift'_same_le_lift' {α : Type u_1} {β : Type u_2} {f : filter α} {g : set αset αset β} :
f.lift (λ (s : set α), f.lift' (g s)) f.lift' (λ (s : set α), g s s)

theorem filter.lift_lift'_same_eq_lift' {α : Type u_1} {β : Type u_2} {f : filter α} {g : set αset αset β} :
(∀ (s : set α), monotone (λ (t : set α), g s t))(∀ (t : set α), monotone (λ (s : set α), g s t))f.lift (λ (s : set α), f.lift' (g s)) = f.lift' (λ (s : set α), g s s)

theorem filter.lift'_inf_principal_eq {α : Type u_1} {β : Type u_2} {f : filter α} {h : set αset β} {s : set β} :
f.lift' h 𝓟 s = f.lift' (λ (t : set α), h t s)

theorem filter.lift'_ne_bot_iff {α : Type u_1} {β : Type u_2} {f : filter α} {h : set αset β} :
((f.lift' h).ne_bot ∀ (s : set α), s f(h s).nonempty)

@[simp]
theorem filter.lift'_id {α : Type u_1} {f : filter α} :
f.lift' id = f

theorem filter.le_lift' {α : Type u_1} {β : Type u_2} {f : filter α} {h : set αset β} {g : filter β} :
(∀ (s : set α), s fh s g)g f.lift' h

theorem filter.lift_infi' {α : Type u_1} {β : Type u_2} {ι : Sort u_4} {f : ι → } {g : set α} [nonempty ι] :
((infi f).lift g = ⨅ (i : ι), (f i).lift g)

theorem filter.lift'_infi {α : Type u_1} {β : Type u_2} {ι : Sort u_4} {f : ι → } {g : set αset β} [nonempty ι] :
(∀ {s t : set α}, g s g t = g (s t))((infi f).lift' g = ⨅ (i : ι), (f i).lift' g)

theorem filter.lift'_inf {α : Type u_1} {β : Type u_2} (f g : filter α) {s : set αset β} :
(∀ {t₁ t₂ : set α}, s t₁ s t₂ = s (t₁ t₂))(f g).lift' s = f.lift' s g.lift' s

theorem filter.comap_eq_lift' {α : Type u_1} {β : Type u_2} {f : filter β} {m : α → β} :

theorem filter.lift'_inf_powerset {α : Type u_1} (f g : filter α) :

theorem filter.eventually_lift'_powerset {α : Type u_1} {f : filter α} {p : set α → Prop} :
(∀ᶠ (s : set α) in , p s) ∃ (s : set α) (H : s f), ∀ (t : set α), t sp t

theorem filter.eventually_lift'_powerset' {α : Type u_1} {f : filter α} {p : set α → Prop} :
(∀ ⦃s t : set α⦄, s tp tp s)((∀ᶠ (s : set α) in , p s) ∃ (s : set α) (H : s f), p s)

@[instance]
def filter.lift'_powerset_ne_bot {α : Type u_1} (f : filter α) :

theorem filter.tendsto_lift'_powerset_mono {α : Type u_1} {β : Type u_2} {la : filter α} {lb : filter β} {s t : α → set β} :
la (lb.lift' set.powerset)(∀ᶠ (x : α) in la, s x t x) la (lb.lift' set.powerset)

@[simp]
theorem filter.eventually_lift'_powerset_forall {α : Type u_1} {f : filter α} {p : α → Prop} :
(∀ᶠ (s : set α) in , ∀ (x : α), x sp x) ∀ᶠ (x : α) in f, p x

theorem filter.eventually.lift'_powerset {α : Type u_1} {f : filter α} {p : α → Prop} :
(∀ᶠ (x : α) in f, p x)(∀ᶠ (s : set α) in , ∀ (x : α), x sp x)

Alias of eventually_lift'_powerset_forall.

theorem filter.eventually.of_lift'_powerset {α : Type u_1} {f : filter α} {p : α → Prop} :
(∀ᶠ (s : set α) in , ∀ (x : α), x sp x)(∀ᶠ (x : α) in f, p x)

Alias of eventually_lift'_powerset_forall.

@[simp]
theorem filter.eventually_lift'_powerset_eventually {α : Type u_1} {f g : filter α} {p : α → Prop} :
(∀ᶠ (s : set α) in , ∀ᶠ (x : α) in g, x sp x) ∀ᶠ (x : α) in f g, p x

theorem filter.prod_def {α : Type u_1} {β : Type u_2} {f : filter α} {g : filter β} :
f ×ᶠ g = f.lift (λ (s : set α), g.lift' s.prod)

theorem filter.prod_same_eq {α : Type u_1} {f : filter α} :
f ×ᶠ f = f.lift' (λ (t : set α), t.prod t)

theorem filter.mem_prod_same_iff {α : Type u_1} {f : filter α} {s : set × α)} :
s f ×ᶠ f ∃ (t : set α) (H : t f), t.prod t s

theorem filter.tendsto_prod_self_iff {α : Type u_1} {β : Type u_2} {f : α × α → β} {x : filter α} {y : filter β} :
(x ×ᶠ x) y ∀ (W : set β), W y(∃ (U : set α) (H : U x), ∀ (x x' : α), x Ux' Uf (x, x') W)

theorem filter.prod_lift_lift {α₁ : Type u_5} {α₂ : Type u_6} {β₁ : Type u_7} {β₂ : Type u_8} {f₁ : filter α₁} {f₂ : filter α₂} {g₁ : set α₁filter β₁} {g₂ : set α₂filter β₂} :
monotone g₁monotone g₂f₁.lift g₁ ×ᶠ f₂.lift g₂ = f₁.lift (λ (s : set α₁), f₂.lift (λ (t : set α₂), g₁ s ×ᶠ g₂ t))

theorem filter.prod_lift'_lift' {α₁ : Type u_5} {α₂ : Type u_6} {β₁ : Type u_7} {β₂ : Type u_8} {f₁ : filter α₁} {f₂ : filter α₂} {g₁ : set α₁set β₁} {g₂ : set α₂set β₂} :
monotone g₁monotone g₂f₁.lift' g₁ ×ᶠ f₂.lift' g₂ = f₁.lift (λ (s : set α₁), f₂.lift' (λ (t : set α₂), (g₁ s).prod (g₂ t)))