Zulip Chat Archive

Stream: new members

Topic: Induction over sigma in filters


view this post on Zulip Aria Miuk (Jan 07 2020 at 20:10):

Hello, could anyone please point me in a good direction wrt. a proof using dependent types - I am not quite used to working with them. It seems to me my approach from non--dependent scenario is completely inapplicable within the realm of dependent types.

The basic version of the theorem is as follows. (I shall just use Lean for brevity.)

import data.list
open list

variables
    {α : Type} {l : list α} [decidable_eq α]
    {P : α  Prop} [decidable_pred P]
    {Q : α  Prop} [decidable_pred Q]
    {R : α  Prop} [decidable_pred R]

lemma filter_partition (h : x, ¬Q x  R x) :
    length (filter P l) = length (filter P (filter Q l)) + length (filter P (filter R l)) :=
begin
  induction l with hd,
    {simp only [add_zero, list.filter_nil, list.length]},
    {
      by_cases h₁ : R hd,
        {
          have : ¬Q hd, from (h _).2 h₁,
          by_cases h₂ : P hd; simp*,
        },
        {
          have : Q hd, from (not_iff_comm.1 (h _)).1 h₁,
          by_cases h₂ : P hd; simp*
        }
    }
end

I included the proof to show what idea doesn't seem to translate (as far as I can tell) into the following version.

lemma filter_partition_dependent
  {P : {x // x  l}  Prop} [decidable_pred P]
  (h : x, ¬Q x  R x) :
  length (filter (λ (x : {x // x  l}), P x) (attach l)) =
  length (filter (λ (x : {x // x  filter Q l}), P x.1, mem_of_mem_filter x.2) (attach (filter Q l))) +
  length (filter (λ (x : {x // x  filter R l}), P x.1, mem_of_mem_filter x.2) (attach (filter R l))) :=
begin
  resetI, induction l with hd tl ih,
    {simp [attach]},
    {
      -- ih : ∀ {P : {x // x ∈ tl} → Prop}
    }
end

This version is not much different. I promoted the original P : α → Prop to P : {x // x ∈ l} → Prop,
which means I had to use attached versions of lists. The filtered lists also need a proof that a ∈ filter p l → a ∈ l.

The problem is that the original proof by induction on l (with hd :: tl in the inductive case) appears to no longer work, because the inductive hypothesis wants P : {x // x ∈ tl} → Prop and I only have P : {x // x ∈ hd :: tl} → Prop.
I tried synthesizing one from P but the conclusion still has the original P that also considers the head.
I can't think of a way to actually successfully use induction here - do I need some filter congruence lemmas?
These seem to only work in "homogeneous" settings with filtering predicates of equivalent types.

Could someone please suggest an alternative way to prove this? Or am I missing something here, have I managed to make the theorem false?
Here's also a link to the web editor which conveniently contains a minimal compilable example - I am not sure how Zulip handles long URLs so I made a pastebin of the link. https://pastebin.com/raw/grX324K2

view this post on Zulip Kevin Buzzard (Jan 07 2020 at 23:27):

I am not a computer scientist but I think I'd be tempted to look for a result in the library of the following form: if L : list X and there's a map f: X -> Y and a predicate Q on Y then map f (filter (Q o f) L) = filter Q (map f L), and then use the fact that list.map doesn't change length, let Q be "if x is in l then P(x) else false" and muddle on from there.

view this post on Zulip Aria Miuk (Jan 07 2020 at 23:36):

Thank you Kevin, I will give it a try! I've been very much "stuck" in the inductive mindset as conceptually it seems like the most obvious thing to do. Surely tagging along "that" obvious properly shouldn't change the way the proof can be done but the more I struggle with it, the more impossible the inductive proof seems to be. Actually understanding why this happens could come in handy.

view this post on Zulip Mario Carneiro (Jan 07 2020 at 23:55):

You can't prove things about attach by induction. You have to generalize it, in the same way that attach itself is generalized, to pmap

view this post on Zulip Aria Miuk (Jan 08 2020 at 00:00):

Is this a common "theme" within the realm of dependent types? I can't even formulate this question more specifically - it just appears to be clear that this is not specific to attach only.

view this post on Zulip Mario Carneiro (Jan 08 2020 at 00:13):

I think something like this will work:

lemma filter_partition_dependent'
  {β} {P : β  Prop} [decidable_pred P]
  (h : x, ¬Q x  R x)
  (p : α  Prop) (f :  a, p a  β)
  {β₁} (i₁ : β₁  β) (p₁ : α  Prop) (f₁ :  a, p₁ a  β₁)
  {β₂} (i₂ : β₂  β) (p₂ : α  Prop) (f₂ :  a, p₂ a  β₂) :
   (H :  (a : α), a  l  p a)
    (H₁ :  (a : α), a  filter Q l  p₁ a)
    (H₂ :  (a : α), a  filter R l  p₂ a),
  length (filter P (pmap f l H)) =
  length (filter (λ x, P (i₁ x)) (pmap f₁ (filter Q l) H₁)) +
  length (filter (λ x, P (i₂ x)) (pmap f₂ (filter R l) H₂)) :=

view this post on Zulip Mario Carneiro (Jan 08 2020 at 00:14):

there may be more hypotheses needed

view this post on Zulip Mario Carneiro (Jan 08 2020 at 00:15):

But this is assuming you actually want a direct inductive proof. It is quite likely that Kevin's suggestion of stringing together other lemmas will work here

view this post on Zulip Aria Miuk (Jan 08 2020 at 00:16):

Interesting. Thanks everyone kindly for the suggestions, very appreciated.

view this post on Zulip Mario Carneiro (Jan 08 2020 at 00:18):

Note that this is a direct generalization of the target statement, like so:

lemma filter_partition_dependent
  {P : {x // x  l}  Prop} [decidable_pred P]
  (h : x, ¬Q x  R x) :
  length (filter P (attach l)) =
  length (filter (λ (x : {x // x  filter Q l}), P x.1, mem_of_mem_filter x.2) (attach (filter Q l))) +
  length (filter (λ (x : {x // x  filter R l}), P x.1, mem_of_mem_filter x.2) (attach (filter R l))) :=
filter_partition_dependent' h _ _ _ _ _ _ _ _ _ _ _

view this post on Zulip Aria Miuk (Jan 08 2020 at 00:20):

I am not sure how I feel about dependent type right now, there's a lot to process. I read a quote on Coq along the lines of "Coq has a very powerful type system. But don't use it." and perhaps I am starting to see as to why that would be the case.

view this post on Zulip Mario Carneiro (Jan 08 2020 at 00:40):

I can get behind that quote


Last updated: May 18 2021 at 16:25 UTC