Prove the following theorem by direct proof. Theorem: For all sets $A, B,$ and $C$, if $A ∩ C ⊆ B ∩ C$ and $A ∪ C ⊆ B ∪ C,$ then $A ⊆ B$.
30065
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 :(&lt;=) 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 :(&lt;=) 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.  (&lt;=) 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.
35160
If $ b\equiv c \pmod m $ then prove that $(b,m)=(c,m)$.  My solution so far:     If $b \equiv c \pmod m$ then $c = b - sm$ for some $s$. Now if $d = (b, m)$ then $ d |  (b + s m)$.
50979
Theorem. Let $X$ denote an arbitrary set such that $|X|=n$. Then $|\mathcal P(X)|=2^n$.      Proof. The proof is by induction on the numbers of elements of $X$.      For the base case, suppose $|X|=0$. Clearly, $X=\emptyset$. But the empty set is the only subset of itself, so $|\mathcal P(X)|=1=2^0$.      Now the induction step. Suppose $|X|=n$; by the induction hypotesis, we know that $|\mathcal P(X)|=2^n$. Let $Y$ be a set with $n+1$ elements, namely $Y=X\cup\{a\}$. There are two kinds of subsets of $Y$: those that include $a$ and those that don't. The first are exactly the subsets of $X$, and there are $2^n$ of them. The latter are sets of the form $Z\cup\{a\}$, where $Z\in\mathcal P(X)$; since there are $2^n$ possible choices for $Z$, there must be exactly $2^n$ subsets of $Y$ of which $a$ is an element. Therefore $|\mathcal P(Y)|=2^n+2^n=2^{n+1}$. $\square$      From the above explanation, I don't understand why the set that contains $\{a\}$ will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$.  The construction of a new set $S$ is the union of the old set with cardinality $n$ and an new element $\{a\}$, therefore the set that do not contain $\{a\}$ still has cardinality $n$ and the set that contains $\{a\}$ is just $\{a\}$, one element...  Can someone please elucidate?
24150
Question:  Show that if $ \ A \cup B = A$ and $ \ A\cap  B = A$ then $ \ A = B$  My attempt:  Proof by contradiction:  Assume $ \ A \cup B = A$ and $ \ A\cap  B = A$ and $ \ A \neq B$   Case 1: $ \exists \ x \in A, x\notin B$  If $ x \in A \implies x\in A \cap B \implies x \in A \ and \  x\in B  \implies x\in B$, a contradiction.   Case 2: $ \exists \ x \in B, x\notin A$  If $ \ x \in B \implies x\in A \cup B \implies x\in A$, since $ \ A \cup B = A$. Contradiction.   Is this approach correct? Could someone please show me how to do a direct proof?
101960
This is a homework question of mine that Ive answered and I'd really like some feedback on my solution.       Prove or find a counter example to the claim that for all sets $A,B,C$, $$\text{if  }A\cap B=B\cap C=A\cap C=\emptyset \text{ then } A\cap B\cap C\neq \emptyset$$.   Since I can only either prove it is true, OR find a counter example I have gone with the latter because I think this statement is not true. My counter example is as follows:  Let $A = \{1,2,3 \}$ , $B = \{4,5,6 \}$ and $C = \{7,8,9 \}$. It is then clear that $A ∩ B =  B ∩ C =  A ∩ C = \emptyset$ .  If we let $x ∈ A\cap B\cap C$ then $x$ must be in $A$ and $B$ and $C$. Since this cannot be possible because there are no common elements then this implies that $A∩B∩C$ has to be equal to a null set i.e $A∩B∩C = \emptyset$ and thereby showing that (at least for this scenario) if $A \cap  B =  B \cap  C =  A \cap  C = \emptyset$ then $A\cap B\cap C = \emptyset$.  Is this okay? Any feedback will be greatly appreciated thank you!
47831
Question states:  Prove the law of double complements for sets:  If $A$ is a set and $A^\complement$ is its complement than prove that:  $$ (A^\complement)^\complement  = A$$  I started with:  $$ A^\complement = U - A$$ where U is the universal set.  But I do not understand how to go further.
4475
I am asked to prove that, if $A, B$ and $C$ are sets, then $$A-(B\cap C)=(A-B)\cap(A-C).$$  However, I think that either I have made an error in my working, or the wording of the problem contains a typographical error.    My working so far is as follows: $$\begin{align}x\in(A-(B\cap C)) &amp;\iff (x\in A)\wedge(x\not\in(B\cap C))\\ &amp;\iff(x\in A)\wedge((x\not\in B)\vee(x\not\in C))\\ &amp;\iff((x\in A)\wedge(x\not\in B))\vee((x\in A)\wedge(x\not\in C))\\ &amp;\iff(x\in(A-B))\vee(x\in(A-C))\\ &amp;\iff x\in((A-B)\cup(A-C)) \end{align}$$  First line to second line: by De Morgan's Law. Second line to third line: by distributivity of set intersection over set union. Third line to fourth line: by definitions of intersection and set difference.   If my working is correct, then I have shown that $$A-(B\cap C)=(A-B)\cup(A-C).$$ Am I correct?
32357
Let $G$ be a finite group. Suppose that $A$ and $B$ are to subsets of $G$. If $|G|&lt;|A|+|B|$ prove that $$G=AB.$$
92216
I just started Set theory And I have the following question. Suppose I have $2$ sets, $A$ and $B$. $A$ is a subset of $B$ (contained inside $B$), then the union of these $2$ sets is $B$ right $?$ If no, could you guys explain to me why, if yes, could you guys provide a simple proof.  Thank you for reading my post.
63412
Prove:  $(A\cup B) \cap C \subseteq A\cup (B\cap C)$  How could I go about proving this?
56925
Prove that if $a^2=a$ for each infinite cardinal $a$ then $b + c = bc$ for any two infinite cardinals $b,c$.   I tried $b+c=(b+c)^2=b^2+2bc+c^2=b+2bc+c$, but then I'm stuck there.
117875
I have been trying to prove the following for a while now, but I can't get to the solution:  $$(A\times C)\cup(B\times D)\subseteq(A\cup B)\times(C\cup D)$$  Can anyone help me?
82869
A set $M = \{1,2,\ldots,100\}$ is divided into seven subsets with no number in $2$ or more subsets. How do you prove that one subset either contains four numbers $a$, $b$, $c$, and $d$ such that $$a + b = c + d$$ or three numbers $p$, $q$, and $r$ such that $$p + q = 2r\,?$$ I am having some issues with this question whether I don't fully understand the question or my arithmetic is wrong. Grateful for any help.
118531
I got the answer as the set $\{5x + 1 : x \in \mathbb{N} ∪ \{0\} \}$. Can anyone confirm if this is correct? Thanks.
74091
Problem: Show that if $(b,c)=1$, then for any integer $a$ we have $(a,bc)=(a,b)(a,c)$. [Hint: Prove that each member of the alleged equation divides the other.]  This is the way I proved it (without the hint): $(a,b)(a,c)=(a(a,b),c(a,b))=(a^2,ab,ac,bc)=(a^2,bc,a(b,c))=(a^2,a,bc)=((a^2,a),bc)=(a,bc)$  But how should I prove it using that hint or at least a similar proof.
91065
I am trying to prove that if $A – C = B – C$ and $A\cap C = B\cap C$ then $A = B$. I have tried using Venn Diagrams as a proof technique, but we are not able to use proof by Venn Diagrams.
154
I need to prove the following letting A and B be subsets of a universal set U. $$A\cup B = U \iff A^c\subset B$$ It just isn't straight forward to me.