How to formally define a predicate?

$\begingroup$

Consider two different ways to formally define a predicate, say the predicate $E(x)$ which is to be interpreted as "$x$ is even."

CASE $~1$

$\forall a:[a \in N \implies [E(a) \iff \exists b:[b \in N \land a=2b]]]$

CASE $~2$

$\forall a:[E(a) \iff a\in N \land \exists b:[b \in N \land a=2b]]$

There is a subtle difference in outcomes. $E(1)$ will be FALSE in both cases. $E(-1)$, however, will be UNDEFINED in case 1, but FALSE in case 2.

Which method, if either, is to be recommended?

$\endgroup$ 8

2 Answers

$\begingroup$

It may be helpful to look into the statements in terms of restricted quantifiers. Restricted quantification is used when the range of a quantified variable is desired to be restricted to a part of the domain of discourse. Usual notations for the general case are (simpler notations are also used):

$(\forall x)_{R(x)}\phi(x)$, which abbreviates $\forall x(R(x)\rightarrow\phi(x))$

and

$(\exists x)_{R(x)}\phi(x)$, which abbreviates $\exists x(R(x)\wedge\phi(x))$,

where $R(x)$ is the restricting predicate and $\phi(x)$ is any formula in the language.

In the context of arithmetic and set theory, they are called bounded quantifiers. For example:

$(\exists n)_{n<t} \phi(n)$

$(\forall x)_{x\in S} \phi(x)$

By restricted quantifiers, we can rewrite the statements as:

1. $(\forall n)_{n\in\mathbb{N}}(E(n) \leftrightarrow (\exists k)_{k\in\mathbb{N}}(n = 2k))$
2. $\forall x(E(x)\leftrightarrow x\in\mathbb{N}\wedge(\exists k)_{k\in\mathbb{N}}(x = 2k))$

In the first case, the universal set for the interpretation of the variable is prespecified as natural numbers.

In the second case, the the universal set for the interpretation of the variable is unrestricted (possibly, real numbers). If the set is specified externally, then $x\in\mathbb{N}$ is rendered superfluous (as well as the restricted quantification of $k$). However, that does not mean that such a definition is inferior with respect to the other, it depends on the practical choice to be made according to the context.

$\endgroup$ 2 $\begingroup$

CASE $~1$

$\forall a:[a \in \mathbb N \implies [E(a) \iff \exists b:[b \in \mathbb N \land a=2b]]]$

Definition 1 accurately and legitimately defines the even natural numbers.

CASE $~2$

$\forall a:[E(a) \iff a\in \mathbb N \land \exists b:[b \in \mathbb N \land a=2b]]$

For Definition 2 on the other hand, it is unclear what the domain of discourse $U$ is. In any case, this definition says that the set of even objects is $$U\cap2\mathbb N.$$ This definition is accurate precisely when $$U\cap (2\mathbb Z{\setminus}2\mathbb N)=\emptyset,$$ that is, when the domain of discourse contains no non-natural even number.

---

ADDENDUM

Not sure about your use of $U$ for CASE 2.

The difference between your two definitions depends on what the universe of discourse $U$ is.

To wit: let $U$ be $\mathbb Z$ (i.e., all the integers) and notice that while Definition 1 leaves ‘$-6$’ undefined (which is fine), Definition 2 nonsensically claims that $\mathbf{-6}$ is non-even.

I was also more interested in the correct way to specify the unary $E$ predicate, rather than the subset of multiples of $2$ in $\mathbb N.$

The above example shows that Definition 2 is incorrect when we consider every possible multiple of $2;$ on the universe $\mathbb Z^+$ though, Definition 2 is legitimate.

Which method, if either, is to be recommended?

On the other hand, Definition 1 is always consistent with the standard interpretation, even as we modify its domain of discourse.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy