Degree reductions

Sets can be simplified by taking subsets of them. Set systems on the other hand can be simplified not only by taking subsets of them, but also by taking subsets of their members. Taking a subset of a member necessarily reduces the degree of some union member of the set system, which is the number of times it is included in different sets of the set system. So taking subsets of members are degree reductions. I will demonstrate this without the nullfree degree reductions, which don't use the empty set. Set partitions are pairwise disjoint so their degree reductions form a boolean algebra. The size of this boolean algebra is determined by the order of the set system rather then its cardinality.



In my brief survey of the smallest set systems, I described the fact that the set theoretic definition of the ordered pair, the kuratowski pair, is in fact the simplest type of set system that isn't pairwise disjoint. It is therefore, also the simplest type of set system whose degree reductions do not form a boolean algebra. In fact, its degree reductions don't even form a lattice, as can clearly by the weak ordering below. The set systems #{#{0}, #{1}} and #{#{0 1}} both have the same degree signature and share the same reductions without a common reduction between them.



To demonstrate further, the degree reductions of the power set like set system with degree signature 2,2 is displayed below. This in some sense, the next simplest type of set system after the kuratowski pair. It also forms a weak ordering, but with a clearly greater height.



Another small set system, the kuratowski pair unioned with a pairwise disjoint member produces a different degree reductions partial order. This order is also not a lattice, just like the kuratowski pair order, nor is it a weak order. Instead, it is the product order of the weak order of the kuratowski pair with a size two total order. As the boolean algebra is a product order of total orders, it follows that all the orderings so far have been product orders of weak orders. The degree reductions order is a product order of the degree reductions of each of the intersection connected components of the partial order, so pairwise disjoint set systems form boolean algebras.



The next set system with cardinality sum four with a slightly larger degree reductions partial order comes from the order three chain seen below. This set system #{#{0} #{0 1 2}} has two kuratowski pairs as immediate degree reductions and two set partitions, determined by reducing degree one elements or degree two elements. Reducing the degree two elements produces set partitions and reducing degree one elements produces kuratowski pairs. As kuratwoski pairs are weak orders and not lattices, this order isn't a lattice either. Only the set partitions form boolean algebras.



This demonstrates what I am talking about when referring to degree reductions, so that it is clear what this concept means. Now there are two types of simplifications of set systems: subsets of the set system and degree reductions taken from subsets of the members of the set system. These two orderings are the main things that have determined by thoughts on pure set theory.

Cardinalities

When studying elementary set theory, the most basic thing that one reasons about sets is their cardinality. A set can only be a subset of another if its cardinality is less then its cardinality. In other words, the cardinality forms a monotone function on partially ordered sets, the sets partially ordered by a boolean algebra, and the cardinalities totally ordered.

Sets -> Cardinalities

Degree multisets and signatures

Given a set system we can form a multiset from that set system, by combining all of its elements counting multiplicity so for example #{#{0} #{0 1}} can be combined to get the multiset {0 0 1}. The degree of some union member of the set system is the number of sets it belongs in, so this is fully determined by the combinational multiset. The operation of taking the multiset associated a set system is a monotone function associated with the degree reductions order rather then the subset reductions order. The distributive lattice of multisets can then be mapped by a monotone function again to the set of signatures ordered by the Young's lattice.

Set systems -> Multisets -> Signatures

All these foundational concepts emerge directly from pure set theory, without the need for any additional structures. As all the introduced concepts like cardinalities, multisets, and multiset signatures all form distributive lattices, they can be represented as sets with their lattice operations left in tact so we don't really leave the domain of pure set theory.