PHIL 3340
Symbolic Logic II

Curtis Brown
Spring, 2008

Zalabardo says that a linear ordering prevents "bifurcations and loops" which are allowed by a nonlinear ordering (either partial or strict). What does he mean by that?

Consider a set A = {a, b, c, d} and a relation R which is a strict ordering of the set.

R must therefore be irreflexive and transitive (and therefore asymmetric!). Moreover, any relation R in A that is irreflexive and transitive will be a strict ordering of A.

Let's represent R(x,y) by drawing an arrow from x to y. To keep the diagrams simple, however, let's leave out the arrows that are implied by transitivity (in the diagram below, we'd need arrows from a to c and from a to d).

Here's a bifurcation:

In this case, R = {<a,b>, <b,c>, <a,c>, <b,d>, <a,d>}.

Notice that this is transitive: whenever R(x, y) and R(y, z) hold, so does R(x, z). It's reflexive, since R(x, x) for every x in A. Finally, it is antisymmetric, since there is no case in which x is not identical with y, R(x, y), and R(y, x) are all true.

So we have a partial order that produces a "bifurcation"! And it's easy to see why this isn't linear.

OK, on reflection I have no idea what Zalabardo means by a "loop"! You'd think he means something like this:

But that's not possible in an ordering, regardless of whether it's strict or partial. We have R(a, b) but by transitivity we also have R(b, a), violating the requirement of antisymmetry and preventing R from being a partial ordering. We'll also have <a, a>, <b, b>, etc., so the irreflexivity condition for a strict ordering is also violated. Here's what the above diagram looks like if we add all the additional relationships that are consequences of transitivity:

Do you folks have any idea what he could mean by a "loop" -- something which looks loop-ish, but doesn't violate the constraints on being an ordering? I haven't come up with anything, but I'm reluctant to say he's slipped up here. More likely I'm just missing something obvious.

Here's one other thing that can happen in a nonlinear ordering but can't in a linear one. We can have clumps of ordered items that aren't connected with one another. The clumps can be either linear or not; if they are, they are chains.

So for instance, let's let B = {a, b, c, d, e, f, g}. Then the following is a cluster of clumps:

Here R = {<a,b>, <b,c>, <b,d>, <a,c>, <a,d>, <e,f>, <f,g>, <e,g>}. It's transitive and irreflexive, so it's a strict ordering. But we have two clumps of items with no connection between them.

Miscellaneous things to notice: {e, f, g} is a chain in B (relative to R).

Also of some interest: relative to R, B has two minimal elements and three maximal elements.