Having some trouble with proving for some sets $M,N$ that $M \cap N = M$ if and only if $M \subseteq N$

Question

Proposition: $\textit{Let M and N be sets. Prove that $M \cap N = M$ iff $M \subseteq N$}\\$

---

My Proof: Going from the definition of set intersection and subsets, the above statement can be rewritten as follows: $$\{a: (a \in M \wedge a \in N) \equiv a \in M \} \equiv \{a: a \in M \Rightarrow a\in N\}.$$ Now let $p = a \in M$ and $q = a \in N$. This allows us to further rewrite the above statement in predicate logic: $$((p \wedge q) \equiv p) \equiv (p \Rightarrow q).$$ This is a tautology, as shown by the truth table below.

Therefore the intersection of the sets M and N equal N if and only if M $\subseteq$ N.

---

Is my proof even correct? My math professor doesn't find it sound to convert this statement into predicate logic and go from there, he just breaks apart the if and only if into two implications, and then goes by the definition of subsets. Which approach is better? Am I not employing the correct definition of set equivalence in terms of logic?

Answer 1

Having some trouble with proving for some sets $M,N$ that $M \cap N = M$ if and only if $M \subseteq N$

To be clear, the proof is required for an arbitrary pair of sets $M,N,$ which is to say that it's for all sets $M,N$ rather than some sets $M,N.$

Proposition: $$M \cap N = M\quad\text{iff}\quad M \subseteq N.$$ My Proof: the above statement can be rewritten as follows: $$\{a: (a \in M \wedge a \in N) \equiv a \in M \} \equiv \{a: a \in M \Rightarrow a\in N\}.$$

You seem to be conflating equivalence, logical equivalence, and equality.

And, just to be clear: while $M \cap N$ is a set, $M \subseteq N$ is not.

Now, consider the set $\{a: a \in M \Rightarrow a\in N\}.$ It is the empty set if, in a given context, $M \not\subseteq N;$ otherwise, it is the universal set.

Now let $p = a \in M$ and $q = a \in N$. This allows us to further rewrite the above statement in predicate logic: $$((p \wedge q) \equiv p) \equiv (p \Rightarrow q).$$

This is more coherent, but better if you use change all the metalogical symbols to logical symbols, and you do need to quantify the predicates ($M\subseteq N$ means $∀a\;(p{\implies}q)$): $$∀a\Big(\big(a{\in}M \wedge a{\in}N\big) \leftrightarrow a{\in}M\Big) \leftrightarrow ∀b\Big(b{\in}M \to b{\in}N\Big).$$

This correctly rewrites the given proposition, but unfortunately it cannot be derived using a truth table.

Incidentally, $$∀a\Big(\big(a{\in}M \wedge a{\in}N\big) \leftrightarrow a{\in}M\Big) \leftrightarrow ∀a\Big(a{\in}M \to a{\in}N\Big)\\\not\equiv\\∀a\;\left[\Big(\big(a{\in}M \wedge a{\in}N\big) \leftrightarrow a{\in}M\Big) \leftrightarrow \Big(a{\in}M \to a{\in}N\Big)\right].$$

Using formal logic to prove the given proposition is not advantageous.

Answer 2

Let's prove the first direction

$(\Rightarrow)$

$M\cap N \subset M$ and $M\cap N \subset N$

Then if $M\cap N = M$, necessarily $M\subset N$.

$(\Leftarrow)$

$\forall m \in M$, $m \in N$

By the definition of intersection

$$ M\cap N =\{x: x\in M \;\;\text{and}\;\;x\in N\} = M $$