2
$\begingroup$

Would a proposition of first-order logic, with N quantifiers, always held the same logical status (of consistency or validity) no matter if the domain has N members, or N + x members? [x being a finite number]

I intuitively think the answer is YES, but what about any kind of proof?!

  • 0
    It sounds like you might have an odd conception of quantifiers. Could you say what you think quantifiers are, how they work, or what your own reasoning about the answer is?2012-03-23

1 Answers 1

2

Let $\mathcal{L}$ be the first-order language with equality that has a single binary predicate symbol $R$. Write down the following sentence, which I describe informally:

1) It is never the case that $R(x,x)$ and

2) $R(x,y)$ iff $R(y,x)$, and

3) for any $x$, there is a unique $y$ such that $R(x,y)$.

The sentence we have given a recipe for is satisfiable in any finite set that has a (non-zero) even number of elements, but not in any finite set that has an odd number of elements. We can modify the sentence by throwing in however many quantifiers that do nothing. Satisfiability of a sentence of this type in a domain of size $N$ does not imply satisfiability in a domain of size $N+1$.