4
$\begingroup$

What is the symmetry between the definitions of the bounded universal/existential quantifiers?

$\forall x \in A, B(x)$ means $\forall x (x \in A \rightarrow B(x))$

$\exists x \in A, B(x)$ means $\exists x (x \in A \land B(x))$

These make intuitive sense, but I would expect there to be some kind of symmetry between how the definitions of the bounded quantifiers work, and I can't see one. $A \rightarrow B$ means $\lnot A \lor B$ which doesn't seem to have a direct relationship with $A \land B$. What am I missing?

  • 0
    I haven't been able to clarify this for myself. I will review the answers and see if I can understand what I still don't get tomorrow.2011-07-15

4 Answers 4

5

Consider $\forall x\in A, B(x)$. That is if $x$ is a member of $A$ then $B(x)$ is true.

This translates, as you well put to $\forall x(x\in A\rightarrow B(x))$, which again translates to $\forall x(x\notin A\lor B(x))$.

Denote $B=\{x\mid B(x)\}$, that is all the elements which satisfy $B(x)$. Now you have that $x\in B \iff B(x)$ is true.

We re-evaluate the previous sentence: $\forall x(x\in A\rightarrow x\in B)$, that is to say $A\subseteq B$, or to say $\forall x(x\notin A\lor x\in B)$.

Now consider the existential version: $\exists x(x\in A\land B(x))$ that is $\exists x(x\in A\land x\in B)$, or in simpler words $A\cap B\neq\emptyset$.

Lastly we recall that $\lnot\forall x\varphi(x) \iff \exists x\lnot\varphi(x)$. This translates well over bounded quantifiers:

$\begin{align} \lnot(\forall x\in A, B(x)) &\iff \lnot\forall x(x\in A\rightarrow x\in B)\\ &\iff \exists x\lnot(x\in A\rightarrow x\in B)\\ &\iff \exists x(x\in A\land x\notin B)\\ &\iff \exists x\in A,\lnot B(x) \end{align}$

  • 0
    @John: Could you elaborate?2011-07-17
2

You might think of universal as a mega-intersection, and existential as a mega-union. E.g., if $A=\lbrace x_1,x_2,\dots\rbrace$ then your first formula is $B(x_1)$ and $B(x_2)$ and ..., while the second is $B(x_1)$ or $B(x_2)$ or ....

There is also some sort of symmetry in noting that "not for all" is the same as "there exists ... not," and "not there exists" is the same as "for all ... not."

  • 1
    @John: It is a standard argument, in fact if you look closely you realize that it is actually the definition. In older papers $\forall$ was denoted by $\bigwedge$ and $\exists$ was denoted by $\bigvee$.2011-05-22
2

Is this more symmetrical?

$\forall x \in A, B(x)$ means $\forall x (x \notin A \lor B(x))$

$\exists x \in A, B(x)$ means $\exists x (x \in A \land B(x))$

  • 0
    You mention the above formula in only in passing.2011-05-22
0

As Asaf Karagila says, those two connectives, $\forall x \in A, \ldots$ and $\exists x \in A, \ldots$ are dual of each other.

Just like the conjunction / disjunction pair or the universal / existential pair, we have that $\lnot (\forall x \in A, \phi(x)) \Leftrightarrow \exists x \in A, \lnot \phi(x)$.

Also, if $A$ is a singleton $\{a\}$, those two connective are logically equivalent, and $\forall x \in A, \phi(x) \Leftrightarrow \exists x \in A, \phi(x) \Leftrightarrow \phi(a)$