Why Not Extend Predicate Logic?

Predicate logic

Probability theory extends propositional logic to allow reasoning about degrees of credibility. Predicate logic extends it in a different direction, replacing simple propositional symbols with a rich language of atomic formulas, adding variables, adding quantification (“for all 𝑣” and “there exists 𝑣”), and allowing reasoning about infinite domains. Predicate logic is, more or less, the language of mathematics.

If you've taken a calculus class, you may remember that

\(\lim_{n\to\infty}a_{n}=x\)

(“the limit of 𝑎ₙ as 𝑛 goes to infinity is 𝑥”) is defined to mean

\(\begin{align*} & \mbox{for all }\epsilon>0\\ & \quad\mbox{there exists }N>0\\ & \quad\quad\mbox{such that for all }n\geq N\\ & \quad\quad\quad\left|x-a_{n}\right|<\epsilon; \end{align*}\)

or, in more formal notation,

\(\begin{flalign*} & \forall\epsilon.\,\epsilon\in\mathbb{R}\wedge\epsilon>0\rightarrow\\ & \quad\exists N.\,N\in\mathbb{N}\wedge N>0\,\wedge\\ & \quad\quad\forall n.\,n\in\mathbb{N}\wedge n\geq N\rightarrow\\ & \quad\quad\quad\mathrm{abs}\left(x-\mathrm{elt}\left(a,n\right)\right)<\epsilon. \end{flalign*}\)

This is an example of a predicate logic formula.

First-order logic

More specifically, it is a first-order predicate logic (FOPL) formula. “First-order” just means that when we write “∀𝑣” or “∃𝑣” the variable 𝑣 is assumed to range over some fixed domain of discourse 𝐷. There is no quantification over functions or relations on 𝐷; that would be second-order predicate logic.

The restriction to first-order quantification is not as important of a limitation as you might think. As Zermelo-Fraenkel set theory demonstrates, your domain of discourse may include objects that behave like functions and relations. In ZF,

• the objects are sets;

• an ordered pair (𝑥,𝑦) is represented as the set {{ 𝑥 } , { 𝑥, 𝑦 }};

• a binary relation is represented as a set of ordered pairs; and

• a function is represented as a binary relation 𝑅 with the special property that if 𝑥 𝑅 𝑦 and 𝑥 𝑅 𝑧 then 𝑦 = 𝑧, guaranteeing that there is a unique 𝑦 associated with 𝑥.

So for most purposes that require predicate logic, FOPL is sufficient.

Propositional vs. predicate logic compared

OK, so FOPL is a powerful and expressive logic. Then why do we extend only the more limited propositional logic to deal with degrees of credibility? Why not do the same with FOPL? The short answer is that 1) it's not clear how to do so, and 2) we don't need to. Let me expand on the latter.

The important difference between propositional logic and FOPL is that FOPL fully supports reasoning about infinite domains. A propositional formula can refer to an infinite domain such as all integers ℤ or all real numbers ℝ, but any single formula can only reference a finite number of distinctions on that domain. For example, a propositional formula can contain a finite number of propositional symbols of the form 𝚡 = 𝑛 for various integers 𝑛, but it cannot express something like ∀𝑛.𝜑(𝑛), where 𝑛 ranges over all infinitely many integers.

As we'll see later, if the domain of discourse 𝐷 is finite and there are constant symbols for each member of 𝐷, then any FOPL formula can be reduced to a propositional formula via a process of propositionalization. This involves

• turning ∀𝑣.𝜑(𝑣) into a conjunction (AND) of formulas, one for each member of 𝐷, and

• likewise turning ∃𝑣.𝜑(𝑣) into a disjunction (OR) of formulas.

This is why the fundamental distinction between propositional logic and FOPL is the latter's support for reasoning about infinite domains. For finite domains FOPL offers notational convenience and improved computational efficiency of deduction, but does not extend what can be said nor what can be deduced.

Finite vs. infinite domains

When considering statements about specific things that may occur, or that we may experience, or data we may acquire, we are in a finitary realm where propositional logic (and its extension to probability theory) are adequate:

• We are talking about specific, concrete instances of possible phenomena.

• We have only a finite number of observations.

• There are finite limits to how fine-grained of distinctions we can observe.

• We can experience only a finite portion of the world.

• A universally quantified statement of the form “for all 𝑣, 𝜑(𝑣) is true'' is something that we can never observe nor experience.

This then is the argument for why it suffices to extend propositional logic. On the other hand, one can make the argument that although a finite set of propositions is adequate for the query 𝐴 in Pr(𝐴 | 𝑋), the premise 𝑋, one's state of information, may need to be an infinite collection of propositions in order to fully capture what is known. Furthermore, the infinite case can often be simpler and more convenient to work with than the (very large) finite case.

For example, suppose that 𝑦 is the sum of a large number of small, independent disturbances:

\(\begin{align*} y & =\sum_{i=1}^{n}\varepsilon_{i}\\ \varepsilon_{i} & =\begin{cases} +n^{-1/2} & \mbox{with probability }1/2\\ -n^{-1/2} & \mbox{with probability }1/2. \end{cases} \end{align*}\)

Then

\(\begin{gather} \Pr\left(a\leq y\leq b\right)=2^{-n}\sum_{i=\left\lceil \left(n^{1/2}a+n\right)/2\right\rceil }^{\left\lfloor \left(n^{1/2}b+n\right)/2\right\rfloor }{n \choose i} \\ \mbox{where }-n^{1/2}\leq a\leq b\leq n^{1/2} \end{gather}\)

and computing this exactly for large 𝑛 generally requires summing a large number of terms. But as 𝑛 goes to ∞, the distribution for 𝑦 converges to the standard (continuous) normal distribution. So for large 𝑛 it is much easier and faster to instead compute

\(\Pr\left(a\leq y\leq b\right)\approx\Phi\left(b\right)-\Phi\left(a\right)\)

where 𝛷 is the standard normal CDF.

The above example shows not only why you might want to work with infinite domains, but how to do it: by taking a large-𝑛 limit of a finite analysis parameterized by an integer 𝑛 that determines the size of the (finite) domain being considered. As I have previously written, we'll be following Jaynes' finite sets policy¹: start by modeling the problem of interest using finite sets of propositions, and observe what happens as the number of propositions increases indefinitely. In a series of future posts I will explore this process in more detail, and formalize both what it means for an infinite sequence of premises to be converging and what its limit is.

1. E. T. Jaynes, 2003, Probability Theory: The Logic of Science, Cambridge University Press, p. 663.