De Morgan's Laws and Commutative Diagrams

New Videos: Videos #3 and #4 on Probability for Actuarial Exam 1/P

As I emphasized in my most recent post “Venn Diagrams and Probability Notation“, simple probability problems are often best solved with pictures and basic logic, but more complicated problems may require formulas.

We are definitely not at the point in my video series where more complicated formulas are required to solve problems. But it is definitely best to start discussing these formulas and using intuitive reasoning to validate them.

My latest two videos (Videos #3 and #4 on Probability for Actuarial Exam 1/P) highlight these points. The content of the first video is purely abstract, but the problem from the second video includes a real-world context.

Act Exam 1/P Prep: Venn Diagrams, Special Addition Rule (w/ Probability Notation), Mathematica Demo. Probability for Actuarial Exam 1/P, Video #3. Online SOA Sample Exam P Questions, Problem #3.

Actuarial Exam 1/P Prep: Venn Diagram Problem, DeMorgan Law, General Addition Rule, Mathematica demo. Probability for Actuarial Exam 1/P, Video #4. Online SOA Sample Exam P Questions, Problem #8.

As a contrast to the intuitive approach taken in the videos, I will now show how to prove one (set) formula, state a second (set) formula, and show how to view them from an advanced (“fancy”) perspective that can tie them to other areas of advanced mathematics.

A Couple Set Laws: De Morgan’s Laws

One of the rules used in the second part of Video #4 is called a De Morgan Law, after Augustus De Morgan. Given two sets (events) $A$ and $B,$ it states that $(A\cap B)'=A'\cup B'.$ In words, this says that the complement of an intersection is the union of the complements.

Visually, the set from the equation above can be represented as shown below. The shading for the set includes both light red/pink and light blue hues (red/pink for outside of the red circle and blue for outside of the blue circle).

The set $(A\cap B)'=A'\cup B'.$ The set $A'$ outside the red circle is colored light red (pinkish). The set $B'$ outside the blue circle is colored light blue. Their intersection has both red and blue hues in it (it is a shade of “light purple”). The **union of all these shades** is the set in question. **It is the set outside of the white region** (the white region is $A\cap B$ ).

The set $(A\cap B)'=A'\cup B'.$ The set $A'$ outside the red circle is colored light red (pinkish). The set $B'$ outside the blue circle is colored light blue. Their intersection has both red and blue hues in it (it is a shade of “light purple”). The **union of all these shades** is the set in question. **It is the set outside of the white region** (the white region is $A\cap B$ ).

The proof of this law is based on a basic understanding of the meanings of set unions, set intersections, and set complements. It is also necessary to understand that two sets are equal if and only if every element of one set is an element of the other. In the proof below, the symbol $\subseteq$ means “is a subset of“.

Proof:

We first show that $(A\cap B)'\subseteq A'\cup B'.$ To do this, suppose that $x\in (A\cap B)'$ . This means that $x\not\in A\cap B$ , implying that either $x\not\in A$ or $x\not\in B.$ But this means that $x\in A'$ or $x\in B'$ so that we can say $x\in A'\cup B'.$ Hence, $(A\cap B)'\subseteq A'\cup B'.$

Next, we show that $A'\cup B'\subseteq (A\cap B)'.$ Essentially this amounts to just reversing the logic from the previous paragraph. If we assume that $x\in A'\cup B',$ this means that $x\in A'$ or $x\in B'$ so that $x\not\in A$ or $x\not\in B.$ But then it follows that $x\not\in A\cap B,$ from which we can say that $x\in (A\cap B)'.$ Hence, $A'\cup B'\subseteq (A\cap B)'.$

These two paragraphs imply equality between the sets: $(A\cap B)'= A'\cup B'.$ Q.E.D.

There is a second De Morgan Law between two sets. It is written as $(A\cup B)'= A'\cap B'.$ See if you can prove it in a similar manner as the proof above. Alternatively, it can be proved using the first of De Morgan’s Laws and the fact that, for any set $C,$ we have $(C')'=C.$

This second De Morgan Law can be visualized with the figure below. The set is shown in light purple. If $A'$ is shaded light red/pink and $B'$ is shaded light blue, their intersection $A'\cap B'$ would be shaded light purple.

*The set $(A\cup B)'=A'\cap B'$ is everything outside of the white region (the set is light purple).* If $A'$ is shaded light red/pink and $B'$ is shaded light blue, their intersection $A'\cap B'$ would be shaded light purple.

*The set $(A\cup B)'=A'\cap B'$ is everything outside of the white region (the set is light purple).* If $A'$ is shaded light red/pink and $B'$ is shaded light blue, their intersection $A'\cap B'$ would be shaded light purple.

An Advanced (Fancier) Perspective on De Morgan’s Laws

Sometimes mathematicians take a fancier perspective on a topic than is strictly necessary for a basic understanding of the topic. This is done for reasons other than just trying to look impressive to their colleagues. The main reason it is done is that it can shed light on relationships (both similarities and differences) between different subjects.

If you desire to be a student of advanced mathematics, it will be good for you to become aware of this tendency so that it does not shock you when you encounter it. Let us get some practice with this now.

In the case of De Morgan’s Laws from the previous section, we can approach them in a fancier way as follows:

Let $\Omega$ be a collection of sets (a set whose elements are themselves sets) which is “closed” under set unions, set intersections, and set complements. This means that, if $A,B\in \Omega,$ then (i) $A\cup B\in \Omega,$ (ii) $A\cap B\in\Omega,$ and (iii) $A'\in \Omega$ (we can say $B'\in \Omega$ too).

For example, if $S$ is the sample space for some random experiment, then we could take $\Omega$ to be the power set of $S$ , often denoted by $\mathcal{P}(S).$ It is the collection of all subsets of $S$ (including the empty set $\emptyset$ and $S$ itself).

Let $\Omega\times\Omega$ represent the Cartesian product of $\Omega$ with itself (the collection of all ordered pairs $(A,B),$ where $A,B\in \Omega$ ). Define functions $\mathcal{U}:\Omega\times\Omega\longrightarrow \Omega,$ $\mathcal{I}:\Omega\times\Omega\longrightarrow \Omega,$ and $\mathcal{C}:\Omega\longrightarrow \Omega$ by the formulas $\mathcal{U}(A,B)=A\cup B,$ $\mathcal{I}(A,B)=A\cap B,$ and $\mathcal{C}(A)=A'.$ (In each case, the set in front of the arrow is the “domain” and the set after the arrow is the “codomain“.)

In other words, $\mathcal{U}$ is a “binary operation” function that forms/returns the union of two sets as output, $\mathcal{I}$ is a “binary operation” function that forms/returns the intersection of two sets as output, and $\mathcal{C}$ is a “unary operation” function that forms/returns the complement of one set as output.

The fact that $(A\cap B)'=A'\cup B'$ can now be written as $\mathcal{C}(\mathcal{I}(A,B))=\mathcal{U}(\mathcal{C}(A),\mathcal{C}(B)).$ And the fact that $(A\cup B)'=A'\cap B'$ can now be written as $\mathcal{C}(\mathcal{U}(A,B))=\mathcal{I}(\mathcal{C}(A),\mathcal{C}(B)).$

Yet an even fancier perspective on this can be described as follows:

For a given function $f:G\longrightarrow H$ (where $G$ is an arbitrary domain and $H$ is an arbitrary codomain), we can define a new function $f\times f:G\times G\longrightarrow H\times H$ by the formula $(f\times f)(g_{1},g_{2})=(f(g_{1}),f(g_{2})).$ If the symbol $\circ$ represents this composition of two functions (another binary operation), then the relationships from the previous paragraph can be written as $\mathcal{C}\circ \mathcal{I}=\mathcal{U}\circ (\mathcal{C}\times \mathcal{C})$ and $\mathcal{C}\circ \mathcal{U}=\mathcal{I}\circ (\mathcal{C}\times \mathcal{C}).$ (Recall that with function composition $\phi\circ \psi,$ you should work from right to left — that is, the function $\psi$ gets applied before the function $\phi.$ )

We can take either of these last two equations from the previous paragraph and visualize it with a “commutative diagram“. For example, for the first of these equations, we get the commutative diagram below. The fact that this diagram “commutes” means it does not matter which way you go through the diagram by following the arrows; you will get the same answer in the end. To be more precise, for a given ordered pair $(A,B)\in \Omega\times\Omega,$ you will get the set $(A\cap B)'=A'\cup B'\in \Omega$ in the end either way you follow the arrows.

A commutative diagram as a way to visualize the relationship $\mathcal{C}\circ \mathcal{I}=\mathcal{U}\circ (\mathcal{C}\times \mathcal{C}).$ If you start with an ordered pair $(A,B)\in \Omega\times\Omega$ in the upper left, you will end up with the same output in the lower right now matter which way you follow the arrows. In other words, $(A\cap B)'=A'\cup B'.$

A commutative diagram as a way to visualize the relationship $\mathcal{C}\circ \mathcal{I}=\mathcal{U}\circ (\mathcal{C}\times \mathcal{C}).$ If you start with an ordered pair $(A,B)\in \Omega\times\Omega$ in the upper left, you will end up with the same output in the lower right now matter which way you follow the arrows. In other words, $(A\cap B)'=A'\cup B'.$

This is fancy stuff. How is it helpful? As I said before, it can help you see relationships with other areas of mathematics. For instance, the ideas in this section have analogs that play big roles in subjects as diverse as linear algebra and algebraic topology. If you go to graduate school in mathematics, you will definitely see these concepts again.

Briefly Back to Probability

Our main goal in coming videos and posts is to relate these things to probability. Ultimately, we will want to take an axiomatic approach to proving probability laws. The main probability laws we will prove soon are: (1) the Complement Rule $P[A']=1-P[A],$ (2) the Addition Rule for Mutually Exclusive Events $P[A\cup B]=P[A]+P[B]$ when $A\cap B=\emptyset,$ and (3) the General Addition Rule $P[A\cup B]=P[A]+P[B]-P[A\cap B].$

These rules play important roles in the videos embedded above, though they are mostly approached from an intuitive standpoint. They are important all throughout the study of probability.