Set Theory

[Cyborg31]

Homework Statement

1. Provide a counterexample to the following conjecture:

For sets $$A, B,$$ $$C \subseteq U$$ if A is a subset of B but B is not a subset of C, then A is not a subset of C

2. $$(A\cap B) \cup C = (A \cap (B \cup C))$$ if and only if $$C \subseteq A$$

3. Prove $$(A - B) - C = (A - C) - (B - C)$$

Homework Equations

The Attempt at a Solution

1. Would it work if I say "If $$\bar{A}\notin U$$ then $$A\subseteq U$$ and thus $$A \subseteq C$$" ?

2. Not sure.

3. $$(A \cap \bar{B}) \cap \bar{C} = (A \cap \bar{C}) - (B \cap \bar{C})$$
$$(A \cap \bar{B}) \cap \bar{C} = (A \cap \bar{C}) \cap \bar{(B \cap \bar{C})}$$
$$(A \cap \bar{C}) \cap (\bar{B} \cap \bar{C}) = (A \cap \bar{C}) \cap \bar{(B \cap \bar{C})}$$

I'm not sure if this is right though. Can't figure out the rest of this part.

 

[CompuChip]

1. No it wouldn't. First of all, you haven't said what $\overline{A}$ means (is it complement?). Second of all, I assume that's a set, so $\overline{A} \not\in U$ doesn't make sense (did you mean $\not\subset$?). Actually the question is quite easy, try to make a picture. You can construct a counterexample by for example looking at subsets of the natural numbers (e.g. $$A = \{0, 1, 2, 3\}, B = \{3, 5\} \cup \{ \text{ even numbers } \}, C = \mathbb{N}$$).

For 2, it might help to draw a diagram again.

For a statement like 3, generally one takes an element in the left hand side and shows that it is also in the set on the right hand side and conversely to show that the LHS is contained in the RHS and vice versa.

 

[HallsofIvy]

Homework Statement

1. Provide a counterexample to the following conjecture:

For sets $$A, B,$$ $$C \subseteq U$$ if A is a subset of B but B is not a subset of C, then A is not a subset of C

2. $$(A\cap B) \cup C = (A \cap (B \cup C))$$ if and only if $$C \subseteq A$$

3. Prove $$(A - B) - C = (A - C) - (B - C)$$

Homework Equations

The Attempt at a Solution

1. Would it work if I say "If $$\bar{A}\notin U$$ then $$A\subseteq U$$ and thus $$A \subseteq C$$" ?

Actually, that makes no sense at all. You are given that U is the universal set so both A and $\bar{A}$ are subsets of U. That has nothing to do with $\bar{A}$ being a member of U. In any case, you are only asked to give a counterexample. Suppose B= {a,b,c,d,e,f}, C= {d,e,f,g, i, j}. Can you find A that is a both a subset of B and a subset of C?

2. Not sure.

Well, I'll give you a start. (2) says, "$$(A\cap B) \cup C = (A \cap (B \cup C))$$ if and only if $$C \subseteq A$$
That is an "if and only if" statement so you need to prove 2 things:
a) If $$(A\cap B) \cup C = (A \cap (B \cup C))$$ then $$C \subseteq A$$

b) If $$C \subseteq A$$ then (A\cap B) \cup C = (A \cap (B \cup C))[/tex]
and the standard way to prove "$A= B$" is to say "If $a\in A$" and show that $a\in B$. That is, assuming that a satisfies whatever conditions define A, show that it must satisfy whatever conditions satisfy B.

To show $$C \subseteq A$$, start by saying "if $x \in C$ and use the fact that $$](A\cap B) \cup C = (A \cap (B \cup C))$$ to show $x \in A$.

To show $$A \subseteq C$$, start by saying "if $x \in A$ and use the fact that $$](A\cap B) \cup C = (A \cap (B \cup C))$$ to show $x \in C$.

Then do it the other way around.

3. $$(A \cap \bar{B}) \cap \bar{C} = (A \cap \bar{C}) - (B \cap \bar{C})$$
$$(A \cap \bar{B}) \cap \bar{C} = (A \cap \bar{C}) \cap \bar{(B \cap \bar{C})}$$
$$(A \cap \bar{C}) \cap (\bar{B} \cap \bar{C}) = (A \cap \bar{C}) \cap \bar{(B \cap \bar{C})}$$

I'm not sure if this is right though. Can't figure out the rest of this part.

Same thing. Don't write set operations like that. Start by saying "if $$x \in (A- B)- C$$ and then show that [tex]x \in (A- C)- (B- C)[/itex]. Using the definitions of those set operations, of course.

 

[matt grime]

Those seem like very complicated examples for 1).

Let's "just do it". A is a subset of B. OK, so let A={a}, and let B=A. Does that work? No.

We're going to have to make B bigger. How about B={a,b}. Now I need to find a C which contains A, and doesn't contain B. Well, that's easy: C=A.

I also think the advice for 2) is overly long. We are surely allowed to use the identity

(A n B) u C = (A u C) n (B u C)

which makes one direction trivial.

Now, what does it mean for C not to be a subset of A? It means that there is a c in C that is not in A. Which proves the other direction.

 

[Cyborg31]

Would A = {3, 4}, B= {0,1,2,3,4}, C= {3,4,5,6,7} work as a counter example in 1? So you can assume that they're proper subsets even if the questions don't mention it?

I thought the difference between $$A\subseteq B$$ and $$A\subset B$$ would be that the latter is a proper subset and the former is a subset AND is equal and thus would make $$B\subseteq A$$ true as well. So even if you use this sign $$A\subseteq B$$ it's not necessarily true that they're also equal?

For 3, would $$x \in (A-B) \wedge x \notin C$$ => $$x \in (x \in A \wedge x\notin B) \wedge \notin C$$ therefore x is an element of (A-B) and not C, then x is an element of A and not B.

$$x \in (A- C) \wedge x \notin (B-C)$$ => $$x \in (x \in A \wedge x \notin C) \wedge x \notin (B-C)$$ therefore x is an element of (A-C) and not (B-C), then x is an element of A and not C.

...be correct?

Thanks.

 

[HallsofIvy]

If A and B were necessarily equal then you would write A= B! If A and B were necessarily not equal, then you would write $$A\subset B$$. $$A\subseteq B$$ means that A may be equal to B or may just be a subset.

 

[Cyborg31]

Well, I'll give you a start. (2) says, "$$(A\cap B) \cup C = (A \cap (B \cup C))$$ if and only if $$C \subseteq A$$
That is an "if and only if" statement so you need to prove 2 things:
a) If $$(A\cap B) \cup C = (A \cap (B \cup C))$$ then $$C \subseteq A$$

b) If $$C \subseteq A$$ then (A\cap B) \cup C = (A \cap (B \cup C))[/tex]
and the standard way to prove "$A= B$" is to say "If $a\in A$" and show that $a\in B$. That is, assuming that a satisfies whatever conditions define A, show that it must satisfy whatever conditions satisfy B.

To show $$C \subseteq A$$, start by saying "if $x \in C$ and use the fact that $$](A\cap B) \cup C = (A \cap (B \cup C))$$ to show $x \in A$.

To show $$A \subseteq C$$, start by saying "if $x \in A$ and use the fact that $$](A\cap B) \cup C = (A \cap (B \cup C))$$ to show $x \in C$.

Then do it the other way around.

Do I have to show that $x \in C$ first for $$(A\cap B) \cup C$$ then show $x \in C$ for $$(A \cap (B \cup C))$$ ?

 

[CompuChip]

Sometimes the notation $A \subset B$ is also used for "A is either a proper subset of B, or A and B are equal" and "A is a proper subset of B, they are not equal" is explicitly written as $A \subsetneq B$. It depends on the author (and most authors will -- and all of them should -- explain their conventions somewhere at the start).

 

[Cyborg31]

Can I prove #2 by saying $x \in C$ then by $(A \cap B) \cup C$, $x \in (A \cap B)$ so if $x \in (A \cap B)$ then $x \in A$ therefore since $x \in C$ and $x \in A$, $C \subseteq A$

If $x \in A$ then by $A \cap (B \cup C)$, $x \in A$ and $x \in B$ or $x \in C$ therefore since $x \in A$ and $x \in C$, $A \subseteq C$

 

[CompuChip]

I don't quite see what you proved. You have to show that:
If $C \subseteq A$ then $(A \cap B) \cup C = A \cap (B \cup C)$ --- so if $C \subseteq A$ then $x \in (A \cap B) \cup C \implies x \in A \cap (B \cup C)$ and $x \in A \cap (B \cup C) \implies x \in (A \cap B) \cup C$

And you have to show that if $(A \cap B) \cup C = A \cap (B \cup C)$, then $x \in C$ implies $x \in A$ (the other way around is not needed, and might not even be true).

 

[Cyborg31]

So if x is an element of $(A \cap B) \cup C$ then it's implied that x is an element of $A \cap (B \cup C)$ and vice versa? Does this need any transformations or is it just like that?

And for the second part of your message, didn't what I write prove it? If x is an element of C, then by Union of (A n B) u C, x is also an element of (A n B) and from that, x is an element of A and B therefore x is an element of A and thus $x \in C$ implies $x \in A$ right? But then, I'm not sure how to work the A n (B u C) into it.

 

[HallsofIvy]

Can I prove #2 by saying $x \in C$ then by $(A \cap B) \cup C$, $x \in (A \cap B)$ so if $x \in (A \cap B)$ then $x \in A$ therefore since $x \in C$ and $x \in A$, $C \subseteq A$

If $x \in A$ then by $A \cap (B \cup C)$, $x \in A$ and $x \in B$ or $x \in C$ therefore since $x \in A$ and $x \in C$, $A \subseteq C$

If x is contained in B or C it does not follow that x is contained in C!

 

[HallsofIvy]

So if x is an element of $(A \cap B) \cup C$ then it's implied that x is an element of $A \cap (B \cup C)$ and vice versa? Does this need any transformations or is it just like that?

No, no one said anything like that. If x is an element of $(A\cap B)\cup C$ then x is an element of $A\cap B$ or x is a member of C. For example, suppose A= {a, b}, B= {b, c} and C= {p, q}. Then [tex]A\cap B[/itex]= {b} and so $$(A\cap B)\cup C}$$= {b, p, q}. If x= p or x= q, then it is true that x is an element of $(A\cap B)\ cup C$ but x is not an element of $A \cap (B \cup C)$ .

And for the second part of your message, didn't what I write prove it? If x is an element of C, then by Union of (A n B) u C, x is also an element of (A n B) and from that, x is an element of A and B therefore x is an element of A and thus $x \in C$ implies $x \in A$ right? But then, I'm not sure how to work the A n (B u C) into it.

I have know idea what you mean by "by Union of $(A\cap B)\cup C$". Are you clear on the definitions of "union" and "intersection"? If x is a member of C, then, yes, it is a member of $(A\cap B)\cup C$ but that tells you nothing at all about whether x is or is not a member of $A\cap B$.
I think you need to go back and review the definitions.

 

[Cyborg31]

Uh ok, if x is an element of C then by the Union of (A n B) u C, x is an element of (A n B) u C but not necessarily an element of (A n B)...

Then how do I prove that x is an element of (A n B)?

The book doesn't show this type of question so I'm stumped. Also, I'm not sure how A n (B u C) plays into this for the whole proof.

If x is an element of C then by the Union of (B u C), x is an element of (B u C). But Intersection of A and (B u C) only works if x is an element of A...

 

[HallsofIvy]

Uh ok, if x is an element of C then by the Union of (A n B) u C,

You mean by definition of ...

x is an element of (A n B) u C but not necessarily an element of (A n B)...

Then how do I prove that x is an element of (A n B)?

Unless you have additional information you don't- it's not necessarily true. What information do you have about A, B, and C?

The book doesn't show this type of question so I'm stumped. Also, I'm not sure how A n (B u C) plays into this for the whole proof.

If x is an element of C then by the Union of (B u C), x is an element of (B u C). But Intersection of A and (B u C) only works if x is an element of A...

You are getting yourself confused. In order to prove $$C \subseteq A$$, yes you should start with "if x is a member of C". Now use the fact that $$(A\cap B) \cup C = (A \cap (B \cup C))$$. If x is in C, then it is in $$(A\cap B)\cup C$$ which mean it is in $$(A\cap (B\cup C))$$ (because they are equal) which, in turn, means x is in ?

 

[Cyborg31]

Because of the brackets, x element of C and by the Union of (A n B) and C, x is an element of (A n B) u C.

(A n (B u C)), has the brackets shifted over. So if x element of C, Union of C and B means x element of (B u C). I know x element of (B u C) but not A, but by the definition of Intersection, x is an element of two intersected sets only if it were in the separate sets to begin with. So I can only know x is an element of (A n (B u C)) if x is an element of A and (B u C), and I do know it is in the latter.

And that's exactly what I'm trying to find out, x an element of A so I'm not sure how the two clauses are equal.

Or is x an element of (A n (B u C)) because the brackets enclose the whole thing?

Hmm, either way I know that x is an element of a combined set (set C with the other sets), but how does one show that x is an element of an individual set, i.e. set A?

Thanks for your help.

 

[matt grime]

2. $$(A\cap B) \cup C = (A \cap (B \cup C))$$ if and only if $$C \subseteq A$$

Look, this really is trivial, and shouldn't have taken this long.

We know that $(A\cap B)\cup C)=(A\cup C)\cap (B\cup C)$, so that is one direction proved. Do you see that? Conversely, if A is not a subset of C....