4
$\begingroup$

The well-known inclusion-exclusion principle states that for two finite sets $A$ and $B$, $$|A| + |B| = |A \cap B| + |A \cup B|$$

It is also a simple result that given positive natural numbers $a$ and $b$, $$ab = \gcd(a, b) \cdot \operatorname{lcm}(a, b)$$

I was struck by the similarity between these two formulae, especially considering that $\cap$ and $\cup$ are the meet and join operations in the poset of sets ordered by inclusion, while $\gcd$ and $\operatorname{lcm}$ are the meet and join operations in the poset of numbers ordered by divisibility. Is there some general principle at work here?

$\endgroup$
4
  • $\begingroup$ Residuated lattices might have something to with this, see en.wikipedia.org/wiki/Residuated_lattice $\endgroup$
    – Reveillark
    Commented Aug 6, 2016 at 22:36
  • 2
    $\begingroup$ There is also $x + y = \min(x,y) + \max(x,y)$ $\endgroup$
    – Steven Alexis Gregory
    Commented Feb 22, 2017 at 8:06
  • $\begingroup$ @steven if we look at numbers as multisets over the domain {1}, then IEP applies again $\endgroup$
    – lily
    Commented Feb 22, 2017 at 16:00
  • $\begingroup$ @IstvanChung - there is also a connection to finite deminsional convolution algebras. $\endgroup$
    – Steven Alexis Gregory
    Commented Feb 22, 2017 at 21:06

1 Answer 1

Reset to default
1
$\begingroup$

I don't know if this counts as a general principle, but we can view the gcd--lcm result as an application of the IEP if we think of $a$ and $b$ as multisets of the factors in their respective prime decompositions. When conceived of in this way, the the union of these multisets is the lcm and the intersection is the gcd.

For instance,

$$24 \to \{2,2,2, 3\} =: A$$ $$30 \to \{2,3,5\}=: B$$ $$\mathrm{lcm}(24,30) =120 \approx A\cup B = \{2,2,2,3,5\}$$ $$\mathrm{gcd}(24,30) = 6 \approx A \cap B = \{ 2,3 \}$$

Perhaps these multisets provide the elements to which we might apply the information in @Reveillark's comment.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .