2 of 2

29.2 “At Most”

Learning to translate “at least” in the previous section was hopefully pretty intuitive. “At most” is a bit messier.

“At most n” means n or fewer. Maybe none!

First notice that saying “There are at most 2 dogs” doesn’t tell us that any dogs exist. “At most 2” means 2 or fewer.

“There are at most two dogs” is true if there are 2, 1 or 0 dogs. That tells us we don’t want an existential quantifier.

Instead, what we’ll say in FOL is: If variables x, y and z all pick out dogs, then two or more of those variables need to be picking out the same dog.

It looks like this:

∀x∀y∀z((D(x)&D(y)&D(z))→(x=y v x=z v y=z))

Recall that generalizations in FOL can be vacuously true, so this does what we wanted: it doesn’t entail the existence of any dogs.

“At most n” takes n+1 universal quantifiers.

Notice that the number of equalities you need in the consequent of the arrow also depends on what number n we are saying there are “at most n” of.

For “at most 1”, we need 1 equality. For “at most 2”, we need 3. The progression works by triangular numbers here as well.