# Decidability of predicate logic

In the language of predicate logic with only identity and no predicates, function symbols, or constants, is it possible to construct infinitely many non-equivalent formulas?

• Maybe I'm missing something, but without predicates how would any such formula not just be tautological or false? – Veedrac Aug 5 '19 at 4:33
• @Veedrac Surprisingly, we can actually get a bit of variety - see my answer below. – Noah Schweber Aug 5 '19 at 14:39
• In the interests of moving this off the "unanswered" queue, is there a further point you'd like explained? – Noah Schweber Aug 26 '19 at 19:23

First, let's observe (in response to a comment) that we can get infinitely nonequivalent sentences; this isn't what you want, but it demonstrates that the situation is nontrivial. Namely, we can talk about cardinality, via the following statements which are easily seen to be appropriately expressible:

N(n): There exist x_1,...,x_n which are all distinct.

This sentence says that the domain has size at least n. And these are clearly not independent.

Exercise 1: show that this is essentially all we can do - that every sentence in our language is (i) determined up to logical equivalence by the set of cardinalities of its finite models, called its spectrum, and (ii) every sentence in our language is either true in all sufficiently large finite models or false in all sufficiently large finite models. (HINT: note that a structure in our language is determined up to isomorphism by its cardinality alone, and use the Compactness and Lowenheim-Skolem theorems ...)

The key idea is the following:

Claim: There is a set S={a_i: i a natural number} of infinite binary strings such that: (1) for all distinct numbers i, j there is some m such that the mth term of a_i is a 0 but the mth term of a_j is a 1; (2) every a in S eventually consists of all 1s; and (3) the first term of a is 0, for every a in S.

REMARK: there were a couple serious errors in my original write-up of this. First, note that condition (1) above is "symmetric" - it also tells us that whenever i, j are distinct there is some m such that the mth term of a_j is a 0 but the mth term of a_i is a 1. This is essential to the argument below, but my phrasing was pretty unclear on this point in my original writeup. Second, and more substantively, condition (3) was missing entirely, and without it we don't get full independence - without it, perhaps two sentences in our set are not consistently both false, and indeed the example I originally proposed has this problem.

First, let's see how this claim will give an affirmative answer to your question. Suppose we have such an S. The key point is that we can turn this S into a set of sentences {p_i: i a natural number} where the sizes of p_i's finite models correspond to the sequence a_i. Specifically, we'll define p_i to be the conjunction - over all k for which the kth bit of p_i is a 0 - of the sentences "There are not exactly k elements in the universe." Condition (2) says that there are only finitely many such k, so this is in fact a sentence in our language.

The set of finite models of p_i are exactly those m such that the mth term of a_i is a 1. Now suppose we have distinct natural numbers i and j.

• By condition (1) on S, whenever we have distinct i and j we get a number which is the size of a model of p_i but is not the size of a model of p_j. So both {p_i, ~p_j} and {~p_i, p_j} are consistent.

• By condition (2) we know that that any sufficiently large structure satisfies both p_i and p_j. So {p_i, p_j} is consistent.

• And finally, by condition (3) we know that the structure with one element satisfies both ~p_i and ~p_j, so {~p_i, ~p_j} is consistent.

So all four possibilities are consistent, meaning that S does indeed consist of pairwise independent sentences.

Now we just need to prove the claim. This is a nice combinatorial problem, and it's worth trying to prove yourself, so to avoid spoiler's I've rot13'd the answer:

Gnxr gur frg bs nyy frdhraprf juvpu ortva jvgu n mreb naq unir rknpgyl bar bgure mreb. Fb, sbe rknzcyr, gur frdhrapr "mreb bar bar mreb bar bar bar bar ..." vf va bhe frg, ohg arvgure "bar mreb mreb bar bar bar bar ..." abe "mreb bar mreb mreb bar bar bar bar ..." ner. Gur guveq pevgrevba sbe bhe pynvz vf fngvfsvrq vzzrqvngryl, naq gur frpbaq pevgrevba ubyqf fvapr gjb vf svavgr. Svanyyl, abgr gung nal gjb qvfgvapg frdhraprf va guvf frg bayl qvssre va gjb cynprf, bar va juvpu gur svefg unf n mreb naq gur frpbaq unf n bar naq gur bgure va juvpu gur svefg unf n bar naq gur frpbaq unf n mreb, naq guvf fngvfsvrf gur frpbaq pevgrevba bs gur pynvz.

And now let me end with a second problem:

Exercise 2: note that I was very careful in the above to talk about sets of pairwise independent sentences. Show that there are no fully independent infinite sets of sentences - where a set {p_i: i in I} of sentences is fully independent if for every subset A of I, the union of the sets {p_i: i in A} and {~p_j: j not in A} is consistent. (HINT: show that for every sentence p in such a set, both p and ~p would have to have arbitrarily large finite models, contradicting the exercise near the start of this answer.)

• @Veedrac Huh, weird formatting fun - not putting spaces next to the less-than sign hid the remaining text. Fixed! – Noah Schweber Aug 6 '19 at 11:03
• @Veedrac I botched some stuff. Fixed. – Noah Schweber Aug 6 '19 at 15:11
• This makes way more sense to me now, thanks! – Veedrac Aug 7 '19 at 6:00