Question on existential quantifier.

456 Views Asked by At

Let us consider the following predicates.

$A(x)$: $x$ is $A$ type.

$B(x)$: $x$ is $B$ type.

Then convert the following statement in terms of predicate expression.

Some $A$'s are $B$.

Then which of the following is correct and why?

1) $\exists_x (A(x) \land B(x))$

which means there exists $x$, which is both $A$ and $B$.

2) $\exists_x (A(x) \implies B(x)) $

which means there exists $x$ such that if $x$ is A type then it is $B$ type.

Both has same meaning that, there exists $x$ which is both $A$ and $B$.

Then why (1) is mostly used, whats wrong with (2)?

Mostly I follow prejudice that if $\exists$ is encountered, use $\implies$ else if $\forall$ is encountered use $\land$.

Is there any reason behind it? In which statements I can use $\implies$ with $\exists$?

1

There are 1 best solutions below

0
On BEST ANSWER

Things are maybe less confusing if we use restricted quantifiers:

  • All $A$ are $B$ - $\forall x\in A\colon x\in B$
  • Some $A$ are $B$ (there exists an $A$ thatis $B$) - $\exists x\in A\colon x\in B$

However, the correct translations to unrestricted quantifiers are $\forall x(x\in A\to x\in B)$ and $\exists x(x\in A\land x\in B)$. Note that the statement $\exists x(x\in A\to x\in B)$ would (unexpectedly) also be true if $A$ is empty. Consequently, we'd have to accept "Some unicorns are tomatoes". It would eeven be true if there exists anything that is not $A$ because for such an object $x\in A\to x\in B$ would be true (ex falso quodlibet). Consequently we'd have to accept "Some tomatoes are unicorns". Thus the intended natural language interpretation really only matches $\exists x(x\in A\land x\in B)$.

One way to approach this is to note that "Some $A$ are $B$" is the negation of "No $A$ are $B$" or equivalently the negation of "all $A$ are not-$B$": $$ \neg \forall x(x\in A\to x\notin B)\iff \exists x\,\neg(x\in A\to x\notin B)\iff \exists x(x\in A\land x\in B)$$