I'm starting to learn Set Theory and I'm stuck on a question:
Show that the relations $(A \cup C)\subset(A\cup B), (A\cap C) \subset (A\cap B)$ when combined, imply $C\subset B$. If it's in anyone's interest, this is from the online textbook "Basic Concepts of Mathematics" by Elias Zakon. I'm afraid I've no idea where to start. Any help would be much appreciated.
Simple Set Theory Question
4 Answers
Suppose $c$ is in $C$. We want to show that $c$ is in $B$. Certainly $C$ is in $A \cup C$, and so by your first assumption, $c$ is in $A \cup B$. That is, either $c$ is in $A$ or $c$ is in $B$. In the latter case we are done. In the former case, $c$ is in $C$ and in $A$ and so $c$ is in $A \cap C$, and so by your second assumption, $c$ is in $A \cap B$ and hence in $B$.
Thus in all cases, if $c$ is in $C$, then $c$ is in $B$, and so we have shown $C \subset B$.
-
0Thank you! I managed to get to $c\in A\cup B$ but didn't manage to extend it - I suppose it's just down to practice now. – 2012-05-29
We begin in the definitions.
$A\cup C\subseteq A\cup B$ means that if $x\in A$ or $x\in C$ then $x\in A$ or $x\in B$.
$A\cap C\subseteq A\cap B$ means that if $x\in A$ and $x\in C$ then $x\in A$ and $x\in B$.
Lastly, $C\subseteq B$ which is what we want to show, namely if $x\in C$ then $x\in B$.
Now assume the first two happen. To show the last we need to show that what is stated in the definition is true. So we begin by taking some arbitrary $c\in C$ and going through what we already know:
Suppose that $c\in C$.
Either $c\in A$ or $c\notin A$.
If $c\in A$ then $c\in A\cap C$, by the second statement we have that $c\in A\cap B$. In particular $c\in B$.
If $c\notin A$ then $c\in A\cup C$, since $c\in C$, and by the first statement we have that $c\in A\cup B$. Therefore $c\in A$ or $c\in B$. However we assume that $c\notin A$ so we have to have $c\in B$.
We showed that either way $c\in C$ implies that $c\in B$. Therefore $C\subseteq B$.
One tip I always repeat when teaching mathematics (especially at intro level) is to have the definitions of all the symbols and terms at reach. Most of these exercises can be solved by simply unraveling the definitions to their bare form and then reconstructing what we have (with the assumptions) to have the conclusion.
When approaching a problem the first thing which one needs to be able to do is tell exactly what each symbol mean and what are the relations between the different symbols. This is often ignored by most first year students. You cannot solve a problem that you do not understand, not in a meaningful and helpful way, anyway.
Suppose $x \in C$. You need to show $x \in B$. Since $x \in C$, $x \in A \cup C$, so either $x \in A$ or $x \notin A$. We consider two cases:
Case 1: $x \in A$. Then, since $x \in C$, we must have $x \in A \cap C$. What does this imply?
Case 2: $x \notin A$.Then $x \in C$. But $A \cup C \subset A \cup B$. What does this imply?
This is the HTML output of my DC Proof proof of this.
It effectively proceeds exactly the same as the other answers: At line 15, assuming $x \in C$, showing this means, at line 42, $x \in A\ or\ B$; then assuming $x \in A$, at line 43 showing this means $x \in B$, at line 58; then just completing the details showing all cases have been covered and $x \in C \implies x \in B$ at line 64.
Simple Set Theory Question http://math.stackexchange.com/questions/151245/simple-set-theory-question DC Proof does not have a built in subset operator, so I have converted that as such Subset(A,B)=>ALL(d):[dεA=>dεB] DC Proof also implies you can't do (all) set operations on the class of all sets, so all entries are in a universal set, u. However I have then deleted all unused lines split from earlier joined entries. 1 ALL(a):[Set(a) => EXIST(b):[Set(b) & ALL(c):[c ε b <=> Set(c) & ALL(d):[d ε c => d ε a]] & ALL(c):ALL(d):[c ε b & d ε b => Set(c||d) & c||d ε b & ALL(e):[e ε c||d <=> e ε c | e ε d]] & ALL(c):ALL(d):[c ε b & d ε b => Set(c&&d) & c&&d ε b & ALL(e):[e ε c&&d <=> e ε c & e ε d]] & ALL(c):[c ε b => Set(`c) & `c ε b & ALL(d):[d ε `c <=> d ε a & ~d ε c]]]] Set Ops 2 Set(u) Axiom 3 Set(u) => EXIST(b):[Set(b) & ALL(c):[c ε b <=> Set(c) & ALL(d):[d ε c => d ε u]] & ALL(c):ALL(d):[c ε b & d ε b => Set(c||d) & c||d ε b & ALL(e):[e ε c||d <=> e ε c | e ε d]] & ALL(c):ALL(d):[c ε b & d ε b => Set(c&&d) & c&&d ε b & ALL(e):[e ε c&&d <=> e ε c & e ε d]] & ALL(c):[c ε b => Set(`c) & `c ε b & ALL(d):[d ε `c <=> d ε u & ~d ε c]]] U Spec, 1 4 EXIST(b):[Set(b) & ALL(c):[c ε b <=> Set(c) & ALL(d):[d ε c => d ε u]] & ALL(c):ALL(d):[c ε b & d ε b => Set(c||d) & c||d ε b & ALL(e):[e ε c||d <=> e ε c | e ε d]] & ALL(c):ALL(d):[c ε b & d ε b => Set(c&&d) & c&&d ε b & ALL(e):[e ε c&&d <=> e ε c & e ε d]] & ALL(c):[c ε b => Set(`c) & `c ε b & ALL(d):[d ε `c <=> d ε u & ~d ε c]]] Detach, 3, 2 5 Set(us) & ALL(c):[c ε us <=> Set(c) & ALL(d):[d ε c => d ε u]] & ALL(c):ALL(d):[c ε us & d ε us => Set(c||d) & c||d ε us & ALL(e):[e ε c||d <=> e ε c | e ε d]] & ALL(c):ALL(d):[c ε us & d ε us => Set(c&&d) & c&&d ε us & ALL(e):[e ε c&&d <=> e ε c & e ε d]] & ALL(c):[c ε us => Set(`c) & `c ε us & ALL(d):[d ε `c <=> d ε u & ~d ε c]] E Spec, 4 6 ALL(c):ALL(d):[c ε us & d ε us => Set(c||d) & c||d ε us & ALL(e):[e ε c||d <=> e ε c | e ε d]] Split, 5 7 ALL(c):ALL(d):[c ε us & d ε us => Set(c&&d) & c&&d ε us & ALL(e):[e ε c&&d <=> e ε c & e ε d]] Split, 5 8 Set(a) & Set(b) & Set(c) & a ε us & b ε us & c ε us Axiom 9 a ε us Split, 8 10 b ε us Split, 8 11 c ε us Split, 8 12 ALL(d):[d ε a||c => d ε a||b] & ALL(d):[d ε a&&c => d ε a&&b] Premise 13 ALL(d):[d ε a||c => d ε a||b] Split, 12 14 ALL(d):[d ε a&&c => d ε a&&b] Split, 12 15 x ε c Premise 16 x ε a||c => x ε a||b U Spec, 13 17 ALL(d):[a ε us & d ε us => Set(a||d) & a||d ε us & ALL(e):[e ε a||d <=> e ε a | e ε d]] U Spec, 6 18 ALL(d):[a ε us & d ε us => Set(a&&d) & a&&d ε us & ALL(e):[e ε a&&d <=> e ε a & e ε d]] U Spec, 7 19 a ε us & b ε us => Set(a||b) & a||b ε us & ALL(e):[e ε a||b <=> e ε a | e ε b] U Spec, 17 20 a ε us & b ε us => Set(a&&b) & a&&b ε us & ALL(e):[e ε a&&b <=> e ε a & e ε b] U Spec, 18 21 a ε us & c ε us => Set(a||c) & a||c ε us & ALL(e):[e ε a||c <=> e ε a | e ε c] U Spec, 17 22 a ε us & c ε us => Set(a&&c) & a&&c ε us & ALL(e):[e ε a&&c <=> e ε a & e ε c] U Spec, 18 23 a ε us & b ε us Join, 9, 10 24 a ε us & c ε us Join, 9, 11 25 Set(a||b) & a||b ε us & ALL(e):[e ε a||b <=> e ε a | e ε b] Detach, 19, 23 26 Set(a&&b) & a&&b ε us & ALL(e):[e ε a&&b <=> e ε a & e ε b] Detach, 20, 23 27 Set(a||c) & a||c ε us & ALL(e):[e ε a||c <=> e ε a | e ε c] Detach, 21, 24 28 Set(a&&c) & a&&c ε us & ALL(e):[e ε a&&c <=> e ε a & e ε c] Detach, 22, 24 29 ALL(e):[e ε a||b <=> e ε a | e ε b] Split, 25 30 ALL(e):[e ε a&&b <=> e ε a & e ε b] Split, 26 31 ALL(e):[e ε a||c <=> e ε a | e ε c] Split, 27 32 ALL(e):[e ε a&&c <=> e ε a & e ε c] Split, 28 33 x ε a||c <=> x ε a | x ε c U Spec, 31 34 [x ε a||c => x ε a | x ε c] & [x ε a | x ε c => x ε a||c] Iff-And, 33 35 x ε a | x ε c => x ε a||c Split, 34 36 x ε a | x ε c Arb Or, 15 37 x ε a||c Detach, 35, 36 38 x ε a||b Detach, 16, 37 39 x ε a||b <=> x ε a | x ε b U Spec, 29 40 [x ε a||b => x ε a | x ε b] & [x ε a | x ε b => x ε a||b] Iff-And, 39 41 x ε a||b => x ε a | x ε b Split, 40 42 x ε a | x ε b Detach, 41, 38 43 x ε a Premise 44 x ε a & x ε c Join, 43, 15 45 x ε a&&c <=> x ε a & x ε c U Spec, 32 46 [x ε a&&c => x ε a & x ε c] & [x ε a & x ε c => x ε a&&c] Iff-And, 45 47 x ε a&&c => x ε a & x ε c Split, 46 48 x ε a & x ε c => x ε a&&c Split, 46 49 x ε a&&c Detach, 48, 44 50 x ε a&&c => x ε a&&b U Spec, 14 51 x ε a&&b Detach, 50, 49 52 x ε a&&b <=> x ε a & x ε b U Spec, 30 53 [x ε a&&b => x ε a & x ε b] & [x ε a & x ε b => x ε a&&b] Iff-And, 52 54 x ε a&&b => x ε a & x ε b Split, 53 55 x ε a & x ε b => x ε a&&b Split, 53 56 x ε a & x ε b Detach, 54, 51 57 x ε a Split, 56 58 x ε b Split, 56 59 x ε a => x ε b Conclusion, 43 60 ~x ε a => x ε b Imply-Or, 42 61 x ε a | ~x ε a Or Not 62 [x ε a => x ε b] & [~x ε a => x ε b] Join, 59, 60 63 x ε b Cases, 61, 62 64 ALL(d):[d ε c => d ε b] Conclusion, 15 65 ALL(d):[d ε a||c => d ε a||b] & ALL(d):[d ε a&&c => d ε a&&b] => ALL(d):[d ε c => d ε b] Conclusion, 12
-
0@AsafKaragila $I$t is not automated, it is just from first principals. $I$ chose to submit it because it was small enough to do so. $I$ agree it doesn't add much to the existing answers, but then a lot of answers can be accused of that. – 2012-05-30