6
$\begingroup$

And the same goes for the existential quantifier: $\exists x \in A : P(x) \; \Leftrightarrow \; \exists x (x \in A \wedge P(x))$. Why couldn’t it be: $\exists x \in A : P(x) \; \Leftrightarrow \; \exists x (x \in A \implies P(x))$ and $\forall x \in A : P(x) \; \Leftrightarrow \; \forall x (x \in A \wedge P(x))$?

$\endgroup$
1
  • 6
    $\begingroup$ Because we would prefer the statement $\exists x\in A: P(x)$ to actually mean that there is some element $x$ in $A$ that satisfies $P$. If $A$ is empty then your alternative version of it would always be true regardless of $P$. $\endgroup$ Commented May 21, 2013 at 18:58

3 Answers 3

7
$\begingroup$

Consider the expression $\forall x \in A : P(x) \; \Leftrightarrow \; \forall x (x \in A \wedge P(x))$. Assuming $A$ to be a proper subset of the domain of discourse, the expression will always be false, because by definition there are $x$ values in the domain of discourse which are not in $A$.

$\endgroup$
2
  • $\begingroup$ What if A equals the domain? $\endgroup$
    – Lenar Hoyt
    Commented May 21, 2013 at 19:17
  • 4
    $\begingroup$ @mcb If A equals the domain, then none of this applies. That's why I said a proper subset. If A equals the domain then the expressions will simply be $(\forall x)P(x)$ and $(\exists x)P(x)$. $\endgroup$ Commented May 21, 2013 at 19:22
5
$\begingroup$

I thought to combine into one post all the answers and comments. One helpful source is pp 68-69 of How to Prove It by Daniel Velleman; see its chapter "Equivalences involving Quantifiers."

For the domain of discourse $D$, the formal definitions (in green) and the inoperational alternatives (in Fire Brick Red) are:

$\color{green}{\exists \;x \in D \; : P(x) = \exists \;x \in D \; \; ( \;x \in A \wedge P(x) \;) \tag{E = Existential}} $

$ \color{green}{\forall \;x \in D \; : P(x) = \forall \;x \in D \; \; ( \;x \in A \Longrightarrow P(x) \;) \tag{U = Universal}} $

$\color{#B22222}{\exists \; x \in D : P(x) \; = \; \exists \; x \in D \; \; ( \;x \in A \Longrightarrow P(x) \;) \tag{E*}}$

$\color{#B22222}{\forall x \in D : P(x) \; = \; \forall \;x \in D \;\; ( \;x \in A \wedge P(x) \;) \tag{U*}}$

As per Tobias Kildetoft's commentary, (E*) is nonoperational, because (E) says:
there is an actual element in $x$ which, due to the $\wedge$, must satisfy $P(x)$.
In the extreme case that $A = \emptyset$, $\color{#B22222}{\;x \in A}$ is false; so the antecedent of (E*) is a false statement. False statements imply anything, so (E*) doesn't help.

Now, we analyse (U*). $\boxed{\text{Case 1 of 2 : } A \subsetneq D}$
Then there exists at least one point $\in D$ but $\notin A$. Thus $\color{#B22222}{... = \; \forall \;x \in D \;\; ( \;x \in A ... \;)}$ fails.

$\boxed{\text{Case 2 of 2 : } A = D}$
Then the RHS of (U*) becomes: $\; \forall \;x \in D \;\; ( \;x \in \color{#318CE7}{D} \wedge P(x) \;)$,
but this just reduces to $\forall \;x \in D \ P(x)$.

So Case 2 is not a problem, but Case 1 is. So we circumvent Case 1 with (U).

$\endgroup$
1
  • 6
    $\begingroup$ Beautiful use of text color! $\endgroup$
    – Lenar Hoyt
    Commented Dec 17, 2013 at 2:35
2
$\begingroup$

I can't answer your first question. It's just the definition of the notation.

For your second question, by definition of '$\rightarrow$', we have

$\exists x (x\in A \rightarrow P(x)) \leftrightarrow \exists x\neg(x\in A \wedge \neg P(x))$

I think you will agree that this is quite different from

$\exists x (x\in A \wedge P(x))$

$\endgroup$

You must log in to answer this question.

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