0

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$?

user2346
  • 631
  • 2
  • 7
  • 14

1 Answers1

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.

MJD
  • 65,394
  • 39
  • 298
  • 580