(************************************************************************)
(*         *   The Coq Proof Assistant / The Coq Development Team       *)
(*  v      *   INRIA, CNRS and contributors - Copyright 1999-2018       *)
(* <O___,, *       (see CREDITS file for the list of authors)           *)
(*   \VV/  **************************************************************)
(*    //   *    This file is distributed under the terms of the         *)
(*         *     GNU Lesser General Public License Version 2.1          *)
(*         *     (see LICENSE file for the text of the license)         *)
(************************************************************************)
(****************************************************************************)
(*                                                                          *)
(*                         Naive Set Theory in Coq                          *)
(*                                                                          *)
(*                     INRIA                        INRIA                   *)
(*              Rocquencourt                        Sophia-Antipolis        *)
(*                                                                          *)
(*                                 Coq V6.1                                 *)
(*									    *)
(*			         Gilles Kahn 				    *)
(*				 Gerard Huet				    *)
(*									    *)
(*									    *)
(*                                                                          *)
(* Acknowledgments: This work was started in July 1993 by F. Prost. Thanks  *)
(* to the Newton Institute for providing an exceptional work environment    *)
(* in Summer 1995. Several developments by E. Ledinot were an inspiration.  *)
(****************************************************************************)

Require Export Ensembles.
Require Export Relations_1.
Require Export Relations_1_facts.
Require Export Partial_Order.
Require Export Cpo.

Section The_power_set_partial_order.
Variable U : Type.

Inductive Power_set (A:Ensemble U) : Ensemble (Ensemble U) :=
    Definition_of_Power_set :
      forall X:Ensemble U, Included U X A -> In (Ensemble U) (Power_set A) X.
Hint Resolve Definition_of_Power_set : core.

Theorem Empty_set_minimal : forall X:Ensemble U, Included U (Empty_set U) X.
U:Type
forall X : Ensemble U, Included U (Empty_set U) X
intro X; red.
U:Type
X:Ensemble U
forall x : U, In U (Empty_set U) x -> In U X x
intros x H'; elim H'.
Qed.
Hint Resolve Empty_set_minimal : core.

Theorem Power_set_Inhabited :
 forall X:Ensemble U, Inhabited (Ensemble U) (Power_set X).
U:Type
forall X : Ensemble U,
Inhabited (Ensemble U) (Power_set X)
intro X.
U:Type
X:Ensemble U
Inhabited (Ensemble U) (Power_set X)
apply Inhabited_intro with (Empty_set U); auto with sets.
Qed.
Hint Resolve Power_set_Inhabited : core.

Theorem Inclusion_is_an_order : Order (Ensemble U) (Included U).
U:Type
Order (Ensemble U) (Included U)
auto 6 with sets.
Qed.
Hint Resolve Inclusion_is_an_order : core.

Theorem Inclusion_is_transitive : Transitive (Ensemble U) (Included U).
U:Type
Transitive (Ensemble U) (Included U)
elim Inclusion_is_an_order; auto with sets.
Qed.
Hint Resolve Inclusion_is_transitive : core.

Definition Power_set_PO : Ensemble U -> PO (Ensemble U).
U:Type
Ensemble U -> PO (Ensemble U)
intro A; try assumption.
U:Type
A:Ensemble U
PO (Ensemble U)
apply Definition_of_PO with (Power_set A) (Included U); auto with sets.
Defined.
Hint Unfold Power_set_PO : core.

Theorem Strict_Rel_is_Strict_Included :
 same_relation (Ensemble U) (Strict_Included U)
   (Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U))).
U:Type
same_relation (Ensemble U) (Strict_Included U)
  (Strict_Rel_of (Ensemble U)
     (Power_set_PO (Full_set U)))
auto with sets.
Qed.
Hint Resolve Strict_Rel_Transitive Strict_Rel_is_Strict_Included : core.

Lemma Strict_inclusion_is_transitive_with_inclusion :
 forall x y z:Ensemble U,
   Strict_Included U x y -> Included U y z -> Strict_Included U x z.
U:Type
forall x y z : Ensemble U,
Strict_Included U x y ->
Included U y z -> Strict_Included U x z
intros x y z H' H'0; try assumption.
U:Type
x, y, z:Ensemble U
H':Strict_Included U x y
H'0:Included U y z
Strict_Included U x z
elim Strict_Rel_is_Strict_Included.
U:Type
x, y, z:Ensemble U
H':Strict_Included U x y
H'0:Included U y z
contains (Ensemble U) (Strict_Included U)
  (Strict_Rel_of (Ensemble U)
     (Power_set_PO (Full_set U))) ->
contains (Ensemble U)
  (Strict_Rel_of (Ensemble U)
     (Power_set_PO (Full_set U))) (Strict_Included U) ->
Strict_Included U x z
unfold contains.
U:Type
x, y, z:Ensemble U
H':Strict_Included U x y
H'0:Included U y z
(forall x0 y0 : Ensemble U,
 Strict_Rel_of (Ensemble U)
   (Power_set_PO (Full_set U)) x0 y0 ->
 Strict_Included U x0 y0) ->
(forall x0 y0 : Ensemble U,
 Strict_Included U x0 y0 ->
 Strict_Rel_of (Ensemble U)
   (Power_set_PO (Full_set U)) x0 y0) ->
Strict_Included U x z
intros H'1 H'2; try assumption.
U:Type
x, y, z:Ensemble U
H':Strict_Included U x y
H'0:Included U y z
H'1:forall x0 y0 : Ensemble U,
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)) x0 y0 ->
Strict_Included U x0 y0
H'2:forall x0 y0 : Ensemble U,
Strict_Included U x0 y0 ->
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)) x0 y0
Strict_Included U x z
apply H'1.
U:Type
x, y, z:Ensemble U
H':Strict_Included U x y
H'0:Included U y z
H'1:forall x0 y0 : Ensemble U,
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)) x0 y0 ->
Strict_Included U x0 y0
H'2:forall x0 y0 : Ensemble U,
Strict_Included U x0 y0 ->
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)) x0 y0
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U))
  x z
apply Strict_Rel_Transitive_with_Rel with (y := y); auto with sets.
Qed.

Lemma Strict_inclusion_is_transitive_with_inclusion_left :
 forall x y z:Ensemble U,
   Included U x y -> Strict_Included U y z -> Strict_Included U x z.
U:Type
forall x y z : Ensemble U,
Included U x y ->
Strict_Included U y z -> Strict_Included U x z
intros x y z H' H'0; try assumption.
U:Type
x, y, z:Ensemble U
H':Included U x y
H'0:Strict_Included U y z
Strict_Included U x z
elim Strict_Rel_is_Strict_Included.
U:Type
x, y, z:Ensemble U
H':Included U x y
H'0:Strict_Included U y z
contains (Ensemble U) (Strict_Included U)
  (Strict_Rel_of (Ensemble U)
     (Power_set_PO (Full_set U))) ->
contains (Ensemble U)
  (Strict_Rel_of (Ensemble U)
     (Power_set_PO (Full_set U))) (Strict_Included U) ->
Strict_Included U x z
unfold contains.
U:Type
x, y, z:Ensemble U
H':Included U x y
H'0:Strict_Included U y z
(forall x0 y0 : Ensemble U,
 Strict_Rel_of (Ensemble U)
   (Power_set_PO (Full_set U)) x0 y0 ->
 Strict_Included U x0 y0) ->
(forall x0 y0 : Ensemble U,
 Strict_Included U x0 y0 ->
 Strict_Rel_of (Ensemble U)
   (Power_set_PO (Full_set U)) x0 y0) ->
Strict_Included U x z
intros H'1 H'2; try assumption.
U:Type
x, y, z:Ensemble U
H':Included U x y
H'0:Strict_Included U y z
H'1:forall x0 y0 : Ensemble U,
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)) x0 y0 ->
Strict_Included U x0 y0
H'2:forall x0 y0 : Ensemble U,
Strict_Included U x0 y0 ->
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)) x0 y0
Strict_Included U x z
apply H'1.
U:Type
x, y, z:Ensemble U
H':Included U x y
H'0:Strict_Included U y z
H'1:forall x0 y0 : Ensemble U,
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)) x0 y0 ->
Strict_Included U x0 y0
H'2:forall x0 y0 : Ensemble U,
Strict_Included U x0 y0 ->
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)) x0 y0
Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U))
  x z
apply Strict_Rel_Transitive_with_Rel_left with (y := y); auto with sets.
Qed.

Lemma Strict_inclusion_is_transitive :
 Transitive (Ensemble U) (Strict_Included U).
U:Type
Transitive (Ensemble U) (Strict_Included U)
apply cong_transitive_same_relation with
 (R := Strict_Rel_of (Ensemble U) (Power_set_PO (Full_set U)));
 auto with sets.
Qed.

Theorem Empty_set_is_Bottom :
 forall A:Ensemble U, Bottom (Ensemble U) (Power_set_PO A) (Empty_set U).
U:Type
forall A : Ensemble U,
Bottom (Ensemble U) (Power_set_PO A) (Empty_set U)
intro A; apply Bottom_definition; simpl; auto with sets.
Qed.
Hint Resolve Empty_set_is_Bottom : core.

Theorem Union_minimal :
 forall a b X:Ensemble U,
   Included U a X -> Included U b X -> Included U (Union U a b) X.
U:Type
forall a b X : Ensemble U,
Included U a X ->
Included U b X -> Included U (Union U a b) X
intros a b X H' H'0; red.
U:Type
a, b, X:Ensemble U
H':Included U a X
H'0:Included U b X
forall x : U, In U (Union U a b) x -> In U X x
intros x H'1; elim H'1; auto with sets.
Qed.
Hint Resolve Union_minimal : core.

Theorem Intersection_maximal :
 forall a b X:Ensemble U,
   Included U X a -> Included U X b -> Included U X (Intersection U a b).
U:Type
forall a b X : Ensemble U,
Included U X a ->
Included U X b -> Included U X (Intersection U a b)
auto with sets.
Qed.

Theorem Union_increases_l : forall a b:Ensemble U, Included U a (Union U a b).
U:Type
forall a b : Ensemble U, Included U a (Union U a b)
auto with sets.
Qed.

Theorem Union_increases_r : forall a b:Ensemble U, Included U b (Union U a b).
U:Type
forall a b : Ensemble U, Included U b (Union U a b)
auto with sets.
Qed.

Theorem Intersection_decreases_l :
 forall a b:Ensemble U, Included U (Intersection U a b) a.
U:Type
forall a b : Ensemble U,
Included U (Intersection U a b) a
intros a b; red.
U:Type
a, b:Ensemble U
forall x : U, In U (Intersection U a b) x -> In U a x
intros x H'; elim H'; auto with sets.
Qed.

Theorem Intersection_decreases_r :
 forall a b:Ensemble U, Included U (Intersection U a b) b.
U:Type
forall a b : Ensemble U,
Included U (Intersection U a b) b
intros a b; red.
U:Type
a, b:Ensemble U
forall x : U, In U (Intersection U a b) x -> In U b x
intros x H'; elim H'; auto with sets.
Qed.
Hint Resolve Union_increases_l Union_increases_r Intersection_decreases_l
  Intersection_decreases_r : core.

Theorem Union_is_Lub :
 forall A a b:Ensemble U,
   Included U a A ->
   Included U b A ->
   Lub (Ensemble U) (Power_set_PO A) (Couple (Ensemble U) a b) (Union U a b).
U:Type
forall A a b : Ensemble U,
Included U a A ->
Included U b A ->
Lub (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) (Union U a b)
intros A a b H' H'0.
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
Lub (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) (Union U a b)
apply Lub_definition; simpl.
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
Upper_Bound (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) (Union U a b)
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
forall y : Ensemble U,
Upper_Bound (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) y ->
Included U (Union U a b) y
-
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
Upper_Bound (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) (Union U a b) apply Upper_Bound_definition; simpl; auto with sets.
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
forall y : Ensemble U,
In (Ensemble U) (Couple (Ensemble U) a b) y ->
Included U y (Union U a b)
  intros y H'1; elim H'1; auto with sets.
-
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
forall y : Ensemble U,
Upper_Bound (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) y ->
Included U (Union U a b) y intros y H'1; elim H'1; simpl; auto with sets.
Qed.

Theorem Intersection_is_Glb :
 forall A a b:Ensemble U,
   Included U a A ->
   Included U b A ->
   Glb (Ensemble U) (Power_set_PO A) (Couple (Ensemble U) a b)
     (Intersection U a b).
U:Type
forall A a b : Ensemble U,
Included U a A ->
Included U b A ->
Glb (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) (Intersection U a b)
intros A a b H' H'0.
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
Glb (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) (Intersection U a b)
apply Glb_definition; simpl.
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
Lower_Bound (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) (Intersection U a b)
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
forall y : Ensemble U,
Lower_Bound (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) y ->
Included U y (Intersection U a b)
-
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
Lower_Bound (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) (Intersection U a b) apply Lower_Bound_definition; simpl; auto with sets.
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
In (Ensemble U) (Power_set A) (Intersection U a b)
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
forall y : Ensemble U,
In (Ensemble U) (Couple (Ensemble U) a b) y ->
Included U (Intersection U a b) y
  +
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
In (Ensemble U) (Power_set A) (Intersection U a b) apply Definition_of_Power_set.
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
Included U (Intersection U a b) A
    generalize Inclusion_is_transitive; intro IT; red in IT; apply IT with a;
      auto with sets.
  +
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
forall y : Ensemble U,
In (Ensemble U) (Couple (Ensemble U) a b) y ->
Included U (Intersection U a b) y intros y H'1; elim H'1; auto with sets.
-
U:Type
A, a, b:Ensemble U
H':Included U a A
H'0:Included U b A
forall y : Ensemble U,
Lower_Bound (Ensemble U) (Power_set_PO A)
  (Couple (Ensemble U) a b) y ->
Included U y (Intersection U a b) intros y H'1; elim H'1; simpl; auto with sets.
Qed.

End The_power_set_partial_order.

Hint Resolve Empty_set_minimal: sets.
Hint Resolve Power_set_Inhabited: sets.
Hint Resolve Inclusion_is_an_order: sets.
Hint Resolve Inclusion_is_transitive: sets.
Hint Resolve Union_minimal: sets.
Hint Resolve Union_increases_l: sets.
Hint Resolve Union_increases_r: sets.
Hint Resolve Intersection_decreases_l: sets.
Hint Resolve Intersection_decreases_r: sets.
Hint Resolve Empty_set_is_Bottom: sets.
Hint Resolve Strict_inclusion_is_transitive: sets.