Introduction to Category Theory/Products and Coproducts of Sets

One of the most simple constructions in category theory is product. In this lesson we first define the product and coproduct of sets, with their natural functions projection and coproduct injection. Then we define subsets, set operations union and intersection, and partially ordered sets. We will also give two examples of product and coproduct that are quite different from the same constructions in sets.

Product of Sets

The cartesian product of two sets X (for example the points on an x-axis) and Y (for example the points on a y-axis), denoted X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y (e.g. the whole of the x-y plane):

$X\times Y=\{(x,y)\mid x\in X\;\mathrm {and} \;y\in Y\}.$

For example, the product of the thirteen-element set of standard playing card ranks {Ace, King, Queen, Jack, 10, 9, 8, 7, 6, 5, 4, 3, 2} and the four-element set of card suits {♠, ♥, ♦, ♣} is the 52-element set of playing cards {(Ace, ♠), (King, ♠), ..., (2, ♠), (Ace, ♥), ..., (3, ♣), (2, ♣)}. The product has 52 elements because that is the product of 13 times 4.

Projections

Projection maps

There are two natural functions associated with the product set $A\times B$ called projection maps. Projection map $\pi _{1}$ maps element $(a,b)$ to its first coordinate a. Likewise projection map $\pi _{2}$ maps element $(a,b)$ to its second coordinate b. If sets A and B are both nonempty, projection maps are surjective as the reader can easily verify.

You can see examples of product sets and projections at this interactive demonstration. Click the button labelled "generate a product and demonstrate its universality", and read down to the end of the text that introduces functions π1 and π2.

Coproduct of Sets

The coproduct of two sets A and B, denoted $A\oplus B$ or $A+B\$ or $A\coprod B$, is their disjoint union. Its elements are pairs (1,a) for every element a in A and pairs (2,b) for every element b in B:

$A\oplus B=\{(1,a)\ |\ a\in A\}\cup \{(2,b)\ |\ b\in B\}$.

If the set A has m elements and the set B has n elements, then their coproduct has m+n elements.

For example, the coproduct of {dog, cat, mouse} and {dog, wolf, bear} is the set {(1,dog), (1,cat), (1,mouse), (2,dog), (2,wolf), (2,bear)}.

Injections

Coproduct injections

There are two natural functions associated with the coproduct $A\coprod B$ called coproduct injections. Injection $\iota _{1}\$ maps elements a from the set A to elements (1, a) in the coproduct set. Likewise injection $\iota _{2}\$ maps elements b from the set B to elements (2, b) in the coproduct set. Coproduct injections are clearly injective.

You can see examples of coproduct sets and injections at this interactive demonstration. Click the button labelled "generate a coproduct and demonstrate its universality", and read down to the end of the text that introduces functions ι1 and ι2.

Subsets

If every member of set A is also a member of set B, then A is said to be a subset of B, written $A\subseteq B$ (also pronounced A is contained in B). Equivalently, we can write $B\supseteq A$, read as B is a superset of A, B includes A, or B contains A. The relationship between sets established by $\subseteq$ is called inclusion or containment.

If A is a subset of, but not equal to, B, then A is called a proper subset of B, written $A\subsetneq B$ (A is a proper subset of B) or $B\supsetneq A$ (B is proper superset of A).

Note that the expressions $A\subset B$ and $A\supset B$ are used differently by different authors; some authors use them to mean the same as $A\subseteq B$ (respectively $A\supseteq B$), whereas other use them to mean the same as $A\subsetneq B$ (respectively $A\supsetneq B$).

A is a subset of B

A is a subset of B

Example:

• The set of all men is a proper subset of the set of all people.
• $\{1,3\}\subsetneq \{1,2,3,4\}$
• $\{1,2,3,4\}\subseteq \{1,2,3,4\}$

The empty set is a subset of every set and every set is a subset of itself:

• $\emptyset \subseteq A$
• $A\subseteq A$

Set operations

Union

The union of two sets A and B, written A ∪ B, is the set that contains all the members of A and all the members of B (and nothing else). That is,

$A\cup B=\{x:x\in A\ \mathrm {or} \ x\in B\}\,\!$

As an example,

$\{1,\ 2,\ 3\}\ \cup \ \{2,\ 3,\ 4\}=\{1,\ 2,\ 3,\ 4\}\,\!$

Intersection

The intersection of two sets A and B, written A ∩ B, is the set that contains everything that is a member of both A and B (and nothing else). That is,

$A\cap B=\{x:x\in a\ \mathrm {and} \ x\in b\}\,\!$

As an example,

$\{1,\ 2,\ 3\}\ \cap \ \{2,\ 3,\ 4\}=\{2,\ 3\}\,\!$

Power set

A power set of a set is the set of all its subsets. A script 'P' is used for the power set. Note that the empty set and the set itself are members of the power set.

${\mathcal {P}}\{1,\ 2,\ 3\}=\{\varnothing ,\ \{1\},\ \{2\},\ \{3\},\ \{1,\ 2\},\ \{1,\ 3\},\ \{2,\ 3\},\ \{1,\ 2,\ 3\}\}\,\!$

Set operations are functions from the product of a powerset to a powerset.

$\operatorname {Union} :{\mathcal {P}}(X)\times {\mathcal {P}}(X)\to {\mathcal {P}}(X),\operatorname {Union} (A,B)=A\cup B$

Partially ordered sets

The Hasse diagram of the powerset of a three-element set {x, y, z}, ordered by inclusion.

Union and Intersection of sets {x,y} and {y,z}.

A partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., for all a, b, and c in P, we have that:

• a ≤ a (reflexivity);
• if a ≤ b and b ≤ a then a = b (antisymmetry);
• if a ≤ b and b ≤ c then a ≤ c (transitivity).

A set with a partial order is called a partially ordered set or poset. We will later see that poset is an example of category, where arrows are not functions.

A set is totally ordered if it's partially ordered and for all a and b

• either a ≤ b or b ≤ a.

The integers or the real numbers ordered by the standard less-than-or-equal relation ≤, are totally ordered sets.

Power set poset

Power set of a set ordered by inclusion is a partially ordered set (see the figures on the right), but it is not totally ordered if the base set has more than one element. For example neither of the subsets {x,y} and {y,z} contain the other. We will later show that the intersection of two sets is their categorical product in powerset poset, and the union of two sets is their categorical coproduct in powerset poset.

Divisibility poset

For example, 7 is a divisor of 42 because 42/7 = 6. We also say 42 is divisible by 7 or 42 is a multiple of 7 or 7 divides 42 or 7 is a factor of 42 and we usually write 7 | 42. For example, the positive divisors of 42 are 1, 2, 3, 6, 7, 14, 21, 42.

In general, we say m|n (read: m divides n) for positive integers m and n if and only if there exists an integer k such that n = km.

Some elementary properties:

• a | a (reflexive)
• If a | b and b | a, then a = b. (antisymmetric)
• If a | b and b | c, then a | c. (transitive)

Divisibility relation defines partial ordering on positive integers.

The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply as (a, b). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2 and gcd(5, 0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

The least common multiple (lcm) of two integers a and b is the smallest positive integer that is a multiple of both a and b.

Later we'll show that categorical product of two positive integers in divisibility poset is their least common multiple. In particular categorical product of two prime numbers is their normal product. We'll also show that coproduct of two integers in divisibility poset is their greatest common divisor.

Divisibility poset {1,2,3,5,6,10,15,30}

Divisibility poset {5,10,15,30}

Summary

We've given 3 examples of category theoretical products (without proofs) in this lesson

• product of sets
• product of elements of powerset (with poset structure)
• product of integers (with divisibility structure)

If you compare the diagrams of all three, can you see what they have in common? They all have 3 objects and 2 arrows pointing away from the middle one. Of course not every pair of outward-pointing arrows defines a product, there's something more to it. The intersection of sets A and B is the largest set that is contained in both. The least common multiple of a and b is the smallest integer divisible by both. Is the product of two sets also smallest or largest with respect to some property? Yes, and if you hang on with us through the next few lessons, you'll see how that property is defined in terms of nothing but arrows.

We've given 3 examples of coproducts in this lesson

• coproduct of sets
• coproduct of elements of powerset (with poset structure)
• coproduct of integers (with divisibility structure)

If you compare the diagrams, you see that they all have 3 objects and 2 arrows pointing towards the middle object. The difference from the product is that all arrows are reversed. This is called the duality principle. For every construction in category theory, there's an opposite construction with arrows reversed.

Related Resources

• w:Cartesian product
• w:Projection (mathematics)
• w:Coproduct
• w:Set
• w:Subset
• w:Union (set theory)
• w:Intersection (set theory)
• w:Power set
• w:Partially ordered set
• w:Order theory
• Jocelyn Paine's interactive demonstrations about products and coproducts of finite sets