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.

I need some help with the follwing: Lets suppose that the sentence $\forall x: x\in I \rightarrow P(x)$ is false. Now consider the sentence $$\forall x: x\in I \rightarrow (P(x) \ \& \ Q(x) ) \ \ \quad (1)$$ for any property $Q(x)$, which is also obviously false. But now I can define a set $I'=\left\{ x \in I| P(x) \right\}$. So the sentence (1) should be equivalent to the sentence $$\forall x: x\in I' \rightarrow Q(x) $$ But since sentence is now true, since there aren't any $x$ such that $x \in I'$, because the first sentence was supposed to be false.

I'm sure the error is, that the two sentences are equivalent. But I can't pinpoint my error. Could someone tell me crystal-clear what I am doing wrong ?

share|improve this question
2  
You're right that the sentences aren't equivalent. But since you've provided no justification for your assumption that they are, it's hard to pinpoint your error. –  user92843 Jul 10 '11 at 19:07
1  
Do you mean $\forall x: \lnot(x\in I \rightarrow P(x))$ or $\lnot (\forall x: x\in I \rightarrow P(x))$? They are not equivalent. The second needs a single $x \in I$ not to satisfy $P(x)$, while the first needs every $x \in I$ not to satisfy $P(x)$ –  Ross Millikan Jul 10 '11 at 21:18

2 Answers 2

up vote 3 down vote accepted

The sentence with the colon (first line) is not a sentence in any formal language that I am acquainted with. Presumably it is meant to assert what would be ordinarily written as $$\left(\forall x\right)\left(x\in I \implies P(x)\right).$$ We are told that this sentence is false.

So there is an element $a$ of $I$ such that $P(a)$ is false. There may also be many elements $b$ of $I$ such that $P(b)$ is true.

Later, $I'$ is defined as the subset of $I$ consisting of the $x$ in $I$ such that $P(x)$ is true. It is then asserted that $I'$ is empty. But there is no reason to conclude that $I'$ is empty.

Example: For example, let $I$ be the set of positive integers. Let $P(x)$ be the assertion that $x$ is prime. Then the assertion $$\left(\forall x\right)\left(x\in I \implies P(x)\right)$$ is false, since there are non-primes. But then $I'$ is the set of primes, which is demonstrably non-empty.

Analysis: Why the mistake? The OP is experienced enough not to make an elementary error. The problem is with the bad notation, which is a hybrid between two not unreasonable standard notations. The first has already been used. The second standard notation, in a corrected version, would read: $$\left(\forall x: x\in I\right) (P(x)).$$ Note the absence of the implication symbol.

share|improve this answer

It's a little neater to avoid $I'$ altogether and write your second displayed expression as $(\forall x \in I)[\lnot P(x) \to Q(x)]$; this captures the same idea.

I think that you've confused conjunction ('and') and disjunction ('or'). If your $(1)$ had been $(\forall x \in I)[P(x) \lor Q(x)]$ instead of $(\forall x \in I)[P(x) \land Q(x)]$, it would have been logically equivalent to $(\forall x \in I)[\lnot P(x) \to Q(x)]$, simply because $P(x) \lor Q(x)$ is logically equivalent to $\lnot P(x) \to Q(x)$. If at least one of $P(x)$ and $Q(x)$ has to be true for each $x \in I$, then it is indeed true that whenever $P(x)$ fails, $Q(x)$ must hold, and conversely. But your $(1)$ says that both $P(x)$ and $Q(x)$ have to be true for each $x \in I$, which is another matter altogether.

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.