Proof of the Model Universe Theorem: Proving the invalidity arguments in quantifier logic

Question

I am studying how to prove an argument in quantifier logic is invalid. The textbook I am using by Virginia Klenk claims that you can use a Model Universe that contains a finite number of objects to substitute in to the propositional functions. The book claims: "Where n is the number of different predicate letters in an argument form, the largest domain you need to test is one with $2^n$ individuals." Can someone explain or refer me to a proof for why this is so?

Answer 1

Consider an open formula F(x). In case that the variable x is bound to an element of the domain of discourse, say z, it becomes a closed formula F(z). We may treat a closed formula as a proposition of propositional calculus. For the semantic values of propositions, we assign the logical predicates truth and falsity; in this case, the question is whether any element of the domain satisfies a predicate or not.

When we have more than one predicate, F, G, H, ..., we have to consider all their possibilities just as in a truth-table of propositional calculus; however, we add a column for the elements, for we indicate each possibility by an element (recall we talk about satisfaction state of each predicate in the context of others). The rightmost column is to indicate a compound of them. I give an example below. In order to emphasise that we talk about satisfaction of an open formula, instead of truth values directly, I've used tick and cross marks.

By the arithmetic of the table, we know that for n predicates, we need 2^n rows to exhaust all the possibilities. Hence, any additional row (indicated by an element other than listed) would repeat one of the rows.