In set theory in a multiset theoretic context the key role of multisets in the theory of set systems in set theory was explained. In particular, a multiset can be formed from a set system by adding all the sets of the set system together counting repetition, which determines the degree distribution of the set system. This is a brief overall survey of the different properties of set systems determined by the degree multiset.
Cardinality sum
The cardinality sum of the set system is equal to the sum of the cardinalities of the sets of the set system, and it corresponds to the cardinality of the multiset. The cardinality sum is the best measure of the size of a set system. Cardinality one multisets include {x}, cardinality two ones include {x,x},{x,y}, and so on. Cardinality sum one set systems are rank one chain families, cardinality sum two set systems are max order two independent families, and cardinality three set systems are either max order three set systems or they are ordered pair like set systems such as the kuratowski pair {{0},{0,1}}. A full survey is presented in set systems of small size .
Order
The order of a set system is the cardinality of its union, and the order of a multiset is the cardinality of its support. Set systems with bounded order have a bounded cardinality sum up to $2^n$ where $n$ is the order, and set systems with bounded cardinality sum are bounded by the same order. This means there are more set systems of a given order, so the kuratowski pair and ordered pairs are order two and so is the larger cardinality sum set system {{0},{1},{0,1}} which is power set like.
Regular families
Regular families are families for which the degree of each element is the same, and they correspond to regular multisets like {a,b,c},{a,a,b,b,c,c}, {a,a,a,b,b,b,c,c,c}, {a,a,a,a,b,b,b,b,c,c,c,c,d,d,d,d}. Corresponding regular families include {{a},{b},{c}}, {{a,b},{a,c},{b,c}}, {{a,b},{a,c},{b,c},{a,b,c}}, and {{a},{b},{c},{d},{a,b},{a,c},{b,c},{a,b,c}}. Finite power set like set systems are a special case of regular families determined by the condition that the cardinality sum is $2^n$ which is the highest it can be for the order of the set system.
Antiregular families
Antiregular families are families for which the degree of each element is different, and they correspond to antiregular multisets like {a},{a,b,b},{a,b,b,c,c,c}, and {a,b,b,c,c,c,d,d,d,d}. Actually, the antiregular multisets must all take this form as multisets like {a,b,b,b} have no corresponding set system partition so they are actually called progression multisets as their multiplicities form a range over the natural numbers. Ordered pairs can be determined by their degrees multiset which is the basis of the multiset theoretic definition of the ordered pair.
Maximum and minimum degrees
Independent families are set systems for which the intersection of all sets is empty, they are also determined by their degree multisets, as their degree multisets are actually sets. Consider the independent family {{0,1},{2,3}} its combinational sum is {0,1,2,3} which is a set, and in this case multiset addition is equal to the union. Max degree two, max degree three, and max degree four families are generalizations. Powerful families are set systems for which each union member has degree at least two. These properties are determined from the minimum and maximum multiplicity of the degrees multiset.
Repetitiveness and pseudo-independent families
The repetitiveness of a multiset is the extent to which it is not a set, or the cardinality of the multiset minus the cardinality of the support. This means that for a set system, it is equal to the cardinality sum minus the order. It is maximized for power sets and minimized for independent families. It is also equal to the total intersection size of the set system, which is the total number of times sets intersect. Every set system has a fundamental intersection multigraph associated with it, which is a multigraph rather then an ordinary graph because sets can have more then one value in common between them.
No comments:
Post a Comment