# Simple Set Theory Question

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.

-

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$.

-
Thank 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. – Daniel Littlewood May 29 '12 at 18:23

We begin in the definitions.

1. $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$.

2. $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$.

3. 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$.

1. 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$.

2. 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


-
Why is this even useful? Even if no other answer had been supplied (and there has been three answers, one of which was even accepted) how does an output of an automated proof is useful for someone who wishes to learn how to prove these things on their own? This is hardly readable in any educational way and merely tells us that "the proposition is true" and that "the proof system is working fine here", neither of which are related to the question. – Asaf Karagila May 30 '12 at 6:13
@AsafKaragila It 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. – Mark Hurd May 30 '12 at 6:59