Question

how is ∀x (~P(x) or ∃y (P(y) and x ≠ y)) equivalent to
∀x ~P(x) or ∃x ∃y (P(x) and P(y) and x ≠ y)

Answer 1

Let me just TeX this to clarify:
\[\forall x\bigg(\neg P(x)\wedge \exists y~\big(P(y)\vee~x\not=y\big)\bigg)\]
\[\forall x~\neg P(x)\wedge \exists x,\exists y~\bigg(P(x)\wedge P(y)\wedge~x\not=y\bigg)\]
Is this what you're trying to say?

Answer 2

yes

Answer 3

basically it's the negation of ∃!x P(x)

Answer 4

I don't see how the two statements are equivalent

Answer 5

Hmm, I'd try approaching it by showing both statements are indeed negations of \(\exists!~x~P(x)\). If both of them are, then they must be logically equivalent.

Answer 6

ok, do you know how to show they're equivalent?

Answer 7

What ever happened to what I wrote the other day?

Answer 8

@wio you wrote ∀x ~P(x) or ∃x ∃y (P(x) and P(y) and x ≠ y)

Answer 9

and i'm trying to see how it is equivalent to ∀x (~P(x) or ∃y (P(y) and x ≠ y))

Answer 10

Try directly negating it and simplifying.

Answer 11

well, I did. It is ∀x (~P(x) or ∃y (P(y) and x ≠ y)), which is different from what you said. So I'm trying to see how the two are equivalent

Answer 12

Well, I haven't taken a formal course in logic, but I have a basic understanding of what the symbols mean. Hopefully that should be enough?

If \(\exists!~x~P(x)\) means there's a unique \(x\) such that \(P(x)\) is true, then the negation would involve the existence of a different element that makes the statement \(P\) true.

So, looking at the first statement, \(\forall x\bigg(\neg P(x)\wedge \exists y~\big(P(y)\vee~x\not=y\big)\bigg)\), which means for any \(x\) both \(P(x)\) is not true AND there's another element \(y\) for which either the statement is true or \(x\) and \(y\) are distinct. Basically, you're given that there's a not necessarily unique \(y\) for which \(P\) holds.

The second statement seems clearer to me, \(\forall x~\neg P(x)\wedge \exists x,\exists y~\bigg(P(x)\wedge P(y)\wedge~x\not=y\bigg)\). For any \(x\), \(\neg P\) is true and there are distinct elements \(x,y\) for which \(P\) is true. I'm not sure if this helps, just rattling off the definitions...

Answer 13

Why are you asking that it is equivalent if it is the negation?

Answer 14

both ∀x (~P(x) or ∃y (P(y) and x ≠ y)) and ∀x ~P(x) or ∃x ∃y (P(x) and P(y) and x ≠ y) are negation of ∃!x P(x).

Answer 15

You said the latter statement. The former one is the result of direct negation. The two are supposedly equivalent. I just don't see how

Answer 16

Okay, distribute the \(\forall x\) part first then.

Answer 17

uhm... i think we can't do that

Answer 18

Oh, right. I see. Actually, showing that two first-order logical statements are equivalent is a very hard problem.

Answer 19

T.T

Answer 20

Showing they are not equivalent requires a counter example.

Answer 21

but they are indeed equivalent D:

Answer 22

There is one thing you can do to make it a bit easier to see I think...

Answer 23

I believe that \(\lnot p \lor q\) is the same as \(\lnot p \lor (p\land q)\).

Answer 24

Since: \[
\lnot p\lor q \iff (\lnot p\lor q ) \land T \iff (\lnot p\lor q ) \land (\lnot p\lor p )
\]

Answer 25

Thus we can say: \[
\forall x (\lnot P(x)\lor \exists y P(x)\land P(y)\land x\neq y)
\]

Answer 26

I understand the (~P or P) and (~P or Q), but the next statement seems to come out of the blue

Answer 27

You are right, the \(\forall x\) complicates things a bit.

Answer 28

But we can consider each \(x\) independently. when doing this \(P(x)\) becomes a constant.

Answer 29

Perhaps i'll try to consider each x independently later on and see what'll happen.

Thank you for your replies!