1
$\begingroup$

This is my first post on the Math Stack Exchange so i'm sorry if questions of this nature are supposed to be tagged in a specific way, if they are please let me know and I will try to update my post to reflect it!
I'm currently trying to self study my way through Vellemans "How to Prove It" 3rd Edition (So far this book has been a phenomenal experience, I originally picked it up for help with a discrete math curriculum I was trying to follow, but the way Velleman build's up logical notation is very beautiful). However I believe I am having some problems formatting some equivalences properly. I'm on chapter 2.2, Equivalences involving quantifiers, exercise 13.

a) Show the statement $A \subseteq B$ and $A \cup B = B$ are equivalent by writing them each in logical symbols, and then showing the resulting formulas are equivalent.

To do this, I used the following logic:
$$ Let A \subseteq B = \forall x(x \in A \rightarrow x\in B) $$ $$ Let (A \cup B = B) = \forall x \in (A \cup B) (x \in B) $$ We start with $\forall x \in (A \cup B) (x \in B)$ and use the expansion for the bounded universal quantifier introduced in this chapter. $\forall x \in A \ P(x) = \forall x(x \in A \rightarrow P(x))$ $$ \forall x(x \in (A \cup B) \rightarrow x \in B) $$ From here it's trivial $$ \forall x((x \in A \vee x \in B) \rightarrow x \in B) $$ $$ \forall x((x \notin A \wedge x \notin B) \vee x\in B) $$ $$ \forall x((x \notin A \vee x \in B) \wedge (x \notin B \vee x \in B)) $$ $$ \forall x((x \notin A \vee x \in B) \wedge \ T) $$ $$ \forall x(x \in A \rightarrow x \in B) $$ $$ A \subseteq B $$ My issues begin in the next part of the exercise:

b) Show that the statements $A \subseteq B$ and $A \cap B = A$ are equivalent.

This statement at first glance seems like it would be easier to show then the original. I set up the statement as follows:

$$ Let (A \cap B = A) = \forall x \in (A \cap B) (x \in A) $$ We then apply an adjacent operation as the first statement $$ \forall x(x \in (A \cap B) \rightarrow x \in A) $$

$$ \forall x((x \in A \wedge x \in B) \rightarrow x \in A) $$ But from here we quickly decay into a tautology $$ \forall x(\neg (x \in A \wedge x \in B) \vee x \in A) $$ $$ \forall x((x \notin A \vee x \notin B) \vee x \in A) $$ Every way forward from here that I have tried ends up just coming back full circle as a tautology. This urges me to wonder if there is something fundamental that I am missing in setting up these equivalencies, and to also second guess if I properly showed what was desired in the first part of the question. If you have any hints or if you see that I'm fundamentally applying something wrong, please let me know. Thank you!

$\endgroup$
3
  • $\begingroup$ You want to show that if $A \subseteq B$, then $A \cup B = B$, which can be broken down as $A \cup B \subseteq B$ and $B \subseteq A \cup B$. For the first, if $x \in A \cup B$, then $x \in B$ or $x \in A$, which also gives $x \in B$ since $A \subseteq B$. So we have $x \in B$, showing that $A \cup B \subseteq B$. The second is trivial. $\endgroup$
    – Prasiortle
    Feb 27 at 1:06
  • $\begingroup$ (A∪B=B) must be $∀x[ x∈(A∪B) \leftrightarrow (x∈B)]$ $\endgroup$ Feb 27 at 8:45
  • $\begingroup$ Hmm, I think you are right Mauro. The author points to another example using a biconditional connective in the book. When I get the free time, I will give it a try. Thank you! $\endgroup$
    – Cibo
    Feb 27 at 9:58

0

You must log in to answer this question.

Browse other questions tagged .