Set and Logic, Proving two quantifier the same

53 Views Asked by At

$(∃x∈A:P(x))∨(∃x∈B:P(x)) = ∃x∈(A∪B):P(x)$

I spent hours approaching this problem many different way

By Definition: $(∃x∈A:P(x))∨(∃x∈B:P(x)) \\ ∃x:[(x∈A \to P(x) \vee (x∈B \to P(x)] \\ ∃x:[(¬x∈A ∨ P(x) \vee (¬x∈B ∨ P(x)] \\ ∃x:[¬x∈A ∨ P(x) \vee ¬x∈B ∨ P(x)] \\ ∃x:[(¬x∈A ∨ ¬x∈B) ∨ P(x)] \\ ∃x:[¬(x∈ A\cap B) ∨ P(x)] \\ ∃x:[(x∈ A\cap B)\to P(x)] \\ ∃x∈(A\cap B):P(x)] \qquad\qquad \neq ∃x∈A∪B:P(x)$

COULD Someone tell me what is wrong with this logic

1

There are 1 best solutions below

0
On BEST ANSWER

This bit: $\exists x\in A\big( P(x) \big) \neq \exists x \big(x \in A \to P(x)\big)$.

For a restriction existential quantification we use the conjunction, not the implication. That's for the restricted universal quantification.

$$\exists x\in A\big( P(x) \big) = \exists x \big(x \in A \wedge P(x)\big)$$


So your proof should look like:

$$\begin{align}& (\exists x\in A:P(x))\vee(\exists x\in B:P(x)) \\[1ex]\Updownarrow & \text{(restricted existential)} \\[1ex] & \exists x:[(x\in A \wedge P(x))] \vee \exists x:[(x\in B \wedge P(x))] \\[1ex]\Updownarrow & \text{(disjunction of existential quantification)} \\[1ex] & \exists x:[(x\in A \wedge P(x)) \vee (x\in B \wedge P(x))] \\[1ex]\Updownarrow & \text{(distribution)} \\[1ex] & \exists x:[(x\in A \vee x\in B) \wedge P(x)] \\[1ex]\Updownarrow & \text{(definition of set union)} \\[1ex] & \exists x:[(x\in (A \cup B)) \wedge P(x)] \\[1ex]\Updownarrow & \text{(restricted existential)} \\[1ex] & \exists x\in (A\cup B):P(x) \end{align}$$