Use a boolean property to show that the following statements about sets X and Y are logically equivalent

Question

I am working on a question that references a previous assignment where we proved that if $p \Rightarrow q, q \Rightarrow r, r \Rightarrow s,s \Rightarrow p$, then p,q,r,s are all logically equivalent. This question asks to prove the following statements about any sets X and Y are all logically equivalent:

$X \subseteq Y$

$X \cap Y = X$

$X \cup Y = Y$

$!Y \subseteq !X$ (was unsure of how to format set compliment)

I attempted to solve the problem by letting a = $x \in X$ and b = $x \in Y$

Then $a \Rightarrow b$, and $a \land b = a$, and $a \lor b = b$

However that isn't really getting me there. I guess my main point of confusion is how I can translate these sets into logical expressions so I can use that first rule? I was under the impression boolean logic and sets were different, so I am finding this question very confusing.

Answer 1

However that isn't really getting me there. I guess my main point of confusion is how I can translate these sets into logical expressions so I can use that first rule? I was under the impression boolean logic and sets were different, so I am finding this question very confusing.

Boolean logic and set operations are very much interrelated.

---

You need to show $a\to b \implies (a\land b)\leftrightarrow a$ and so forth.

Natural Deduction

Take the premise $a\to b$.   Assuming $a$, derives $b$ by conditional elimination (aka "modus ponens") and thus $a\wedge b$ by conjunction introduction ("addition"), so therefore $a\to a\wedge b$ is infered from the premise.   Assuming $a\wedge b$ of course derives $a$ by conjunction elimination ("simplification"), so $a\wedge b\to a$ is immediately infered.   Thus demonstrating that $a\to b\implies (a\land b)\leftrightarrow a$.

Old School

Or you might leave it as $x\in X\to x\in Y\implies x\in X\land x\in Y\leftrightarrow x\in Y$, and argue that if anything in $X$ is in $Y$, then clearly: anything which is in $X$ and in $Y$ is in $X$, and anything which is in $X$ is in $X$ and in $Y$, so therefore the claim holds.

Or use whatever rules you have been given .

---

Hence $X\subseteq Y \implies X\cap Y=X$.

I'll leave it to you to do the other implications.