0
$\begingroup$

Let $FO-SIZE[s(n)]$ be the set of properties expressible by uniform sequences of first- order formulas, $\{\phi_{i}\}_{i\in \mathbb{Z^+}}$ , such that the $n$th formula has $O(s(n))$ symbols and expresses the property in question for structures of size $n$.

So, does this mean that the total number of formulae for expressing a property is $n$?

1 Answers 1

0

No, there are an infinite number of formulas for any expressible property. If $F$ is some formula that expresses the property, then you can always add $\lnot\lnot$ to the front to obtain a longer formula expressing the same property.