In first-order logic, it is possible for a sentence $S$ and its negation $\lnot S$ to both be invalid. That is, it is possible for there to not exist a proof of $S$, and also not of $\lnot S$.

For instance, consider the following sentence $S$, followed by its negation:

  • $\exists x \exists y \lnot (x = y)$
  • $\forall x \forall y (x = y)$

$S$ states that there exist two objects that are not equal, and $\lnot S$ states that all objects are equal. Neither of these sentences are valid, because first-order logic says nothing about the size of the universe. If the universe has only one object, the sentence is true, and if not, it is false.

My question: the problem is that $S$ can hold only in some models of first-order logic, and $\lnot S$ can also hold only in some models. If we restrict the cardinality of the set of objects in our logic, then do we end up in a situation where a sentence either holds (e.g. are "valid" for those models), or where its negation holds?

If not, how does this fail?

Note that this is different than asking whether we can prove every sentence or its negation within some theory, which we know is not true because there can be more than one model of a theory with the same cardinality. I am asking about proving the validity of a first-order sentence in general, or proving its negation, if the cardinality of the universe is somehow specified.

  • 2
    $\begingroup$ "$T\vdash S$ or $T\nvdash S$" is provably true because $A\lor \neg A$ is a logical axiom $\endgroup$ – Max Oct 20 '17 at 17:31
  • $\begingroup$ No. $S \lor \lnot S$ is valid, but this does not imply that either $S$ or $\lnot S$ is valid. The same applies to your claim about provability for the reason stated - for a finitely axiomatizable theory, this can be converted to a sentence, and for a countable one, we can extend this principle via compactness. $\endgroup$ – Mike Battaglia Oct 20 '17 at 17:40
  • $\begingroup$ For a straightforward application of this principle to show exactly why your claim is wrong, let $T$ be the trivial theory where the only axiom $A$ is that $\forall x (x=x)$. This is always true. Regardless, if you look at that original sentence $S$ in my post, the sentences $\lnot A \lor S$ and $A \land \lnot S$ are NOT both valid, because there are universes in which both sentences don't hold. Their disjunction, $(\lnot A \lor S) \lor (A \land \lnot S)$ is valid, because in every universe you either have all elements equal or there exist two equal elements, but that doesn't mean much. $\endgroup$ – Mike Battaglia Oct 20 '17 at 18:04
  • $\begingroup$ And I'm a bit disappointed that that comment was upvoted, as it just adds to the noise here. Perhaps I should move this question to MathOverflow. $\endgroup$ – Mike Battaglia Oct 20 '17 at 18:04
  • 2
    $\begingroup$ That's not at all what I'm saying. You're asking "can you always prove $T\vdash S$ or $T\nvdash S$", and I'm saying "yes you can prove that", which is not at all saying "$S$ is valid or $\neg S$ is valid", which is clearly false $\endgroup$ – Max Oct 20 '17 at 18:36

No, restricting the size of the model doesn't change anything. Take e.g. the sentence $S\equiv$ "$\forall x(U(x))$" (where $U$ is a unary predicate symbol); for every cardinal $\kappa$, there will be structures of size $\kappa$ satisfying $S$ and structures of size $\kappa$ satisfying $\neg S$.

Meanwhile, if you are looking only at structures in the empty language, then the answer to your question is "yes," but for a trivial reason: any two structures in the empty language with the same cardinality are isomorphic.

EDIT: here's a quick exercise. Show that a pair $(L,\kappa)$ - where $L$ is a first-order language and $\kappa$ is a cardinal $>0$ - has the property $$\mbox{"Every $L$-sentenceis either true of every structure of size $\kappa$ or false of size $\kappa$"}$$ if and only if one of the following holds:

  • $\kappa=1$ and $L$ contains no relation symbols. (As is standard, I'm viewing "$=$" as a logical symbol, not a relation symbol, here.)

  • $L$ is empty.

  • $L$ consists of a single constant symbol.

Also, contra your last paragraph: we can specify the cardinality of the model with a first-order sentence, in some cases. Namely, if we want to restrict attention to structures of cardinality $n$ where $n$ is finite, this can be done: for each finite $n$ there is a sentence $\varphi_n$ in the empty language which is true in exactly those structures of size $n$. "True in every structure of size $n$" (for $n$ finite) is exactly the same as "Provable from the theory $\{\varphi_n\}$." So I'm not really sure what you're getting at, in your last paragraph.

(For completeness: let $\psi_m$ be the sentence "$\exists x_1...\exists x_m(\bigwedge_{1\le i<j\le m}x_i\not=x_j)$." Then we set $\varphi_n=\psi_n\wedge\neg\psi_{n+1}$.)

  • $\begingroup$ Thanks, glad I clarified! This is helpful. A terminology point - when you say "first-order language" here, are you using this to mean the set of first-order sentences that can are entailed by some theory? And by the empty language, do you mean the theory with no axioms? $\endgroup$ – Mike Battaglia Oct 21 '17 at 2:54
  • 1
    $\begingroup$ @MikeBattaglia No - by "language" I mean what is also sometimes called the "signature" or "vocabulary:" the set of function, constant, and relation symbols being used (that is, the set of nonlogical symbols). For example, a structure in the empty language is just a set. $\endgroup$ – Noah Schweber Oct 21 '17 at 3:20
  • $\begingroup$ So by the empty language you mean the universe has cardinality zero, right? In other words, no objects, and hence no predicates, functions, etc. $\endgroup$ – Mike Battaglia Oct 21 '17 at 3:26
  • 1
    $\begingroup$ @MikeBattaglia No, the size of the universe is unrelated to the size of the language. A structure in a language is a set together with an interpretation; if the language is empty, that means the interpretation is just the empty map, so a structure in the empty language is just a set. (Maybe easier to think about: the language of groups has (usually) three symbols, but there are groups of size $\not=3$. The empty language is no different.) $\endgroup$ – Noah Schweber Oct 21 '17 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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