Quantifier equivalence in set theory

In summary, the author is trying to show that if there exists a certain color or shape then the person likes that object. However, they are not able to complete the task and are not sure where they are going wrong.
  • #1
GregA
210
0

Homework Statement


I have been asked to show that [tex]\exists xAP(x)\vee\exists xBP(x)[/tex] is equivalent to [tex]\exists x(A\cup B)P(x)[/tex]



Homework Equations


1) [tex] P\rightarrow Q \equiv \neg P \vee Q[/tex]
2) [tex] \neg(P\vee Q)\equiv \neg P \wedge \neg Q [/tex]
3) [tex] P \vee (Q\vee R) \equiv (P\vee Q) \vee R \equiv P \vee Q\vee R [/tex]


The Attempt at a Solution


[tex]\exists xAP(x)\vee\exists xBP(x)[/tex]
[tex]\exists x(x\in A \rightarrow P(x))\vee\exists x(x\in B \rightarrow P(x))[/tex] definition of the above
[tex]\exists x[(x\notin A \vee P(x))\vee (x\notin B \vee P(x))][/tex] using (1)
[tex]\exists x(x\notin A \vee x\notin B \vee P(x))[/tex] using (3)
[tex]\exists x[\neg(x\in A \wedge x\in B) \vee P(x)][/tex] using (2)
[tex]\exists x[x\in (A\cap B) \rightarrow P(x)] [/tex] using (1) and simplifying the expression ... [tex]\exists x(A\cap B)P(x)[/tex]

This is not what the book is asking me to show though!...and I can't see where I've gone wrong either:frown: ...Starting from the RHS and trying to show it is equivalent to the LHS gets me:
[tex]\exists xAP(x)\wedge\exists xBP(x)[/tex] which is still no good!

Trying to think of it in terms of words then:
Referring to A as (the set of colours of an object), referring to B as (the set of shapes of an object) and P(x) as ( P likes it) then
[tex]\exists xAP(x)\vee\exists xBP(x)[/tex] is saying that if there exists a certain colour then P likes the object or if there exists a certain shape then P likes the object
My conclusion [tex]\exists x(A\cap B)P(x)[/tex] however says that if there exists a certain shape AND a certain colour then P likes the object

what I am meant to show however seems correct inspite of my efforts ie: [tex]\exists x(A\cup B)P(x)[/tex] if there exists a certain shape OR a certain colour then P likes the object

Can anyone show me where I'm going wrong?
 
Last edited:
Physics news on Phys.org
  • #2
GregA said:

Homework Statement


I have been asked to show that [tex]\exists xAP(x)\vee\exists xBP(x)[/tex] is equivalent to [tex]\exists x(A\cup B)P(x)[/tex]
That is: "either there exist x in A such that P(x) is true or there exist x in B such that P(x) is true" is equivalent to "there exist x in A union B such that P(x) is true"



Homework Equations


1) [tex] P\rightarrow Q \equiv \neg P \vee Q[/tex]
2) [tex] \neg(P\vee Q)\equiv \neg P \wedge \neg Q [/tex]
3) [tex] P \vee (Q\vee R) \equiv (P\vee Q) \vee R \equiv P \vee Q\vee R [/tex]


The Attempt at a Solution


[tex]\exists xAP(x)\vee\exists xBP(x)[/tex]
Yes, that is one of the two statements

[tex]\exists x(x\in A \rightarrow P(x))\vee\exists x(x\in B \rightarrow P(x))[/tex] definition of the above
Are you sure that's the same thing? I would interpret this as "either there exist x such that if x is in A then P(x) is true or there exist x such that if x is in B then P(x) is true. If P(x) were false for all x in A or B, both statements would be true!

Since [tex]x in A \rightarrow x in A\cup B[/tex] and [tex]x in B \right arrow x in A\cup B[/tex],
[tex](\exists xAP(x)\vee\exists xBP(x))\rightarrow x in A\cup B P(x)[/tex]
 
Last edited by a moderator:
  • #3
[tex]\exists x(x\in A \rightarrow P(x))\vee\exists x(x\in B \rightarrow P(x))[/tex]should be [tex]\exists x(x\in A \vee x\in B) \rightarrow P(x))[/tex]
 
  • #4
HallsofIvy said:
Are you sure that's the same thing? I would interpret this as "either there exist x such that if x is in A then P(x) is true or there exist x such that if x is in B then P(x) is true. If P(x) were false for all x in A or B, both statements would be true!

I see your point!...thanks for that :smile:
Will now return to my book, figure out where I mis-understood it and then try to finish this question properly

*edit* and thankyou to you Courtigrad as well...I was totally unaware of where I was messing up
 

1. What is quantifier equivalence in set theory?

Quantifier equivalence in set theory is a concept that relates to the logical quantifiers "for all" (∀) and "there exists" (∃). In set theory, quantifier equivalence states that the statements "for all elements x in a set S, P(x) is true" and "there exists an element x in set S such that P(x) is true" are equivalent. This means that if one statement is true, then the other must also be true.

2. How does quantifier equivalence affect set operations?

Quantifier equivalence plays a crucial role in set operations, as it allows us to simplify complex statements involving logical quantifiers. For example, the statement "for all elements x in set A, x is also an element of set B" can be rewritten using quantifier equivalence as "there exists an element x in set A that is not an element of set B". This simplification makes it easier to prove certain properties and relationships between sets.

3. Are there any exceptions to quantifier equivalence in set theory?

No, quantifier equivalence is a fundamental principle in set theory and applies to all sets and logical statements. It is a logical truth that can be proven using mathematical reasoning.

4. How is quantifier equivalence related to other concepts in set theory?

Quantifier equivalence is closely related to other concepts in set theory, such as set equality and set membership. It is used to prove theorems and properties about sets, and is an important tool in understanding the relationships between different sets.

5. Can quantifier equivalence be extended to other mathematical systems?

Yes, quantifier equivalence is a general concept that can be applied to other mathematical systems beyond set theory. It is a key principle in mathematical logic and is used in various fields such as algebra, analysis, and topology.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
796
  • General Math
Replies
1
Views
718
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
899
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
5K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
Back
Top