Proof. Consider $x\in A \overset{\text{def}}{\Longrightarrow} x \notin A^C$. Therefore $A\nsubseteq A^C$.

Consider also $x\in A^C \overset{\text{def}}{\Longrightarrow} x \notin A$. Therefore $A^C\nsubseteq A$.

Since $A^C\nsubseteq A$ and $A\nsubseteq A^C$ we prove that $A^C \cap A = \varnothing$.

I have a simple question: does my proof contain errors?


I think I have got it now.

Proof. Let $A \subseteq \Omega$.

Assume there is an element such that $x \in A\cap A^C$. This is equivalent to $x\in A$ and $x\in A^C. $

Since $x \in A \overset{\text{def}}{\Longrightarrow}x\notin A^C$, there exists no $x$ such that $x\in A$ simultaneously as $x\in A^C$.

Therefore, $\nexists x: x\in A \wedge x\in A^C$ and $A\cap A^C=\varnothing$.

  • $\begingroup$ In your title you mention $A'$ but nowhere do you mention it in your body. I assume you mean $A'=A^c$. Your proof contains errors assuming this is what you mean because $A \not\subset B$ and $B \not\subset A$ doesn't imply $A \cap B = \emptyset$. For example, the nonnegative numbers and the nonpositive numbers do not contain each other, but 0 is in both sets. $\endgroup$ – Connor Malin Feb 19 at 19:23
  • $\begingroup$ Um.. why does $X \not \subset Y$ and $Y\not \subset X$ imply $X\cap Y =\emptyset$? Is that an axiom? A definition? I think for a proof about basic concepts one has to be extra precise about definitions. Frankly I have to wonder about anyone being asked to "prove" this. It is essentially definition. $A^c$ is defined to be the set of precisely the elements that are not contained in $A$ so there can't be any elements in both. $\endgroup$ – fleablood Feb 19 at 20:08
  • $\begingroup$ I've made an edit. I keep the previous mistakes as reference. $\endgroup$ – user615771 Feb 19 at 20:10
  • $\begingroup$ It might help your proof to begin it with a clear, self-contained definition of $A^C$, e.g., "If $A$ is a set, its complement is the set $A^C=\{x: x\not\in A\}$." $\endgroup$ – Barry Cipra Feb 19 at 20:53

You state that $A^C \not\subseteq A$ and $A \not\subseteq A^C$ implies $A^C \cap A = \emptyset$. This is not true. For example, $A = \{1,2,3\}$ and $B = \{3,4,5\}$ have the property $A \not\subseteq B$ and $B \not\subseteq A$, but their intersection is $\{3\}$, which is nonempty.
For a correct proof of this fact, we need to show that there exist no elements in the intersection, not just that they are not subsets of each other.
To this end, suppose there is an element $x$, in $A^C \cap A$. Since $x$ in $A^C \cap A$, then $x \in A^C$, by definition of $\cap$. But since $x \in A^C$, then $x \not\in A$, by the definition of the complement. So $x \in A^C \cap A$ implies that $x \not\in A$. If $x \not\in A$, then $x \not\in A^C \cap A$. But this contradicts the assumption that $x \in A \cap A^C$. Thus, there cannot exist any elements in $A^C \cap A$, which means $A^C \cap A = \emptyset$.


You cannot conclude $X\cap Y = \varnothing $ from $X\nsubseteq Y$ and $Y\nsubseteq X$ (take, for instance, $X=\{a,b\}$ and $Y=\{b,c\}$). That being said, your first two lines are true, and any one of your two implications can be used to deduce that no $x$ can be in both $A$ and its complement.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy