Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I corrected "n finite" to "a finite". If you meant "an infinite" please fix it. –  Ross Millikan Mar 21 '12 at 20:59
    
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? –  Rachel Mar 23 '12 at 19:23

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.