The expressions are part of the proofs of the expressions $M\setminus (N \cup P) = (M \setminus N) \cap  ( (M\setminus P) \text{ and } M\setminus (N ∩ P) = (M \setminus N) \cup  ( (M\setminus P)$. So when I was trying to prove the first one I thought $\{x \mid x \in M  \text{ and } x \notin N \cup P\}$ would be expressed as  $\{x \mid x ∈ M \text{ and } x \notin N  \text{ or } x ∈ M  \text{ and } x \notin P\}$ as the "and" from the intersection would distribute over the "or" from the union. Yet to prove the equality, it should be $\{x \mid x \in M  \text{ and } x \notin N  \text{ and } x \in M  \text{ and } x \notin P\}$ so that the equality holds until last step. For the second example just change the middle "and" with "or". Again I thought it should have been "and" as "and"s have associativity. I can simply memorize it and use it this way whenever a similar proof comes. Yet, I would be more than happy if someone tells me the reason behind this expressions, so that I see what's going on.   Edit: My question has been identified as a possible duplicate of Proving DeMorgan's Theorem. First of all, my problem is not about proving the entire theorem. I actually have the proof in front of me. It is about a proof step I couldn't internalize. In the linked question there is limited mention of that specific step except for the fact that it is taken for granted as in the proof in front of me now (so again after reading the question and answers, I am at where I was before). I want an explanation of that step specifically and my question is about that step not a whole proof. Moreover, although I have to admit that my question depicts a step on proving DeMorgan's theorem, in this case M is not fixed as a universe and difference relation is not absolute but relative. As such the equalities can be thought of displaying properties of set difference as well. After I understand these relative difference properties (including a third one) and the specific steps I mentioned in my question, I want to continue with DeMorgan. As such I would appreciate help on a topic that is a step in moving to a more advanced topic and a question on a minor detail rather than the proof of a whole theorem.
122574
I'm trying to prove that (without using logical equivalencies):  $\overline{A\cap B} = \bar A \cup \bar B$  by proving both sides:  (1) $ x \in \overline{A\cap B} \to x \in \bar A\cup\bar B$  (2) $ x \in \bar A\cup\bar B \to x \in \overline{A\cap B}$  I figured out the 2nd part, but I'm struggling with the first. The only thing I'm confident about now is:  Let $x \in \overline{A\cap B}$. We prove that $x \in \bar A\cup \bar B$. By definition of complement, $x \not\in A\cap B$.  I'm not sure if I should use cases, or if I should prove by contradictions. With the other variation of DeMorgan's, I could assume $x \in A$ and $x \in B$ and they would lead to contradictions with the first assumption, but I can't do that here because it's a $\cap$ instead of a $\cup$.  For reference, here's the proof I was given for the other variation of DeMorgan's:  Prove: $\overline{A \cup B} = \bar A \cap \bar B$  (1) if $x \in \overline{A \cup B}$ then $x \in \bar A \cap \bar B$  (2) if $x \in \bar A \cap \bar B$ then $x \in \overline{A \cup B}$  Proof:  (1)Let $x \in \overline{A \cup B}$. We prove that $x \in \bar A \cap \bar B$. By definition of complement, $x \not\in A \cup B$. Suppose, for contradiction, $x \not\in \bar A$. By definition of complement, $x \in A$, and by definition of union, $x \in A\cup B$, a contradiction. Thus, $x \in \bar A$. Now, suppose for contradiction, $x \not\in \bar B$. By definition of complement, $x \in B$, and by definition of union, $x \in A \cup B$, a contradiction. So, $x \in \bar B$. Therefore, $x \in \bar A$ and $x \in \bar B$, so by definition of intersection, $x \in \bar A \cap \bar B$.  (I'm leaving out the 2nd part, as I've figured out the 2nd part in my problem above)  Any ideas? I'm assuming it has to be of similar complexity.
88980
Trying to prove $(A ∩ B) − C=(A − C) ∩ (B − C)$ Im stuck here on this problem:  $(A∩B)−C=\{x | x ∈ (A ∩ B)∧ x ∉ C\}$  $(A∩B)−C=\{x|(x ∈ A ∧ x ∈ B) ∧ x ∉ C\}$  $(A∩B)−C=\{x|(x ∈ A ∧ x ∉ C) \lor (x ∈ B ∧ x ∉ C)\}$  I'm stuck right about here because how do I change the or (v) sign to the intersection sign (∩).  Please don't link me to the other question like this, I had a typo in it.
3279
I have to resit a calculus exam and for some reason set proofs were never my best friend...  Anyway, on a practice exam I encountered the following proof:  $$A\cap(B\cup C) = (A\cap B)\cup(A\cap C)$$  When I draw a Venn-diagram it seems quite obvious but I couldn't manage to write the proof down properly.  If someone could help me, that'd be great!
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!
89618
Please proof that $A\cap B=A\setminus(A\setminus B)$ this really gave me sleepless night. I tried using the set intersection properties but I still got confused.
63087
Suppose $A,B,C$ are sets.  Prove that $A\mathbin\triangle B\subseteq C \iff A\cup C=B\cup C$.  I proved that for $x\in A\setminus B$, $x\in A\cup C$ and for $x\in B\setminus A$, $x\in B\cup C$. How do I show that $A\cup C=B\cup C$, and that $A\mathbin\triangle B\subseteq C \iff A\cup C=B\cup C$?
22175
Suppose that $X$ is infinite and that $A$ is a finite subset of $X$. Then $X$ and $X \setminus A$ are equinumerous.     My attempt:  Let $|A|=n$. We will prove by induction on n. It's clear that the the theorem is trivially true for $n=0$. Assume the theorem is true for all $n=k$. For $n=k+1$, then $|A \setminus \{a\}|=k$ for some $a \in A$. Thus $X \setminus (A \setminus \{a\}) \sim X$ by inductive hypothesis, or $(X \cap \{a\}) \cup (X \setminus A) \sim X$, or $\{a\} \cup (X \setminus A) \sim X$. We have $\{a\} \cup (X \setminus A) \sim X \setminus A$ since the theorem is true for $n=1$. Hence $X \setminus A \sim \{a\} \cup (X \setminus A) \sim X$. Thus $X \setminus A \sim X$. This completes the proof.       Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!     Update: Here I prove that the theorem is true for $n=1$.  Assume that $A = \{a\}$ and consequently $X \setminus A= X \setminus\{a\}$. It's clear that $|X \setminus A| \le |X|$. Next we prove that $|X| \le |X \setminus A|$. Since $X$ is infinite, there exists $B \subsetneq X$ such that $B \sim X$ (Here we assume Axiom of Countable Choice). Thus $|X|=|B|$. There are only two possible cases.   $a \in X \setminus B$   Then $B \subseteq X \setminus \{a\}=X \setminus A$ and consequently $|X|=|B| \le |X \setminus A|$. Thus $|X| \le |X \setminus A|$ and $|X \setminus A| \le |X|$. By Schröder–Bernstein theorem, we have $|X \setminus A| = |X|$. It follows that $X \setminus A \sim X$.   $a \in B$.   Let $b \in X \setminus B$. We define a bijection $f:X \setminus \{a\} \to X \setminus \{b\}$ by $f(x)= x$ for all $x \in X \setminus \{a,b\}$ and $f(b)=a$. Thus $X \setminus \{a\} \sim X \setminus \{b\}$. Since $b \in X \setminus B$, it follows from Case 1 that $X \setminus \{b\} \sim X$. Hence $X \setminus \{a\} \sim X \setminus \{b\} \sim X$. Thus $X \setminus \{a\} = X \setminus A \sim X$.  To sum up, $X \setminus A \sim X$ for all $|A|=1$.
20531
I'll denote closure of A with $\overline{A}$, $A^\circ$ as the interior of A, $\partial A$ as the boundary of $A$ and $A'$ as the accumulation points. I'm trying to prove the following:   $$\overline{A}=A^\circ \cup\partial A$$  Is this a valid proof?  Take $x \in A^\circ \cup \partial A$ then $x \in A^\circ$ or $x \in \partial A$   if $x \in A^\circ$ then $x \in \overline{A}$  if $x \in \partial A$ then $x \in \overline{A} \cap\overline{(X\setminus A)}$ thus $x \in\overline{A} $ so $A^\circ\cup\partial A\subset\overline{A}$  Take $x \in \overline{A}$ then $x \in A' \cup A$ thus $x \in A'\setminus A$ or $x \in A^\circ$  if $x \in A'\setminus A$ then $x \in \overline{(X\setminus A)}$ so $x \in \overline{A}\cap\overline{(X\setminus A)}$ and $x \in\partial A$ so $x\in A^\circ\cup\partial A$  if $x \in A^\circ$ then $x \in A^\circ\cup \partial A$ so $\overline{A}\subset A^\circ\cup\partial A$
36022
the background I'm allowed to deal with to solve this problem is as follows:  Definition of +: \begin{equation} m+0=m\quad \text{for all}\quad m \in \mathbb{N} \\ m+(k+1) = (m+k)+1  \end{equation} in conjunction with the induction property of $\mathbb{N}$. In a previous task I showed that $ 0+m=m \quad \forall \, m \in \mathbb{N}$.  Task: Prove $m+n=n+m$ by induction on $n$.  Now, it follows directly that $0+m=m=m+0$. With the assumption that $k+m=m+k$ for a $k\in\mathbb{N}$, it can be deduced: \begin{eqnarray} m+(k+1) &amp; = &amp; (m+k)+1\quad \text{by def. of}+\\ &amp; = &amp; (k+m) + 1\quad \text{with assumption}\\ &amp; = &amp; k + (m+1)\quad \text{by def. of}+. \end{eqnarray} Here, it looks to me that the true base step would be $m+1 = 1+m$, because then it would be possible to bring the proof straight to an end. But I tried hard to hack this last nut without any results. Is there anybody who could help me with this? Or maybe there is a completely different way to come up with the proof requested?  Thanks in advance for your help
88648
I am trying to define a proof for  $A \cup B = B$ if and only if $A \subset B$  I started with:  $$A \cup B$$ $$x \in A \lor x \in B$$   but I am unsure on how to continue.
85029
I was wondering if this proof of this basic topological result concerning the  closure works.  Proposition: Let $A \subseteq (X,\tau)$. Then, $A$ is dense in $X$ if and only if every non-empty open subset of $X$ intersects $A$ non trivially. Proof: [only if] Assume that $A$ is dense in $X$. This means that $A \cup A' = X$, where $A'$ denotes the set of all the limit points of $A$. Let $G \in \tau$ be non-empty. Thus, $G \subseteq (A \cup A') = X$. Hence, either $G \cap A \neq \varnothing$, which establishes the result, or $G \cap A' \neq \varnothing$, which leads to a contradiction. [if] Assume that $A$ is not dense in $X$. Thus, there is a $x^* \in X \setminus (A \cup A')$. Notice, that $X \setminus (A \cup A')$ is open, because $A \cup A'$ is closed, and it is not empty. Hence, we can conclude by realizing that $X \setminus (A \cup A') \cap A = \varnothing$, which completes the proof. $\square$  It is one of the first proofs I attempt in topology, and I am not planning to see how it is proved in the book I am reading (unless you answer me that my proof is completely wrong). Thus, I am really looking forward to any feedback, also contentwise. Thank you for you time.
3633
Show that  $A \setminus ( B \setminus C ) \equiv ( A \setminus B) \cup ( A \cap C )$  This is an exercise I was trying to do ( not homework ) and I got stuck as follows:  Working from $A \setminus ( B \setminus C )$:  $x \in A \wedge x \notin ( B \setminus C )$ $x \in A \wedge ((x \in B \wedge x \in C) \vee (x \notin B \wedge x \in C) \vee (x \notin B \wedge x \notin C) )$  At this point I'm not sure how to proceed.  Working from the other side $ ( A \setminus B) \cup ( A \cap C ) $:  $ x \in ( A \setminus B) \cup ( A \cap C ) $  $ x \in ( A \setminus B) \vee x \in ( A \cap C ) $  $ ( x \in A \wedge x \notin B ) \vee ( x \in A \wedge x \notin C ) $  $ x \in A \wedge (x \notin B \vee x \notin C ) $  $ x \in A \wedge x \notin ( B \cap C ) $  $ A \setminus ( B \cap C ) $  I could also use some formating tips like how display logical not and how to get the lines to display properly without blank lines inbetween. :-)
60912
We were ask to prove that $|A \cup B| = |A| + |B| - |A \cap B|‫‪$. It was easy to prove it using a Venn diagram, but I think we might be expected to do if more formally. Is there a formal way?
68462
I know that they are equivalent if we have $\cap$ instead of $\cup$.  If we start from left, we have:  $X \in P(A) \cup P(B)$  $X \subset A \lor X \subset B$  If we start from right, we have:  $X \in P(A \cup B)$  $X \subset (A \cup B)$  And now, how do we proceed proving that they are not equivalent?
26905
Assume $\bar A\cap\bar B=\emptyset$. Is $\partial (A \cup B)=\partial A\cup\partial B$, where $\partial A$ and $\bar A$ mean the boundary set and closure of set $A$?   I can prove that $\partial (A \cup B)\subset \partial A\cup\partial B$ but for proving $\partial A\cup\partial B\subset \partial (A \cup B)$ it seems not trivial. I tried to show that for $x\in \partial A\cup\partial B$ WLOG, $x\in \partial A$ so $B(x)\cap A$ and $B(x)\cap A^c$ not equal to $\emptyset$ but it seems not enough to show the result.
93154
I'm having problems with this; the strategy is to show the left side is in the right side, and vice versa. Thus far I can only show that both sides of the equality are in A\B. Can I use "the empty set = A and not A" as a fact? Because then it works. Or just show me how to do it!
120472
Let $(\Omega,\mathcal F, P)$ be a probability space and let $A_1,A_2,...,A_n$ be events in $\mathcal F$.  Prove the following inclusion-exclusion formula  $P(\bigcup_{i=1}^nA_i)=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$  I am trying to prove this formula by induction; for $n=2$, let $A, B$ be two events in $\mathcal F$. We can write $A=(A \setminus B) \cup (A\cap B)$, $B=(B \setminus A) \cup (A\cap B)$, since these are disjoint unions, then  $P(A)=P(A \setminus B)+P(A\cap B)$ and $P(B)=P(B \setminus A)+P(A\cap B)$.  Now, $A \cup B$ can be expressed as $A \cup B= (A\setminus B) \cup (A \cap B) \cup (B \setminus A)$, which it's also union of disjoint sets, so  $P(A \cup B)=P(A \setminus B)+P(A\cap B)+P(B \setminus A)=P(A)+P(B)-P(A \cap B)$.  This proves that for $n=2$, the formula is correct.  Now, I want to show that the formula is true for $n \implies$ the formula is satisfied for $n+1$, I got stuck at this point, maybe I could express $P(\cup_{i=1}^{n+1} A_i)=P((\cup_{i=1}^n A_i \setminus A_{n+1}) \cup A_{n+1})=P(\cup_{i=1}^n A_i \setminus A_{n+1})+P(A_{n+1})$ (1)  I can use the inductive hypothesis on the term $P(\cup_{i=1}^n A_i \setminus A_{n+1})$, so $P(\cup_{i=1}^n (A_i \setminus A_{n+1}))=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} (A_i\setminus A_{n+1}))$  Expression (1) becomes $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} (A_i\setminus A_{n+1})) +P(A_{n+1})$  I don't know to to take this expression to the one I want, which is  $\sum_{k=1}^{n+1}$ $\sum_{\mathcal J \subset \{1,...,n+1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$  I would like to know how to continue this part of the exercise.