LO11 is QBF

This next problem is related to QBF and is proved in a similar way.

**The problem: **First Order Theory of Equality. This is problem LO12 in the appendix.

**The description: **Given a set U of variables {u_{1}..u_{n}}, and a sentence S over U in the first order theory of equality. Is S true in all models of the theory?

The first order theory of equality defines logical operations for equality (on variables), and the standard ∧, ∨, ¬, → operations (on expressions). It also lets us define ∀ and ∃ quantifiers on variables outside of an expression.

**Example: **My lack of mathematical logic knowledge is again letting me down as I’m not entirely sure what the difference between “models of the theory” and “assignments of truth values” is. It seems to me that this is very similar to QBF, with the addition of equality. So I think we can ask whether an expression like:

∀x ∀y ∀z (x=y) → (x = z) is always true. (It is).

I think, at least, this is the meaning that the Stockmeyer and Meyer paper use.

**Reduction: **Stockmeyer and Meyer again do a “generic transformation” using Turing Machines. What they do is the generic transformation for QBF (it’s Theorem 4.3), and then show this problem is a corollary to it because it follows from the “well-known fact that a first-order formula with n quantifiers and no predicates other than equality is valid iff it is valid for domains of all cardinalities between 1 and n”.

It’s not a well-known fact to me, so I guess I’ll just trust them.

**Difficulty: **I guess it depends on just how “well-known” that fact is for your class. If I gave the QBF reduction a 3, maybe this is a 5? But if you have to tell them the fact, maybe it’s too obvious? I don’t know.