src/HOL/Real/HahnBanach/FunctionOrder.thy
changeset 27612 d3eb431db035
parent 25762 c03e9d04b3e4
equal deleted inserted replaced
27611:2c01c0bdb385 27612:d3eb431db035
     3     Author:     Gertrud Bauer, TU Munich
     3     Author:     Gertrud Bauer, TU Munich
     4 *)
     4 *)
     5 
     5 
     6 header {* An order on functions *}
     6 header {* An order on functions *}
     7 
     7 
     8 theory FunctionOrder imports Subspace Linearform begin
     8 theory FunctionOrder
       
     9 imports Subspace Linearform
       
    10 begin
     9 
    11 
    10 subsection {* The graph of a function *}
    12 subsection {* The graph of a function *}
    11 
    13 
    12 text {*
    14 text {*
    13   We define the \emph{graph} of a (real) function @{text f} with
    15   We define the \emph{graph} of a (real) function @{text f} with
    25 definition
    27 definition
    26   graph :: "'a set \<Rightarrow> ('a \<Rightarrow> real) \<Rightarrow> 'a graph" where
    28   graph :: "'a set \<Rightarrow> ('a \<Rightarrow> real) \<Rightarrow> 'a graph" where
    27   "graph F f = {(x, f x) | x. x \<in> F}"
    29   "graph F f = {(x, f x) | x. x \<in> F}"
    28 
    30 
    29 lemma graphI [intro]: "x \<in> F \<Longrightarrow> (x, f x) \<in> graph F f"
    31 lemma graphI [intro]: "x \<in> F \<Longrightarrow> (x, f x) \<in> graph F f"
    30   by (unfold graph_def) blast
    32   unfolding graph_def by blast
    31 
    33 
    32 lemma graphI2 [intro?]: "x \<in> F \<Longrightarrow> \<exists>t \<in> graph F f. t = (x, f x)"
    34 lemma graphI2 [intro?]: "x \<in> F \<Longrightarrow> \<exists>t \<in> graph F f. t = (x, f x)"
    33   by (unfold graph_def) blast
    35   unfolding graph_def by blast
    34 
    36 
    35 lemma graphE [elim?]:
    37 lemma graphE [elim?]:
    36     "(x, y) \<in> graph F f \<Longrightarrow> (x \<in> F \<Longrightarrow> y = f x \<Longrightarrow> C) \<Longrightarrow> C"
    38     "(x, y) \<in> graph F f \<Longrightarrow> (x \<in> F \<Longrightarrow> y = f x \<Longrightarrow> C) \<Longrightarrow> C"
    37   by (unfold graph_def) blast
    39   unfolding graph_def by blast
    38 
    40 
    39 
    41 
    40 subsection {* Functions ordered by domain extension *}
    42 subsection {* Functions ordered by domain extension *}
    41 
    43 
    42 text {*
    44 text {*
    45 *}
    47 *}
    46 
    48 
    47 lemma graph_extI:
    49 lemma graph_extI:
    48   "(\<And>x. x \<in> H \<Longrightarrow> h x = h' x) \<Longrightarrow> H \<subseteq> H'
    50   "(\<And>x. x \<in> H \<Longrightarrow> h x = h' x) \<Longrightarrow> H \<subseteq> H'
    49     \<Longrightarrow> graph H h \<subseteq> graph H' h'"
    51     \<Longrightarrow> graph H h \<subseteq> graph H' h'"
    50   by (unfold graph_def) blast
    52   unfolding graph_def by blast
    51 
    53 
    52 lemma graph_extD1 [dest?]:
    54 lemma graph_extD1 [dest?]:
    53   "graph H h \<subseteq> graph H' h' \<Longrightarrow> x \<in> H \<Longrightarrow> h x = h' x"
    55   "graph H h \<subseteq> graph H' h' \<Longrightarrow> x \<in> H \<Longrightarrow> h x = h' x"
    54   by (unfold graph_def) blast
    56   unfolding graph_def by blast
    55 
    57 
    56 lemma graph_extD2 [dest?]:
    58 lemma graph_extD2 [dest?]:
    57   "graph H h \<subseteq> graph H' h' \<Longrightarrow> H \<subseteq> H'"
    59   "graph H h \<subseteq> graph H' h' \<Longrightarrow> H \<subseteq> H'"
    58   by (unfold graph_def) blast
    60   unfolding graph_def by blast
    59 
    61 
    60 
    62 
    61 subsection {* Domain and function of a graph *}
    63 subsection {* Domain and function of a graph *}
    62 
    64 
    63 text {*
    65 text {*
    79 *}
    81 *}
    80 
    82 
    81 lemma graph_domain_funct:
    83 lemma graph_domain_funct:
    82   assumes uniq: "\<And>x y z. (x, y) \<in> g \<Longrightarrow> (x, z) \<in> g \<Longrightarrow> z = y"
    84   assumes uniq: "\<And>x y z. (x, y) \<in> g \<Longrightarrow> (x, z) \<in> g \<Longrightarrow> z = y"
    83   shows "graph (domain g) (funct g) = g"
    85   shows "graph (domain g) (funct g) = g"
    84 proof (unfold domain_def funct_def graph_def, auto)  (* FIXME !? *)
    86   unfolding domain_def funct_def graph_def
       
    87 proof auto  (* FIXME !? *)
    85   fix a b assume g: "(a, b) \<in> g"
    88   fix a b assume g: "(a, b) \<in> g"
    86   from g show "(a, SOME y. (a, y) \<in> g) \<in> g" by (rule someI2)
    89   from g show "(a, SOME y. (a, y) \<in> g) \<in> g" by (rule someI2)
    87   from g show "\<exists>y. (a, y) \<in> g" ..
    90   from g show "\<exists>y. (a, y) \<in> g" ..
    88   from g show "b = (SOME y. (a, y) \<in> g)"
    91   from g show "b = (SOME y. (a, y) \<in> g)"
    89   proof (rule some_equality [symmetric])
    92   proof (rule some_equality [symmetric])
   117 lemma norm_pres_extensionE [elim]:
   120 lemma norm_pres_extensionE [elim]:
   118   "g \<in> norm_pres_extensions E p F f
   121   "g \<in> norm_pres_extensions E p F f
   119   \<Longrightarrow> (\<And>H h. g = graph H h \<Longrightarrow> linearform H h
   122   \<Longrightarrow> (\<And>H h. g = graph H h \<Longrightarrow> linearform H h
   120         \<Longrightarrow> H \<unlhd> E \<Longrightarrow> F \<unlhd> H \<Longrightarrow> graph F f \<subseteq> graph H h
   123         \<Longrightarrow> H \<unlhd> E \<Longrightarrow> F \<unlhd> H \<Longrightarrow> graph F f \<subseteq> graph H h
   121         \<Longrightarrow> \<forall>x \<in> H. h x \<le> p x \<Longrightarrow> C) \<Longrightarrow> C"
   124         \<Longrightarrow> \<forall>x \<in> H. h x \<le> p x \<Longrightarrow> C) \<Longrightarrow> C"
   122   by (unfold norm_pres_extensions_def) blast
   125   unfolding norm_pres_extensions_def by blast
   123 
   126 
   124 lemma norm_pres_extensionI2 [intro]:
   127 lemma norm_pres_extensionI2 [intro]:
   125   "linearform H h \<Longrightarrow> H \<unlhd> E \<Longrightarrow> F \<unlhd> H
   128   "linearform H h \<Longrightarrow> H \<unlhd> E \<Longrightarrow> F \<unlhd> H
   126     \<Longrightarrow> graph F f \<subseteq> graph H h \<Longrightarrow> \<forall>x \<in> H. h x \<le> p x
   129     \<Longrightarrow> graph F f \<subseteq> graph H h \<Longrightarrow> \<forall>x \<in> H. h x \<le> p x
   127     \<Longrightarrow> graph H h \<in> norm_pres_extensions E p F f"
   130     \<Longrightarrow> graph H h \<in> norm_pres_extensions E p F f"
   128   by (unfold norm_pres_extensions_def) blast
   131   unfolding norm_pres_extensions_def by blast
   129 
   132 
   130 lemma norm_pres_extensionI:  (* FIXME ? *)
   133 lemma norm_pres_extensionI:  (* FIXME ? *)
   131   "\<exists>H h. g = graph H h
   134   "\<exists>H h. g = graph H h
   132     \<and> linearform H h
   135     \<and> linearform H h
   133     \<and> H \<unlhd> E
   136     \<and> H \<unlhd> E
   134     \<and> F \<unlhd> H
   137     \<and> F \<unlhd> H
   135     \<and> graph F f \<subseteq> graph H h
   138     \<and> graph F f \<subseteq> graph H h
   136     \<and> (\<forall>x \<in> H. h x \<le> p x) \<Longrightarrow> g \<in> norm_pres_extensions E p F f"
   139     \<and> (\<forall>x \<in> H. h x \<le> p x) \<Longrightarrow> g \<in> norm_pres_extensions E p F f"
   137   by (unfold norm_pres_extensions_def) blast
   140   unfolding norm_pres_extensions_def by blast
   138 
   141 
   139 end
   142 end