# Find a counter example/predicate logic

1. Aug 13, 2012

### Mixer

1. The problem statement, all variables and given/known data
Find a counter example to show that the following is invalid:

∃xP(x) ∧ ∃x(P(x) → Q(x)) → ∃xQ(x)

2. Relevant equations

-

3. The attempt at a solution

Well, I have tried to find something related to properties of numbers but found nothing... Then I tried to mess around with some nonsense sentences like:

Let x be a creature, P(x) = "x is human being", Q(x) = "x is male".

So:

Some creature is human being - true
For some creature if it is human being then it is male. - true
Some creature it is a male - true

(true and true) = true

(true → true) = true

So no counter example here. Any hint for me? I'm pretty much stuck..

2. Aug 13, 2012

### bonfire09

a counter example is where the premises are true and conclusion is false leading to a invalid argument form.

Take this example

For some person x1 and if some person x2 hits person x1 then x2 will hurt x1 only if x2 was sleeping.

so your counterexample to this would be
x2 hits person x1
x2 does not hurt person x1
but
x2 was sleeping

statement is also invalid since you have an existential quantifier being used which is usually coupled with an and operator and not with a conditional operator since the premises can all be false yet yield a true conclusion.

3. Aug 13, 2012

### Mixer

Hi!

Thanks for reply. I do know what I'm supposed to do i.e found something that ∃xP(x) and ∃x(P(x) → Q(x)) are true but ∃xQ(x) is false. I think that I'm confuced about two points:

1) Is x same in every premise and in conclusion?
2) I think I interpret the premises incorrectly. So if there is x that has property P and the same x has the property that if it has property P then it has property Q. It seems so obvious that there then must be x that has property Q. But I know this kind of reasoning is wrong..

Any more help for me?

4. Aug 13, 2012

### Mixer

Hmm.. I came up with this:

Let x be human being.
P(x) = "x curses"
Q(x) = "x insults"

So I thought this as follows:
There is a person who curses and the same person by cursing does insult someone. (These are the premises) i.e ∃xP(x) ∧ ∃x(P(x) → Q(x))

So it doesn't follow that x insults because he/she hasn't intention to do so. He/She is just cursing.

Does this disprove this:

∃xP(x) ∧ ∃x(P(x) → Q(x)) → ∃xQ(x) ?

5. Aug 13, 2012

### bonfire09

hmm I believe I was mistaken with my example. What is going on here is that there are three quantifiers with the same predicate variable x. But they are three separate predicate variables. Are you sure they use x throughout the formula? I think what your statement says is this "For some x1 and for some other x2, If x2... then x2... is sufficient for some other x3."

6. Aug 13, 2012

### Bacle2

Why not do piece-by-piece:

You need the antecedent to be true and the consequent must be false:

so (sorry, I don't know how to Tex logic formulas )

i) ~∃xQ(x) , or, for all x, ~Q(x)

ii)∃xP(x)

iii)∃x(P(x)→Q(x))

So, say you have S={a,b} as your universe, with:

~Q(a), ~Q(b)

P(a) , ~P(b)

Then:

i)From P(a) , you have ∃xP(x)

ii) Since ~P(b) , then ~P(b)\/ Q(b) , so P(b)→Q(b), so ∃x(P(x)→Q(x) ) is satisfied by b

iii) Clearly, ~∃xQ(x)

I think this does it.

The method is using a truth-tree.

+++++++++++++++++++++++++++++++++++++++

Sorry, it is difficult for me to tell if yours is a counterexample: I don't know what your universe of domain is

let alone an assignment of the satisfaction values , i.e., which elements of

your universe satisfy Q(x) or not, and which satisfy P(x) or not.

Last edited: Aug 13, 2012
7. Aug 13, 2012

### voko

Observe that implication holds even if its left-hand argument does not.

8. Aug 13, 2012

### jahaan

Bacle is right...

The point is, the x's DON'T have to be the same throughout the whole argument. The x's only have to be the same inside the 'scope' of the quantifier, and the scope is the scentence between cases right after the quantifier.

So, like Bacle said, if you have a set S= {a,b} as your universe:

It is possible that P(a) is true, but P(b), Q(a) and Q(b) are all false. Then both premises are true, but the consequent is false:

P is true for a, so Ex(P(x)); (P(b) -> Q(b)) is true; but there is no x so Q(x) is true!

9. Aug 13, 2012

### Mixer

I think I got it now.

So let x $\in$ {a,b}

Let's assume that for a P(a) is true, and P(b) is not, and both Q(a) and Q(b) are false.

So:

1) a satisfies P therefore $\exists$P(x)
2) P(b) and Q(b) satisfy ∃x(P(x) → Q(x)) (because (false -> false ) = true

So they are both true.

3) But there is no x that satisfies ∃x(Q(x)) (Because for a and b Q(x) doesn't hold!)

So there is the counterexample!

Thank you very much Bacle2 (and others) !

I think my mistake was that I was assuming that x must be the same troughout the argument.