6
$\begingroup$

I am a bio student self-studying Abbott's Understanding Analysis and would love some feedback on one of my answers to an exercise. I have no experience writing proofs, and I'm used to plug-n-chug math taught by school, but I'm determined to get through this book as I find it fascinating. Thanks!

Q: If $x ∈ (A ∩ B)^c$, explain why $x ∈ A^c ∪ B^c$. This shows that $(A ∩ B)^c ⊆ A^c ∪ B^c$

Pf: If $x \in A\cap B$, then $x \in A,B$ and $x \in A\cup B$. We can think of $A\cap B$ as the collection of elements in both $A$ and $B$. The complement $(A\cap B)^c$ is therefore the set of elements not in $A$ and $B$, elements can still originate from $A$ or $B$, just not those in both.

The set $(A\cap B)^c$ is equal to $A^c\cup B^c$ because $A^c$ is the set of elements not in A (but, again, can contain elements in $B$). But, if an element is in A and also in B, neither $A^c$ nor $B^c$ will contain that elements. Thus, $A^c\cup B^c$ can be thought of as the set of elements not in $A$ and $B$, just as with $(A ∩ B)^c$.

$\endgroup$
6
  • 1
    $\begingroup$ I think your reasoning is fine. This is handy too: If $A,B\subset X$, then $X=(A \cup B)^\complement \cup (A \cap B^\complement) \cup (B \cap A^\complement) \cup (A \cap B)$. Related stuff: math.stackexchange.com/questions/3706996 $\endgroup$
    – 311411
    Commented Dec 16, 2021 at 5:54
  • 2
    $\begingroup$ This proof just describes the idea of a formal proof. Give it another try and begin by taking an $x\in(A\cap B)^{c}$ and by using only definitions, show that this $x\in A^c\cup B^c$. $\endgroup$ Commented Dec 16, 2021 at 5:55
  • 1
    $\begingroup$ Have you heard of Venn Diagrams? $\endgroup$ Commented Dec 16, 2021 at 10:32
  • 2
    $\begingroup$ Venn diagrams with only a small number of sets are a useful guide to get an idea (a picture) of what's going on. That's about all. $\endgroup$ Commented Dec 17, 2021 at 9:43
  • 1
    $\begingroup$ I think if you have a look at logic and elementary set theory, you will find yourself more fascinated because it will save you a lot of time in learning analysis. $\endgroup$
    – Hermis14
    Commented Dec 18, 2021 at 2:25

3 Answers 3

6
$\begingroup$

What you are doing is writing the correct logic using words. You only need to write it in terms of set theoratic symbols and sort out a few degeneracies (Also this is called the De-Morgan's Law). Assume you are working under the universal set $U$.

Step 0:- Assume the non-emptiness of $(A\cap B)^c$ and $A^c\cup B^c$

Step 1. pick $x\in (A\cap B)^{c}$ . So $x\notin A\cap B$.

Step 2. $x\notin A\cap B\implies x\notin A\,\text{or}x\notin B$.

Step 3. $x\notin A\,\text{or}x\notin B\implies x\in A^c\text{or}\,x\in B^{c}$

Step 4:- $x\in A^c\text{or}\,x\in B^{c}\implies x\in A^c \cup B^c$

So $(A\cap B)^{c}\subset A^c\cup B^c$.

Step 5:-Now pick $y\in A^c\cup B^c$.

Step 6:-$y\in A^c\cup B^c\implies y\in A^c\,\text{or}\,y\in B^c$

Step 7:-$y\in A^c\text{or}y\in B^c\implies y\notin A\,\text{or}\,y\notin B$

Step 8:-$y\notin A\,\text{or}\,y\notin B\implies y\notin A\cap B$

Step 9:-$y\notin A\cap B\implies y\in (A\cap B)^c$

So $A^c\cup B^c\subset (A\cap B)^c$.

So you now see that $A^c\cup B^c\subset (A\cap B)^c$ and $(A\cap B)^{c}\subset A^c\cup B^c$ . This can only mean that $(A\cap B)^{c}=A^c\cup B^c$

Now you sort out the Degenerate cases:- if $(A\cap B)^{c}=\phi$. Then $A\cap B=U$. So $A=U$ and $B=U$ as $A\cap B\subset A$ and $A\cap B\subset B$. In this case the LHS is $\phi$ and the RHS is $A^c\cup B^c=U^c\cup U^c = \phi\cup \phi = \phi$. So equality holds.

If $A^c\cup B^c=\phi$ imply $A^c=\phi$ and $B^c=\phi$ as $A^c\subset A^c\cup B^c$ and $B^c\subset A^c\cup B^c$. So you have $A^c=\phi\implies A=U$ and $B^c=\phi\implies B=U$. So again $LHS=\phi=RHS$. Hence again equality holds.

This completes the proof.

Note that you need to sort out the cases when they are empty because in that case we cannot "pick" any $x$ from anywhere. So you need to deal with the cases separately

$\endgroup$
1
  • $\begingroup$ Thank you so much!! This REALLY helps. It did feel wrong to have my answer be written in words. But I had no idea how to "manipulate" set theory symbols, it's not like algebra where you're moving things back and forth across the "=" sign. Thank you again so much. $\endgroup$
    – GMoss
    Commented Dec 17, 2021 at 9:20
3
$\begingroup$

With some practice you can write more succint proofs using the logical "or" and "and", that is, $\lor$ and $\land$, as well as the symbols $\implies$ and $\iff$. Treat $\lor$ and $\land$ as binary operations, with each one being distributive over the other.

Supposing we are taking complements in a set $X$, with $A\subseteq X$ and $B\subseteq X.$ Then for any $x$ we have $$x\in (A\cap B)^c \iff (x\in X\land x\not \in A\cap B)\iff$$ $$\iff (x\in X\land [x\not\in A\lor x\not\in B])\iff$$ $$\iff ([x\in X\land x\not\in A]\lor [x\in X\land x\not\in B])\iff$$ $$\iff ([x\in A^c]\lor [x\in B^c])\iff$$ $$\iff x\in A^c\cup B^c.$$ So we conclude that$$(A\cap B)^c =A^c\cup B^c.$$

$\endgroup$
2
  • $\begingroup$ Thank you! Your answer and the above are a huge help. Definitely going to get to practicing writing my proofs in symbols, I really want to get it down. I just didn't know how to approach it as this is my first encounter with set theory (and proofs). But your answer is a good guide. $\endgroup$
    – GMoss
    Commented Dec 17, 2021 at 9:22
  • 2
    $\begingroup$ @GMoss . Your "wordy" solution is the opposite of what many students do. They write a sequence of separate assertions without any explanation of how they are related to each other. $\endgroup$ Commented Dec 17, 2021 at 9:39
2
$\begingroup$

The idea, to some extent expressed in the other answers, that substituting symbols for words somehow improves proofs is (at least from my personal perspective) false. Indeed, whenever I have taught undergraduate students to write proofs, the main obstacle at the beginning of the course is to get them to write comprehensible English statements rather than just sequences of symbols. Of course, this is not to say that you need to avoid symbols. But there is no reason to go out of your way to cram more symbols into a proof just to make it look more "formal" or "mathematical". Whether a proof is valid or not has nothing to do with the ratio of words to symbols.

The idea that symbols are somehow intrinsically better than words is more of a cargo cult idea of mathematics rather than an opinion that a majority of mathematicians hold. You seem to have understood this part of writing proofs just fine, so my advice is to build on your good habit of writing perfectly comprehensible English, rather than trying to replace it by symbols.

Now, for some feedback: the stylistic feedback would be to avoid phrases like "elements originate from $A$" or "... can be thought of as the set of elements not in $A$ and $B$". We do not really say that elements originate from a set. Rather, you say that they belong to, or lie in, or are elements of a set. Also, if you want to say that $X$ is $Y$, just say that $X$ is $Y$. Saying that it "can be thought of as $Y$" just makes it sound like you are hedging because you are unsure whether or to what extent this is true. The phrase that $X$ can be thought of as $Y$ is more appropriate when you are trying to intuitively explain some complicated construction in a brief slogan, which is not really what you are doing here.

The formulation "the set of elements not in $A$ and $B$" is somewhat ambiguous: it could also be read as "elements which are not in $A$ and not in $B$". If you say something like "elements which do not belong to both $A$ and $B$", it would be less ambiguous.

As far as the logic of the proof goes, it makes sense but it has some redundant parts and sort of goes back and forth instead going from point A (assumption) to point B (conclusion). For example, one could completely remove the first paragraph of the proof and it would still be an okay argument. Here is how you could write a more succinct proof:

If $x \in (A \cap B)^c$, then $x$ is not an element of the set $A \cap B$. Now $x$ is an element of $A \cap B$ if and only if both $x \in A$ and $x \in B$. Therefore, if $x \notin A \cap B$, then either $x \notin A$ or $x \notin B$. In other words, $x \in A^c$ or $x \in B^c$. In either case, $x \in A^c \cup B^c$.

(Also, my final piece of feedback is that this is not really what one would think of as a "real analysis proof", despite occurring in a real analysis textbook, since it does not involve any of the characteristic notions of real analysis like derivatives, integrals, or indeed functions. Rather, it would be categorized as elementary set theory.)

$\endgroup$
4
  • $\begingroup$ Ok gotcha! This is excellent advice and feedback; I'll definitely keep what you've said in mind as I continue my work. (I am blown away by the willingness of this community to help.) $\endgroup$
    – GMoss
    Commented Dec 19, 2021 at 6:19
  • $\begingroup$ @GMoss I definitely agree with what Pilcrow delivered. However, I often face cases where mathematical statements written in natural language entail unignorable ambiguity or the use of uncommon jargon, which makes me really hard to follow. In those cases, I try to rewrite them in concise symbols to clarify things described by the sentences. It's just a matter of familiarity. So, I recommend you make yourself familiar with both approaches and utilize them to boost your learning efficiency. To make it sense, of course, you have to learn first how to use symbols formally. $\endgroup$
    – Hermis14
    Commented Dec 21, 2021 at 9:40
  • $\begingroup$ @GMoss If you have time, refer to the well-written book Barker-Plummer's Language, Proof and Logic (2011). $\endgroup$
    – Hermis14
    Commented Dec 21, 2021 at 9:43
  • $\begingroup$ This is an underrated answer. It explains really well what is going on behind those symbols. You see @GMoss that those symbols are precisely shortened form of words. For example $\in$ just translates to "belong to" or "lie in". If you write that instead of the symbol it is perfectly fine. As this answer points out , the wording should be precise and make perfect sense. This is main reason for adopting symbols. It provides a sort of universality to the proof writing process. $\endgroup$ Commented Dec 22, 2021 at 7:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .