#partial order

Big O notation is important for explaining growth

One thing about comparing using it: it is a partial order and not a total order. This means that there are some functions that cannot be compared.

Examples of why not usually go between two different functions, and functions that grow faster than one and slower than the other are neither faster or slower than the example

If this wave seems like a cheat, because it is decreasing in part, there are functions that do this without decreasing

I am sure that this title confuses you. I am sure that some of you are saying "Matan, I know you love gefilte fish, and to do that, you must think it exists."

I am sure that each creature we call a fish or zebra exists, I just don't think those categories are valid.

Why are they not?

Because they are not ideals, and so therefore are not ideal.

An ideal is a subset of a POSet, where if two elements are in it, their least common ancestor is also in it, and all descendants are in it.

This might be mathematically pretty, but that mathematical prettiness is actually biologically useful.

If you make a tree of vertebrates, and label what is or isn't a 'fish,' then you will see that it excludes a big chunk for tetrapods (amphibians, reptiles (which also don’t exist), mammals, etc.). There is no way to make an ideal with the 3 species we call 'zebras' without including something we don't think of as a zebra. We are imposing a bias on how evolution worked, that some creature stopped being something else.

Now, subgroups are still valid in this, since you can gain a new feature, and it groups organisms by shared descent, meaning shared characteristics.

This asymmetry is a good thing, because it allows change to make a new group, without destroying previous structures.

It also defeats bizarrely imposed hierarchies, the whole "order, class, phylum" stuff, because it is much simpler, and does not distinguish them.

It's simplicity also allows us to actually handle the problems given by ring species. In a ring species, every population is definitely part of the same "species" as its neighbors, but too different from populations on the other side.

With ideals, since they don't care about hierarchy, we can talk about portions of it or the whole thing, and not have any problems.

And this all comes from properties of ideals on POSets which we want categories of organisms to have.

A lattice is a POSet where every pair has a join and a meet.

Here is a picture a lattice showing the join of two points. Meet is the closest one below both.

Here are some examples of lattices:

Power set, ordered by inclusion

join(a,b) = union(a,b) meet(a,b) = intersection(a,b)

2D grid, ordered by (a,b) ≤ (c,d) if a≤c and b≤d

join((a,b),(c,d)) = (max(a,c),max(b,d)) meet((a,b),(c,d)) = (min(a,c),min(b,d))

Positive integers, ordered by Divisibility

join(m,n) = lcm(m,n) meet(m,n) = gcd(m,n)

All strings of the same length of "true" and "false" (or 1 and 0) ordered by "bigger or same in each place" (or "ordered bitwise"). In many ways, this is the exact same lattice as the power set.

join(s,t) = bitwise_or(s,t) meet(s,t) = bitwise_and(s,t)

Where the bitwise operators work place by place.

A POSet is a generalization of the properties of order.

We can use this to generalize properties that we think orders should have.

Something that does not work without a little bit of tweaking are the maximum and minimum functions.

First, we should try to figure out what properties we want in a lineär order, before we expand it.

Max(x,y) only works if two things are comparable, because it should return the "bigger" one.

But, we can use a more general concept. Clearly, the max is at least as big as either input. Also, anything that is bigger than both clearly above the max.

We traditionally call something that fits the expanded defintion the Least Upper Bound or the supremum.

In a partial order, the join of two elements is the element that is above (including equality) the two elements, and any other element with that property is above it.

Note that there are many reasons that two elements might not have a join.

The first is if there is no element that is above both of them.

The second is if there are multiple non-comparable elements that are minimal.

The expanded minimum, the biggest thing smaller than a set, is called the Greatest Lower Bound or the infimum.

A partial order relation is not an object in itself. But, a set can have a partial order. We call such a set a Partially Ordered Set, or POSet for short.

So, if we make a partial order on X and call that partial order ≤, then we can just refer to the POSet as (X,≤)

We usually write sets with structure as a list*, the first being the set of elements and the rest being the bits of structure on it.

The first thing we should notice is that a POSet fulfills all the conditions to be a directed graph. This is great, since we have a convention about how to show an ordered graph. You represent each element as a circle, and each connection (a,b) by an arrow from point a to point b.

But, we can take advantage of the structure of the partial order to simplify the diagram.

Reflexivity/anti-reflexivity: We choose before-hand if we want every element to be related to itself or not. So, we add no information by including self-loops.

Transitivity: If x≤y and y≤z, then x≤z. This means that we should just show the closer pairs, and not x≤z, since it is implied.

Anti-symmetry: Since if two elements are comparable, only one comparison is true, we can take advantage of height, and make earlier things higher.

The representation that takes advantage of this structure is called a Hasse Diagram

Here are some examples: The power set, ordered by subset:

It can have multiple bottoms:

A family tree ordered by “is a descendant”:

And a linear order:

In order theory, a Hasse diagram (/ˈhæsə/; German: /ˈhasə/) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set (S, ≤) one represents each element of S as a vertex in the plane and draws a line segment or curve that goes upward from x to y whenever y covers x (that is, whenever x < y and there is no z such that x < z < y). These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order.

The power set of a 2-element set ordered by inclusion

  A "good" Hasse diagram

Although Hasse diagrams are simple as well as intuitive tools for dealing with finite posets, it turns out to be rather difficult to draw "good" diagrams. The reason is that there will in general be many possible ways to draw a Hasse diagram for a given poset. The simple technique of just starting with the minimal elements of an order and then drawing greater elements incrementally often produces quite poor results: symmetries and internal structure of the order are easily lost.

The following example demonstrates the issue. Consider the power set of a 4-element set ordered by inclusion Below are four different Hasse diagrams for this partial order. Each subset has a node labelled with a binary encoding that shows whether a certain element is in the subset (1) or not (0):