# Reasons behind the analogy between “order of groups” and “sets” (if it exists).

I had this question which I had to prove:

Let G be a group and H,K < G. Then if H,K are ﬁnite subgroups,
$$|HK| = |H||K|\div|H\cap K|$$

As I was trying to solve this question, it struck my mind that something of the form: $$|H \cup K| = |H|+|K|-|H\cap K|$$ is true for sets.

Analogies I found

1. $$-$$ (in set expression) $$\leftrightarrow \div$$ (in group expression)
2. $$+$$ (in set expression) $$\leftrightarrow \times$$ (in group expression)
3. Take the order of all separate sets seen in the equality for sets to obtain the corresponding equality for groups.
4. $$\cup$$ (in set expression) $$\leftrightarrow$$ group operation (in group expression)

My curiosity

Do these analogies exist always, or is it just an accidental similarity? If they do, then what are the reasons behind such a similarity.

Thanks

• What does $H+K$ mean for sets? If it means the symmetric difference, then your expression is wrong. Unless you meant $H\oplus K = (H\cup K) - (H\cap K)$. – Arturo Magidin Jun 16 at 4:05
• The set containing all the elements of $H$ and $K$ is $H\cup K$ – J. W. Tanner Jun 16 at 4:18
• I don't agree with the downvote. I think this is a deep question, or at least one with significant implications. A wishy-washy attempt at an answer: "dimension" or "degrees of freedom" can often be counted combinatorially (hence the inclusion-exclusion principle), but in fact they function more like the logarithm of actual cardinality. For instance, with an algebraic variety defined over $\Bbb F_q$, the cardinality is a polynomial of degree $n$ in $q$. (Note if one takes logs of both sides of $|HK|=|H||K|/|H\cap K|$, one gets the an equation with $\pm$ instead of $\times,\div$.) – runway44 Jun 16 at 4:47
• If by $H+K$ you mean the union, then your equation is incorrect. You have the union on the left, but the symmetric difference on the right. In short, your “set” equation is incorrect. Given that it is incorrect, asking for whether the “similarity” reflects something deeper starts from the wrong assumption: there is no similarity here, only an incorrect equation. – Arturo Magidin Jun 16 at 5:16
• What do you think the symbol $|\cdot |$ means? $n(A)$ is nonstandard notation, at best. If you mean the cardinality, then you write $|A\cup B| = |A|+|B| - |A\cap B|$ (which only holds for finite sets). – Arturo Magidin Jun 16 at 5:55

## 2 Answers

Note: Question has now been edited; first paragraph applies to original write-up.

Your “set equation” is wrong; if by $$H+K$$ you mean, as you say in comments, “the set of all elements of $$H$$ and of $$K$$ combined”, then that’s nothing more than $$H\cup K$$. But then your “equation” is: $$H\cup K = H\cup K - H\cap K$$ which is incorrect: the left hand side is the union, the right hand side is the symmetric different, the set of all elements that are in $$H$$ or in $$K$$, but not in both.

There is also a serious problem in that $$HK$$ is not in general the smallest subgroup containing both $$H$$ and $$K$$; that is, it does not play the same role as the union for sets (the least upper bound in the corresponding lattice).

At best, you could (if you look at this sideways) think of the equation $$|HK| = \frac{|H|\,|K|}{|H\cap K|}$$ as an instance of “inclusion/exclusion”, in which case the corresponding set equation would be $$|H\cup K| = |H| + |K| - |H\cap K|.$$

(Note that both equations only hold in the finite case; for groups, the correct equation which holds in the sense of cardinality is $$|HK|\,|H\cap K| = |H|\,|K|$$; for sets, the corresponding equation would be $$|H\cup K| + |H\cap K| = |H| + |K|$$; h/t to Paul K for pulling my ears and reminding me of it.)

It’s a stretch. What you have is two instance of overcounting-adjusting. In the latter case, you count everyting, then remove the things you counted twice. In the former case, you are counting all products (the cardinality of $$|HK|$$) by counting all possible pairs (the product $$|H||K|$$), and then dividing by the number of repetitions of the count. They are both very standard counting techniques, though the one for sets is when you are adding things, and the one in groups is when you are combining things. They both involve overcounting, then adjusting the overcount by a calculable quantity to get the correct result.

• Are you sure the set equation is false in the infinite case if we put $\lvert H \cap K \rvert$ on the left hand side? – Paul K Jun 16 at 6:07
• @PaulK: You mean, $|H\cup K| + |H\cap K| = |H| + |K|$? Ah, yes, that would work. – Arturo Magidin Jun 16 at 6:21

It turns out that one of these two facts can be seen as a special case of the other.

If $$S$$ is a set, we can make the power set $$G=\mathcal{P}(S)$$ into a group using the symmetric difference $$A\Delta B = (A-B)\cup (B-A)$$. (to see quickly that this is a group, note that it is isomorphic to the vector space $$\mathbb{F}_2^S$$ under addition)

Then, if $$A,B\subset S$$, we have subgroups $$H=\mathcal{P}(A)$$ and $$K=\mathcal{P}(B)$$ of $$G$$. The counting formula for subgroups gives us:

$$|H\Delta K| \cdot |H\cap K| = |H| \cdot |K|$$

It is straightforward to verify that $$H\Delta K = \mathcal{P}(A\cup B)$$ and $$H\cap K = \mathcal{P}(A\cap B)$$. So this gives us:

$$|\mathcal{P}(A\cup B)|\cdot|\mathcal{P}(A\cap B)| = |\mathcal{P}(A)|\cdot|\mathcal{P}(B)|$$

But this is just:

$$2^{|A\cup B|} \cdot 2^{|A \cap B|} = 2^{|A|} \cdot 2^{|B|}$$

...which is equivalent to:

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

In general, I think we can see both of these facts as special cases of something like the excision theorem for calculating the Euler characteristic, but I haven't worked out the details. (the Euler characteristic is tightly related to the principle of inclusion/exclusion, we can maybe use Eilenberg-MacLane spaces to bring groups in)