# Expressing a first order logic sentence that requires counting

Given the set $R(x,t)= \{ (a, 1), (b, 1), (c, 1), (a, 2), (b, 2) \}$. How can I express with a first-order logic sentence "if for $t$ the amount of tuples $(x, t)$ is equal to $d$, then for $t+1$ the amount of tuples $(x,t+1)$ is equal to $d$, $d+1$ or $d-1$?

For example, at $t=1$, $d=3$ so at $t=2$ $d$ should be $2, 3$ or $1$.

-
If we have an explicit upper bound for $d$, as is the case in this example, there is no problem. Suppose now there is no such bound. Then in general it cannot be done without extending the language to include a significant fragment of formal number theory, since sentences cannot be of variable length. – André Nicolas Dec 21 '12 at 18:50
Thank you @AndréNicolas. I would accept if it were an answer, since it cannot be expressed in my case. – codd Dec 22 '12 at 20:55

If we have an explicit upper bound for $d$, as is the case in this example, there is no problem. So for example in the language of elementary graph theory, one can say that there is a path of length $\le 17$ joining any two points.

Suppose now there is no such bound. Then in general it cannot be done without extending the language and theory to include a significant fragment of formal number theory, since sentences cannot be of variable length.

There are partial workarounds. For example, in the language of elementary field theory, one can, by adding an infinite number of sentences, produce a theory all of whose models are algebraically closed. But one cannot do it with a single sentence (or equivalently a finite set of sentences).

-

As André Nicolas said, if you have no bound on $d$, then you can't express "$A$ has one more element than $B$" in first-order logic. André suggests adding formal number theory to first-order logic, and this will indeed work. Another possibility is to go slightly beyond first-order logic, allowing one existential second-order quantifier. Then you can formalize "there is an $a\in A$ and there is a function $f$ that is a bijection between $A-\{a\}$ and $B$." Alternatively (as long as $d$ is finite) you can get by with a single universal second-order quantifier, saying "For every one-to-one function $f$ whose domain is a subset $B'$ of $B$ and whose image is a subset $A'$ of $A$, the range is not all of $A$ and, furthermore, if the domain is all of $B$ then the range is all of $A$ except for exactly one element." It's unpleasantly long, but probably still easier than incorporating a lot of number theory.

-

Let's say we're trying to express "there exist exactly two $x$ such that $\phi(x)$".

1. We need to say that there are two things, $x_1$ and $x_2$, satisfying $\phi$.
2. $x_1$ and $x_2$ should be distinct.
3. $x_1$ and $x_2$ should be the only elements satisfying $\phi$. That is, for anything else $y$ which satisfies $\phi$, $y$ should be equal to $x_1$ or $x_2$.

$\exists x_1\,\exists x_2\, \phi(x_1)\land\phi(x_2)\land(x_1\neq x_2)\land(\forall y\,\phi(y)\rightarrow (y = x_1 \lor y = x_2))$

Now can you generalize "there exist exactly $n$"?

-
Yes, but I don't see how I can apply it on my problem. With this I can say there exist exactly $n$ for a specific $n$, but I want to be able to be more abstract and say if it's $d$ at $t$ then it should be $d+1$ or $d$ or $d-1$ at $t+1$. – codd Dec 21 '12 at 13:31
Ah, I misread your question, sorry. I didn't realize that $d$ was variable depending on $t$. In this case, Andre Nicolas's comment is correct. – Alex Kruckman Dec 22 '12 at 16:22