0
$\begingroup$

Given the following logical equivalence, $$\forall x \in D, P(x) \equiv \forall x, x \in D \rightarrow P(x)$$

The LHS of the equivalence states that "for all $x$ in the domain $D$, $P(x)$". The RHS in the other hand states that "for all $x$, if $x$ is an element of $D$, then $P(x)$". From the book Discrete Mathematics and Its Applications by Kenneth H. Rosen, he says that

The domain must always be specified when a universal quantifier is used; without it, the universal quantification of a statement is not defined.

The RHS of the logical equivalence doesn't seem have a domain. I've also seen in a few places where people only write "$\forall x$" without specifying the domain, which would be understood as "$\forall x \in \mathbb{U}$", where $\mathbb{U}$ is the universe of discourse. Should it assumed that the domain of the RHS of the logical equivalence is the set $\mathbb{U}$ such that $D \subseteq \mathbb{U}$? Also, I know that the "ultimate" universal set doesn't exists which means that the domain of $x$ can't just be the set of everything (I used to think that the domain of $x$ in this case would be the "ultimate" universal set).

If there's no universe of discourse, then wouldn't $\forall x, x \in D \rightarrow P(x)$ be not defined? What's the domain for $x$ in the RHS then?

$\endgroup$
3
  • 2
    $\begingroup$ The "universe of discourse" is specified by the interpretation. $\endgroup$ Commented May 6, 2023 at 9:26
  • 1
    $\begingroup$ The equiv above holds because the two formulas have the same truth value, whatever the interpretation is. $\endgroup$ Commented May 6, 2023 at 9:27
  • 3
    $\begingroup$ Yes in $\forall x$ the domain is the universe of discourse. Note also that in most cases (known to me) the equivalence you wrote above is a definition, not a result. You define $\forall_{x\in D} ~P(x)$ to mean $\forall_x( x\in D\rightarrow P(x))$ $\endgroup$ Commented May 6, 2023 at 9:28

1 Answer 1

2
$\begingroup$

As Mauro states in the Comments, it's all about interpretations.

Take a logic statement like $\forall x \ P(x)$

What does this say? We read this as 'All objects have property $P$". OK, but what exactly is this property $P$? And what do you mean by 'all'? Indeed, what are we really talking about?

This is where interpretations come in. An interpretation might say: This sentence is about natural numbers, and $P(x)$ means that "$x$ is even". So under that interpretation, the above statement would mean that "all natural numbers are even".

OK, but there are many other interpretations possible. I could say that the domain is my clothes, and that $P(x)$ means "$x$ is red". So now the statement means "All my clothes are red". A totally different statement

Part of the power of logic is that the statement itself doesn't fix any interpretation... and therefore point out interesting relationships about any domain. For example, you can show that $\neg \forall x \ P(x)$ is logically equivalent to $\exists x \ \neg P(x)$, no matter what the domain is or what $P(x)$ means.

Now, in your case we use a restricted quantifier of the form $\forall x \in D ...$. Again, when we use such a quantifier, we do often have some specific domain in mind ... but logic itself does not. So, you'll have to say what this $D$ is in the interpretation. And, here we do make the stipulation that whatever $D$ is, it is part of a larger domain. That is, the very idea of the restricted quantifier is of course that out of some larger domain, there exists a subset $D$ to which we want to restrict our claim.

So, the interpretation will have to define two groups of objects: the group of objects represented by $D$, and the group of objects that the unrestricted quantifier $\forall x$ would range over, where we specify that the first group of objects is a subset of the latter group. But no, neither $D$ nor the larger domain is specified by the statement itself.

However, showing the power of logic once again, no matter what we pick for $D$, the larger domain that $D$ is a subset of, and $P$, it will always have to be the case that $\forall x \in D, P(x)$ is true if and only if $\forall x, x \in D \to P(x)$ is true. And that makes them logically equivalent statements.

$\endgroup$
2
  • $\begingroup$ I believe this means that $\forall x$ is an unrestricted quantifier which ranges over the universe of discourse (the set of everything we're talking about)? $\endgroup$ Commented May 7, 2023 at 2:47
  • 1
    $\begingroup$ @Mohammadmuazzamali Correct $\endgroup$
    – Bram28
    Commented May 7, 2023 at 4:48

You must log in to answer this question.

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