How are bounded quantifiers defined?

Question

From wikipedia I take that:

Let $X$ be a set. Then

$$ \exists x \in X : P(x) \Leftrightarrow \exists x: x \in X \land P(x) $$

$$ \forall x \in X : P(x) \Leftrightarrow \forall x: x \in X \Rightarrow P(x) $$

Ok, so I don't have much experience with mathematical logic. But I have two problems.

1. Why does one quantifier use a $\land$ and the other one a $\Rightarrow$. Can they both be defined with a $\land$, or both be defined with a $\Rightarrow$ ? I don't see a problem with this, thought my intuition is weak. So a counterexample would be appreciated.
2. How do they justify using a variable without defining it beforehand, like $\forall x$. Can $x$ stand for any object a human can think of up to this point? I am asking because I think expressions like $\{x : P(x)\}$ are illegal in mathematical set theory. You have to specify where you are taking your $x$ from $\{x \in \mathbb{R} : P(x) \}$ . Though I could be wrong on that.

Answer 1

For part one, I think convincing yourself that the statements "mean what they're supposed to" by writing them down informally and thinking it through will improve your intuition. It has to do with the different meanings of 'for all' and 'there exists'. Edit: Actually, I'll give you a hint: $$\forall x (x\in X \land P(x))$$ would mean "for all $x,$ $x\in X$ and $P(x)$ holds." That implies in particular that "for all $x,$ $x\in X,$" i.e. that every $x$ in in the set $X.$ That is surely not implied by the statement "for all x that are in $X,$ $P(x)$ holds," which is what we want $(\forall x\in X)P(x)$ to mean. I'll leave it to you to confirm that $$\forall x(x\in X\implies P(x))$$ does mean this, and to handle the existential quantifier.

For part two, in an interpretation, quantifiers always range over some particular defined universe of objects. So it's not 'literally anything we can think of', merely anything in our universe.

Expressions like $\{x:P(x)\}$ have an interesting standing in set theory. They are called classes and may or may not be formal objects of the theory (i.e. objects of the aforementioned universe). In ZFC classes are not formal objects but it is still helpful to sometimes reason informally about 'the class of objects that satisfy the property.' Some classes, like $\{x:x=3\}$ do happen to correspond to bona fide sets, but others, like $\{x:x=x\}$ do not and are called proper classes. Restricted comprehension $\{x\in S:P(x)\}$ where $S$ is a set does always correspond to an actual set.

However, don't be misled: unrestricted quantification in logical statements (as opposed to in class comprehensions) are totally fine in set theory without any caveats. So that $P(x)$ formula inside the comprehension can have unbound quantifiers. In ZFC the quantifiers, if unbound, range over all sets.

And it's not the case that proper classes are 'illegal.' In fact there are set theories like NBG and Morse-Kelley where the universe consists of all classes, so they are actual formal objects. However, there is still a special distinction of being a set as opposed to a proper class (sets are classes that are elements of some other class).

Answer 2

You can think of it this way:

In both cases you have $\forall x.\varphi(x)$ or $\exists x.\varphi(x)$ with the additional condition that you have a formula $\beta(x)$ where you don't want the possible existence of $x$ that doesn't satisfy $\beta(x)$ to influence the truth value of the entire quantified formula.

You can view $\forall x$ as an "infinite conjunction". If we want some of the conjuncts to have no influence on the truth value of the conjuction, they need to he true, since "true" is the neutral element for $\land$.

Similarly, $\exists x$ is an "infinite disjunction", so in that case disjuncts that must have no influence on the truth value of the disjunctions must be false.

In other words we need $$ \forall x.\Bigl(\varphi(x)\text{ except always true whenever }\neg \beta(x)\Bigr) \\ \exists x.\Bigl(\varphi(x)\text{ except always false whenever }\neg \beta(x)\Bigr) $$

We can then write down the truth tables for "$A$, except true if $\neg B$" and "$A$, except false if $\neg B$" and find that they are the same as connectives for truth tables we already know, namely $B\to A$ and $B\land A$. And that is why the restricted quantifiers unfold to $$ \forall x.(\beta(x)\to \varphi(x)) \qquad\qquad \exists x.(\beta(x)\land \varphi(x)) $$ Written this way, $\to$ and $\land$ don't look very symmetric. But the underlying meaning-in-words above is nicely symmetric.

---

Note that we could also write the unfolding of the restricted $\forall$ as $$ \forall x(\neg\beta(x)\lor \varphi(x)) $$ in which case it is easier to see the duality: To change from $\exists$ to $\forall$ or vice versa we interchange $\land$ and $\lor$ and negate the bound.

And that's actually a pretty good motivation for the $\to$ connective: Since we often want to express bounded $\forall$s, we often need to write formulas of the form $\neg B\lor A$ under the quantifier -- so often that it is practical to have a shorthand for it, which is exactly $B\to A$.

Indeed, in ordinary mathematical reasoning you will hardly ever encounter a $\to$ that does not serve this role -- though the $\forall$ quantifier in front of it is othen left implicit in semi-informal writing.

We don't need a corresponding shorthand for the $\exists$ case because $\land$ is already as short as we could wish for.

Answer 3

The universal quantifier is conjunctive. All is all in $X$ and all elsewhere. $$\forall x~Q(x)\iff \big(\forall x\in X:Q(x)\big)\wedge \big(\forall x\notin X:Q(x)\big)$$

The existential quantifier is disjunctive. Some is some in $X$ or some elsewhere. $$\exists x~Q(x)\iff \big(\exists x\in X:Q(x)\big)\lor \big(\exists x\notin X:Q(x)\big)$$

In any universe where there is $y$ such that $y\notin X$, we have $y\in X\to P(y)$ is true and $y\in X\wedge P(y)$ is false, whatever $P(y)$ may be.

In any universe where there is $x$ such that $x\in X$, we have $x\in X\to P(x)$ is $P(x)$, and $x\in X\wedge P(x)$ is $P(x)$ too.

$$\begin{split}\forall x~\big(x\in X\to P(x)\big) ~&\iff~ \Big(\forall x\in X:\big(x\in X\to P(x)\big)\Big)~\wedge~\Big(\forall x\notin X:\big(x\in X\to P(x)\big)\Big) \\&\iff~ \big(\forall x\in X:P(x)\big)~\wedge~\top \\ &\iff~ \forall x\in X:P(x)\\[2ex]\exists x~\big(x\in X\land P(x)\big) ~&\iff~ \Big(\exists x\in X:\big(x\in X\land P(x)\big)\Big)~\vee ~\Big(\exists x\notin X:\big(x\in X\land P(x)\big)\Big) \\&\iff~ \big(\exists x\in X:P(x)\big)~\vee~\bot \\ & \iff \exists x\in X:P(x) \end{split}$$