This question must have been asked before but I couldn't find it anywhere.

Defining a mapping from two sets to the set of their Cartesian product seems seems pretty easy, unless I'm completely wrong:

$$f(A,B) = \{(a,b) \mid a∈A, b∈B\}$$

My question is - how do I define the inverse function? I want to define a function that takes a set of ordered pairs and returns the original sets. The process is clear to me, but I find it hard writing it mathematically.

Also what is a little unclear to me is the idea of inverting a pairing function: it takes two parameters and return one, so when you invert it you have two solutions from one parameter. How is it not a problem?

Hope I was clear, thanks in advance.


You can't. Firstly, one must be quite careful in talking about functions whose inputs could range over all sets; I am not an expert in set theory by any means, but I believe we still can refer to functions between proper classes (of which the collection of all sets is an example). Letting $\mathsf{Set}$ denote the class of all sets (in fact it can be given the extra structure of a category, though that doesn't really concern us here, I suppose), we can define the "Cartesian product" function (or rather, functor, if we want to use categories*), $P:\mathsf{Set}\times\mathsf{Set}\to\mathsf{Set}$ by $$\text{for any }(A,B)\in\mathsf{Set}\times\mathsf{Set},\quad P(A,B)=A\times B$$

and this is the function you are talking about, but certainly any set $X$, not all of whose elements are ordered pairs, will not be in the image of $P$, and therefore there is no inverse function $Q:\mathsf{Set}\to\mathsf{Set}\times\mathsf{Set}$ such that $Q(P(A,B))=(A,B)$ for all $(A,B)\in\mathsf{Set}\times\mathsf{Set}$, because it makes no sense to talk about "the original sets" of the sets $X=\{5,\pi\}$ or $Y=\{\mathbb{Z}\}$, for example, so we cannot define $Q(X)$ or $Q(Y)$.

*talking about a functor would also require defining $P$ on functions; we would do so by $$\text{for any }(f,g)\in\text{Hom}_{\mathsf{Set}\times\mathsf{Set}}((A,B),(C,D)),\qquad P(f,g)=A\times B\;\;\xrightarrow{\;\;f\times g\;\;}\;\; C\times D$$

  • $\begingroup$ It wasn't two clear but It won't work. I am trying to show that the correspondence between (AXB)XC and AXBXC is one to one and onto. I thought maybe I could find an inverse function. So, do you have any suggestions? $\endgroup$ – yotamoo Nov 28 '11 at 10:18
  • $\begingroup$ The best way to show something is one-to-one and onto is to construct an inverse. Show that, for any three sets $A$, $B$, and $C$, the functions $$f:(A\times B)\times C\to A\times B\times C$$ $$g:A\times B\times C\to (A\times B)\times C$$ defined by $$f\big(((a,b),c)\big)=(a,b,c)\qquad g\big((a,b,c)\big)=((a,b),c)$$ are inverse to each other. $\endgroup$ – Zev Chonoles Nov 28 '11 at 10:20
  • $\begingroup$ You can also ask your real question, about $A\times B\times C$ and $(A\times B)\times C$, in a separate post. $\endgroup$ – Zev Chonoles Nov 28 '11 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.