1

Can you verify my proof if it is right?

Let $A$ and $B$ be sets. (a) Show that $A$ is a subset of $B$ if and only if for any set $C$, one has $A$ union $C$ is a subset of $B$ union $C$. (b) Show that $A$ is a subset of $B$ if and only if for any set $C$, one has $A$ intersect $C$ is a subset of $B$ intersect $C$.

Edited Solution :

(a) (=>) Given A is a subset of B, this implies A U B = B. Given a set C, A U B U C = B U C. Since A is a subset of B, this implies A U C is a subset of B U C. Solution 1 :(<=) Given A U C is a subset of B U C , For A U C , x is a member of A U C . For B U C, x is a member of B U C. Suppose x is a member of A but not a member of B, meaning A is not a subset of B. Therefore , A U C is not a subset of B U C. Hence, A must be a subset of B. Solution 2 :(<=) Given A U C is a subset of B U C, For A U C, x is a member of A U C and for B U C, x is a member of B U C. Suppose C is a disjoint set. Since A U C is a subset of B U C, it follows that A is a subset of B.

(b) (=>) Since A is a subset of B , it follows that A U B = B. [A intersect C] is a subset of A and [B intersect C ] is a subset of B by definition of intersection. Let x be member of A and member of C. Since [ A intersect C ] is a subset of A, x must be in A. Let x be a member of B and member of C. Since [ B intersect C ] is a subset of B, x must be in B. Therefore, A intersect C is a subset of B intersect C.

(<=) Since A intersect C is a subset of B intersect C, suppose we let Set C be a subset of B and a subset of A as well. C is a subset of A implies A intersect C is equals to C. C is a subset of B implies B intersect C is equals to C as well. Since A intersect C is equals to B intersect C, A is a subset of B.

frosh
  • 1,300
Joe
  • 143
  • 1
    I take you mean intersect not 'intercept'. Also I need to admit I have not read the whole proof but what are you really asking? Do you want us to verify the proof? Or you think something is wrong? – Jack Yoon Sep 08 '14 at 14:57
  • The proof of the second half of (a) is not correct : "Since A union C is a subset of B union C , i conclude that A is a subset of B" is what you have to prove ... You have only proved that : if "x is a member of A or x is a member of C", then "x is a member of B or x is a member of C". – Mauro ALLEGRANZA Sep 08 '14 at 15:22
  • if x is a member of A or x is a member of C, i can take x is a member of A and show that it is a subset of A union C right? The same goes for x is a member of B being a subset of B union C. Thus since A union C is a subset of B union C, therefore A is a subset of B. – Joe Sep 08 '14 at 15:27
  • We have to facts : (i) if x is a member of A or x is a member of C, i can take x is a member of A and show that it is a subset of A union C, and it is right. Then, form this we have that : (ii) x is a member of B union C (by the inclusion $A \cup C \subseteq B \cup C$). But how we conclude with $A \subseteq B$? To do this we have to pick $x \in A$ and show that $x \in B$. – Mauro ALLEGRANZA Sep 08 '14 at 15:35
  • How do i show x is a member of A is also a member of B? – Joe Sep 08 '14 at 15:37
  • Hi mauro, if it x is a member of A , x is a member of B as well? – Joe Sep 08 '14 at 15:46
  • (a) (=>) is Ok, but I should "streamline" it a little bit : A is a subset of B, this implies $A \cup B = B$ : fine. But $B \subseteq B \cup C$, and it is enough to conclude with : $A \cup B = B \subseteq B \cup C$. – Mauro ALLEGRANZA Sep 09 '14 at 07:12
  • For (a) : Solution 1 :(<=) and Solution 2 :(<=) , I assume that they are two different proof; the 2nd one does not seem correct to me ; what does it mean "C is a disjoint set" ? – Mauro ALLEGRANZA Sep 09 '14 at 07:15
  • Regarding (a) Solution 1 :(<=) you suppose that x is a member of A but not a member of B, and you conclude with : "Therefore , A U C is not a subset of B U C. Hence, A must be a subset of B." But it is possible that $x \in A$ and $x \notin B$ but still $x \in C$. In this case $x \in B \cup C$, and it is not true that "A U C is not a subset of B U C" ... – Mauro ALLEGRANZA Sep 09 '14 at 07:18
  • Whether your proof is correct or not, it is far too long for such a simple result .If something holds for all C, examine a particular case. $(\forall C(A\cup C\subset B\cup C))\to (A=A\cup \not 0\subset B\cup \not 0=B.$ For the other direction, $A\subset B\to B=A\cup (B\backslash A)\to \forall C(A\cup C\subset (A\cup C)\cup ((B\backslash A)\cup C)=((A\cup (B\backslash A))\cup C=B\cup C.$ – DanielWainfleet Jan 05 '16 at 23:26

3 Answers3

1

Let me analyze your proof attempt, and provide some hints for correction.

What i did for (a) was :

Since A is a subset of B, (=>)

x is a member of A , x is a member of B. Therefore, since x is a member of A, x is a member of A union C as well. Since x is a member of B as well, x is a member of B union C. I conclude that A union C is a subset of B union C.

What you've done here is to show that an arbitrary element of $A$ must also be an element of $B\cup C.$ This is true, but it only shows that if $A\subseteq B,$ then for any set $C$ we have $A\subseteq B\cup C.$ This isn't what you want to show, or at least, isn't all of it. Instead, start with some $x\in A\cup C,$ and show that it must be in $B\cup C.$ If $x\in A,$ then by your reasoning, we have $x\in B\cup C,$ but what if $x\notin A$?

Since A union C is a subset of B union C, (<=)

For A union C , x is a member of A or x is a member of C.

Take x is a member of A. A is a subset of A union C. (By definition of union)

For B union C, x is a member of B or x is a member of C.

Take x is a member of B. B is a subset of B union C. (By definition of union)

Since A union C is a subset of B union C , i conclude that A is a subset of B.

You want to take an arbitrary $x\in A,$ and show that $x\in B.$ Now, it's true that we can conclude that $x\in A\cup C$ for every set $C,$ and so $x\in B\cup C$ for every set $C.$ But why does this let us conclude that $x\in B$? Can you think of any particular sets $C$ that let us make this leap?

What i did for part (b) was :

Since A is a subset of B, (=>)

x is a member of A , x is a member of B. Therefore since x is a member of A, x is a member of A intersect C. Since x is a member of B as well, x is a member of B intersect C. Therefore, i conclude that A intersect C is a subset of B intersect C.

Your first mistake in reasoning happens when you conclude that since $x\in A,$ then $x\in A\cap C.$ This need not be true for every set $C.$ In fact, there are many sets $C$ for which it isn't true. Likewise, in general, an element of $B$ need not be an element of $B\cap C.$ More than that, though, you're starting from the wrong place. You want to show that $A\cap C\subseteq B\cap C$ for every set $C.$ To do this, you should start with an arbitrary set $C,$ and an arbitrary element $x$ of $A\cap C,$ then show that $x\in B\cap C.$ This is pretty straightforward. See what you can do.

Since A intersect C is a subset of B intersect C, (<=)

For A intersect C, x is a member of A and x is a member of C as well. Therefore A intersect C is a subset of A. (By definition of intersection) For B intersect C, x is a member of B and x is a member of C as well. Therefore B intersect C is a subset of B. (By definition of intersection)

Since A intersect C is a subset of B intersect C, i conclude that A is a subset of B.

So far, you've noted that $A\cap C\subseteq A$ and $B\cap C\subseteq B$ for any set $C.$ While true, this isn't helpful. You'd like to show that $A\subseteq B,$ which means we need to start with some $x\in A$ and show that $x\in B.$ But all you know is that for any set $C,$ we have $A\cap C\subseteq B\cap C.$ This part may be the trickiest. The idea here is to find a set $C$ such that $A\cap C=A$ and $B\cap C=B.$ Once you've found such a set, the rest is very straightforward. Try using Venn diagrams to figure out a set $C$ that works. Do you know how to use Venn diagrams to find intersections and unions?


Added:

Your second attempt shows more promise, but there are still some issues.

(a) (=>) Given A is a subset of B, this implies A U B = B.

True, but why? Have you already proved this?

Given a set C, A U B U C = B U C.

Again, this is true, but why?

Since A is a subset of B, this implies A U C is a subset of B U C.

But this is what you should be proving, and you haven't actually finished the job. You're on your way, though. Try to justify the following inclusions and equalities: $$A\cup C\subseteq (A\cup C)\cup B=A\cup B\cup C=B\cup C.$$

Solution 1 :(<=) Given A U C is a subset of B U C. For A U C, x is a member of A U C . For B U C, x is a member of B U C.

I'm not entirely sure what the last two sentences are supposed to mean, here. Do you mean that you choose $x$ to be a member of $A\cup C,$ from which it follows by the given condition that $x\in B\cup C$? Remember, though, that you're trying to show that $A\subseteq B.$ So, instead, you should let $x$ be an arbitrary member of $A,$ and try to show that $x\in B$ by choosing $C$ carefully.

Suppose x is a member of A but not a member of B, meaning A is not a subset of B. Therefore , A U C is not a subset of B U C. Hence, A must be a subset of B.

Here, you have a good setup for a proof by contradiction, but you don't actually follow through with it. Your contradictory conclusion doesn't actually follow. Consider $A=C=\{1\},$ $B=\emptyset.$ That's an instance where we can have $A\nsubseteq B,$ but still have $A\cup C\subseteq B\cup C.$ Your second approach shows more promise.

Solution 2 :(<=) Given A U C is a subset of B U C, For A U C, x is a member of A U C and for B U C, x is a member of B U C.

Again, not sure what this means.

Suppose C is a disjoint set.

You may have the right idea here. Disjoint from what?

Since A U C is a subset of B U C, it follows that A is a subset of B.

Depending on what you mean above, this may well work. Still, it's a good idea to actually justify it, rather than just saying "it follows." Textbooks will often just say "it follows," and leave the details to the reader, but it's a bad personal practice.

(b) (=>) Since A is a subset of B , it follows that A U B = B. [A intersect C] is a subset of A and [B intersect C ] is a subset of B by definition of intersection. Let x be member of A and member of C. Since [ A intersect C ] is a subset of A, x must be in A.

You're off to a great start!

Let x be a member of B and member of C.

Oh, no! This is what you're trying to show. You can't just declare it. However, you're on your way, if somewhat awkwardly. Instead, start with some $x\in A\cap C.$ By definition of intersection, we have $x\in A$ and $x\in C.$ Since $x\in A$ and $A\subseteq B,$ then $x\in B.$ Since $x\in B$ and $x\in C,$ then $x\in B\cap C.$ Since $x$ was an arbitrary member of $A\cap C,$ then we have $A\cap C\subseteq B\cap C,$ and since $C$ was an arbitrary set, then this is true for any set $C.$

(<=) Since A intersect C is a subset of B intersect C, suppose we let Set C be a subset of B and a subset of A as well.

You've almost got the right idea, here. Instead, let $C$ be a superset of $B$ and a superset of $A$, and see if you can take it from there. Can you think of any examples of such a set $C$?

C is a subset of A implies A intersect C is equals to C. C is a subset of B implies B intersect C is equals to C as well.

Both of these are very true.

Since A intersect C is equals to B intersect C, A is a subset of B.

Uh oh! This doesn't follow. Consider $A=\{1\},$ $B=\{2\},$ and $C=\emptyset.$ We can certainly see that $A\cap C=B\cap C=C,$ but we don't have $A\subseteq B.$

Cameron Buie
  • 102,994
  • Yes , i do. Really thank you for the paragraph by paragraph analysis, i will post my revamped solution again later. Will you verify my proof later on? :) A big thank you again! – Joe Sep 08 '14 at 16:07
  • I will be glad to take a look at your altered proof later. Please leave a comment on this answer to let me know when it is posted. Good luck! – Cameron Buie Sep 08 '14 at 16:09
  • thanks again i am going to sap my brain on this question haha! I am glad for your hint! – Joe Sep 08 '14 at 16:19
  • Hi, proving by contradiction stating A is not a subset of B is it a good way? – Joe Sep 08 '14 at 16:55
  • For which part? – Cameron Buie Sep 08 '14 at 17:25
  • for (a) solution 1 (<=) – Joe Sep 08 '14 at 17:33
  • Hi there, i am done! Hopefully i have a better solution this time! :) – Joe Sep 08 '14 at 18:40
  • Proof by contradiction can work just fine, but you'll need to choose $C$ carefully either way. I've looked at your new proof attempt. You've made several improvements, but you're not quite there, yet. Take a look at my updated answer, and let me know if you have any questions. By the way, instead of replacing your old answers, you should just make a note that you've added an updated attempt. For example, **Proof Attempt 2** will render as Proof Attempt 2, and *** will insert a dividing line between sections, like you see before "Added" in my answer. – Cameron Buie Sep 09 '14 at 13:52
0

For the second let x be in A , since for any set C , AUC is subset of BUC we can take C as the complement of the single element set containing x then it follows that x must be in B

0

Just for comparison, here is a different style proof that I find simpler to design and simpler to follow. You are asked to prove that for any $\;A,B\;$, $$ A \subseteq B \;\equiv\; \langle \forall C :: A \cup C \subseteq B \cup C \rangle $$


$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Tag}[1]{\text{(#1)}} $Starting at the most complex side, expanding the definitions, and simplifying gives us, for any $\;A,B\;$, $$\calc \langle \forall C :: A \cup C \;\subseteq\; B \cup C \rangle \calcop\equiv{definitions of $\;\subseteq\;$ and of $\;\cup\;$ twice} \langle \forall C, x :: x \in A \lor x \in C \;\Rightarrow\; x \in B \lor x \in C \rangle \calcop\equiv{logic: $\;P \Rightarrow Q\;$ to $\;\lnot P \lor Q\;$ for easier manipulation; DeMorgan} \langle \forall C, x :: (x \not\in A \land x \not\in C) \lor x \in B \lor x \in C \rangle \calcop\equiv{logic: simplify using negation of $\;x \in C\;$ on other side of $\;\lor\;$} \langle \forall C, x :: x \not\in A \lor x \in B \lor x \in C \rangle \calcop\equiv{logic: move $\;\forall C\;$ to the only place where it is actually used} \langle \forall x :: x \not\in A \lor x \in B \lor \langle \forall C :: x \in C \rangle \rangle \calcop{\tag{*}\equiv}{set theory: no $\;x\;$ is in all $\;C\;$: take $\;C := \emptyset\;$; simplify} \langle \forall x :: x \not\in A \lor x \in B\rangle \calcop\equiv{logic: write $\;\lnot P \lor Q\;$ as $\;P \Rightarrow Q\;$; definition of $\;\subseteq\;$} A \subseteq B \endcalc$$


The crucial step $\Tag{*}$ here is that $\;\langle \forall C :: x \in C \rangle\;$ is false, since it is false for $\;C := \emptyset\;$.

Note how there was no need for proving both directions separately.