# Thread: Basic Set Theory Proofs

1. ## Basic Set Theory Proofs

I'm taking Topology next semester and, to prepare, I'm learning a little set theory. I had bought a Topology book from Dover Publications a couple years ago and am now starting to do some problems in it. The very first section is on Set Theory. Here's the first couple problems:

1. S ⊂ T, then T - (T - S) = S.

Proof:
Let x ∈ (S ⊂ T). Therefore, x ∉ (T – S). If x ∉ (T – S), then x ∈ T – (T – S). And x ∈ (S ⊂ T). Therefore, S ⊂ (T - (T - S))

Let x ∈ (T - (T - S)). This implies that x ∉ (T – S). Which implies that x ∈ S. Therefore, T – (T – S) ⊂ S and T - (T - S) = S.

2. S ⊂ T iff S ∩ T = S.

Proof:
If S ⊂ T, every x ∈ S is in T. That implies that every x ∈ S is in S ∩ T. This implies that S ∩ T = S.

Let x ∈ S. If S ∩ T = S, then x ∈ (S ∩ T). This implies that S is contained in T and S ⊂ T.

I could really use some direction/correction.

2. ## Re: Basic Set Theory Proofs

First, the symbol ⊂ is somewhat ambiguous because it may mean either proper or improper subset in different sources. To clear the ambiguity, ether use ⊆ for improper subset and ⊊ for proper subset or describe your notation in words.

Originally Posted by aareavis
1. S ⊂ T, then T - (T - S) = S.

Proof:
Let x ∈ (S ⊂ T).
An object x cannot belong to (S ⊂ T) because (S ⊂ T) is a proposition (something that is either true or false), not a set. It is sometimes possible to write x ∈ S ⊆ T as a contraction to "x ∈ S and S ⊆ T," but such shortcuts are better avoided in the beginning.

Originally Posted by aareavis
If x ∉ (T – S), then x ∈ T – (T – S).
Only if x ∈ T, which, granted, is apparently the case here.

Originally Posted by aareavis
Let x ∈ (T - (T - S)). This implies that x ∉ (T – S). Which implies that x ∈ S.
Or x ∉ T.

Originally Posted by aareavis
2. S ⊂ T iff S ∩ T = S.

Proof:
If S ⊂ T, every x ∈ S is in T. That implies that every x ∈ S is in S ∩ T. This implies that S ∩ T = S.
Strictly speaking, it just implies that S ∩ T ⊇ S. The other inclusion is obvious, but at this high level of proof detail maybe it should be said explicitly.

3. ## Re: Basic Set Theory Proofs

Originally Posted by aareavis
1. S ⊂ T, then T - (T - S) = S.
If you have already studied the concept of universal set $\displaystyle U$ , the complementary $\displaystyle M^c$ of a subset $\displaystyle M\subset U$, distributive and Morgan's laws, etc you can prove the equality in another way.

Choosing as universal set any set $\displaystyle U$ such that $\displaystyle S\cup T\subset U$ (in this case for example $\displaystyle U=T$) we have $\displaystyle M-N=M\cap N^c$ for $\displaystyle M,N\subset U$ . So,

$\displaystyle T-(T-S)=T\cap (T-S)^c=T\cap (T\cap S^c)^c=T\cap (T^c\cup S)=$

$\displaystyle (T\cap T^c)\cup(T\cap S)=\emptyset \cup (T\cap S)=T\cap S=S$

4. ## Re: Basic Set Theory Proofs

Originally Posted by FernandoRevilla
If you have already studied the concept of universal set $\displaystyle U$ , the complementary $\displaystyle M^c$ of a subset $\displaystyle M\subset U$, distributive and Morgan's laws, etc you can prove the equality in another way.

Choosing as universal set any set $\displaystyle U$ such that $\displaystyle S\cup T\subset U$ (in this case for example $\displaystyle U=T$) we have $\displaystyle M-N=M\cap N^c$ for $\displaystyle M,N\subset U$ . So,

$\displaystyle T-(T-S)=T\cap (T-S)^c=T\cap (T\cap S^c)^c=T\cap (T^c\cup S)=$

$\displaystyle (T\cap T^c)\cup(T\cap S)=\emptyset \cup (T\cap S)=T\cap S=S$
I have studied the concept of a universal set (Prob & Stat). I just didn't think I could use it here. Now that I think about it, the way my book describes it is this: T - S is "the compliment of S in T" which is the same as saying T ∩ S’. (I use apostrophe instead of C. Habit from Prob & Stat.)

5. ## Re: Basic Set Theory Proofs

Originally Posted by aareavis
I have studied the concept of a universal set (Prob & Stat). I just didn't think I could use it here. Now that I think about it, the way my book describes it is this: T - S is "the compliment of S in T" which is the same as saying T ∩ S’. (I use apostrophe instead of C. Habit from Prob & Stat.)
Well, in that case you can use the alternative way I provided (if you have previously covered distributive laws, etc).