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 |