Introduction to Category Theory/Products and Coproducts of Sets

From Wikiversity
Jump to navigation Jump to search

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[edit]

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):

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.

Cartesian product graph.svg

Projections[edit]

Projection maps

There are two natural functions associated with the product set called projection maps. Projection map maps element to its first coordinate a. Likewise projection map maps element 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[edit]

The coproduct of two sets A and B, denoted or or , 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:

.

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[edit]

Coproduct injections

There are two natural functions associated with the coproduct called coproduct injections. Injection maps elements a from the set A to elements (1, a) in the coproduct set. Likewise injection 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[edit]

If every member of set A is also a member of set B, then A is said to be a subset of B, written (also pronounced A is contained in B). Equivalently, we can write , read as B is a superset of A, B includes A, or B contains A. The relationship between sets established by 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 is a proper subset of B) or (B is proper superset of A).

Note that the expressions and are used differently by different authors; some authors use them to mean the same as (respectively ), whereas other use them to mean the same as (respectively ).

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.

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

Set operations[edit]

Union[edit]

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

As an example,


Intersection[edit]

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

As an example,


Power set[edit]

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.

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


Partially ordered sets[edit]

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[edit]

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[edit]

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(ab), or sometimes simply as (ab). 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[edit]

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's in common? They all have 3 objects and 2 arrows pointing away from the middle one. Of course not every pair of outwards pointing arrows define a product, there's something more into it. Intersection of sets A and B is the largest set that is contained in both. Least common multiple of a and b is the smallest integer divisible by both. Is 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 duality principle. For every construction in category theory, there's an opposite construction with arrows reversed.

Related Resources[edit]