Total predicates

A total predicate is a total function whose image is \(\{\text{true}, \text{false}\}.\) This subset of total functions is very important, because often in mathematics, we want to ask whether some proposition is true or false. If we had a mapping of some language into the natural numbers, we could imagine putting each of these numbers into a total predicate to determine whether number encodes a true statement.

Here are a couple properties of total predicates. They're not terribly interesting, but they're worth noting:

If \(P\) is the indicator function of a recursive set, then there is no greatest \(x\) such that \(P(x).\) We can state this mathematically:

$$\forall x : \left(P(x) \longrightarrow \left[\exists y: x \lt y \wedge P(y)\right]\right)$$

If \(P\) is the indicator function of a finite set, then there is a greatest \(x\) such that \(P(x).\) This can also be stated mathematically:

$$\exists x : \left(P(x) \longrightarrow \left[\forall y: y \gt x \longrightarrow \neg P(y)\right]\right)$$