0
$\begingroup$

I have a pretty simple question on mathematical logic.

Consider two logical statements $\exists x\in A \ (P(x))$ and $\exists x \ (x\in A \land P(x))$. How are they logically different from each other?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

These two logical statements are the same, by definition of $\exists x \in A ...$

When working with quantifiers and sets, it's important to remember these two definitions: $$ \exists x \in A (P(x)) \iff \exists x (x\in A \land P(x)) $$ $$ \forall x \in A (P(x)) \iff \forall x (x\in A \implies P(x)) $$

Notice how it's a $\land$ when $\exists$ is used but $\implies$ when $\forall$ is used.

$\endgroup$
5
  • $\begingroup$ +1 Fun fact: $~\exists x (x \in A \implies P(x))$ is always true. Not a very useful construct, but fun. See "Drinkers Paradox." $\endgroup$ Apr 17 at 15:10
  • $\begingroup$ Thank you for your reply! I have a question: So, we know what $\exists x (Q(x))$ means. Are you saying that the definition of $\exists x\in A (P(x))$ is $\exists x (A \land P(x))$? $\endgroup$
    – RFZ
    Apr 19 at 3:06
  • $\begingroup$ So if $\exists x \in A (P(x)) \equiv \exists x(x \in A \land P(x))$ as you said. Then the negation of $\exists x \in A (P(x))$ would be $\forall x (x \notin A \lor \neg P(x))$. But I thought that the negation of $\exists x \in A (P(x))$ is $\forall x \in A (\neg P(x))$. But you see that they are not identical. What am I missing? $\endgroup$
    – RFZ
    Apr 19 at 3:22
  • $\begingroup$ They are identical, because of the rule of material implication, which says $\neg X \vee Y$ is logically equivalent to $X\implies Y$: $$\begin{align*} & \forall x (x\notin A \vee \neg P(x)) \\ \iff & \forall x (x\in A\implies \neg P(x)) \\ \iff & \forall x\in A (\neg P(x))\end{align*}$$ $\endgroup$ Apr 20 at 2:04
  • $\begingroup$ Also, yes I am saying the definition of $\exists x\in A (P(x))$ is $\exists x (x\in A \land P(x))$ $\endgroup$ Apr 20 at 2:05

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