# Set theory pertaining to category theory and functional programming

I'm reading an unfinished Introduction to Category Theory/Products and Coproducts of Sets and have come across the following:

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. $$\begin{equation}\mathcal{P}\{1,2,3\} = \{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\end{equation}$$ Set operations are functions from the product of a power set to a power set. $$\begin{equation}\text{Union}:\mathcal{P}(X) \times \mathcal{P} \to \mathcal{P}(X), \text{Union}(A,B) = A \cup B\end{equation}$$

I don't understand the last part.

To me a product of a power set should equate to a set of tuples where the first of the ordered pair is a subset from first power set and the second is a subset from the second power set. Whereas a power set is just a set of subsets.

How can this mismatch be explained or is it a mistake?

Taking on board the advice below:

If the set $$X$$ is a singleton value $$1$$, then: $$\begin{equation}X = \{1\}\end{equation}$$ The power set of $$X$$ is then: $$\begin{equation}\mathcal{P}(X) = \{\varnothing,\{1\}\}\end{equation}$$ The product of $$\mathcal{P}(X)$$ is then: $$\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) = \{(\varnothing,\varnothing),(\varnothing,\{1\}),(\{1\},\varnothing),(\{1\},\{1\})\}\end{equation}$$ Applying $$\text{Union}$$ to the $$\mathcal{P}(X)\times\mathcal{P}(X)$$ is: $$\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) = \{(\varnothing,\varnothing)\mapsto\varnothing,(\varnothing,\{1\})\mapsto\{1\},(\{1\},\varnothing)\mapsto\{1\},(\{1\},\{1\})\mapsto\{1\}\}\end{equation}$$ As the result is a set, duplicates can be removed: $$\begin{equation}\{\varnothing,\{1\},\{1\},\{1\}\} = \{\varnothing,\{1\}\}\end{equation}$$ Thus: $$\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) \to\mathcal{P}(X)\end{equation}$$ And so the set operation of $$\text{Union}$$, which is one of a family of set operations (a set of functions) is a function from the product of a power set to a power set

## 3 Answers

The notation $$f:E\times F \to G$$ means that $$f$$ is a function that needs two arguments, one from $$E$$, one from $$F$$, and the image is in $$G$$.

This is how the function $$\text{Union}$$ is defined: the two arguments $$A$$, $$B$$ are in $$\mathcal{P}(X)$$ and the image $$\text{Union}(A, B) = A\cup B$$ is in $$\mathcal{P}(X)$$.

• So is E E×F→G another way of writing f:(E,F)→G, which maps a pair of elements to another element in the same set? Or seen from another view a function that takes a single element and returns a partial functional expecting another element and returns another element? I guess I am confused as to the nature of an argument being a set or an element of a set. – potong May 14 at 14:51
• The notation $f:(E, F) \to G$ is wrong, you should use $f:E\times F \to G$. Also, in this notation, it is not required that $E = F$ or $E = G$, so the image is not necessarily an element of the "same set". Finaly please note that a pair of elements may be an incomplete description, and you should add if it is an ordered or unordered pair. – Nathaniel May 14 at 15:11
• To add a bit more details, see these notation: $f : E\times F\to G$ means that $f$ takes an element of $E$ and an element of $F$ and returns an element of $G$. $f:(A, B)\mapsto A\cup B$ means that if the arguments of $f$ are $A$ and $B$, then $f(A, B)$ equals $A\cup B$. Note that the arrow is not the same. – Nathaniel May 14 at 15:13
• Thanks, the language of mathematics can be tricky and then again obvious (once you know it), elegant but in the same breath esoteric! – potong May 14 at 15:43
• @potong: To borrow some programming terminology (which, of course, is ultimately borrowed from math again) $f: E \times F \to G$ is a type signature for $f$: it tells what kinds of arguments $f$ takes (i.e. whict sets they must belong to) and what kind of value the function evaluates to, but says nothing about how the actual result is computed. $f: (A, B) \mapsto A \cup B$, on the other hand, is a compact definition of how the return value of $f$ is calculated based on its arguments, but leaves the domain and codomain of the function (i.e. its "type signature") unspecified. – Ilmari Karonen May 15 at 11:42

As you have said, $$X\times Y = \{(x,y) \mid x\in X, y\in Y\}$$.

Thus, a function $$f:X\times Y\rightarrow Z$$ would get two arguments: one from $$X$$ and the other from $$Y$$, and output a value from $$Z$$. Formally, this is written as $$f((x,y))=z$$, and to reduce the number of brackets, its usually written as just $$f(x,y)=z$$.

In your case, $$f$$ is a function that computes the union: It takes two elements from $$A,B\in P(X)$$ and outputs $$A\cup B\in P(X)$$.

For clarity, the formal definition of $$P(X)$$ is given by:

$$\begin{equation}P(X):=\{A\mid A\subseteq X\}\end{equation}$$

Is the set of all subsets of $$X$$.

• Right, so it's a function from a pair of values to a single value and the function extracts the left and right values of the pair and applies them to the union function which fuses the pair into a single value. In the same way a pair of lists is fused to a single list by concatenation? – potong May 14 at 15:09
• Similarly, but the union operation makes sure that every element is in the set only once. In a list you can have any number and any order of elements (even with repetitions, like [5,1,5]), but a set doesn't have repetitions, and the order of the elements in it doesn't matter. What matters for a set is only whether an element is in it or not and not where that element is in the order, or how many times it was inserted to the set – nir shahar May 14 at 15:20
• Ah, so if a is in X and the product value (a,a) were supplied to the union function the return value would be a which again is within X? And for good measure if one of the ordered pairs was empty the result would be a singleton set again contained within X? – potong May 14 at 15:37
• the product of $P(X)\times P(X)$ are tuples of sets. I recommend taking a look at this page: en.wikipedia.org/wiki/Set_(mathematics) explaining the mathematics of sets – nir shahar May 14 at 15:48

The product of a power set to a power set is, indeed, "a set of tuples where the first of the ordered pair is a subset from first power set and the second is a subset from the second power set", to use your own words.

What you reported, though, is the definition of the Union operation. You can think of it as a function that associates an element of the set "tuples..." to an element of the set P(x). In particular, the Union operator, when applied to a pair of subsets, returns a single subset that is the union of the two subsets in the tuple.

• I think the penny has dropped but could you indicate a concrete example? – potong May 14 at 14:54