8
$\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$
    – Tobias Kildetoft
    May 21, 2013 at 18:58

3 Answers 3

Reset to default
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
    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$
    – rurouniwallace
    May 21, 2013 at 19:22
4
$\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
    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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.