.Open Families of Sets/Hypergraphs
Everything on this page depends on
.See ./logic_30_Sets.html
for syntax, semantics and properties.
. The Power Set of a Type
For Type T.
For S:@T, @S::= `the set of subsets of a set S`,
For S, @S::@@T= @^ S, the set of subsets of S, also known as the power set.
For S, SetOf(S) ::= @S, and form used with audiences unused to MATHS and/or
set theory.
()|- {1,3} and {2} in SetOf({1,2,3}).
()|- @S={B:@T || B==>S}.
()|- |@^S|=|@|^|S|=2^|S|,
. The Set of families of sets
A family is a collection of subsets of a given set - Given a set S of
elements {x,y,...} then @S is the set of all subsets of S, @S = {{},{x},
{x,y},{y},...}. @@S is short for @(@S) - the set of subsets of subsets of
S. Thus @@S={{}, {{}}, {{},{x}}, {{},{y}}, {{x},{y}},...}. An element of
@@S is a called a family of subsets of S. It turns out that many important
ideas can be best modelled as particular kinds of families - in particular,
abstract families of languages, families of open and closed sets,
partitions and covers all turn out to be important.
|-(union):For \beta:@@T, |(\beta)={x:T || for some B:\beta (x in B)},
|-(intersection):For \beta:@@T, &(\beta)={x:T || for all B:\beta(x in B)}.
.Open Quick results
For Type T, A,B:@T.
(union)|- (family1):|{A} = A.
(intersection)|- (family2):&{A} = A.
(union)|- (family3):|{ A, B } = A|B.
(intersection)|- (family4):&{ A, B } = A&B.
(union, intersection)|-(family5):For \alpha:@@T,A:\alpha( &\alpha ==> S ==> |\alpha).
In the following "{}" is short for the "{}.@T", the null or empty set of subsets of type T.
(union)|- (null_family_union): |{} = {}.
(intersection)|- (null_family_intersection): &{} = T.
Can you provide proofs
.Hole family
?
.Close Quick results
.Open Special Types of Families
. Covers
Families that have every element in them at least once, but may overlap...
For S:Sets, covers(S) ::={\alpha:@@S || |(\alpha)=S},
(covers)|- {S} in covers(S),
(covers)|- for A:@S {A,S~A} in covers(S),
(covers)|- for \alpha, \beta:covers(S)(\alpha | \beta in covers(S)),
(covers)|- for \alpha:covers(S), \beta:@@S, if \alpha==>\beta then \beta in covers(S)).
. Simplicial Complexes
If S is a finite set and C:@S, then we can call each element of C a `simplex`. When we do this we imply that the elements of C are classified by the number of elements in them:
For c:C, dim(c) ::=order(c) ::= |C|-1, for p:0..|S|-1, p.simplex={c:C || dim(c)=p}.
A face `f` of a simplex `c` in `C` is any simplex which is subset of `c`.
For p,c, p.face(c) ::=@c and p.simplex.
For p,c, faces(c)=|[p](p.face(c)).
There are several definitions of a `simplicial complex`.
.Source According to Ron Atkin(Casti92, Atkin74):
(atkin): C in simplicial_complex iff S==>C and for all c:C(faces(c) in C).
The dimension of a simplicial complex C, dim(C) ::=max(dim(C)).
If dim(C)=n then S can be embedded in a Euclidean Space of 2n+1 dimensions so that
(1) each simplex of dimension p is a convex polytope of dimension p
(2) the convex polytopes overlap iff the simplices do.
Given a family C of subsets of a finite set S then we can construct an Atkin-complex by adding all subsets of elements of C to C:
complex(C) ::={x:@c || for some c:C }.
Another definition (JamesJames68) is
C is a simplicial_complex iff for all c,c':C, either c&c'={} or c&c' in faces(c) and faces(c').
Simplicial Complexes are generated by relations between finite sets
.See http://www/dick/maths/logic_42_Properties_of_Relation.html#complex
for example. The link has some nice graphics.
. Mosaics
A mosaic is a collection of mutually disjoint subsets of a set that may or may not cover the set.
.Source Botting 1970
For S:Sets, mosaics(S) ::={\mu:@@S || for all A,B:\mu, if A<>B then A&B={}}.
For S:Sets, \mu:mosaics(S), free(\mu) ::=S~ |(\mu).
(mosaics)|- for S, ( {S},{{}} )in mosaics(S) ).
(mosaics, free)|- for A:@S, {A,S~A} in mosaics(S) and free({A,S~A} )={}.
(mosaics)|- for \mu:mosaics(S), \nu:@\mu (\nu in mosaics(S)).
. Partitions
Mutually disjoint covers.
For S:Sets, partitions(S) ::= $covers(S) & $mosaics(S).
(mosaics, partitions)|- For \mu:mosaics(S) ( (\mu | free(\mu) ) in partitions(S) ),
For \pi:@S, S>==\pi::=for all a:S, one b:\pi(a in \pi),
(-1, partitions)|- For all \pi: partitions(S), S>==\pi,
(partitions)|- For all A,B:@S, {A&B,A~B} in partitions(S).
For S,\pi, s:S, \pi(s)=the [A:\pi]( s in A ).
(partitions)|- For S, \pi, rel[a,b](\pi(a)=\pi(b)) in eguivalence_relation.
.See http://www.csci.csusb.edu/dick/maths/logic_41_Maps.html#Equivalence Relations
. Open and closed families
.Used_in topology(continuity, limits,...).
.See http://www.csci.csusb.edu/dick/maths/math_91_Topology.html
Useful whenever the idea of limit is needed to define what happens to iterative and recursive processes.
For S:Sets, open_family(S):@@S::= { open:@S || (open,&,{}) in monoid and for G:@open(|(G) in open) and S in open },
|- for all open:open_family(S), G:finite(open)(&(G) in open).
For S:Sets, closed_family(S):@@S::= { closed:@S || (closed,|,S) in monoid and for all G:@closed( &(G) in closed) and {} in closed },
|- for closed:closed_family(S), G:finite(closed) (|(G) in closed).
(Duality): for \alpha:@@S, \beta={ S~A || A:\alpha} ( \alpha in closed_family(S) iff \beta in open_family(S))
.Open Filters
Bourbaki's Abstract Model of `x tends to x0`. A filter is closed under finite intersections and `supersetting`
.Used_in Math.Topology.
.See http://www.csci.csusb.edu/dick/maths/math_91_Topology.html
For S:Sets, filters(S) ::={f:@(@S-{}) || for all B:@S(if for some A:f(A==>B) then B in f) and for all A,B:f ( A & B in f) },
()|- for all G:finite(f) ( &(G) in f).
.Open Filter Bases
For S:Sets, filter_bases(S) ::={f:@(@S-{}) || for all A,B:f, some C:f(C==>A&B) },
()|- for all f:filter_bases(S), A,B:f (A & B).
()|- for all f:filter_bases(S) ({A:@S || for some B:f(B==>A)} in filter(S) ).
Every set in a filterbase has its own filterbase,...
()|- for all f:filter_bases(S), F:f, {A&F || A:f} in filter_bases(F).
. Ultra-Filters
For S:Sets, ultrafilters(S) ::={f:filters(S) || for all A:@S(A in f or S~A in f) }.
.Close Filters Bases
.Close Filters
.Open Lattices of Sets
An abstract lattice has two operations that are idempotent and absorbative.
A set of sets is a lattice with respect to union and intersection iff every
union and intersection of every pair of sets in the family is also in the family.
This is the same as requiring that all finite intersections and unions are
members of the family.
. Complete Lattices of Sets
A collection of sets is a complete lattice is all unions and intersections
of all sets of sets in the family are also in the family ... even with
infinite unions and interesections.
generate(\alpha) ::=`the smallest lattice of sets containing all elements of \alpha`.
. Bracketing sets
A pair of sets in a complete lattice `L` form a `bracket` if the first is a
subset (or is equal to) the other:
Bracket(L) ::@(L> T }.
Each Bracket (B,T) determines a sublattice { U:L. B==>U==>T } of L.
. Rough sets
A rough set that approximates set Target in lattice L is the bracket (Lower,Upper) where
Lower:= &{ X:L . Target ==> X},
Upper:= |{ X:L . X ==>Target }.
rough_set[L](T) ::=(&{ X:L . Target ==> X}, |{ X:L . X ==>Target }).
|- rough_set[L](T) in Bracket(L).
. Lattice based Partition sets
Given a map f from set X to Y, lattice(f) ::= generate(X/f).
Given maps a:X>->attributes (assumed normalized), b>->decisions,
rough_sets(c,L) ::= { rough_set(L)(c) || c: X/b }.
.Close Lattices of Sets
.Close Special types of Families
. Refinement of families
For S:Sets, \alpha:@@S, refinement(\alpha ) ::={ \beta in @@S || for all B in \beta, some A in \alpha (B==>A)}.
For S:Sets, \alpha,\beta:@@S, (\beta finer \alpha ) ::=for all B in \beta, some A in \alpha (B==>A).
.Close Families of Sets/Hypergraphs