Skip to main content
\(\newcommand{\versionNum}{$4.0$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section4.4Venn diagrams

Hopefully, you've seen Venn diagrams before, but possibly you haven't thought deeply about them. Venn diagrams take advantage of an obvious but important property of closed curves drawn in the plane. They divide the points in the plane into two sets, those that are inside the curve and those that are outside! (Forget for a moment about the points that are on the curve.) This seemingly obvious statement is known as the Jordan curve theorem, and actually requires some details. A Jordan curve is the sort of curve you might draw if you are required to end where you began and you are required not to cross-over any portion of the curve that has already been drawn. In technical terms such a curve is called continuous, simple and closed. The Jordan curve theorem is one of those statements that hardly seems like it needs a proof, but nevertheless, the proof of this statement is probably the best-remembered work of the famous French mathematician Camille Jordan.

The prototypical Venn diagram is the picture that looks something like the view through a set of binoculars.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

In a Venn diagram the universe of discourse is normally drawn as a rectangular region inside of which all the action occurs. Each set in a Venn diagram is depicted by drawing a simple closed curve — typically a circle, but not necessarily! For instance, if you want to draw a Venn diagram that shows all the possible intersections among four sets, you'll find it's impossible with (only) circles.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

Exercise4.4.1

Verify that the diagram above has regions representing all 16 possible intersections of 4 sets.

There is a certain “zen” to Venn diagrams that must be internalized, but once you have done so they can be used to think very effectively about the relationships between sets. The main deal is that the points inside of one of the simple closed curves are not necessarily in the set — only some of the points inside a simple closed curve are in the set, and we don't know precisely where they are! The various simple closed curves in a Venn diagram divide the universe up into a bunch of regions. It might be best to think of these regions as fenced-in areas in which the elements of a set mill about, much like domesticated animals in their pens. One of our main tools in working with Venn diagrams is to deduce that certain of these regions don't contain any elements — we then mark that region with the emptyset symbol (\(\emptyset\)).

Here is a small example of a finite universe.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

And here is the same universe with some Jordan curves used to encircle two subsets.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

This picture might lead us to think that the set of cartoon characters and the set of horses are disjoint, so we thought it would be nice to add one more element to our universe in order to dispel that notion.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

Suppose we have two sets \(A\) and \(B\) and we're interested in proving that \(B \subseteq A\). The job is done if we can show that all of \(B\)'s elements are actually in the eye-shaped region that represents the intersection \(A \cap B\). It's equivalent if we can show that the region marked with \(\emptyset\) in the following diagram is actually empty.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

Let's put all this together. The inclusion \(B \subseteq A\) corresponds to the logical sentence \(M_B \implies M_A\). We know that implications are equivalent to OR statements, so \(M_B \implies M_A \, \cong \, {\lnot}M_B \lor M_A\). The notion that the region we've indicated above is empty is written as \(\overline{A} \cap B \, = \, \emptyset\), in logical terms this is \({\lnot}M_A \land M_B \, \cong \, c\). Finally, we apply DeMorgan's law and a commutation to get \({\lnot}M_B \lor M_A \, \cong \, t\). You should take note of the convention that when you see a logical sentence just written on the page (as is the case with \(M_B \implies M_A\) in the first sentence of this paragraph) what's being asserted is that the sentence is universally true. Thus, writing \(M_B \implies M_A\) is the same thing as writing \(M_B \implies M_A \, \cong \, t\).

One can use information that is known a priori when drawing a Venn diagram. For instance if two sets are known to be disjoint, or if one is known to be contained in the other, we can draw Venn diagrams like the following.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

However, both of these situations can also be dealt with by working with Venn diagrams in which the sets are in general position — which in this situation means that every possible intersection is shown — and then marking any empty regions with \(\emptyset\).

Exercise4.4.2

On a Venn diagram for two sets in general position, indicate the empty regions when

  • The sets are disjoint.

  • \(A\) is contained in \(B\).

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

There is a connection, perhaps obvious, between the regions we see in a Venn diagram with sets in general position and the recognizers we studied in the section on digital logic circuits. In fact both of these topics have to do with disjunctive normal form. In a Venn diagram with \(k\) sets, we are seeing the universe of discourse broken up into the union of \(2^k\) regions each of which corresponds to an intersection of either one of the sets or its complement. An arbitrary expression involving set-theoretic symbols and these \(k\) sets is true in certain of these \(2^k\) regions and false in the others. We have put the arbitrary expression in disjunctive normal form when we express it as a union of the intersections that describe those regions.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

Subsection4.4.1Exercises

  1. Let \(A = \{1,2,4,5\}\), \(B=\{2,3,4,6\}\), and \(C=\{1,2,3,4\}\). Place each of the elements \(1, \ldots , 6\) in the appropriate regions of a three-set Venn diagram. \ \hint{The center region contains \(2\) and \(4\).}

  2. Prove or disprove: \begin{equation*} ( A \cap C \; \subseteq \; B \cap C ) \implies A \; \subseteq B \end{equation*} \hint{What will be the implications of the region \(A \cap \overline{B} \cap \overline{C}\) being non-empty?}

  3. Venn diagrams are usually made using simple closed curves with no further restrictions. Try creating Venn diagrams for 3, 4 and 5 sets (in general position) using rectangular simple closed curves. \hint{I found it easier to experiment by making my drawings on graph paper. I never did manage to draw the \(5\) set Venn diagram with just rectangles… probably just a lack of persistence.}

  4. We call a curve rectilinear if it is made of line segments that meet at right angles. If you have ever played with an Etch-a-Sketch you'll know what we mean by the term “rectilinear.” The following example of a rectilinear curve may also help to clarify this notion. \ Use rectilinear simple closed curves to create a Venn diagram for 5 sets. \hint{Of course, rectangles are rectilinear, so one could use the solution from the previous problem (if, unlike me, you were persistant enough to find it). Otherwise, start with the \(4\) set diagram made with rectangles and use your \(5\)th (rectilinear) curve to split each region into \(2\) — don't forget to split the region on the outside too.}

  5. Argue as to why rectilinear curves will suffice to build any Venn diagram. \hint{Fortunately the instructions don't say to prove that rectilinear curves will always suffice, so we can be less rigorous. Try to argue as to why it will alway be possible to add one more rectilinear curve to an existing Venn diagram and split every region into two. One might also argue that any continuous curve can be approximated using rectilinear curves. So if a Venn diagram can be constructed using continuous curves we can also get the job done with rectilinear curves.}

  6. Find the disjunctive normal form of \(A \cap (B \cup C)\). \hint{ \((A \cap B \cap \overline{C}) \cup (A \cap \overline{B} \cap C)\) }

  7. Find the disjunctive normal form of \((A \triangle B) \triangle C\) \hint{It is \((A \cap \overline{B} \cap \overline{C}) \cup (\overline{A} \cap B \cap \overline{C}) \cup (\overline{A} \cap \overline{B} \cap C)\). Now find the disjunctive normal form of \(A \triangle (B \triangle C)\).}

  8. The prototypes for the modus ponens and modus tollens argument forms are the following:

    \begin{minipage}{.3\textwidth}All men are mortal. Socrates is a man. Therefore Socrates is mortal. and \begin{minipage}{.3\textwidth}All men are mortal. Zeus is not mortal. Therefore Zeus is not a man.
    Illustrate these arguments using Venn diagrams. \hint{The statement “All men are mortal” would be interpreted on a Venn diagram by showing the set of “All men” as being entirely contained within the set of “mortal beings.” Socrates is an element of the inner set. Zeus, on the other hand, lies outside of the outer set.}

  9. Use Venn diagrams to convince yourself of the validity of the following containment statement \begin{equation*} (A \cap B) \cup (C \cap D) \; \subseteq \; (A \cup C) \cap (B \cup D). \end{equation*} Now prove it! \hint{Obviously we'll need one of the \(4\)-set Venn diagrams.}

  10. Use Venn diagrams to show that the following set equivalence is false. \begin{equation*} (A \cup B) \cap (C \cup D) \; = \; (A \cup C) \cap (B \cup D) \end{equation*} \hint{After constructing Venn diagrams for both sets you should be able to see that there are \(4\) regions where they differ. One is \(A \cap B \cap \overline{C} \cap \overline{D}\). What are the other three?}