1

I have a problem:

Let P be the statement " x $\in$ A and x $\in$ $\mathbb{Z}$ "

statement: ($\forall$x)P $\Longrightarrow$ ($\exists$x)P

Is there a set A for which the truth value of the above statement is false? Explain.

My approach is:

The statement is only false when the antecedent is true and the consequent is false.

This is not possible because ...

Can someone help, please?

NOTE: Please forgive me : our assumption is that x is in the universal set R

hanamontana
  • 333

2 Answers2

0

Yes, when $A \cap \mathbb Z$ is the empty set.

Then there are no such $x$ and so $(\forall x) P$ is true vacuously.

But as there exist no such $x$, there can exist no $x$ such that $P$ holds, so $(\exists x)P$ is false.

Prime Mover
  • 5,005
  • But $\forall x,P$ doesn't mean the same as $\forall x \in A,P$ for the given $P$. – Rob Arthan Mar 05 '21 at 16:29
  • @RobArthan Good call, I'm confused by the nature of the statement of the question. I'll rethink it. – Prime Mover Mar 05 '21 at 16:34
  • It is a contingent sentence, depending on A and Z, it can be true and it can be false. If A is a subset of Z, then the antecendent is true, and the conclusion is true. It is also true if when A and Z are both empty. – amWhy Mar 05 '21 at 16:56
  • But $\mathbb Z$ is not empty because $\mathbb Z$ is the set of integers. I presume. OP does not give any information about the range of $x$, we have been left to guess. But the point is that "forall $x$ implies exists $x$" is true iff there are any $x$ to begin with. And if $x$ are such that $x \in A$ and $x \in \mathbb Z$ that means there has to be at least one element in $A \cap \mathbb Z$ in the first place. If not, then $(\forall x) P \implies (\exists x) P$ is false. If not, then can someone rewrite the question to clarify exactly what is meant? Domain of $x$, what means $\mathbb Z$ etc.? – Prime Mover Mar 05 '21 at 17:24
0

In first-order logic as presented in standard textbooks and standard introductory courses, the universe of discourse (i.e., the set of things that we talk about in our logical language) is non-empty. $\forall x\,P(x)$ means that $P(x)$ holds for every element of the universe and, as that universe is non-empty, $\exists x\,P(x)$ must hold if $\forall x\,P(x)$ does. So $(\forall x\,P(x)) \Rightarrow (\exists x\,P(x))$ is valid, for any predicate $P(x)$. In particular, $(\forall x\,(x \in A \land x \in \Bbb{Z})) \Rightarrow (\exists x\,(x \in A \land x \in \Bbb{Z}))$ is valid for any set $A$. So you correct in concluding that there is no set $A$ that makes this proposition false.

To address Prime Mover's concerns: if we are working in a first-order language that can talk about sets and set membership, then it is convenient to use relative quantifiers: i.e., to write $\forall x \in A\,Q(x)$ as an abbreviation for $\forall x \, (x \in A \Rightarrow Q(x))$ and to write $\exists x \in A, Q(x)$ as an abbreviation for $\exists x(x \in A \land Q(x))$. Using this short-hand $\forall x \in \emptyset\,Q(x))$ is true and $\exists x \in \emptyset\,Q(x)$ is false, but this does not contradict the statement that $(\forall x\,P(x)) \Rightarrow (\exists x\, P(x))$, since when we expand the abbreviations, the matrix (body) of the two quantified subformulas are not the same.

Finally, I should say that there are logics that do not assume that quantification ranges over non-empty sets. Tennant's Natural Logic is one such system. Martin-Löf type theory is another. Such logics are, in some sense, more precise than traditional first-order logic, but the extra precision has to be paid for by more onerous proof obligations.

Rob Arthan
  • 48,577