:: Algebra of Normal Forms :: by Andrzej Trybulec :: :: Received October 5, 1990 :: Copyright (c) 1990-2018 Association of Mizar Users :: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland). :: This code can be distributed under the GNU General Public Licence :: version 3.0 or later, or the Creative Commons Attribution-ShareAlike :: License version 3.0 or later, subject to the binding interpretation :: detailed in file COPYING.interpretation. :: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these :: licenses, or see http://www.gnu.org/licenses/gpl.html and :: http://creativecommons.org/licenses/by-sa/3.0/. environ vocabularies XBOOLE_0, FINSUB_1, SUBSET_1, ZFMISC_1, TARSKI, MCART_1, BINOP_1, FUNCT_1, SETWISEO, RELAT_1, FINSET_1, ORDINAL4, STRUCT_0, LATTICES, EQREL_1, NORMFORM; notations TARSKI, XBOOLE_0, ZFMISC_1, SUBSET_1, XTUPLE_0, MCART_1, RELAT_1, FUNCT_2, FINSET_1, BINOP_1, DOMAIN_1, FINSUB_1, SETWISEO, STRUCT_0, LATTICES; constructors PARTFUN1, BINOP_1, DOMAIN_1, FINSET_1, SETWISEO, LATTICES, RELSET_1, XTUPLE_0; registrations SUBSET_1, FINSUB_1, LATTICES, RELAT_1, XTUPLE_0; requirements SUBSET, BOOLE; begin :: A u x i l i a r y t h e o r e m s :: Part 1. BOOLEan operations on pairs & relations between pairs reserve A, B for non empty preBoolean set, x, y for Element of [:A,B:]; definition let A,B,x,y; pred x c= y means :: NORMFORM:def 1 x`1 c= y`1 & x`2 c= y`2; reflexivity; func x \/ y -> Element of [:A, B:] equals :: NORMFORM:def 2 [x`1 \/ y`1, x`2 \/ y`2]; commutativity; idempotence; func x /\ y -> Element of [:A, B:] equals :: NORMFORM:def 3 [x`1 /\ y`1, x`2 /\ y`2]; commutativity; idempotence; func x \ y -> Element of [:A, B:] equals :: NORMFORM:def 4 [x`1 \ y`1, x`2 \ y`2]; func x \+\ y -> Element of [:A, B:] equals :: NORMFORM:def 5 [x`1 \+\ y`1, x`2 \+\ y`2]; commutativity; end; reserve X for set, a,b,c for Element of [:A,B:]; theorem :: NORMFORM:1 a c= b & b c= a implies a = b; theorem :: NORMFORM:2 a c= b & b c= c implies a c= c; theorem :: NORMFORM:3 (a \/ b) \/ c = a \/ (b \/ c); theorem :: NORMFORM:4 (a /\ b) /\ c = a /\ (b /\ c); theorem :: NORMFORM:5 a /\ (b \/ c) = a /\ b \/ a /\ c; theorem :: NORMFORM:6 a \/ (b /\ a) = a; theorem :: NORMFORM:7 a /\ (b \/ a) = a; theorem :: NORMFORM:8 a \/ (b /\ c) = (a \/ b) /\ (a \/ c); theorem :: NORMFORM:9 a c= c & b c= c implies a \/ b c= c; theorem :: NORMFORM:10 a c= a \/ b & b c= a \/ b; theorem :: NORMFORM:11 a = a \/ b implies b c= a; theorem :: NORMFORM:12 a c= b implies c \/ a c= c \/ b & a \/ c c= b \/ c; theorem :: NORMFORM:13 a\b \/ b = a \/ b; theorem :: NORMFORM:14 a \ b c= c implies a c= b \/ c; theorem :: NORMFORM:15 a c= b \/ c implies a \ c c= b; reserve a for Element of [:Fin X, Fin X:]; definition let A be set; func FinPairUnion A -> BinOp of [:Fin A, Fin A:] means :: NORMFORM:def 6 for x,y being Element of [:Fin A, Fin A:] holds it.(x,y) = x \/ y; end; reserve A for set; definition let X be non empty set, A be set; let B be Element of Fin X; let f be Function of X, [:Fin A, Fin A:]; func FinPairUnion(B,f) -> Element of [:Fin A, Fin A:] equals :: NORMFORM:def 7 FinPairUnion A \$\$(B,f); end; registration let A be set; cluster FinPairUnion A -> commutative idempotent associative; end; theorem :: NORMFORM:16 for X being non empty set for f being Function of X, [:Fin A,Fin A:] for B being Element of Fin X for x being Element of X st x in B holds f.x c= FinPairUnion(B,f); theorem :: NORMFORM:17 [{}.A, {}.A] is_a_unity_wrt FinPairUnion A; theorem :: NORMFORM:18 FinPairUnion A is having_a_unity; theorem :: NORMFORM:19 the_unity_wrt FinPairUnion A = [{}.A, {}.A]; theorem :: NORMFORM:20 for x being Element of [:Fin A, Fin A:] holds the_unity_wrt FinPairUnion A c= x; theorem :: NORMFORM:21 for X being non empty set for f being (Function of X,[:Fin A,Fin A:]), B being (Element of Fin X) for c being Element of [:Fin A, Fin A:] st for x being Element of X st x in B holds f.x c= c holds FinPairUnion(B,f) c= c; theorem :: NORMFORM:22 for X being non empty set, B being Element of Fin X for f,g being Function of X,[:Fin A,Fin A:] st f|B = g|B holds FinPairUnion(B,f) = FinPairUnion(B,g); :: Part 2. Disjoint pairs of finite sets definition let X; func DISJOINT_PAIRS(X) -> Subset of [:Fin X, Fin X:] equals :: NORMFORM:def 8 { a : a`1 misses a`2 }; end; registration let X; cluster DISJOINT_PAIRS(X) -> non empty; end; theorem :: NORMFORM:23 for y being Element of [:Fin X, Fin X:] holds y in DISJOINT_PAIRS X iff y`1 misses y`2; reserve x,y for Element of [:Fin X, Fin X:], a,b for Element of DISJOINT_PAIRS X; theorem :: NORMFORM:24 y in DISJOINT_PAIRS X & x in DISJOINT_PAIRS X implies (y \/ x in DISJOINT_PAIRS X iff y`1 /\ x`2 \/ x`1 /\ y`2 = {}); theorem :: NORMFORM:25 a`1 misses a`2; theorem :: NORMFORM:26 x c= b implies x is Element of DISJOINT_PAIRS X; theorem :: NORMFORM:27 not (ex x being set st x in a`1 & x in a`2); theorem :: NORMFORM:28 not a \/ b in DISJOINT_PAIRS X implies ex p being Element of X st p in a`1 & p in b`2 or p in b`1 & p in a`2; theorem :: NORMFORM:29 x`1 misses x`2 implies x is Element of DISJOINT_PAIRS X; theorem :: NORMFORM:30 for V,W being set st V c= a`1 & W c= a`2 holds [V,W] is Element of DISJOINT_PAIRS X; reserve A for set, x for Element of [:Fin A, Fin A:], a,b,c,d,s,t for Element of DISJOINT_PAIRS A, B,C,D for Element of Fin DISJOINT_PAIRS A; definition let A; func Normal_forms_on A -> Subset of Fin DISJOINT_PAIRS A equals :: NORMFORM:def 9 { B : a in B & b in B & a c= b implies a = b}; end; registration let A; cluster Normal_forms_on A -> non empty; end; reserve K,L,M for Element of Normal_forms_on A; theorem :: NORMFORM:31 {} in Normal_forms_on A; theorem :: NORMFORM:32 B in Normal_forms_on A & a in B & b in B & a c= b implies a = b; theorem :: NORMFORM:33 (for a,b st a in B & b in B & a c= b holds a = b) implies B in Normal_forms_on A; definition let A,B; func mi B -> Element of Normal_forms_on A equals :: NORMFORM:def 10 { t : s in B & s c= t iff s = t }; let C; func B^C -> Element of Fin DISJOINT_PAIRS A equals :: NORMFORM:def 11 DISJOINT_PAIRS A /\ { s \/ t: s in B & t in C }; end; theorem :: NORMFORM:34 x in B^C implies ex b,c st b in B & c in C & x = b \/ c; theorem :: NORMFORM:35 b in B & c in C & b \/ c in DISJOINT_PAIRS A implies b \/ c in B ^C; theorem :: NORMFORM:36 a in mi B implies a in B & (b in B & b c= a implies b = a); theorem :: NORMFORM:37 a in mi B implies a in B; theorem :: NORMFORM:38 a in mi B & b in B & b c= a implies b = a; theorem :: NORMFORM:39 a in B & (for b st b in B & b c= a holds b = a) implies a in mi B; theorem :: NORMFORM:40 mi B c= B; theorem :: NORMFORM:41 b in B implies ex c st c c= b & c in mi B; theorem :: NORMFORM:42 mi K = K; theorem :: NORMFORM:43 mi (B \/ C) c= mi B \/ C; theorem :: NORMFORM:44 mi(mi B \/ C) = mi (B \/ C); theorem :: NORMFORM:45 mi(B \/ mi C) = mi (B \/ C); theorem :: NORMFORM:46 B c= C implies B ^ D c= C ^ D; theorem :: NORMFORM:47 mi(B ^ C) c= mi B ^ C; theorem :: NORMFORM:48 B^C = C^B; theorem :: NORMFORM:49 B c= C implies D ^ B c= D ^ C; theorem :: NORMFORM:50 mi(mi B ^ C) = mi (B ^ C); theorem :: NORMFORM:51 mi(B ^ mi C) = mi (B ^ C); theorem :: NORMFORM:52 K^(L^M) = K^L^M; theorem :: NORMFORM:53 K^(L \/ M) = K^L \/ K^M; theorem :: NORMFORM:54 B c= B ^ B; theorem :: NORMFORM:55 mi(K ^ K) = mi K; definition let A; func NormForm A -> strict LattStr means :: NORMFORM:def 12 the carrier of it = Normal_forms_on A & for B, C being Element of Normal_forms_on A holds (the L_join of it).(B, C) = mi (B \/ C) & (the L_meet of it).(B, C) = mi (B^C); end; registration let A; cluster NormForm A -> non empty; end; reserve K, L, M for Element of Normal_forms_on A; registration let A; cluster NormForm A -> Lattice-like; end; registration let A; cluster NormForm A -> distributive lower-bounded; end; theorem :: NORMFORM:56 {} is Element of NormForm A; theorem :: NORMFORM:57 Bottom NormForm A = {};