Thursday, July 25, 2013

Algebraic preorders

Two of the most common algebraic structures, binary relations and monoids, have a preorder associated with them:
  • Monoids: reachability can be defined by $(x <= y) \implies \exists \; a,b: axb = y$
  • Binary relations: reachability can be defined by $x <= y$ if there exists some path from x to y
I believe that the applicability of order theory to such common structures is a solid justification for its foundational status.

Tuesday, July 23, 2013

Interval orders

We can represent a wide variety of partial orders as interval orders:
([0 0])
([0 0] [0 0])
([0 0] [1 1])
([0 0] [0 0] [0 0])
([0 0] [0 0] [1 1])
([0 0] [0 1] [1 1])
([0 0] [1 1] [1 1])
([0 0] [1 1] [2 2])
According to automorphism groups of forbidden posets by Gerhard Behrendt the class of automorphisms of finite interval orders is equal to that of finite weak orders which motivates our discussion of interval orders. The order 2+2 avoided by interval orders is the first partial order which has an automorphism group that isn't orbit symmetric.

Monday, July 22, 2013

Forbidden induced suborders

Several classes of partial orders can be described by their avoidance of a single induced suborder:
  • Antichains: [1 1]
  • Total orders: [2]
  • Weak orders: {1 1, [1 1] 1}
  • Upper/lower forests: [1 2] and [2 1]
  • Interval orders: {[1 1] 2}
  • Series-parallel partial orders: the zigzag poset
The semiorders can be described as the subset of the set of interval orders that avoid another order type in addition to the one the interval orders avoid.

Friday, July 19, 2013

Subsets of a poset

There are certain special subsets of a partially ordered set:
  • Directed Sets: these are subsets whose every pair of elements contains an upper or lower bound.
  • Centered Sets: these are subsets whose every finite subset of elements contain an upper or lower bound.
  • Upper/Lower Sets: subsets that contain all elements less then or greater then values that they contain. The lattice of these sets is a sufficient basis for representing distributive lattices.
  • Dedekind Cuts: subsets whose set of lower bounds of its set of upper bounds is equal to itself. The lattice of these is the dedekind completion.
The analysis of such subsets is important to our understanding of order theory.

Wednesday, July 17, 2013


Transseries are a composable, differentiable totally ordered field whose values can be used to approximate rates of growth of real functions. Here are a few transseries listed in order: $x^{-2}$, $x^{-1}$, $log(x)$, $12$, $x^2 + 2x + 1$, sinh, cosh, $e^x$, $e^{e^x}$.

Transeries can also be used to solve homogeneous LODEs with constant coefficients and real roots which is why they include cosh, sinh, $e^x$, and all polynomial functions. Functions with growth rates less then polynomials like $log(x)$ and $x^{-1}$ and functions with growth rates that are greater then exponential like the double exponential $e^{e^x}$ do not fall into this category of functions.

The theory of transseries subsumes much of surreal analysis because transseries are simultaneously surreal numbers and transformations of themselves. The full extent of the applications of transseries has not yet been fully explored.

Tuesday, July 16, 2013

Elements of distributive lattices

Every element in a distributive lattice such as the total ordering on the natural numbers can be represented as a lower set of join irreducible elements. This approach allows us to represent all natural numbers as sets:
#{#{} #{#{}}}
#{#{} #{#{}} #{#{} #{#{}}}}
This also can be used to represent all natural numbers as sets of prime powers with respect to the divisibility relation:
#{2 4}
#{2 3 6}
#{2 4 8}
We can also use this to effectively represent abstract simplical complexes as sets of lower sets of the set of lower sets of an antichain.

Thursday, July 11, 2013

On multiplicative lower sets

The set of all orders of elements of the symmetric group S_n forms a multiplicative lower set:
 #{2 3} 
 #{3 4} 
 #{4 5 6} 
 #{4 5 6} 
 #{7 10 12} 
 #{7 8 10 12 15} 
 #{8 9 12 14 15 20})
The set of lower sets over the divisibility relation forms a distributive lattice with its own union and intersection operations.

Friday, July 5, 2013

Data dependencies

We can associate an input place and an output place with every operation in order to model data dependencies. Bernstein's condition describes when two operations are independent and can therefore be executed in parallel.