predicate logic/binary relation help

(1) ∀x, y, z (x < y ∧ y < z → x < z) (transitivity)

(2) ∀x ¬(x < x) (antisymmetry)

(3) ∀x, y (x < y ∨ x = y ∨ y < x) (linearity)

I need to give an example of a (nonempty) structure with one binary relation that satisfies (1)and (2) but not (3), and in addition the formula ∀x ∃y (x < y). I was thinking naively of y = x + 1 but im certain this is wrong.

I'm essentially trying to find a structure where every X there is a bigger y.

• Your update to your question is a good hint. Here is a further hint. Suppose you have a biggest element and no other relationships. – Apass.Jack Nov 26 '18 at 15:12

This sounds like homework, and I do not wish to ruin the value of your homework for you by giving answers too quickly; the point of homework is to exercise and solidify the skills learned in the lesson. So I will approach this step by step; please follow along carefully, and try to find an answer yourself before I start considering possible answers.

First, note that the problem makes heavy use of an asymmetrical binary relation, represented by $$<$$. This is apt to confuse the student, so I will instead use $$\prec$$, which probably has no particular associations for students at this level. The point is, we are not talking about the familiar “less than” relation, nor necessarily about numbers.

We are instead talking about (1) some binary relation, which (2) is asymmetrical, i.e. $$a\prec b$$ is not the same as $$b\prec a$$, and which (3) is well-defined for pairs of elements drawn from some set. It doesn’t have to be a set of numbers; we could be talking about graphs, matrices, vectors, sets … universities … bananas … any number of things.

Note, also, that $$\prec$$ does not have to necessarily be defined for all pairs of elements; there could be some pairs where it’s simply meaningless. More on that below.

So. We need to find a set of elements, such that some relation $$\prec$$ is defined for at least some pairs of elements, and that satisfies some of these properties but not others. So let’s take a closer look at the properties.

(1) $$\forall x,y,z(x\prec y\land y\prec z\rightarrow x\prec z)$$ (transitivity)

Meaning, elements can to some extent be ordered: if $$x$$ is “before” or “over” or “colder than” or “hoopier than” $$y$$, and the same is true of $$y$$ with respect to $$z$$, then the same is true of $$x$$ w.r.t. $$z$$. Note that this doesn’t necessarily mean that all of the elements can be ordered relative to each other. For example, in a family or other tree structure, one node can be “an ancestor of” another, and this is transitive, but siblings, cousins, etc. cannot be ordered in this way. We say the set is partially ordered, but not necessarily totally ordered.

(2) $$\forall x\neg(x\prec x)$$ (antisymmetry)

This just means that no element can be its own “ancestor”, thus ruling out, for example, directed graphs that contain any cycles.

(3) $$\forall x,y(x\prec y\lor x=y\lor y\prec x)$$ (linearity)

This means that the elements can all be placed on a line, so that the set is totally ordered. This is the one we need to avoid, so we can’t use any set that is totally ordered by $$\prec$$.

(4) $$\forall x\exists y(x\prec y)$$

This means that every element has some other element that is, e.g., “scarier than” it. Since (2) ruled out cycles, this implies that the set must be infinite; otherwise, some element (possibly more than one) would be as “scary” as possible, with nothing coming after it.

Note that this doesn’t necessarily work in both directions. For the set of natural numbers, every number has a successor, but $$1$$ does not have a predecessor.

At this point, hopefully, the student’s thinking has been loosened up a bit, and concrete ideas have become more abstract. So, for example, can we use the integers, or rationals, or real numbers, with $$<$$? No, because that satisfies all four properties, including (3) which we are trying to avoid.

What about the natural numbers, with $$\prec$$ meaning “is a divisor of”? Does (1) hold? How about (2)? Ah, (2) does not hold, no good; every number divides itself. Okay then, “is a divisor of and is less than”. Now (2) holds. (3)? (4)?

How about members of a family and “is an ancestor of”? (1) is satisfied; (2) is satisfied, barring time-traveling incest; (3) is satisfied; but (4) is not, because not everyone has descendants.

Consider an infinite directed graph in the shape of a pyramid. We have one “root” node, with three descendants. Each of those descendants likewise has three descendants of its own, and this continues forever. This is like the family above, but satisfies (4) as well.

How about sets? Subsets of the natural numbers, say, with $$\prec$$ defined as “is a proper subset of”. Does (1) hold? (2)? (3)? (4)?