How to convert numerical claims to first order logic?

Solution 1:

Here are some possible ways to make these kinds of numerical claims in general:

'At least n' (Method 1)

"There is at least 1 P" : $\exists x P(x)$

"There are at least 2 P's" : $\exists x \exists y (P(x) \land P(y) \land x \not = y)$

"There are at least 3 P's" : $\exists x \exists y \exists z (P(x) \land P(y) \land P(z) \land x \not = y \land x \not = z \land y \not = z)$

Etc.

Note that with this method you need to use $n \choose 2$ non-identity claims (in addition to $n$ $P$ claims) so that increases rather quickly (e.g. to express there are at least 10 P's, we would need 45 non-identity statements! ... can we improve on that? Yes! But first let's discuss 'at most':

'At most n' (Method 1)

One method to do 'at most n' is to deny 'at least n+1'. So:

"There is at most 1 P": $\neg \exists x \exists y (P(x) \land P(y) \land x \not = y)$

If you bring the negation inside, this is equivalent to: $\forall x \forall y ((P(x) \land P(y)) \rightarrow x = y)$

"There are at most 2 P's": $\neg \exists x \exists y \exists z (P(x) \land P(y) \land P(z) \land x \not = y \land x \not = z \land y \not = z)$

Again, bringing the negation inside you get:

$\forall x \forall y \forall z ((P(x) \land P(y) \land P(z)) \rightarrow (x = y \lor x = z \lor y = z))$ ... which is what goblin did!

Etc.

OK, so here we get even more (non-)identity statements: $n+1 \choose 2$ (in addition to n+1 $P$ claims). Later we will see how we can do this more efficiently, but first:

'Exactly n' (Method 1)

One method is to recognize that 'Exactly n' is equivalent to 'at least n and at most n'. Doing a straightforward conjunction, we thus get:

"There is exactly 1 P" : $\exists x P(x) \land \neg \exists x \exists y (P(x) \land P(y) \land x \not = y)$

or, equivalently: $\exists x P(x) \land \forall x \forall y ((P(x) \land P(y)) \rightarrow x = y)$

"There are exactly 2 P's" : $\exists x \exists y (P(x) \land P(y) \land x \not = y) \land \neg \exists x \exists y \exists z (P(x) \land P(y) \land P(z) \land x \not = y \land x \not = z \land y \not = z)$

or, equivalently: $\exists x \exists y (P(x) \land P(y) \land x \not = y) \land \forall x \forall y \forall z ((P(x) \land P(y) \land P(z)) \rightarrow (x = y \lor x = z \lor y = z))$

Etc.

'Exactly n' (Method 2)

OK, so these claims get really big really fast. Can we do better? Yes. In stead of just conjuncting the 'at least' and 'at most' claims, let's integrate these two ideas: To say there are exactly $n$ P's, we can say that there are $n$ different P's ... but no others:

"There is exactly 1 P" : $\exists x (P(x) \land \neg \exists y (P(y) \land x \not = y))$

or, equivalently: $\exists x (P(x) \land \forall y (P(y) \rightarrow x = y))$

"There are exactly 2 P's" : $\exists x (\exists y (P(x) \land P(y) \land x \not = y) \land \neg \exists z (P(z) \land z \not = x \land z \not = y))$

or, equivalently: $\exists x \exists y ((P(x) \land P(y) \land x \not = y) \land \forall z (P(z) \rightarrow (z = x \lor z = y)))$

"There are exactly 3 P's" : $\exists x \exists y \exists z ((P(x) \land P(y) \land P(z) \land x \not = y \land x \not = z \land y \not = z \land \neg \exists w (P(w) \land w \not = x \land w \not = y \land w \not = z))$

or, equivalently: $\exists x \exists y \exists z ((P(x) \land P(y) \land P(z) \land x \not = y \land x \not = z \land y \not = z \land \forall w (P(w) \rightarrow (w = x \lor w = y \lor w = z)))$

Etc.

Interestingly, we see that in the second half of the statement, we no longer get $n+1 \choose 2$ (non-)identity claims plus $n+1$ $P$ claims, but merely $n$ (non-)identity claims and exactly one $P$ claim, because we end up saying: once you have your $n$ different P's, then any P is one of the $n$ objects, so you can't have any more than $n$. This is an idea that we can use to write the 'at least' and 'at most' claims more efficiently as well:

'At most n' (Method 2)

As just observed, we can say that there are exactly $n$ P's by saying that if you already have $n$ different P's, you can't get any other $P$. But to say that there are 'at most' $n$ P's, we don't have to require those $n$ P's to be different. In fact, we don;t even have to require that they be P's: we can simply say that we can pick $n$ objects, that may or may not be different, and that may or may not be P's, such that there is no object that is different from all those, and that is a P. So:

'There is at most one P' : $\exists x \forall y (P(y) \rightarrow y = x)$

Again, notice that I am not saying that $x$ is a P ... this statement would also be true if there are not any P's at all (of course, I do need a non-empty domain, but that assumption is typically built into our logic systems). However, any P's that do exist will have to be the same ... hence there is at most 1 P.

"There are at most 2 P's" : $\exists x \exists y \forall z (P(z) \rightarrow (z = x \lor z = y))$

Again, this is not saying that $x$ and $y$ are P's, but they could be. And I am also not claiming that $x$ and $y$ are different ... but they could be. Hence, you can have 0,1, or 2 different P's, but you definitely can't have 3 or more!

"There are at most 3 P's" : $\exists x \exists y \exists z \forall w (P(w) \rightarrow (w = x \lor w = y \lor w = z))$

Etc.

So, in general, the claim is that there are $n$ objects such that any $P$ has to be one of those objects, and that means that you can't have more than $n$ P's.

The nice thing about this expression is that it uses exactly $n$ identity statements, so it is quite a bit more efficient to write than the first method for expressing 'at most', especially for large n. In fact, you only have to use exactly one $P$ predicate, instead of $n$.

'At least n' (Method 2)

We pointed out earlier that 'at most n' is the negation of 'at least n+1', but that also means that 'at least n+1' is the negation of 'at most n'.

So:

"There are at least 2 P's": $\neg \exists x \forall y (P(y) \rightarrow y = x)$ which is equivalent to $\forall x \exists y (P(y) \land y \not = x)$

The latter statement says that for whatever object $x$ I pick, I can always find a different object that is a P. So, if there would be only one P, then that wouldn't be true, since I can pick that P for the $x$, and now there is no different $y$ that is also a $P$. So, you need at least 2 P's to make this true.

"There are at least 3 P's": $\neg \exists x \exists y \forall z (P(z) \rightarrow (z = x \lor z = y))$ which is equivalent to: $\forall x \forall y \exists z (P(z) \land z \not = x \land z \not= y)$

Etc.

To say that there are at least $n$ P's, we can say that no matter how you pick $n-1$ objects (so even if those are all different and all P's), you can always find an object different from all those, and that is a P.

And, once again, this method saves us a lot of writing: only $n-1$ identity claims plus 1 $P$ claim.

'Exactly n' (Method 3)

In the second method for 'exactly n', we saw that a claim like "There are exactly 3 P's" translated into:

$\exists x \exists y \exists z (P(x) \land P(y) \land P(z) \land x \not = y \land x \not = z \land y \not = z \land \forall w (P(w) \rightarrow (w = x \lor w = y \lor w = z))$

Thus, while in the second half we reduce the number of identity and $P$ statements in comparison to the first method, we still get $3 \choose 2$ non-identity claims, and $n$ $P$ claims in the first half. Now, one trick to get rid of all the $P$ claims in the first half is to do this:

"There is exactly 1 P" : $\exists x \forall y (P(y) \leftrightarrow x = y)$

"There are exactly 2 P's" : $\exists x \exists y (x \not = y \land \forall z (P(z) \leftrightarrow (z = x \lor z = y))$

"There are exactly 3 P's" :

$\exists x \exists y \exists z ( x \not = y \land x \not = z \land y \not = z \land \forall w (P(w) \leftrightarrow w = x \lor w = y \lor w = z))$

That is, by using a biconditional, any of the existentially quantified objects will have to be a $P$, so we don;t have to individually specify this.

Of course, the drawback of this method is that we still have $n \choose 2$ non-identity claims.

'Exactly n' (Method 4)

Especially for large $n$ then, the most efficient way to express 'exactly n' seems to be the conjunction of the efficient ways to expressing 'at least n' and 'at most n'. That is:

"There are exactly 2 P's" : $\forall x \exists y (P(y) \land y \not = x) \land \exists x \exists y \forall z (P(z) \rightarrow (z = x \lor z = y))$

"There are exactly 3 P's" : $\forall x \forall y \exists z (P(z) \land z \not = x \land z \not= y) \land \exists x \exists y \exists z \forall w (P(w) \rightarrow (w = x \lor w = y \lor w = z))$

(ok, so these two are not any more efficient than earlier ones, but again, once $n$ gets large, this method will be most efficient, as it has $2n-1$ non-identity claims, and 2 $P$ claims.)

Wow, ok, so that turned out to be a much larger post than I intended, sorry!