# Are there paradoxes involved in allowing for an unrestricted domain in predicate logic?

I've put some thought into this, and just want to make sure I'm on track, or if I need to be corrected. Basically, my answer is this: Yes, you need to always specify a domain when formalizing into predicate logic, an unrestricted domain results in paradoxes. I guess in general I'm not exactly sure what the basis is for demanding that you specify a domain in predicate logic, other than that is a requirement of the completeness proofs or other kinds of proofs for it.

On the other hand, an unrestricted domain does seem harmless at first, for when you say "All men are mortal", the first predicate "man" does seem to restrict the domain for you. Even so, it might allow other "categories" of "man" that you didn't intend: fictional men, men in the future, toy soldier men, etc. So the option here seems to be that either you restrict the domain to an ontological/semantic category, or the category should be contained in the predicate. As an example of the latter, it could be implied in the predicate "man" above that the category is restricted to contemporary, flesh-and-blood, and real human beings. Is the choice on whether the category should be determined by the domain or contained in the predicate arbitrary or is there a good logical reason for preferring one over the other?

Since I was thinking about categories, and wondering about domains in the context of "category mistakes, I found the SEP article on "Categories" and there they (referencing someone named Thomasson) linked domains with the difficulty of Russell's Paradox. So, first, does an unrestricted domain cause Russell's paradox? Second, is there some sort of philosophical connection between Russell's paradox and what are known as ontological or semantic categories? By ontological categories, I mean the systems of Aristotle, Kant, et al. By semantic categories I mean the analysis of category mistakes by Ryle, Sommers, et al.

• What do you mean by "unrestricted domain"s? Models of predicate logic always contain a domain of individuals. I don't understand what the alternative is. To not have a domain? Without a domain, the notion of an assignment is meaningless and therefore the notion of truth for such languages cannot be given, at least in the usual way. I think the question contains lots of very interesting points and sub-questions (hence: +1), but I can't quite get passed the notion of unrestricted domains. Maybe you were actually thinking of unrestricted quantifiers? – Hunan Rostomyan Oct 10 '13 at 6:21
• I think that the OP by "unrestricted domain" actually means "under-restricted domain" where problems result from the domain not being sufficiently restricted. – Dan D. Oct 10 '13 at 6:51
• Right, that's what I mean. I mean the difference between a proposition like (Ax)(Men(x) --> Mortal(x)) where the domain is unrestricted, and the similar proposition (Ax)(Mortal(x)) where the domain is restricted to men. Seems to me that the first proposition is also implicitly restricted, but it is difficult to explicate how the domain is restricted other than resorting to some sort of category theory. – Kevin Holmes Oct 11 '13 at 4:21

In set theory, the distinction you are asking about translates to the question of whether the domain of a model must be a set, or whether it is allowed to be a proper class. This is an important distinction giving rise to many subtle issues. In many mathematical contexts, we are tempted to allow a structure whose domain is a proper class, and the question is whether this is a sensible thing to do.

The Gödel completeness theorem, for example, says that a first-order theory is consistent if and only if it has a model. In this theorem, one should take the meaning of "model" to be a model whose domain is a set.

In a first-order structure whose domain is a proper class, we are not able in general in the usual ZFC axiomatization of set theory to undertake Tarski's recursive definition of truth, and it is not the case that every proper class model has a satisfaction predicate.

For example, when Gödel proved the relative consistency of the axiom of choice over ZF, he built a proper class structure L called the constructible universe, and proved in ZF that every axiom of ZFC holds in L. But this is merely a theorem scheme, an assertion about each axiom of ZFC separately, and one cannot in general even formalize the assertion "L is a model of ZFC" as a single statement.

This is part of the reason why the theorem is only a relative consistency result. Although Gödel built a model of ZFC, it was a proper class model, and this is not sufficient to prove the consistency of the theory, since the completeness theorem requires a set model of the theory. But if we have a set model of ZF, then we may construct L relative to that model, and thereby get a set model of ZFC. So what he proved is that if ZF is consistent, then so is ZFC.

Meanwhile, many applications of category theory lead one to want to form proper class categories, such as the category of all groups or the category of all partial orders. Since one wants to undertake additional category-theoretic analysis on top of those categories, it leads to problematic issues similar to the Russell paradox. To prevent this issue, category theorists stratify the universe into levels, forming small categories and large ones in analogy with the set/class distinction in set theory. The axiom of universes is a convenient way to assert that there are sufficient levels for most of this kind of analysis. This axiom is equivalent to the existence of a proper class of inaccessible cardinals, and is therefore a mild large cardinal axiom, a strong axiom of infinity.

If you have a system of formal logic where your predicates can take other predicates as arguments, it quickly leads to paradoxes of the sort such as

There exists a man, such that he cuts the hair of all and only men who don't cut their own hair.

(Does he cut his own hair?)

This is closely related to Russell's paradox which is the same problem in set theory. It led to the development of first order logic, in which the domain of any predicate cannot include functions or predicates. The wikipedia article about the Barber paradox goes into more detail, and has a formal logical rendering of the paradox. http://en.wikipedia.org/wiki/Barber_paradox

• Note: Second-order logic is such "a system of formal logic where [second-level] predicates can take [first-level] predicates as arguments", but it can be developed in such a way that Russell's Paradox is avoided. The levels there contain a hint: make it so that a predicate of level k is applicable meaningfully only to predicates of level m < k. You will, of course, recognize this is as the second-order logical analogue of Russell's type-theoretic route out of the paradoxes of naive set theory. – Hunan Rostomyan Oct 10 '13 at 20:25
• I looked at the Wikipedia page about the Barber Paradox that you cite and they formalize the paradox as (Ex)(man(x) ^ (Ay)(man(y) --> (shaves(x, y) <--> -shaves(y, y)))). First I don't see any predicates taking other predicates as arguments. Second this paradox reduces to a contradiction when x and y share the same domain. I guess I don't see how this relates to Russell's Paradox. – Kevin Holmes Oct 11 '13 at 4:08