Venn things get messy
Once upon a time, a long long time ago, in a land far far far away (Chinhoyi actually), I was in Form One learning about sets. Soon the teacher began setting up hair-raising questions like "Show that AcÇBc = (AÈB)c." I gave him the following Venn diagram in response.
"We-lll" he said, "You can't really do that."
"But it's correct sir, isn't it?"
"Ummmmm... yes, but you can't use Venn diagrams to prove things."
"Why not?"
"Okay, your proof is correct. But what if I asked you to apply the same method to show that, say, (AÈBÈCÈDÈE)c = AcÇBcÇCcÇDcÇEc?"
I didn't think it could be too hard. My mind changed as I tried to do it
though, and the next day I returned with something like this. "Well
done!" said my teacher. "But your diagram is incorrect." It took me a
while to see the mistake (try finding it yourself), and my spirits were
further lowered when he suggested that I do the same problem with a
THOUSAND sets instead of just five! In other words, could I use Venn
diagrams to show that
(A1ÈA2ȼÈA1000)c = A1cÇA2cǼÇA1000c? I didn't bother trying.
You see, the reason Venn diagrams aren't encouraged as a tool to prove things is that it is very hard to draw a correct diagram for more than four sets. And it gets very messy.
About ten years ago (that's 1989 if you're like me and can't count), a Cambridge mathematician called Anthony Edwards published an article in the British magazine New Scientist where he described a beautifully symmetrical procedure for drawing Venn diagrams for multiple sets. Strangely, no-one for a whole century after Venn had thought of it ! The diagrams for one, two and three sets hold no surprises and are given below:
Before we continue, some words of explanation. Our diagrams always have a boundary rectangle, called the universe U. We assume that the elements of every set we deal with are already in U (otherwise nasty things happen, but don't worry about that).
When we have one set A1, every element x of U is either in A1 or in A1c (i.e. not in A1). Thus U is divided into two parts.
When we have two sets A1,A2, every x Î U is in one of four sets: A1ÇA2, A1ÇA2c, A1cÇA2, A1cÇA2c.
When we have three sets A1,A2,A3, every x Î U is in one of
eight sets:
(A1ÇA2)ÇA3, (A1ÇA2c)ÇA3, (A1cÇA2)ÇA3,
(A1cÇA2c)ÇA3,
(A1ÇA2)ÇA3c, (A1ÇA2c)ÇA3c,
(A1cÇA2)ÇA3c, (A1cÇA2c)ÇA3c,
Can you predict what will happen when we add a fourth set A4? At the moment every section of U is of the form A1 (or A1c)ÇA2 (or A2c)ÇA3 (or A3c), e.g. A1ÇA2cÇA3c. With A4, each such part is split into two, e.g. (A1ÇA2cÇA3c)ÇA4 or (A1ÇA2cÇA3c)ÇA4c.This fact can be used to add A4 to our Venn diagram: with care we draw a symmetrical curve that chops each of the 8 parts of U into two others. Next, for A5, we must make a sort of necklace curve that goes around the circle, weaving in and out again between those 8 crossing points already on the circle.
We can continue this procedure indefinitely, but obviously our curves will eventually get too intricate to be useful. Useful to humans, that is. But for computer science, this method (as it can be explicitly described, and also for reasons in our next article) is a boon - it has already been used to help design circuit boards.
Previous Article in Venn series: All's not fair Venn you're a girl
Next Article: Venn binary is better
File translated from TEX by TTH, version 1.50.
Back to Zimaths Issue 3.1