How many Romans?More Advanced Topics

CENTURION: But ‘Romans, go home’ is an order, so you must use the…?
BRIAN: The… imperative!
CENTURION: Which is…?
BRIAN: Umm! Oh. Oh. Um, ‘i’. ‘I’!
CENTURION: How many Romans?
BRIAN: Ah! ‘I’— Plural. Plural. ‘Ite’. ‘Ite’.
 
Monty Python: The Life of Brian

It often happens—and not just to please a passing centurion—that we wish to state the existence of things (in the plural) satisfying a description. The existential quantifier allows us to say that there exists such a thing as a Roman, but how are we to say there are Romans, meaning more than one? The formula in the constraints box to the right may look like a reasonable candidate, but try clicking “Solve” and you will see that it doesn’t work. Go on: click it!

The first model found by the solver has the domain consisting of four persons as specified, but only one person in it is a Roman. Hence the formula in the box does not say that there is more than one Roman, because it is satisfied in a domain where there isn’t more than one. The problem is that x and y are both the same person: (namely, Aurelia in that case).

To prevent this from happening, we need to add another atom to the conjunction, saying that x and y are not identical:

SOME x SOME y ( Roman(x) AND Roman(y) AND NOT (x = y) ).

Now if we ask the solver to satisfy the constraint, we get a model with two people, Aurelia and Brutus, who are both Romans, as required. An equivalent formula, a little shorter and more convenient, would be

ALL x SOME y ( Roman(y) AND NOT (x=y) ).

The technique for saying that there are at least two things of some kind extends to “at least three…”, “at least four…” and so forth. For example, to require the existence of three little pigs, we might write

ALL x ALL y SOME z ( little(z) AND pig(z) AND NOT (x=z OR y=z) ).

Clearly, to say that there are at most three bears, at most seven dwarves, etc. is the same as saying there are not four or more bears, not eight or more dwarves, etc. Since we know how to say “at least n” and have negation in the language, we can also say “at most n”.

Finally, there are exactly two ugly sisters if there are at least two and at most two. Since we have AND in the language, we can say that too. The most useful such numerical phrase is “exactly one”, which expresses unique existence. There is exactly one big bad wolf:

SOME w ALL x ( (big(x) AND bad(x) AND wolf(x))   IFF   x = w ).

Notice that this implies the existence of a big bad wolf, because there is this thing w which is identical to itself and therefore big, bad and a wolf. It also implies uniqueness: take any big bad wolf you like and it will turn out to be w. That is, there is no choice.