Finding the relationship (equivalence or implication) between two expressions

Question

I am trying to find the relationship between $$\exists X \; (p(X) ∧ q(X))$$ and $$\exists X \; p(X) ∧ \forall X \; q(X).$$

I believe that quantifiers cannot be used in forming truth tables, after all both expressions become equal if we take out the quantifiers.

Without a truth table I do not know how to find the relationship between these two expression.

Answer 1

The formula $\exists x Px \wedge \forall x Qx$ states "There exists at least one $x$ such that $x$ is $P$, and for every $x$, $x$ is $Q$."

The formula $\exists x [Px \wedge Qx]$ states "There exists at least one $x$ such that $x$ is $P$ and $x$ is $Q$."

If the former is true, then so is the latter. However, if the the latter is true, then the former is not necessarily true. In other words, it may be the case there is exactly one element of the given domain that is both $P$ and $Q$, and that element may be the only element that is $P$ or $Q$. If that is in fact true, then the latter statement is satisfied, but the former statement is not satisfied because it asserts every element in the domain is $Q$.

Answer 2

To check the conditional relationship between two sentences, making sense of them is usually faster than formal proof methods:

$$\exists X \; (p(X) ∧ q(X))$$

Some object is both pink and quirky.

$$\exists X \; p(X) ∧ \forall X \; q(X)$$

Some object is pink and every object is quirky.

P.S. It is better to call them sentences rather than expressions (what’s the diference?).

Answer 3

The second implies the first. Suppose we have the second already. Then we can get in our context the following $x_0 \in X$ and $p(x_0)$ as well as $\forall x \; q(x)$. Combining the first and third gives $q(x_0)$. Then $p(x_0) \wedge q(x_0)$ so with that and $x_0 \in X$, we have the goal of the first statement. Note we don't have to worry about the empty set here because the left hand side of the implication was an existential so we can start off with $x_0 \in X$ as at least one element of the set $X$.

To give a counterexample to first implies second use $X$ is the two element set of A and B. Let $q(x)$ be the proposition that x is the A element. Let $p$ be the vacuous true. The first is true because we can take $x$ to be A which exists and $p(A) \wedge q(A)$. The second is false because it is not the case that $\forall x \; q(x)$. That makes the entire second proposition false. So even though the first was true, the second was not in this case. The first does not imply the second.

We can even formalize these exact arguments for the computer.

Definition r (A : Type) (P Q : A -> Prop) := (exists (x:A), P(x)) /\ (exists (x:A), Q(x)).

Definition s (A : Type) (P Q : A -> Prop) := exists (x:A), P(x) /\ Q(x).

Definition t (A : Type) (P Q : A -> Prop) := (exists (x:A), P(x)) /\ (forall (x:A), Q(x)).

Lemma s_to_r : (forall A : Type, forall P Q : A -> Prop, s(A)(P)(Q) -> r(A)(P)(Q)).
Proof.
intros. destruct H as [x H1]. destruct H1 as [H1 H2].
assert (exists x, P x) as H3. exists x. assumption.
assert (exists x, Q x) as H4. exists x. assumption.
assert ((exists x, P x) /\ (exists x, Q x)). split. assumption. assumption.
assumption.
Qed.

Lemma t_to_s : (forall A : Type, forall P Q : A -> Prop, t(A)(P)(Q) -> s(A)(P)(Q)).
Proof.
intros. destruct H as [H0 H1]. destruct H0 as [x H0]. assert (Q x). apply H1.
assert (P x /\ Q x) as H2. split. assumption. assumption.
assert (exists x, P x /\ Q x) as H3. exists x. assumption.
assumption.
Qed.

Lemma not_s_to_t : ~ (forall A : Type, forall P Q : A -> Prop, s(A)(P)(Q) -> t(A)(P)(Q)).
Proof.
intros H.
specialize H with bool (fun x => True) (fun x => x=true).
assert ( s bool (fun x => True) (fun x => x=true)) as Hs. exists true.   split. reflexivity. reflexivity.
assert ( t bool (fun x => True) (fun x => x=true)) as Ht. specialize (H Hs). assumption.
assert (not (forall x: bool, x=true)) as side_1. intuition.
specialize (H0 false) as H2_2.
inversion H2_2.
assert ((forall x: bool, x=true)) as side_2. destruct Ht. assumption.
contradiction.
Qed.

Answer 4

Take as the domain whole numbers, let $p(X)$ be '$X$ is odd', and $q(X)$ be 'X is prime'.

Then $\exists X (p(X) \land q(X))$ is true: "there is some odd prime number". Sure!

But $\exists X \ p(X) \land \forall X \ q(X)$ is false: "there is an odd number, and every number is prime". No!

And please note that if we say that $q(X)$ stands for 'X is even', we can see that $\exists X (p(X) \land q(X))$ is also not equivalent to $\exists X \ p(X) \land \exists X \ q(X)$:

$\exists X (p(X) \land q(X))$ : "There is a number that is odd and even". No!

$\exists X (p(X) \land \exists \ q(X)$ : "There is at least one odd number and there at least one even number". Sure!