Proving Set Theory Statements: A Guide for Beginners

[mrsmith]

I've been working on these problems and unfortunately i can't make heads or tails of these two.
Any insight where to start the proof would be great.

1)Let A, B and C be sets. Show that if A~B⊆C, then A~C⊆B holds.
What I got so far:

Is it correct to state that A~B = A⋂B' and A~C = A⋂C'
and my target goal should be to prove that A⋂B'⊆A⋂C' and A⋂C'⊆A⋂B'?


2)If A and B are two non-empty subsets (of the same universe U), then A⋂B≠∅ or B⊆A'.

This i just don't understand how to start a proof of that. Its an OR statement does it suffice to say either condition is true? Doesnt seem much of a proof is you could simply state:

Since A and B are non-empty there are elements in it... namely x which belongs to A and B thus A⋂B≠∅

or

there is an x that belongs to B and B is a subset of A' which A' is U~A, since B is in U then B is a subset of A'

is it that simple or am i missing something? Many thanks

 

[CompuChip]

I don't think you are using standard notation (although there are many different ones for set theory). What does the wiggly thing mean? Does A ~ B mean: "A without B"?

In that case I wouldn't rewrite the first one, but just start a standard proof:
Assume that $A \setminus B \subseteq C$. Let $x \in A \setminus C$, try to talk x into C. Drawing a picture might help.

Similarly for the second one, you can assume that the intersection is empty and then show that indeed $B \subseteq A^C$ by letting $x \in B$ and showing that $x \in A^C$. To get you started, let me write down the first two lines:

Proof: Let A, B be two non-empty subsets. If they have an element in common, $A \cap B \neq \emptyset$ and we are done. So let's assume that $A \cap B = \emptyset$. Let $x \in B$ be any element of B (such an element exists, because B is non-empty). [... fill in some details here yourself ...] therefore, $x \in A^C$. Since x was arbitrary, we have $\forall x \in B, x \in A^C$, in other words, $B \subset A^C$. Therefore, either A⋂B≠∅ or B⊆A'.

Note that

Since A and B are non-empty there are elements in it... namely x which belongs to A and B thus A⋂B≠∅

is not true: if I take the universe to be all natural numbers and I take A = {1, 2, 3} and B = {12, 13, 14} then they are both non-empty but there is no element which is in both. (However, the complement of A is A' = { n natural number | n > 3 } so B is indeed contained in it).

 

[mrsmith]

I don't think you are using standard notation (although there are many different ones for set theory). What does the wiggly thing mean? Does A ~ B mean: "A without B"?

Yes that's correct.

In that case I wouldn't rewrite the first one, but just start a standard proof:
Assume that $A \setminus B \subseteq C$. Let $x \in A \setminus C$, try to talk x into C. Drawing a picture might help.

thats the issue I'm having, I don't know how to proceed from here. It really doesn't make sense to me. Unfortunately the only things we went through in class was one step equavilence examples such as proof of de'morgan's law.

This is totaly different and new to me and can't understand how to put these two together. If there was an example, I could probably get an idea of how to do it, but without a starting point, I am a bit lost.

Thanks for the help.

 

[CompuChip]

I see that I screwed up some letters ($x \in A - C \implies x \in C$ is nonsense of course).

It's usually just a matter of splitting things up until you can draw conclusions about membership of single sets, and then putting it back together in the correct order again.

For example, suppose you want to prove that if A~B⊆C, then A~C⊆B holds.
So suppose you have $x \in A \setminus C$. You can split this into: $x \in A$ and $x \not\in C$. Somehow, you have to talk it into B. So we know it is in A, it's not in C and we want to say something about the membership of B.

For this you will have to use the given information. The given information is: if $y \in A \setminus B$ -- that is: if $y \in A$ but $y \not\in B$ -- then $y \in C$. Do you see how you can do this? (Hint: you want x to be in B. What would happen if $x \not\in B$?)By the way, did you learn about Venn diagrams? It might help drawing the pictures to check if it's true at all.

 

[mrsmith]

I see that I screwed up some letters ($x \in A - C \implies x \in C$ is nonsense of course).

It's usually just a matter of splitting things up until you can draw conclusions about membership of single sets, and then putting it back together in the correct order again.

For example, suppose you want to prove that if A~B⊆C, then A~C⊆B holds.
So suppose you have $x \in A \setminus C$. You can split this into: $x \in A$ and $x \not\in C$. Somehow, you have to talk it into B. So we know it is in A, it's not in C and we want to say something about the membership of B.

For this you will have to use the given information. The given information is: if $y \in A \setminus B$ -- that is: if $y \in A$ but $y \not\in B$ -- then $y \in C$. Do you see how you can do this? (Hint: you want x to be in B. What would happen if $x \not\in B$?)By the way, did you learn about Venn diagrams? It might help drawing the pictures to check if it's true at all.

Learned of the diagrams but it didnt seem to help me much. Unfortunately its been about 15 years (i just recently went back to school to pursue a new degree) and this is just an introductory course of mathematical proofs.

I guess what I fail to see is the actual relationship between these two statements.

I see how statements as individual facts. So based on your comments I already know that A-C is just A and C' or just x is in A and x is not in C. But the very logic just fails me how to relate it back to A~B⊆C.

Here is my second attempt at this:

let x be an element in (A-B), then x is in A but Not in B.

so there exists an x such that {x belongs in A and x does not belong in B therefore x belongs in C}

A-B⊆C implies that x has to be in C

If x is in A-C, then x is in A but not in C.

Here is where I get stuck... I had someone else advice me that this is
Due to the first statement, x is not in A or x is in B. But since x was taken from A thus x is in B.

I don't understand this logic. How can this be?

Thanks again you've been a great help.

 

[mrsmith]

Yet another attempt:

I guess you have to start with the statement you want to prove first and use the given as you said.

So based on that:

if x in (A-C) then x is in A and x is not in C
then x in A

if x was not in B which just the compliment of B we can say that it also can be in the set (A-B)

but by the given A-B ⊆ C

It states that it should be in C, but based on the part we want to prove its not the case.

So does this make a valid argument that x is in B? Thus conclude
A~C⊆B holds?

 

[CompuChip]

The second attempt is almost correct. Indeed, assuming x is in B', you can show that it is both in C and it is not. That's a contradiction, so it is not in B' (therefore, it is in B), etc.
Just a basic proof by contradiction.

You've found it