Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$

share|improve this question
    
What does the bar indicates? –  Asaf Karagila May 20 '11 at 17:08
    
$\overline A = \lnot A$. It's just another syntax for negation. –  FUZxxl May 20 '11 at 17:51
    
Please try and be consistent with your own notation, you're switching from $\bar\cdot$ to $\lnot\cdot$ along your question. –  Asaf Karagila May 20 '11 at 17:53
    
@Asaf: Sorry. It's just that I am used to use both styles simutanously - Usually, it is more readable to use the bar notation for long expressions and the $\lnot$ notation for short expressions. –  FUZxxl May 20 '11 at 17:57
    
I usually just use parenthesis. The overline notation is way overused throughout mathematics. –  Asaf Karagila May 20 '11 at 18:07

3 Answers 3

up vote 3 down vote accepted

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)$.

share|improve this answer
    
Is $\bigwedge_{x\in\{\}}P(x)$ true? And what about $\bigvee_{x\in\{\}}P(x)$? It is supposed to be false, isn't it? But thank you for that answer. It helped me quite much. –  FUZxxl May 20 '11 at 16:14
    
Yes, $\bigwedge_{x\in\{\}}P(x)$ is true. And $\bigvee_{x\in\{\}}P(x)$ is false. To remember these peculiar facts, think about AND'ing things together one by one: Your answer is "true" until the first false thing arrives. Viewed this way, it is obvious that your answer must be "true" when nothing has arrived yet. Similarly for OR'ing things together, your answer is "false" until the first true thing arrives, so the OR of nothing must be false. –  Matt May 20 '11 at 16:22

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.

share|improve this answer

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)}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.