# 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. $$$$\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 power set to a power set. $$$$\text{Union}:\mathcal{P}(X) \times \mathcal{P} \to \mathcal{P}(X), \text{Union}(A,B) = A \cup B$$$$

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: $$$$X = \{1\}$$$$ The power set of $$X$$ is then: $$$$\mathcal{P}(X) = \{\varnothing,\{1\}\}$$$$ The product of $$\mathcal{P}(X)$$ is then: $$$$\mathcal{P}(X)\times\mathcal{P}(X) = \{(\varnothing,\varnothing),(\varnothing,\{1\}),(\{1\},\varnothing),(\{1\},\{1\})\}$$$$ Applying $$\text{Union}$$ to the $$\mathcal{P}(X)\times\mathcal{P}(X)$$ is: $$$$\mathcal{P}(X)\times\mathcal{P}(X) = \{(\varnothing,\varnothing)\mapsto\varnothing,(\varnothing,\{1\})\mapsto\{1\},(\{1\},\varnothing)\mapsto\{1\},(\{1\},\{1\})\mapsto\{1\}\}$$$$ As the result is a set, duplicates can be removed: $$$$\{\varnothing,\{1\},\{1\},\{1\}\} = \{\varnothing,\{1\}\}$$$$ Thus: $$$$\mathcal{P}(X)\times\mathcal{P}(X) \to\mathcal{P}(X)$$$$ 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

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. 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. 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. 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! 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. 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:

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

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? 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 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? 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 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? May 14 at 14:54