5

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?

  • 1
    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
  • 1
    @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
  • Incidentally, while I can understand voting to close this question on the grounds that it's more about math than philosophy (although personally I think it's fine here), note that the current vote to close is as "opinion based" - which is clearly bonkers. – Noah Schweber Feb 29 at 20:42
7

EDIT: here I've looked at sentences, as opposed to mere formulas, since the resulting situation is more interesting. If we allow formulas with free variables, then as Toothpick Anemone essentially observes below the situation is quite trivial.


Perhaps surprisingly - and contra Veedrac's comment above - we can indeed get infinitely many inequivalent sentences. 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 equivalent.

Exercise 1: show that this is essentially all we can say in first-order logic without equality. Specifically, show:

  • Every sentence in first-order logic with only equality is determined up to logical equivalence by the set of cardinalities of its finite models, called its spectrum.

  • 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 ...)


In fact, however, we can do even better: there is an infinite set of fully independent sentences in first-order logic with equality alone. Here by "fully independent" I mean that any assignment of true/false to the sentences in the set is consistent; note that this is a much stronger condition than mere pairwise independence (although by the compactness theorem it is enough to only consider finite subsets). The sentences constructed above don't qualify, since N(n) implies N(m) whenever m

The key idea is the following:

Claim: There is a set S={a_i: i a natural number} of infinite binary sequences with the following three properties:

  • (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.

  • (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 true 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 hidden the answer:

Take the set of all infinite binary sequences which begin with a 0 and have exactly one other 0. So, for example, the sequence "01101111..." is in our set, but neither "1001111..." nor "01001111..." are. The third criterion for our claim is satisfied immediately, and the second criterion holds since two is finite. Finally, note that any two distinct sequences in this set only differ in two places, one in which the first has a zero and the second has a one and the other in which the first has a one and the second has a zero, and this satisfies the second criterion of the claim.

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

| improve this answer | |
  • This makes way more sense to me now, thanks! – Veedrac Aug 7 '19 at 6:00
  • Out of curiosity, why the downvote? – Noah Schweber Feb 29 at 13:46
0

Is it possible to construct infinitely many non-equivalent formulas in predicate logic?


The answer is yes.

You do not even need the "for all" and "there exists." It is enough to have NOT, OR, IF-THEN, etc...

There are infinitely many non-equivalent formulas in propositional (zeroth order) logic. Introducing "for all" and "there exists" only increases the variety of formulas that you can make.

If there are infinitely many non-equivalent formulas in propositional (zeroth order) logic, then there are also infinitely many non-equivalent formulas in predicate (first order) logic.


EXPLANATION WHY:

  • a formula on one Boolean variable cannot be logically equivalent to a formula on two Boolean variables.
  • a formula on two Boolean variables cannot be equivalent to a formula on three variables.
  • and so on...

No two formulas can be logically equivalent if the two formulas have a differing number of input variables.

Just do the following:

  • offer an example a formula on 1 variable
  • offer an example of a formula on 2 variables
  • offer an example of a formula on 3 variables.

None of the formulas will be equivalent!

  • Let F(1) denote the formula: x1
  • Let F(2) denote the formula: x1 AND x2
  • Let F(3) denote the formula x1 AND x2 AND x3

Let us just continue that above pattern. For any number taken from {1, 2, 3, 4, 5, ...} Let F(n) denote the following formula:

x1 AND x2 AND x3 [...] AND xn


I tried to keep my explanation above pretty simple. I wanted someone without a background in mathematics to be able to understand it.

However, if you want math, then have some math:

There exists a set S subset of (the set of all formulas in propositional logic) such that

  • for all a, bS a ≠ b
  • the cardinality of set S is non-finite

PROOF:

Define mapping F from ℕ to the set of all formulas in propositional logic such that:

  • F(1) = "x1"
  • For all k{n ∈ ℕ: n ≥ 2}, F(k) = F(k -1) AND xn

Take S to be {F(n): n ∈ ℕ}

For any two formulas, a and b in propositional logic, if a and b do not have the same number of variables, then a ≠ b

For all a, bS, a and b do not have the same number of variables.

Thus, F is a bijection between and {F(n): n ∈ ℕ} the cardinality of set S is equal to the cardinality of
The cardinality of is non-finite.
Therefore, the cardinality S is non-finite.
QED


BONUS INFO:

The following is closely related to what you asked for.

Consider a mathematical "relation" (i.e. a "table" in everyday English).

This table has two inputs columns and one output column.
The two inputs are TRUE/FALSE variables and the output is TRUE/FALSE.

+----+----+--------+
| X1 | X2 | OUTPUT |
+----+----+--------+
|  0 |  0 |      0 |
|  0 |  1 |      0 |
|  1 |  0 |      1 |
|  1 |  1 |      1 |
+----+----+--------+

Consider all formulas on two variables. Do not worry about what each formula "looks like." That is, do not worry about the ANDs, and ORs, and IF-THENs. Only consider the truth tables.

How many possible truth tables for two variables are there?
Two tables always have the same input columns. Only the output columns change.

How many table rows are there? Well...

  • there are two choices (true or false) for variable 1
  • there are two choices (true or false) for variable 2.

There are 2*2 = 4 table rows.

  • For table row 1 of 4, we choose true or false for the output.
  • For table row 2 of 4, we choose true or false for the output.
  • For table row 3 of 4, we choose true or false for the output.
  • For table row 4 of 4, we choose true or false for the output.

This means that there are 2*2*2*2 different output columns.

There are 2^4 = 16 tables on two inputs.

This means that, for two input variables, you can have at most 16 formulas in zeroth order logic where no two formulas are logically equivilanet.

In general, if a table has ROW_COUNT rows, and the output value must be true or false for each input, then there are 2^(ROW_COUNT) such tables.

For example, if a table has 4 rows, then there are 2^4 = 16 such tables.

What about logical formulas with 3 input variables?

An example of a formula with 3 input variables is x1 OR (x2 AND x3)

How many table rows are there?

  • 2 choices for x1
  • 2 choices for x2
  • 2 choices for x3

There are 2*2*2 = 2^3 = 8 table rows.

For each row, you have to choose true or false for the output column.

So, there are 2^(ROW_COUNT) = 2^8 = 256 such tables.

If every formula has exactly 3 variables, then you can write down at most 256 formulas before you are forced to write down a formula logically equivalent to one of the already written formulas.

In general, if you have n variables, then you can have at most 2^(2^n) distinct formulas.

  • There are 2^(2^1) = 4 distinct formulas on 1 variable
  • There are 2^(2^2) = 16 distinct formulas on 2 variables
  • There are 2^(2^3) = 256 distinct formulas on 3 variables
  • There are 2^(2^4) = 65,536 distinct formulas on 4 variables
  • There are 2^(2^5) = 4,294,967,296 distinct propositional logic formulas on 5 variables
| improve this answer | |
  • "If there are infinitely many non-equivalent formulas in propositional (zeroth order) logic, then there are also infinitely many non-equivalent formulas in predicate (first order) logic." That's misleading although ultimately true: propositional logic isn't a sublogic of predicate logic, since predicate logic does not have propositional variables (only object variables). That said, the same idea works: consider formulas of the form x=y for x,y object variables. But this doesn't help you whip up examples of independent sentences (sentences can't have free variables) - that takes work. – Noah Schweber Mar 1 at 5:54

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.