0

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?

3
  • I am guessing that all the predicates involved are monadic (one place), otherwise this is false, as arithmetic shows. If there are n monadic predicates and each can be assigned T/F there are 2^n possible assignments, and the truth value of the formula depends only on that. With 2^n individuals in the domain every possible assignment can be made to be satisfied by an individual.
    – Conifold
    Jan 7, 2022 at 3:44
  • @Conifold, what example from arithmetic would show that this is not case for anything other than monadic predicates?
    – Name
    Jan 10, 2022 at 0:20
  • "Every element has a successor" with a dyadic successor predicate from arithmetic is unsatisfiable on any finite domain.
    – Conifold
    Jan 10, 2022 at 1:12

1 Answer 1

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.

enter image description here

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .