Common — library colibrilib.dv — module RealSets

Sets of reals (as set.Set) and the sets built by an operation on the reals: the concrete semantics that the specifications of the domains compare with.

162
module RealSets
163
use real.RealInfix
164
use set.Set as S
165
use map.MapExt

Two sets with the same elements are equal

  Valid (21ms) (cvc5)
168
let ghost
set_ext
(s1 s2: S.set 'a) : unit
169
requires { forall x. S.mem x s1 <-> S.mem x s2 }
170
ensures { s1 = s2 }
171
= {proof…} assert { s1 == s2 };
172
MapExt.extensionality s1 s2 {qed}

The image of s by f

175
function
image
(f: 'a -> 'b) (s: S.set 'a) : S.set 'b =
176
fun y -> exists x. S.mem x s /\ y = f x

The values of f x y for x in s1 and y in s2

179
function
map2
(f: 'a -> 'b -> 'c) (s1: S.set 'a) (s2: S.set 'b) : S.set 'c =
180
fun z -> exists x y. S.mem x s1 /\ S.mem y s2 /\ z = f x y

The same, for y different from zero

183
function
map2nz
(f: real -> real -> real) (s1 s2: S.set real) : S.set real =
184
fun z -> exists x y. S.mem x s1 /\ S.mem y s2 /\ y <> 0.0 /\ z = f x y

The y such that f y is in s

187
function
preimage
(f: 'a -> 'b) (s: S.set 'b) : S.set 'a =
188
fun y -> S.mem (f y) s

The x such that x * y is in sr for a y in sb

191
function
pre_mul
(sb sr: S.set real) : S.set real =
192
fun x -> exists y. S.mem y sb /\ S.mem (x *. y) sr

t is the image of s by f when f maps s into t and has an inverse g that maps t into s

  Valid (36ms) (colibri2)
196
let ghost
image_bij
(f g: 'a -> 'a) (s t: S.set 'a) : unit
197
requires { forall y. S.mem y s -> S.mem (f y) t }
198
requires { forall x. S.mem x t -> S.mem (g x) s }
199
requires { forall x. f (g x) = x }
200
ensures { t = image f s }
201
= {proof…} let lemma pw (x: 'a) : unit
202
ensures { S.mem x t <-> S.mem x (image f s) }
203
= () in
204
set_ext t (image f s) {qed}
205
Valid (18ms) (colibri2)
206
let ghost
image_sound
(f: 'a -> 'b) (s: S.set 'a) (t: S.set 'b) : unit
207
requires { forall x. S.mem x s -> S.mem (f x) t }
208
ensures { S.subset (image f s) t }
209
= ()
210
Valid (21ms) (colibri2)
211
let ghost
map2_sound
(f: 'a -> 'b -> 'c) (s1: S.set 'a) (s2: S.set 'b) (t: S.set 'c) : unit
212
requires { forall x y. S.mem x s1 -> S.mem y s2 -> S.mem (f x y) t }
213
ensures { S.subset (map2 f s1 s2) t }
214
= ()
215
Valid (22ms) (colibri2)
216
let ghost
map2nz_sound
(f: real -> real -> real) (s1 s2 t: S.set real) : unit
217
requires { forall x y. S.mem x s1 -> S.mem y s2 -> y <> 0.0 -> S.mem (f x y) t }
218
ensures { S.subset (map2nz f s1 s2) t }
219
= ()
220
end