A question on logic - where intuition can fail

Question

Suppose I have two predicates $P(x)$ and $Q(x)$, such that $\overline{P(x)\wedge Q(x)}$ holds for all $x$.

Now, if $\displaystyle \bigwedge_{x\in A}P(x)$ for a set $A$, it must be certainly true, that $\displaystyle \overline{\bigwedge_{x\in A}Q(x)}$ by intuition. But suppose, that $A = \{\;\;\}$, then obviously both $\displaystyle \bigwedge_{x\in A}P(x)$ and $\displaystyle\bigwedge_{x\in A}Q(x)$.

Where is my mistake? I guess it is in the assumption that $$\bigwedge_x\overline{P(x)\wedge Q(x)} \rightarrow \left(\bigwedge_{x\in A}P(x) \rightarrow \overline{\bigwedge_{x\in A}Q(x)}\right)?$$

*Note: $\displaystyle \overline{P(x)\wedge Q(x)} \equiv \lnot(P(x)\land Q(x))$
$\displaystyle \quad\quad\quad\quad \overline{\bigwedge_{x\in A}Q(x)} \equiv \lnot \left(\bigwedge_{x\in A}Q(x)\right)$

Answer 1

Your intuition is based on the set $A$ having some nontrivial size. But as you note, the intuition is wrong if $A$ is empty.

You only need to change your intuition slightly. If $P$ holds for all $x \in A$, then we know that $Q$ cannot hold for any $x \in A$. That is, $\bigwedge_{x\in A} \lnot Q(x)$.

The mistaken intuition is in transforming $\bigwedge_{x\in A} \lnot Q(x) \ \ \ \rightarrow \ \ \ \lnot \bigwedge_{x\in A} Q(x)$. This step is only correct if $A$ is nonempty, but even then it is a weak step (for large $A$ the left hand side is a strong statement while the right hand side is relatively weak), so you would do best to forget about this sort of transformation — try to erase it from your intuitive repertoire!

The correct transformation would be that of De Morgan: $\bigwedge_{x\in A} \lnot Q(x) \ \ \ \rightarrow \ \ \ \lnot \bigvee_{x\in A} Q(x)$.

Answer 2

You are given $\forall x \lnot(P(x)\land Q(x))$, which is the same as $\forall x \ \lnot P(x) \lor \lnot Q(x)$. Then you are given $\forall x \in A\ P(x)$. You are right that you can then derive $\forall x \in A \lnot Q(x)$. If $A$ is empty, it is also true (without any of the preceding) that $\forall x \in A \ Q(x)$. But for empty $A$, this is not a contradiction, as it expands to $\forall x (x \in A) \implies Q(x)$ As the antecedent is always false, the implication is always true.

Answer 3

When I TA'd a course which covered similar topics we specifically required for the structure to be nonempty.

This is in order to avoid the very problem that you refer to in your question.

In fact, the assumption that you made is very true if you require the structure to have a nonempty universe. Let us prove it quickly:

Suppose that for all $x\in A$ we have $\overline{P(x)\land Q(x)}$, and that for all $x\in A,\ P(x)$ holds.

Let $x$ be an arbitrary element of $A$, then $\overline{P(x)\land Q(x)}$ which by DeMorgan is equivalent to $\overline{P(x)}\lor\overline{Q(x)}$. We assume that $P(x)$ is also true, therefore it must be that $\overline{Q(x)}$.

Since this $x$ was arbitrary it holds for all $x\in A$, i.e. $\bigwedge_{x\in A}\overline{Q(x)}$.