4.4 Venn 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 as illustrated in Figure 4.2.
Figure 4.2: A prototypical Venn digram.
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. Figure 4.3 shows a drawing of a Venn diagram for four sets.
Figure 4.3: A four-set Venn diagram.
Exercise 4.11 Verify that the diagram above has regions representing all 16 possible intersections of four 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\)).
Figure 4.4 shows a small example of a finite universe.
Figure 4.4: A finite universe.
And Figure 4.5 shows the same universe with some Jordan curves used to encircle two subsets.
Figure 4.5: A finite universe with two subets.
The picture in Figure 4.5 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. (See Figure 4.6.)
Figure 4.6: A finite universe with two subsets having a common element.
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 Figure 4.7 is actually empty.
Figure 4.7: An illustrating Venn diagram for proving set inclusion.
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 \, \bot\). Finally, we apply De Morgan’s law and a commutation to get \({\lnot}M_B \lor M_A \, \cong \, \top\). 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 as writing \[M_B \implies M_A \, \cong \, \top.\]
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 ones in Figure 4.8 and Figure 4.9
Figure 4.8: Venn diagram illustrating two disjoint sets.
Figure 4.9: Venn diagram illustrating set containment.
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\).
Exercise 4.12 On a Venn diagram given in Figure 4.10 for two sets in general position, indicate the empty regions when
- The sets are disjoint.
- \(A\) is contained in \(B\).
Figure 4.10: Venn diagram of two sets in general position
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.
Figure 4.11: Venn diagram of three sets in general position
4.4.1 Exercises
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 shown in Figure 4.12.
Figure 4.12: Three-set Venn diagram
Prove or disprove: \[ ( A \cap C \; \subseteq \; B \cap C ) \quad \implies \quad A \; \subseteq B \]
Venn diagrams are usually made using simple closed curves with no further restrictions. Try creating Venn diagrams for three, four and five sets (in general position) using rectangular simple closed curves.
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.” Figure 4.13 shows an example of a rectilinear curve.
Figure 4.13: A rectilinear curve.
Use rectilinear simple closed curves to create a Venn diagram for five sets.
Argue as to why rectilinear curves will suffice to build any Venn diagram.
Find the disjunctive normal form of \(A \cap (B \cup C)\).
Find the disjunctive normal form of \((A \triangle B) \triangle C\)
The prototypes for the modus ponens and modus tollens argument forms are the following:
All men are mortal.
Socrates is a man.
Therefore Socrates is mortal.and
All men are mortal.
Zeus is not mortal.
Therefore Zeus is not a man.Illustrate these arguments using Venn diagrams.
Use Venn diagrams to convince yourself of the validity of the following containment statement \[ (A \cap B) \cup (C \cap D) \; \subseteq \; (A \cup C) \cap (B \cup D).\] Now prove it!
Use Venn diagrams to show that the following set equivalence is false. \[ (A \cup B) \cap (C \cup D) \; = \; (A \cup C) \cap (B \cup D) \]