Monday, September 30, 2013

Veblen hierachy of ordinal numbers

We already know that a wide variety of ordinal numbers be expressed in cantor norm formal such as 0,1,2,3,4, $\omega$, $\omega+1$, $\omega^2+2\omega+1$, $\omega^\omega$, and $\omega^{2\omega^3+1}+2\omega^5+3\omega^2+2$.

We can use the generalized veblen function of one argument to express these same ordinals so we get $\phi(1)$, $\phi(1)+1$, $\phi(2)+2\phi(1)+1$, $\phi(\phi(1))$, $\phi(2\phi(3)+1)+2\phi(5)+3\phi(2)+2$. The first ordinal that cannot be expressed as such a number in Cantor normal form is $\epsilon_0$ which equals $\phi(0,1)$.

The first ordinal which cannot be expressed through addition and the veblen function of two arguments is the Fefermann-Schutte ordinal which is equal $\phi(0,0,1)$. A considerable amount of countable ordinal numbers can be expressed by the generalized veblen function.

Saturday, September 28, 2013

Mathematical ions

The most common numbers used in mathematics have an ordering relation <= associated with them for example the natural numbers appear in the order 0,1,2,3,4,... the integers appear in the unbounded order ...,-2,-1,0,1,2,... the rational numbers are are densely ordered variant of the integers and the reals are the dedekind completion of the rational numbers.

The ordinal numbers are the order types of well orders and therefore they include the natural numbers 0,1,2,3,4,... mentioned before as well as infinite numbers such as $\omega$, $2\omega$, $\omega^2$ and $\omega^\omega$. The surreal numbers are a large ordered field that include the natural numbers, the integers, the rational numbers, the real numbers, the transfinite ordinals, infinitesimals, and much more.

It is my contention that numbers should be related to ordering and not just arithmetic so the so called "complex numbers" belong to the class of ions which includes binarions, quaternions, octonions, and sedenions rather then the class of numbers. Numbers should be related to ordering which implies that the class of surreal numbers is the single class of numbers to rule them all. In conclusion every number is a surreal number.

Friday, September 20, 2013

Incidence structures as height two orders

Incidence structures are defined by a set of elements and another set of edges over those elements such that each edge is dependent upon some subset of the set of elements. Every incidence structure can be expressed as an oriented set system with sets of edges grouped by their corresponding elements:
{#{1 2} #{4}, 
 #{0 1} #{3}}
Incidence structures may be represented as height two partial orders with an option to classify disconnected nodes as either empty nodes or empty edges. If we exclude empty edges as a possibility as we can also represent height two partial orders as incidence structures:



One advantage of such incidence structures is that they allow us to define mathematical substructures of a structured sets such as relations and hypergraphs as lower suborders of the height two partial order and they can likewise be used to describe all other parts of an incidence structure.

Thursday, September 19, 2013

Orders derived from group action

Each permutation group produces a partition of the power set of the underlying set of the group. By the definition of partitioned partial orderings this produces a partial ordering relation from the group action. The partial ordering of a disjoint union of permutation groups is the product order of the partial orderings of each of those permutation groups.

The symmetric group and the alternating group are both completely transitive so they produce a total ordering relation $T_n$. Permutation groups that are defined as the disjoint union of such completely transitive groups effectively produce a multiset inclusion lattice. The cyclic group $C_4$ produces the free distributive lattice of size 2:


The cyclic group $C_2$ is the smallest group that doesn't produce a complete lattice as its underlying partial order and it is the smallest group that isn't the product of transitive groups:


The cyclic group $C_5$ is an example of a transitive group whose partial ordering is also not a complete lattice:


As I already mentioned in my post on ranking elements of partial orders the size of an element of one of these partial orders is its height and the cardinality of one of these partial orders is the total height minus one.

Saturday, September 14, 2013

Ranking elements of distributive lattices

There is a correspondence between the number of join irreducibles contained in an element of a distributive lattice and its ordinal height minus one:
(= (dec (count [1 1 1 1]))
   (count #{#{} #{#{}} #{#{} #{#{}}}}))
The same principle applies to multisets which are elements of a distributive inclusion lattice:
(= (rank {:x 1, :y 2})
   (dec (count [1 2 2 1]))
   (count #{{:x 1} {:y 1} {:y 2}))
This implies that we can use the idea of join irreducible elements as a basis for structured multisets and canonical forms of structures. A canonical labeling of a structure is one over a set-theoretic natural number such as #{#{} #{#{}} #{#{} #{#{}}}} and a structured multiset is a structure over the join irreducibles of the multiset. The key is to implement an effective partial canonization technique so that we can properly determine the equality of such structures.

Friday, September 13, 2013

Ordered multisets

Partially ordered multisets are a generalization of sets, multisets, and lists so they provide a fairly general setting from which to describe mathematical collections. We can define series parallel collections that are closed under the fundamental operations of union and ordinal sum:
(= (ordinal-union {:x 1, :y 2} {:x 2, :y 1})
   {:x 3, :y 3})
(= (ordinal-sum [1 2 3] [4 5 6])
   [1 2 3 4 5 6])
The operation of union corresponds to the combination of multisets and the operation of the ordinal sum corresponds to the concatenation of lists. Things get really interesting once we combine these two operation together to get series parallel collections that cannot be classified as any of the familiar collection types.

Thursday, September 12, 2013

Partitions of a poset

Given a partitioned partial ordering relation we can produce a new partial order on the parts of the partition defined the condition that part one is less the part two if for every element of part one there exists some element of part two such that these two elements are less then one another in the underlying partial order.

We can use this notion of partitioned posets to partially order isomorphism types including cardinal numbers and the canonical labelings of relations. This allows us to maintain the use of partial orders even when we aren't dealing with structured sets which demonstrates how fundamental order theory really is.

Wednesday, September 11, 2013

Closure operators

A closure operator on a partially ordered set is an increasing, extensive, idempotent endofunction. Of particular interest to us are closure operators on the boolean algebra which can in fact be described by their set of fixed points which form an upper bounded meet subsemilattice of the boolean algebra.

A preorder can be produced from a closure operator on a boolean algebra by the inclusion order on the closure of singletons. Set systems that are entirely determined by their closure preorder are equivalent to Alexandrov topologies.

Besides the reachability closure on any binary relation we have the closure of upper sets, lower sets, convex sets, rank complete suborders, join subsemilattices, meet subsemilattices, sublattices, and complemented sublattices among others.

Monday, September 9, 2013

Boolean algebraic closure

Given a subset of a boolean algebra the closure of the subset under the operations of union, intersection, and complementation is equivalent to a partition of the boolean algebra.

Consider the set system #{#{0 1} #{2 3}} of #{0 1 2 3 4}. The boolean algebraic closure of this set system is defined by partition #{#{0 1} #{2 3} #{4}}. For the set system #{#{0 1} #{0 1 2}} of #{0 1 2 3 4} the resulting partition is #{#{0 1} #{2} #{3 4}}.

I believe this correspondence between boolean subalgebras and equivalence relations demonstrates the close connection between sets and equality. A fundamental aspect of the definition of a set is that a set must not contain elements that are equivalent to one another.

Thursday, September 5, 2013

Symmetries and functional dependiencies

We can combine the functional dependencies of a set of elements with a group of symmetries of the set in order to construct an advanced system of reasoning about relations. One immediate application of the combination of these two notions is that we can combine symmetry and dependency to find involutions amongst the elements.

The set of relations with certain functional dependencies and symmetries forms a meet subsemilattice of the set of all relations. This allows us to use the combination of symmetries and functional dependencies to reason logically about classes of relations such as functions, bijections, constants, symmetric relations, binary operators, cancellative operations, and commutative operations.

Sunday, September 1, 2013

Complementary pairs

Given a lattice we can find certain elements that are both independent and covering which are called complements of one another. If we order pairs of such elements we can get complementary pairs. Here is an example of an expression of the boolean algebra on three elements as complementary pairs:
[#{0 1 2} #{}]
[#{1 2} #{0}], [#{0 2} #{1}], [#{0 1} #{2}]
[#{2} #{0 1}], [#{1} #{0 2}], [#{0} #{1 2}]
[#{} #{0 1 2}]
By convention such complementary pairs are expressed such that sets in a boolean algebra are equivalent to height two weak orders or in other words total functions from the underlying set to the two valued total order. One of the the major reasons I am interested in exploring such complementary pairs is their applications to set partitions:
[#{#{0} #{1} #{2}} #{#{0 1 2}}]
[#{#{1} #{0 2}} #{#{0 1} #{2}}], 
[#{#{0} #{1 2}} #{#{0 1} #{2}}], 
[#{#{0 1} #{2}} #{#{1} #{0 2}}], 
[#{#{0} #{1 2}} #{#{1} #{0 2}}], 
[#{#{0 1} #{2}} #{#{0} #{1 2}}],
[#{#{1} #{0 2}} #{#{0} #{1 2}}]
[#{#{0 1 2}} #{#{0} #{1} #{2}}]
Such complementary pairs of set partitions are a generalization of place forms applicable to other means of decomposing structures. In the most general setting we simply consider set partitions that are covering by ignoring the independence property but such pairs of set partitions aren't necessarily decompositions so that makes them much less interesting to us.