Last time I boldly stated that if a Venn diagram is made up of $N$ sets, where $N$ is a composite number, i.e. not prime [1], then the Venn diagram can never be rotationally symmetric.
Before we prove the statement we first define the "rank" of the section in a Venn diagram.
The rank of a section is the number of sets, which the section is a part of.
For example, in the 2-set Venn diagram, the region outside of the circles has rank zero, because any point out there is in neither set. The sections on the extreme left and right of the circles each have rank 1, because they are a member of the either the right or left sets only. Finally, the overlapping region in the center has rank 2, because this section belongs to both sets.
Using this definition we can now head towards proving the initial statement. We do this by combining three smaller proofs concerning a general $N$-set Venn diagram. Explicitly, we
Before we prove the statement we first define the "rank" of the section in a Venn diagram.
The rank of a section is the number of sets, which the section is a part of.
For example, in the 2-set Venn diagram, the region outside of the circles has rank zero, because any point out there is in neither set. The sections on the extreme left and right of the circles each have rank 1, because they are a member of the either the right or left sets only. Finally, the overlapping region in the center has rank 2, because this section belongs to both sets.Using this definition we can now head towards proving the initial statement. We do this by combining three smaller proofs concerning a general $N$-set Venn diagram. Explicitly, we
- count how many sections there are of each rank;
- show that in a rotationally symmetric Venn diagram these ranks must be divisible by $N$;
- prove that the ranks are divisible by $N$ if and only if $N$ is prime.
Without further delay the three theorems and proofs can be found below.
Theorem 1
Suppose $k$ is an integer where $0\leq k\leq N$ then in an $N$-set Venn diagram there are
\begin{equation}
\frac{N!}{k!(N-k)!},
\end{equation}
sections of rank $k$ [2].
Proof 1
In order to help our intuition in counting the sections of a given rank we consider the 1-, 2-, 3-, 4-set Venn diagrams and summarise their details in the table below.
The pattern of numbers within the table maybe familiar to you, as it is the famous Pascal's triangle. We may have expected these numbers to appear in this formation, because the numbers in Pascal's triangle represent exactly the quantity we are trying to calculate. Namely, the $(k+1)^{th}$ number in the $(N+1)^{th}$ row of Pascal's triangle tells us how many ways there are of choosing $k$ objects from $N$ objects. Note that we need to use the $(k+1)^{th}$ number and not the $k^{th}$ number, because the first number of each row deals with the trivial section, which is in none of the sets. Similarly, we use $(N+1)^{th}$ row and not the $N^{th}$ row because the first row deals the trivial Venn diagram of 0 sets.
To cement this idea, suppose we have three objects {A,B,C}. How many different ways are there of choosing two objects from these three (under the assumption that ordering doesn't matter)? Explicitly, there are three ways, {A,B}, {B,C} and {A,C}. This is exactly the answer we get from Pascal's triangle if we look at the third number on the fourth row. Because of this identification we normally call the numbers $N$ choose $k$, or, $_NC_k$, for short.
There are many ways to calculate the coefficients of Pascal's triangle. The quickest way is to use the formula [3]
\begin{equation}
_NC_k= \frac{N!}{k!(N-k)!}.
\end{equation}
Theorem 2
If an $N$-set Venn diagram is rotationally symmetric the number of section of a given rank $k$, where $0\leq k\leq N$, must be divisible by $N$.
Proof 2
By definition, an $N$-set Venn diagram is rotationally symmetric if it has $N$ orders of rotational symmetry. This means that if we find the rotational center of the diagram and split the diagram into equal sectors of $2\pi/N$ radians (or $360/N$ degrees) each sector should "look" identical. For example, have a look at the 3-set Venn diagram which has been split into thirds. Each third contains sections with exactly the same rank.
We deduce that the total sum of sections with rank $k$ (where $0\leq k\leq N$ [4]) must be divisible by $N$. Suppose it wasn't true, we would not be able to divide the sections of rank $k$ into $N$ identical parts and therefore our diagram could not have $N$ identical sectors, suggesting that the diagram wasn't rotationally symmetric. In order to avert this contradiction we conclude that $N$ divides the total number of sections with rank $k$ for all values of $k$, where $0\leq k\leq N$.
Theorem 3
\begin{equation}
_NC_k= \frac{N!}{k!(N-k)!},
\end{equation}
is divisible by $N$ for all values of $k$ such that $0\leq k\leq N$ if and only if $N$ is prime.
Proof 3
We finish this week's post by noting that, although we have proven that an $N$-set Venn diagram is not rotationally symmetric when $N$ is composite, this does not mean that it is rotationally symmetric if $N$ is prime. We will discuss more about this point next time.
________________________________________________________________
_NC_k= \frac{N!}{k!(N-k)!},
\end{equation}
is divisible by $N$ for all values of $k$ such that $0\leq k\leq N$ if and only if $N$ is prime.
Proof 3
Firstly, suppose $N$ is prime. Consider $N$ choose $k$, which has a simplified form
\begin{equation}
_NC_k= \frac{N(N-1)(N-2)\dots(N-k+1)}{k(k-1)(k-1)\dots1},
\end{equation}
for all $0\leq k\leq N$. Note $_NC_k$ is an integer and that the top of the fraction has a prime factor $N$, which does not cancel down because there is no factor of $N$ on the bottom. Thus, $_NC_k$ contains a factor of $N$, and so it is divisible by $N$.
Conversely, suppose $N$ is composite. Choose $p$ to be the smallest prime factor of $N$, and define $n=N/p$ then
\begin{equation}
_NC_p=\frac{N(N-1)(N-2)\dots(N-p+1)}{p!}=\frac{n(N-1)(N-2)\dots(N-p+1)}{(p-1)!}.
\end{equation}
Now if $_NC_p$ is divisible by $N$ the top of the fraction must contain a factor of $N$ and therefore a factor of $p$. Because $N=np$ and we already have a factor of $n$ on the top then $p$ must divide at least one of the factors of $N-1$, $N-2$, ..., or $N-p+1$. But $p$ divides $N$, so it does not divide any of these other factors. Once again the only way out of the contradiction is to conclude that when $N$ is composite $N$ does not divide $_NC_p$ and, hence, $_NC_k$ is divisible by $N$ for all values of $k$ such that $0\leq k\leq N$ if and only if $N$ is prime.
Putting these three theorems together we generate the proof we were originally searching for.
Theorem 4
If $N$ is a composite number then the $N$-set Venn diagram is not rotationally symmetric.
Proof 4
\begin{equation}
_NC_k= \frac{N(N-1)(N-2)\dots(N-k+1)}{k(k-1)(k-1)\dots1},
\end{equation}
for all $0\leq k\leq N$. Note $_NC_k$ is an integer and that the top of the fraction has a prime factor $N$, which does not cancel down because there is no factor of $N$ on the bottom. Thus, $_NC_k$ contains a factor of $N$, and so it is divisible by $N$.
Conversely, suppose $N$ is composite. Choose $p$ to be the smallest prime factor of $N$, and define $n=N/p$ then
\begin{equation}
_NC_p=\frac{N(N-1)(N-2)\dots(N-p+1)}{p!}=\frac{n(N-1)(N-2)\dots(N-p+1)}{(p-1)!}.
\end{equation}
Now if $_NC_p$ is divisible by $N$ the top of the fraction must contain a factor of $N$ and therefore a factor of $p$. Because $N=np$ and we already have a factor of $n$ on the top then $p$ must divide at least one of the factors of $N-1$, $N-2$, ..., or $N-p+1$. But $p$ divides $N$, so it does not divide any of these other factors. Once again the only way out of the contradiction is to conclude that when $N$ is composite $N$ does not divide $_NC_p$ and, hence, $_NC_k$ is divisible by $N$ for all values of $k$ such that $0\leq k\leq N$ if and only if $N$ is prime.
Putting these three theorems together we generate the proof we were originally searching for.
Theorem 4
If $N$ is a composite number then the $N$-set Venn diagram is not rotationally symmetric.
Proof 4
- By proof 1 the total number of sections of a given rank is given by $_NC_k$.
- By proof 2 if a Venn diagram is rotationally symmetric the total number of sections of a given rank must be divisible by $N$ for all $0\leq k\leq N$ .
- We conclude that if a Venn diagram is rotationally symmetric $_NC_k$ must be divisible by $N$ for all $0\leq k\leq N$.
- Finally, by proof 3, $_NC_k$ is be divisible by $N$ for all $0\leq k\leq N$ if and only if $N$ is prime.
We finish this week's post by noting that, although we have proven that an $N$-set Venn diagram is not rotationally symmetric when $N$ is composite, this does not mean that it is rotationally symmetric if $N$ is prime. We will discuss more about this point next time.
________________________________________
[1] For those of you who may have forgotten the definition: a positive number is prime if and only if it was only two distinct integer factors, which are itself and 1. For example 2, 3, 5 and 7 are all prime numbers. However, 9 is not a prime number, because 3$\times$3=9 and the factors of 9 are 1, 3 and 9. Any number that is not prime (other than 1) is called composite. The number 1 is a special case as it is neither prime nor composite. It is called a unit.
[2] The exclamation mark symbol $n!$ represents the product of all positive integers up to and including $n$, i.e. $n!=1\times2\times3\times...\times n$.
[3] Ok, I've slightly cheated and not proven that this formula does give us the numbers that we want. However, if you want to read more about the connection between the Pascal numbers and the formula see this post.
[4] Note that we have excluded $k=0$ and $k=N$, why is that?
[2] The exclamation mark symbol $n!$ represents the product of all positive integers up to and including $n$, i.e. $n!=1\times2\times3\times...\times n$.
[3] Ok, I've slightly cheated and not proven that this formula does give us the numbers that we want. However, if you want to read more about the connection between the Pascal numbers and the formula see this post.
[4] Note that we have excluded $k=0$ and $k=N$, why is that?
This post has covered everything about set theory. Its a good help for understanding.
ReplyDelete