ORDERING RELATIONS

A paradigm example of an ordering relation is the relation < (is less than or equal to) on the domain of rational numbers. As we noted in the previous chapter, this relation is not asymmetric, since, for example, 3/3 < 1 but it is not the case that -∣ 1 < 3/3.

A binary relation R is antisymmetric iff

An equivalent definition of antisymmetry is:

A binary relation R is antisymmetric iff

Another characteristic feature of this relation is that any pair of rational numbers x and ó are related by it: either x > ó or ó > x. Any relation having this property is said to be totally connexive^x on its domain:

A binary relation R is totally connexive iff

Now one might think that this is a common property, shared for instance by the relation > on rationals, or the alphabetical ordering of the letters of the alphabet. But a little further reflection (!) shows that this cannot be, for if x and ó are the same individual u, then total Connexivity would give uRu v uRu, i.e., uRu, allowing a proof of reflexivity. But asym­metric relations cannot be reflexive: no number can be greater than itself, and no letter can precede itself in the alphabet. Things are otherwise if we are talking about pairs of different numbers or letters, however; for if x ≠ ó, the relation x > ó or ó < x will hold for rational numbers, and similarly for distinct letters in alphabetical order.

A binary relation R is simply connexive iff

Of course, a given relation R could also fail to be connexive. This would happen if there were pairs of individuals in the domain that were not related by R. For example, the rela­tion “is a COUSIN₂ of’ on all the individuals who are cousins of mine is nonconnexive. An individual who is a cousin of mine on my mother’s side of the family is not a cousin of someone who is a cousin of mine on my father’s side. We therefore have a fourth family of relational properties, the Connexivity family: 693" class="lazyload" data-src="/files/uch_group76/uch_pgroup316/uch_uch7361/image/image691.jpg">

¹ The terminology among logicians is not very uniform here. A totally connexive relation is also called strongly connexive or just plain total.

Meanwhile the full symmetry family is:

Unlike the groups of properties of relations in the last chapter, however, it is not the case that a relation may have only one property from each of these groups. As we have already noted, > is both nonsymmetric and antisymmetric. Also, any binary relation that is totally connexive is also simply connexive (exercise below), and any binary relation that is asymmetric is also simply antisymmetric (exercise below).

A relation that is antisymmetric and transitive on a given domain is said to induce an ordering on that domain. If the relation is also reflexive it is a (weak) partial ordering; if it is in addition totally connexive, this is a (weak) total ordering. If the relation is asym­metric and transitive, and therefore irreflexive, the ordering is a strict partial ordering. If in addition it is simply connexive, it is a strict total ordering. In sum,

An ordering relation is a relation that is transitive and antisymmetric.

A weak partial ordering relation is transitive, antisymmetric, and reflexive.

A weak total ordering relation is transitive, antisymmetric, and totally connexive.

A strict partial ordering relation is transitive, asymmetric, and irreflexive.

A strict total ordering relation is transitive, asymmetric, and simply connexive.

There are further relations between these orderings. For example, every weak total order­ing, such as < on the rational numbers, has associated with it a strict total ordering, such as works for most if not all relational statements, and I would recommend that you apply it whenever you can. It is the safest way to ensure that you have the right quantifiers in the right order. A further example:

(S4) “Every CHARACTER HAS₂ at least one FLAW.”

22.1.2 PRENEX FORMS (challenge level)

It is important to realize that many equivalent alternative symbolizations of these state­ments are possible. For instance, (S4) above could have been symbolized as:

On inspection, we see that (F4a) is the same as (F4) except that all the quantifiers are out in front in the same order. An expression with all the quantifiers governing it lined up in front like this is said to be in Prenex Normal Form (or just prenex form for short).^[LXXXVI]

This raises two questions: (i) is it always possible to symbolize a statement in prenex form—or equivalently, can any symbolized statement be put into prenex form? (The answer is yes!); and (ii) does converting a statement that isn’t in prenex form into one that is just involve pulling all the quantifiers out of the middle and putting them in front? Let’s see. Consider:

(S5) ^tTfHilda RESIGNS, then everyone will.” [UD: people]

A natural symbolization would be:

In prenex form:

Here (F5a) has been obtained from (F5) simply by pulling out the quantifier in front of the consequent and then putting it in front to quantify the whole conditional.

(Check to make sure that no restrictions on UI have been violated.) You should try:

But what about this statement:

(S6) “If anything will CAUSE Hilda to resign, this will.”

We know that in statements like this the “anything” in the antecedent stands for “some­thing,” so (S6) is symbolized as:

But we know this is not logically equivalent to

but to

Now this holds generally: when the antecedent of a conditional is an existential quan­tification, then we must change this to a universal quantifier when sticking it in front to convert the statement to prenex form. More examples:

Note that Vx(Fx → Gx) is not logically equivalent to any of the three latter statements. ⁴Tf someone finds the net, everyone goes home” is not the same as “Anyone who finds the net goes home.” Also note thatis not a wff, since no variable in a wff is

bound by—occurs within the scope of—more than one quantifier.

Again, when the antecedent of a conditional statement is a universal quantification, when we pull the quantifier out in front it changes to an existential quantifier. Examples:

Here’s a proof of the first of these equivalences:

22.2