0
$\begingroup$

I know this statement is not always true, but I'm having a hard time proving it.

I'm also wondering what the difference between:

$[\exists x \in U, P(x)] \implies [\forall x \in U, P(x)]$

and

$[\exists x \in U, P(x)] \implies [\forall y \in U, P(y)]$

would be?

For the first one, when I try to negate it and show that the negation is true, I end up with something like:

$[\exists x \in U, P(x)] \land [\exists x \in U, \lnot P(x)]$,

but if it was written as the second one I could just provide some counterexample y...?

Or am I just not parsing the statement correctly?

Thanks in advance!

$\endgroup$
  • $\begingroup$ It is only true if $U$ is non-empty. $\endgroup$ – user99680 Jun 18 '14 at 6:47
  • $\begingroup$ There is no difference between the two statements - the choice of letter is not significant. To disprove it, you need to show a single counterexample to the statement. (Actually, the negation isn't always false, just like the original isn't always true). $\endgroup$ – user61527 Jun 18 '14 at 6:48
  • $\begingroup$ To prove that your statement is not a logical truth, demonstrate a domain with two elements such that $P$ holds for one and not the other. $\endgroup$ – Robert Wolfe Jun 18 '14 at 6:48
  • $\begingroup$ My bad, I flipped the two premises. $\endgroup$ – user99680 Jun 18 '14 at 6:51
  • $\begingroup$ @Bryan: I was about to do just that to review my logic: are you going to do it yourself? $\endgroup$ – user99680 Jun 18 '14 at 6:53
1
$\begingroup$

Unless you restrict the set $U$ to having one element, then your statement is not a theorem: you basically state: if there is one element that satisfies property $P$, then all elements satisfy property $P$. Like Bryan said, a counterexample, i.e., a world/interpretation in which your premises are not mapped to truths. Consider a world with two elements {$a,b$}, and just declare $P(a) $ $\land \neg P(B) $ . For a more substantial example, let $P(x):=$ x is even, be a property defined on the universe of all numbers, then your statement would be interpreted as: "if there is an even number, then all numbers are even." Or consider the example with $P(x)$:= "x is male" , defined in the world of all people. Then, you interpret this as: If there is a male, all people are males.

And, actually $ A \implies B $ is equivalent to $\neg A \lor B$, so that its negation is $A \land \neg B $, i.e., your statement $$[\exists x \in U, P(x)] \implies [\forall x \in U, P(x)]$$ negates to:

$$ [\exists x \in U, P(x)] \land \neg [\forall x \in U, P(x)]$$ negates to:

$\endgroup$
  • $\begingroup$ Thank you for your answer! but doesnt $\lnot [\forall x \in U, P(x)]$ negate to what I had in the second part before? thanks again $\endgroup$ – user157742 Jun 18 '14 at 7:30
  • $\begingroup$ @user157742: It negates to " There is x in U with $\neg P(x) $, which is indeed the same as what you wrote; sorry if I misread before, you were correct. $\endgroup$ – user99680 Jun 18 '14 at 7:33
  • $\begingroup$ ahh. Thanks! I've got it now! $\endgroup$ – user157742 Jun 18 '14 at 7:36
  • $\begingroup$ Good going, user 157742. $\endgroup$ – user99680 Jun 18 '14 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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