Theory Minimal_Bad_Sequences

(*  Title:      Well-Quasi-Orders
    Author:     Christian Sternagel <>
    Maintainer: Christian Sternagel
    License:    LGPL

section ‹Constructing Minimal Bad Sequences›

theory Minimal_Bad_Sequences

text ‹
  A locale capturing the construction of minimal bad sequences over values from @{term "A"}. Where
  minimality is to be understood w.r.t.\ @{term size} of an element.
locale mbs =
  fixes A :: "('a :: size) set"

text ‹
  Since the @{term size} is a well-founded measure, whenever some element satisfies a property
  @{term P}, then there is a size-minimal such element.
lemma minimal:
  assumes "x  A" and "P x"
  shows "y  A. size y  size x  P y  (z  A. size z < size y  ¬ P z)"
using assms
proof (induction x taking: size rule: measure_induct)
  case (1 x)
  then show ?case
  proof (cases "y  A. size y < size x  ¬ P y")
    case True
    with 1 show ?thesis by blast
    case False
    then obtain y where "y  A" and "size y < size x" and "P y" by blast
    with "1.IH" show ?thesis by (fastforce elim!: order_trans)

lemma less_not_eq [simp]:
  "x  A  size x < size y  x = y  False"
  by simp

text ‹
  The set of all bad sequences over @{term A}.
definition "BAD P = {f  SEQ A. bad P f}"

lemma BAD_iff [iff]:
  "f  BAD P  (i. f i  A)  bad P f"
  by (auto simp: BAD_def)

text ‹
  A partial order on infinite bad sequences.
definition geseq :: "((nat  'a) × (nat  'a)) set"
  "geseq =
    {(f, g). f  SEQ A  g  SEQ A  (f = g  (i. size (g i) < size (f i)  (j < i. f j = g j)))}"

text ‹
  The strict part of the above order.
definition gseq :: "((nat  'a) × (nat  'a)) set" where
  "gseq = {(f, g). f  SEQ A  g  SEQ A  (i. size (g i) < size (f i)  (j < i. f j = g j))}"

lemma geseq_iff:
  "(f, g)  geseq 
    f  SEQ A  g  SEQ A  (f = g  (i. size (g i) < size (f i)  (j < i. f j = g j)))"
  by (auto simp: geseq_def)

lemma gseq_iff:
  "(f, g)  gseq  f  SEQ A  g  SEQ A  (i. size (g i) < size (f i)  (j < i. f j = g j))"
  by (auto simp: gseq_def)

lemma geseqE:
  assumes "(f, g)  geseq"
    and "i. f i  A; i. g i  A; f = g  Q"
    and "i. i. f i  A; i. g i  A; size (g i) < size (f i); j < i. f j = g j  Q"
  shows "Q"
  using assms by (auto simp: geseq_iff)

lemma gseqE:
  assumes "(f, g)  gseq"
    and "i. i. f i  A; i. g i  A; size (g i) < size (f i); j < i. f j = g j  Q"
  shows "Q"
  using assms by (auto simp: gseq_iff)

sublocale min_elt_size?: minimal_element "measure_on size UNIV" A
rewrites "measure_on size UNIV  λx y. size x < size y"
apply (unfold_locales)
apply (auto simp: po_on_def irreflp_on_def transp_on_def simp del: wfp_on_UNIV intro: wfp_on_subset)
apply (auto simp: measure_on_def inv_image_betw_def)

  fixes P :: "'a  'a  bool"

text ‹
  A lower bound to all sequences in a set of sequences @{term B}.
abbreviation "lb  lexmin (BAD P)"

lemma eq_upto_BAD_mem:
  assumes "f  eq_upto (BAD P) g i"
  shows "f j  A"
  using assms by (auto)

text ‹
  Assume that there is some infinite bad sequence @{term h}.
  fixes h :: "nat  'a"
  assumes BAD_ex: "h  BAD P"

text ‹
  When there is a bad sequence, then filtering @{term "BAD P"} w.r.t.~positions in @{term lb} never
  yields an empty set of sequences.
lemma eq_upto_BAD_non_empty:
  "eq_upto (BAD P) lb i  {}"
using eq_upto_lexmin_non_empty [of "BAD P"] and BAD_ex by auto

lemma non_empty_ith:
  shows "ith (eq_upto (BAD P) lb i) i  A"
  and "ith (eq_upto (BAD P) lb i) i  {}"
  using eq_upto_BAD_non_empty [of i] by auto

  lb_minimal = min_elt_minimal [OF non_empty_ith, folded lexmin] and
  lb_mem = min_elt_mem [OF non_empty_ith, folded lexmin]

text @{term "lb"} is a infinite bad sequence.
lemma lb_BAD:
  "lb  BAD P"
proof -
  have *: "j. lb j  ith (eq_upto (BAD P) lb j) j" by (rule lb_mem)
  then have "i. lb i  A" by (auto simp: ith_conv) (metis eq_upto_BAD_mem)
  { assume "good P lb"
    then obtain i j where "i < j" and "P (lb i) (lb j)" by (auto simp: good_def)
    from * have "lb j  ith (eq_upto (BAD P) lb j) j" by (auto)
    then obtain g where "g  eq_upto (BAD P) lb j" and "g j = lb j" by force
    then have "k  j. g k = lb k" by (auto simp: order_le_less)
    with i < j and P (lb i) (lb j) have "P (g i) (g j)" by auto
    with i < j have "good P g" by (auto simp: good_def)
    with g  eq_upto (BAD P) lb j have False by auto }
  ultimately show ?thesis by blast

text ‹
  There is no infinite bad sequence that is strictly smaller than @{term lb}.
lemma lb_lower_bound:
  "g. (lb, g)  gseq  g  BAD P"
proof (intro allI impI)
  fix g
  assume "(lb, g)  gseq"
  then obtain i where "g i  A" and "size (g i) < size (lb i)"
    and "j < i. lb j = g j" by (auto simp: gseq_iff)
  moreover with lb_minimal
    have "g i  ith (eq_upto (BAD P) lb i) i" by auto
  ultimately show "g  BAD P" by blast

text ‹
  If there is at least one bad sequence, then there is also a minimal one.
lemma lower_bound_ex:
  "f  BAD P. g. (f, g)  gseq  g  BAD P"
  using lb_BAD and lb_lower_bound by blast

lemma gseq_conv:
  "(f, g)  gseq  f  g  (f, g)  geseq"
  by (auto simp: gseq_def geseq_def dest: less_not_eq)

text ‹There is a minimal bad sequence.›
lemma mbs:
  "f  BAD P. g. (f, g)  gseq  good P g"
  using lower_bound_ex by (auto simp: gseq_conv geseq_iff)