I'm trying to prove the following with no success:
$\forall$A $\in$ F $\forall$B $\in$ G(A $\not\subseteq$ B) $\leftrightarrow$ $\cup$F $\not\subseteq$ $\cup$G
In order to prove this statement, I should prove both sides of the implication.
I was able to prove $\cup$F $\not\subseteq$ $\cup$G $\to$ $\forall$A $\in$ F $\forall$B $\in$ G(A $\not\subseteq$ B), but I got stuck with:
$\forall$A $\in$ F $\forall$B $\in$ G(A $\not\subseteq$ B) $\to$ $\cup$F $\not\subseteq$ $\cup$G
First approach:
- Suppose $\forall$A $\in$ F $\forall$B $\in$ G(A $\not\subseteq$ B). My goal then becomes $\cup$F $\not\subseteq$ $\cup$G.
Using the subset definition, I can express $\cup$F $\not\subseteq$ $\cup$G as $\exists$x(x $\in$ $\cup$F $\land$ x $\not\in$ $\cup$G).
My only given is $\forall$A $\in$ F $\forall$B $\in$ G(A $\not\subseteq$ B) and my goal is $\exists$x(x $\in$ $\cup$F $\land$ x $\not\in$ $\cup$G). I'd need universal instantiation on the given to deduce A $\not\subseteq$ B, however I don't have any values to plug for A and B. For the goal, I should let x equal a value that is a member of $\cup$F but not a member of $\cup$G, however I can't think of any value without some more givens.
If I try to prove a contradiction, I assume $\neg$$\exists$x(x $\in$ $\cup$F $\land$ x $\not\in$ $\cup$G) which means $\forall$x(x $\not\in$ $\cup$F $\lor$ x $\in$ $\cup$G), but I end up with another universal quantifier given that I cannot instantiate.
Second approach: Prove the contrapositive.
- Suppose $\cup$F $\subseteq$ $\cup$G. My goal then becomes $\exists$A $\in$ F $\exists$B $\in$ G(A $\subseteq$ B).
- $\cup$F $\subseteq$ $\cup$G means $\forall$x(x $\in$ $\cup$F $\to$ x $\in$ $\cup$G).
- I end up in the same situation as the first approach, as I don't have a value to plug for the goal and no value to use universal instantiation with the given neither.
How should I continue my proof? Is there anything that I'm not seeing?