Cardinality of a Union

How many unique items are there in two or more overlapping groups? This simple question poses a common challenge: if we just add the groups' sizes, we end up counting the shared items more than once. This "double-counting" problem is not just a daily nuisance but a fundamental barrier to accurately understanding the combined size of collections in various domains. Correcting for this error requires a formal and scalable method that works for simple lists, complex databases, and even infinite collections.

This article demystifies the process of counting elements in a union of sets. In the following chapters, you will first learn the core concepts behind this calculation. Then, you will see how this single idea provides a powerful analytical tool across a surprising range of disciplines. The "Principles and Mechanisms" chapter will introduce the elegant Principle of Inclusion-Exclusion, generalize it for multiple sets, and explore its fascinating behavior when applied to the strange arithmetic of infinite sets and power sets. Following this, the "Applications and Interdisciplinary Connections" chapter will showcase how this mathematical rule underpins everything from software development and probability theory to abstract algebra and the biological mechanisms of our immune system. Let's begin by unraveling the elegant solution to the double-counting problem.

Have you ever tried to count your friends? Suppose you have a group of friends from your neighborhood and another group from school. If you want to know the total number of unique friends you have, you can’t simply add the number of people in each group. Why not? Because some friends might be in both groups—they live in your neighborhood and go to your school. If you just add the two numbers, you’ve counted these poor individuals twice!

This simple, everyday dilemma lies at the heart of one of the most fundamental and useful ideas in mathematics: counting the elements in a union of sets. To do it right, we have to be clever. We have to add the counts, but then correct for the "double-counting." This process of adding and correcting is more than just arithmetic; it’s a beautiful principle that scales from simple friend groups to the dizzying complexities of infinite sets.

Let's formalize our little problem. Imagine two sets, $A$ and $B$. We want to find the size, or ​​cardinality​​, of their union, $A \cup B$, which is the set of all elements that are in $A$, or in $B$, or in both. We denote the cardinality of a set $S$ as $|S|$.

Our first intuition is to add the sizes: $|A| + |B|$. But as we saw, this counts the elements in the ​​intersection​​—the part common to both, $A \cap B$—twice. To fix this, we simply subtract the size of the intersection once. This gives us the famous ​​Principle of Inclusion-Exclusion​​ for two sets:

$|A \cup B| = |A| + |B| - |A \cap B|$

It’s called "Inclusion-Exclusion" because we include the sizes of the individual sets and then exclude the size of their overlap. For example, if you have a set $A$ with 12 elements and a set $B$ with 18, and you know they share 5 elements, the total number of unique elements is not $12+18=30$, but rather $12 + 18 - 5 = 25$. This elegant formula is the bedrock of our journey. We can see it at work in practical scenarios, like a network security system that flags data packets. If one algorithm flags multiples of 6 and another flags multiples of 10, the total number of flagged packets isn't just the sum of the two counts; you must subtract the packets divisible by both 6 and 10 (that is, by their least common multiple, 30) to get the correct total.

What if we have three sets? Let's say we're counting the total number of students in three university a cappella groups: Altos ($A$), Baritones ($B$), and Chorales ($C$). The plot thickens.

If we start by adding them up, $|A| + |B| + |C|$, we've made an even bigger mess. Anyone in two groups, say $A$ and $B$, has been counted twice. So, just like before, we subtract the pairwise overlaps: $-|A \cap B| - |A \cap C| - |B \cap C|$.

But have we fixed it? Let's think about the most dedicated students, those who are in all three groups ($A \cap B \cap C$). In our first step, we included them three times (once for each group). In our second step, we excluded them three times (once for each pairwise intersection). The result? They've been counted $3 - 3 = 0$ times! We've accidentally made them vanish from our total. To correct this new error, we must add them back in.

This gives us the full principle for three sets:

$|A \cup B \cup C| = \underbrace{|A| + |B| + |C|}_{\text{Include individuals}} - \underbrace{(|A \cap B| + |A \cap C| + |B \cap C|)}_{\text{Exclude pairs}} + \underbrace{|A \cap B \cap C|}_{\text{Include triples}}$

Do you see the beautiful pattern? We include the singles, exclude the pairs, include the triples... It's an alternating dance of adding and subtracting. This pattern continues for any number of sets. For four sets, you would subtract the intersection of all four. If you were to stop the formula early, as a student in one problem did, your calculation would be off by precisely the term you neglected. This shows that every term in this alternating sum plays a crucial role in correcting the counts of the previous steps.

Sometimes, we're interested in what's not in the union. If we know the total number of elements in our universe (say, 50 people in a room), we can easily find how many like neither coffee nor tea by first finding how many like at least one, and then subtracting that from the total. Counting the inside helps us count the outside.

The Principle of Inclusion-Exclusion is not just a formula for finding a final number. It describes a rigid relationship between the sizes of sets and their intersections. This means we can use it to work backward and solve puzzles.

Imagine a fascinating scenario from a data science team analyzing customer reviews. They have three models flagging "urgent" reviews, and they know how many reviews each model flagged individually. The cost of verifying a review depends on how many models flagged it. To find the minimum possible cost, they need to figure out the minimum possible number of reviews flagged by all three models.

This is no longer a simple counting problem; it's an optimization problem. The Principle of Inclusion-Exclusion becomes a set of constraints. By cleverly manipulating the formulas that relate the total counts of individual sets to the counts of their intersections, we can establish a hard lower bound on the size of the triple-intersection. It turns out this minimum depends only on the sum of the sizes of the three sets and the size of the total universe of reviews. The principle gives us the power not just to count what is, but to deduce the limits of what could be.

Our counting rules work perfectly for things we can, well, count: friends, students, data packets. But what happens when we venture into the realm of the infinite? Do the same rules apply?

Let's start with a "small" infinity, the ​​countably infinite​​ sets. These are sets whose elements can be listed out, one by one, in a sequence that goes on forever, like the natural numbers $\{1, 2, 3, \dots\}$. The set of all rational numbers, $\mathbb{Q}$, is a classic example. Its cardinality is denoted $\aleph_0$ ("aleph-naught").

What happens if we take a countably infinite set, like the rational numbers, and unite it with a small, finite set, like the three real solutions to a polynomial equation? Intuitively, adding a few extra items to an infinite list doesn't make the list "more infinite." You can just tack the new elements onto the beginning of your infinite list. The new set is still countably infinite. In the language of cardinal numbers, if $|A|$ is finite and $|B| = \aleph_0$, then $|A \cup B| = \aleph_0$. Adding a finite drop to an infinite ocean doesn't change the ocean.

Now for a bigger leap. What about uniting a countably infinite set ($|F| = \aleph_0$) with an ​​uncountably infinite​​ set ($|E| = \mathfrak{c}$), one so vast its elements cannot be put into a simple list? (The set of all real numbers is the classic example, with cardinality $\mathfrak{c}$). This is like adding the infinite set of all integers to the infinite set of all points on a line.

Here, a new and powerful intuition emerges. The cardinality of the union is bounded. It must be at least as large as the larger set, so $|F \cup E| \ge \mathfrak{c}$. And it can be no larger than the sum of their sizes, $|F \cup E| \le \aleph_0 + \mathfrak{c}$. In the bizarre arithmetic of infinite cardinals, adding two different infinities just gives you the larger of the two. So, $\aleph_0 + \mathfrak{c} = \mathfrak{c}$.

We are squeezed from both sides: $\mathfrak{c} \le |F \cup E| \le \mathfrak{c}$. The only possibility is that $|F \cup E| = \mathfrak{c}$. The larger infinity has completely "swallowed" the smaller one. This is a fundamental rule when uniting sets of different infinite sizes: the biggest one wins.

Let's return to the safety of finite sets for one last, crucial lesson. We've mastered the union of sets $A$ and $B$. But what about the union of their ​​power sets​​? A power set, $\mathcal{P}(S)$, is the set of all possible subsets of $S$. If $|S|=n$, then $|\mathcal{P}(S)|=2^n$.

Does our trusty Inclusion-Exclusion principle work here? Let's check. If sets $A$ and $B$ are disjoint (have no elements in common), is $\mathcal{P}(A) \cup \mathcal{P}(B)$ simple to calculate? Almost! The power sets $\mathcal{P}(A)$ and $\mathcal{P}(B)$ are not disjoint. They share exactly one element: the empty set, $\emptyset$, which is a subset of every set. So, for disjoint $A$ and $B$, the principle applies beautifully: $|\mathcal{P}(A) \cup \mathcal{P}(B)| = |\mathcal{P}(A)| + |\mathcal{P}(B)| - |\mathcal{P}(A) \cap \mathcal{P}(B)| = 2^{|A|} + 2^{|B|} - 1$.

This might lead to a dangerous temptation. Perhaps the cardinality of the power set of a union follows a similar rule? Is $|\mathcal{P}(A \cup B)|$ somehow equal to $|\mathcal{P}(A)| + |\mathcal{P}(B)| - |\mathcal{P}(A \cap B)|$?

Let’s test it with an example. Let $A = \{\text{red}, \text{green}\}$ and $B = \{\text{green}, \text{blue}\}$.

• $|A|=2, |B|=2, |A \cap B|=1, |A \cup B|=3$.
• $|\mathcal{P}(A)| = 2^2=4$, $|\mathcal{P}(B)| = 2^2=4$, $|\mathcal{P}(A \cap B)|=2^1=2$.
• The mistaken formula gives $4+4-2=6$.
• But the actual value is $|\mathcal{P}(A \cup B)| = 2^3=8$.

They are not equal! Why did the analogy fail? The answer provides a deeper insight. The set $\mathcal{P}(A) \cup \mathcal{P}(B)$ contains only subsets made entirely of elements from $A$ or entirely of elements from $B$. In our example, it contains $\{\text{red}\}$, $\{\text{green}\}$, $\{\text{blue}\}$, etc., but it does not contain the "mixed" subset $\{\text{red}, \text{blue}\}$. The set $\mathcal{P}(A \cup B)$, on the other hand, contains all subsets of the combined elements, including all the mixed ones. These mixed subsets are numerous and account for the large discrepancy.

This final puzzle is a perfect illustration of the scientific spirit. A beautiful pattern appears, and we push it to its limits. When it breaks, we don't discard it. Instead, we ask why it broke. The answer reveals a hidden layer of structure, teaching us that the union of power sets is a fundamentally different and more complex object than the power set of a union. It’s in these moments—when our simple rules fall short—that we often learn the most.

Having grappled with the principles of counting elements in combined sets, you might be tempted to file this away as a neat bit of mathematical tidiness, a tool for solving textbook puzzles. But that would be a profound mistake. The Principle of Inclusion-Exclusion, in its elegant simplicity, is not just a formula; it is a fundamental pattern of thought, a lens through which we can understand the structure of the world. It reveals itself in the most unexpected corners of human endeavor, from the logic of our daily decisions to the intricate machinery of life itself. It is a beautiful example of how a single, simple idea can ripple outwards, providing clarity and insight in field after field. Let us go on a small tour and see for ourselves.

At its most tangible, the cardinality of a union is about managing resources and avoiding the simple error of counting things twice. Imagine a software company trying to figure out how many of its engineers know either Python or Java. If you simply add the number of Python programmers to the number of Java programmers, you have a problem: what about the polyglots who know both? You have counted them twice! To get the true total of unique individuals with these skills, you must subtract the size of this overlapping group. This is the Principle of Inclusion-Exclusion in its most direct form, a cornerstone of data analysis and workforce planning.

The same logic applies when a university designs its curriculum. If they want to know how many courses satisfy either a 'Quantitative Methods' requirement or an 'Ethics in Technology' designation, a simple sum will be misleading if some courses, by their interdisciplinary nature, carry both labels. In a world of overlapping categories—be they skills, course tags, or customer demographics—understanding the union is the first step toward a correct and rational accounting of what you truly have.

A particularly clean version of this appears in software architecture, when analyzing dependencies in a complex system of microservices. Here, services can be classified as "source" services (with no dependencies) or "terminal" services (which nothing depends on). If the system architecture guarantees that no service can be both a source and a terminal, then the two sets are disjoint. The intersection is zero! In this special case, the union is simply the sum. The total number of services that are either a source or a terminal is just $|S| + |T|$. This "Sum Rule" is the simplest form of inclusion-exclusion, the baseline from which we build when things get more complicated.

This principle of counting takes on a new life when we step from the world of definite sets into the world of uncertainty and chance. The formula for the cardinality of a union, $|A \cup B| = |A| + |B| - |A \cap B|$, has a direct and powerful twin in probability theory:

$P(A \cup B) = P(A) + P(B) - P(A \cap B)$

Here, $P(A \cup B)$ represents the probability of either event $A$ or event $B$ occurring. The logic is identical: the chance of $A$ or $B$ happening is the sum of their individual chances, minus the chance that they both happen together, which we have double-counted.

But we can push this connection further. What if we want to know the probability that neither $A$ nor $B$ happens? This corresponds to the event $A^c \cap B^c$. At first, this seems unrelated to the union. But here, a beautiful piece of logic known as De Morgan's Law comes to our aid, telling us that $A^c \cap B^c = (A \cup B)^c$. In plain English: "not A and not B" is the same thing as "not (A or B)". The number of outcomes where neither event occurs is simply the total number of outcomes minus the number where at least one of them occurs. This turns the problem on its head, allowing us to calculate the probability of an absence by first understanding the probability of a presence. It is a wonderfully counter-intuitive and powerful maneuver, bridging counting and probability.

In computer science, where efficiency is king, counting the size of a union is not always a simple matter of having two lists and comparing them. Imagine two massive databases, each held by a different research lab, Alice and Bob. They want to know if their datasets are identical, which is equivalent to asking if the size of their union is the same as the size of each individual set. Sending the entire database over the network to check would be prohibitively slow and expensive.

Here, the properties of sets and unions inspire brilliant algorithmic shortcuts. In a method known as randomized communication complexity, Alice and Bob can agree on a protocol without ever exchanging their full datasets. Alice can represent her set as a polynomial, $P_A(x)$, and send Bob not the whole polynomial, but its value at a single, randomly chosen point, $r$. Bob does the same for his set, $P_B(x)$, at the same point $r$. If their sets are different, the polynomials $P_A(x)$ and $P_B(x)$ will be different, and the probability that they happen to be equal at a random point $r$ is very small. If $P_A(r) = P_B(r)$, they can be reasonably confident their sets are the same. A mismatch tells them the union is larger than they thought. This isn't a foolproof method—there's a small chance of failure—but it's astonishingly efficient. It's a beautiful example of how abstract properties of sets and unions underpin modern algorithms for handling massive data.

One might think that this principle, born of simple counting, would lose its relevance in the rarefied air of abstract algebra. Nothing could be further from the truth. In group theory, mathematicians study the abstract nature of symmetry itself, using objects like groups, subgroups, and cosets. Yet even here, when we want to know the size of a collection formed by uniting two of these abstract structures, the same fundamental rule applies.

Whether we are calculating the number of unique permutations contained in the union of two subgroups of $S_4$, like the Klein four-group and a cyclic group, or in the union of two of their cosets, the procedure is the same: add the sizes of the individual sets and subtract the size of their intersection. The fact that this simple counting rule holds for such complex and non-intuitive objects is a testament to its fundamental nature. It is a thread of logic that runs through all of mathematics.

A particularly elegant extension appears when considering the union of all Sylow 3-subgroups of $S_4$. These are four distinct subgroups of order three. A key property is that any two of them only share a single element: the identity. So, when we unite them, we have the identity element, plus four sets of two unique, non-identity elements. The total count is $1 + 4 \times (3-1) = 9$. This is a direct application of inclusion-exclusion to multiple sets where the overlaps are minimal but crucial.

Perhaps the most breathtaking applications of set union cardinality are found not in mathematics or computers, but in biology. Our very survival depends on it.

Consider the human immune system. Your cells are constantly displaying fragments of their internal proteins, called peptides, on their surface using molecules encoded by HLA genes. T-cells patrol the body, inspecting these peptides. If they find a foreign one—from a virus, say—they trigger an immune response. Each HLA allele (a variant of an HLA gene) can bind to and present a specific set of peptides. Now, you inherit one set of HLA alleles from each parent. If you are heterozygous at an HLA locus, you have two different alleles. Because they are expressed co-dominantly, your cells use both to present peptides.

Let's model this. Assume, for simplicity, that the set of peptides presented by allele $A_1$ is completely different from the set presented by allele $A_2$. A person homozygous for $A_1$ can present only the set of peptides corresponding to $A_1$. But a heterozygous person can present the union of the peptides from $A_1$ and $A_2$. Since we assumed the sets don't overlap, the size of the union is the sum of the sizes of the two sets. The heterozygote can present twice as many distinct types of peptides as the homozygote! This "heterozygote advantage" is a dramatic evolutionary benefit. The larger union of presentable peptides gives the immune system a much wider surveillance net, increasing the odds of detecting a novel pathogen. Genetic diversity, in this view, is a biological strategy for maximizing the cardinality of a set union.

This theme continues at the ecosystem level in the cutting-edge field of metagenomics. Scientists now study the collective DNA of entire microbial communities, like the one in your gut. A fascinating discovery is the principle of "functional redundancy." Two people might have vastly different species of bacteria in their gut, but their microbiomes might be equally healthy because the two communities, despite being composed of different members, perform the same set of essential metabolic functions.

How can we quantify this? We can use a metric called the Jaccard Similarity Index, which is defined as $\frac{|A \cap B|}{|A \cup B|}$. It is a normalized measure of overlap, ranging from 0 (no overlap) to 1 (identical sets). By calculating the Jaccard index for the sets of bacterial species and comparing it to the Jaccard index for the sets of functional genes, we can see this redundancy in action. It is common to find a low species similarity but a very high functional similarity. The language of set intersections and unions provides the precise vocabulary needed to articulate and prove one of the most important concepts in modern ecology.

From counting programmers to fighting disease, the simple act of counting the elements in a union reveals itself as a deep principle about how systems, categories, and functions overlap and combine. It is a beautiful, unifying idea that reminds us how a single thread of logic can weave together the fabric of our world.