Equinumerous Sets: Defining D_x

[Andrei1]

For any sets \(\displaystyle A,\ B,\ C\), \(\displaystyle ^{(A\times B)}C\sim ^A\left(^BC\right).\)

First I could not find a formula for the required function.
Then I defined the set \(\displaystyle D_x=\{(y,z)\in B\times C\mid f(x,y)=z\},\) where \(\displaystyle f\colon A\times B\to C.\) What do you think?

 

[Evgeny.Makarov]

For any sets \(\displaystyle A,\ B,\ C\), \(\displaystyle ^{(A\times B)}C\sim ^A\left(^BC\right).\)

Oh, it's such a nice formula that has applications to different areas of mathematics. Some of us could probably write an article on it.

First I could not find a formula for the required function.

This is not clear. What do you mean by the required function? What kind of formula you were looking for?

Then I defined the set \(\displaystyle D_x=\{(y,z)\in B\times C\mid f(x,y)=z\},\) where \(\displaystyle f\colon A\times B\to C.\) What do you think?

This is fine, but what are you going to do with $D_x$?

The idea is to construct a bijection between the two sets. Take an $f\in{}^{A\times B}C$. We'll build a $g\in{}^A({}^BC)$. Let $x\in A$ and $y\in B$. Then $g(x)(y)\stackrel{\text{def}}{=}f((x,y))$. By $(x,y)$ I denote an ordered pair in $A\times B$; hence the double parentheses. You need to show that this is a bijection.

 

[Andrei1]

I proved \(\displaystyle ^A(B\times C)\sim^AB\times ^AC.\) I found the function \(\displaystyle F(f)=(g\circ f,\ h\circ f)\) for some \(\displaystyle g\) and \(\displaystyle h.\) I named this a formula.

I have never used the notation \(\displaystyle g(x)(y)\). \(\displaystyle D_x\in ^BC\). It was I try.

 

[Deveno]

Oh, it's such a nice formula that has applications to different areas of mathematics. Some of us could probably write an article on it.

This is not clear. What do you mean by the required function? What kind of formula you were looking for?

This is fine, but what are you going to do with $D_x$?

The idea is to construct a bijection between the two sets. Take an $f\in{}^{A\times B}C$. We'll build a $g\in{}^A({}^BC)$. Let $x\in A$ and $y\in B$. Then $g(x)(y)\stackrel{\text{def}}{=}f((x,y))$. By $(x,y)$ I denote an ordered pair in $A\times B$; hence the double parentheses. You need to show that this is a bijection.

You mean we can consider functions of two variables one variable at a time? I'm shocked! Who knew?

 

[Evgeny.Makarov]

I proved \(\displaystyle ^A(B\times C)\sim^AB\times ^AC.\) I found the function \(\displaystyle F(f)=(g\circ f,\ h\circ f)\) for some \(\displaystyle g\) and \(\displaystyle h.\)

You probably mean that $g:B\times C\to B$ and $h:B\times C\to C$ are left and right projections, respectively.

I named this a formula.

I would call it the definition of a bijection $F$ (for the given two sets, not a bijection in general). The word "formula" is too nonspecific.

I have never used the notation \(\displaystyle g(x)(y)\).

If $g$ is a function that returns functions, then it is only natural to denote consecutive application by $g(x)(y)$. If it were up to me, I would drop parentheses and denote function application by juxtaposition. ("Juxtaposition in mathematics, adjacency of factors with the absence of an explicit operator in an expression, especially for multiplication" -- Wikipedia.)

\(\displaystyle D_x\in ^BC\). It was I try.

I see now what you meant. The only remark is that $D_x$ depends not just on $x$, but first of all on $f$, so it could be denoted, say, by $D_x(f)$. It's $f$ with the first argument fixed to $x$. Then you could define the bijection as follows:
\[
F(f):x\mapsto D_x(f)
\]
or
\[
F(f)(x)=D_x(f)
\]
I am not sure it is necessary to introduce the notation $D_x(f)$ because it is used only once.

Another remark: If we view a function as a set of pairs, then a function in ${}^{A\times B}C$ consists of tuples of the form $((x,y),z)$ where $x\in A$, $y\in B$ and $z\in C$. On the other hand, a function in ${}^A({}^BC)$ consists of tuples of the form $(x,(y,z))$. So the bijection just reorders parentheses in each element of a function.

However, I would not commit to the view of functions as sets of pairs and instead define the required bijection in terms of function applications, as I did in post #2:
\[
\begin{aligned}
&F:{}^{A\times B}C\to {}^A({}^BC)\\
&Ffxy=f(x,y)\\
\end{aligned}
\]

 

[mathbalarka]

You mean we can consider functions of two variables one variable at a time? I'm shocked! Who knew?

I believe that comes from the basics of lambda calculus, also known as currying.

 

[Deveno]

In reading this thread, I noticed that Evgeny proposed the map:

$F: { }^{A\times B}C \to { }^A({ }^BC)$

as:

$F(f) = g$, where $g(a) = f(a,-)$

Is this a bijection?

Well, I propose the following map:

$G: { }^A({ }^BC) \to { }^{A\times B}C$

given by:

$G(h) = k$ where $k(a,b) = [h(a)](b)$.

Let's compute $F\circ G(h)$:

$F(G(h)) = F(k)$ and we have (for all $a \in A$):

$F(k)(a) = k(a,-) = h(a)$, that is: $F(G(h)) = h$

(both $k(a,-)$ and $h(a)$ take $b$ to the same element of $C$ at every $b \in B$).

On the other hand:

$G \circ F(f) = G(F(f)) = G(g)$ and for every $(a,b) \in A \times B$:

$G(g)(a,b) = [g(a)](b) = f(a,b)$, that is: $G(F(f)) = f$.

Evidently: $G = F^{-1}$, so $F$ is a bijection.

**********

Something deeper is going on, here, though, and I'd like to attempt to explain. Sets are ubiquitous through mathematics, and it turns out that most of what is interesting about sets can be explained in terms of the functions between them. This is a perfect case in point: to show two sets are "the same size", we display a bijection (a certain kind of function between them which "compares size").

A function is actually 3 sets:

the domain, the co-domain, and a certain subset of their cartesian product.

Functions are *directed", due to the uniqueness of any image, functions can "shrink" a domain set, but they cannot "expand" it. This creates a kind of "flow", represented by an arrow:

$f:A \to B$, or: $A \stackrel{f}{\to} B$

Now, given a set $X$, we can think about functions to or from $X$ Let's talk about "from" first. Given any other set (say $A$), we can form a third set:

${}^XA$ of all functions from $X$ to $A$.

The nifty thing is: given any function $f:A \to B$, we get a function:

${}^XA \to {}^XB$ in a fairly "obvious" way:

If $g \in {}^XA$, we can form $f\circ g$ (post-composition with $f$).

So the mapping $X \to {}^XA$ not only gives us a set, it gives us a new function for any function $f:A \to B$.

"To" acts in a similar fashion, but we use "pre-composition" so now for every function $f: A \to B$, we get a function:

${}^BX \to {}^AX$ (using pre-composition reverses the "flow" of $f$).

It should be obvious that the "from" version preserves composition of functions, given:

$A \stackrel{f}{\to} B \stackrel{f'}{\to} C$

We get the composition:

$(f' \circ f)(-) = [f'\circ (-)]\circ [f\circ(-)]$

that is: $(f'\circ f)\circ g = f'\circ (f\circ g)$

and that "to" does the same thing, but reverses the order. Hold those thoughts.

We have a similar situation when we "pair" sets (take the cartesian product). Given a set $Y$, and any other set, $A$, we can form a new set $A \times Y$. And, given a function $f: A \to B$, we can form a new function $g: A \times Y \to B \times Y$ in a fairly obvious way:

$g(a,y) = (f(a),y)$.

I leave it to you, dear reader, to show that a similar idea holds using $A \to Y \times A$.

Now, for notational reasons the set of mappings ${}^AB$ is usually denoted:

$\text{hom}(A,B)$

If we call the assignment (sets to sets, and functions to functions) $(X,Y) \to \text{hom}(X,Y)$ by the letter $G$, and the assignment (similarly) $(X,Y) \to X \times Y$, by the letter $F$, what the bijection we established above says is:

$\text{hom}(F(X,Y),Z) \cong \text{hom}(X,G(Y,Z))$

and what this "means" (in a loose sort of way) is that "taking the cartesian product" and "forming the exponential set" are in a sense, partners. It actually means something more, because the bijection we established above is actually "natural", there is a technical way of describing this, but what it boils down to is "it's the bijection you would obviously come up with if you are very lazy".

 

[Andrei1]

However, I would not commit to the view of functions as sets of pairs and instead define the required bijection in terms of function applications, as I did in post #2:
\[
\begin{aligned}
&F:{}^{A\times B}C\to {}^A({}^BC)\\
&Ffxy=f(x,y)\\
\end{aligned}
\]

I am allmost finishing to read "How to prove it" by Daniel Velleman. He teaches that a function is some set of order pairs. I am not willing to deviate from this definition.
Now I have come to the function \(\displaystyle F\colon ^{(A\times B)}C\to ^A\left(^BC\right)\) defined as follows:
\(\displaystyle F(f)=\{(x,D)\in A\times ^BC\mid D=\{(y,z)\in B\times C\mid f(x,y)=z\}\}\)

 

[Deveno]

I am allmost finishing to read "How to prove it" by Daniel Velleman. He teaches that a function is some set of order pairs. I am not willing to deviate from this definition.
Now I have come to the function \(\displaystyle F\colon ^{(A\times B)}C\to ^A\left(^BC\right)\) defined as follows:
\(\displaystyle F(f)=\{(x,D)\in A\times ^BC\mid D=\{(y,z)\in B\times C\mid f(x,y)=z\}\}\)

Yes, a function can be defined as a certain subset of the cartesian product of its domain and co-domain. This is particularly useful when seeing functions as a special kind of relation (which is an *arbitrary* such subset).

However, in much of mathematics, you will see the following usage:

$x \mapsto f(x)$

and to make things even more confusing, usually just the image is referred to when talking about $f$.

AND...putting things in this form can get really confusing, requiring you to wade through lots of syntactical decisions.

For example, if you are going to write your function:

$F:{}^{A \times B}C \to {}^A({}^BC)$

this way, you are not quite doing it right, you should write:

$F = \{(f,g) \in {}^{A \times B}C \times {}^A({}^BC): g = \{(x,D) \in A \times {}^BC:D = \{(y,z) \in B \times C: z = f(x,y)\}\}\}$

This does not make it any clearer what it going on, which is essentially this:

Path 1: start with a pair $(x,y)$ and end up with $z = f(x,y)$

Path 2: start with $x$ and induce a function $g_x$ which starts with $y$ and ends up with $z = g_x(y) = f(x,y)$.

For example, binary operations are functions:

$S \times S \to S$ (examples: addition, or multiplication).

To write these as triples $(s_1,s_2,s_3)$ is often notationally inconvenient; in fact, it is often simpler to fix an element $a\in S$, and instead of considering the binary operation:

$\ast:S \times S \to S$ given by $\ast(s_1,s_2) = s_1\ast s_2$

consider the family of (single-valued) functions:

$f_a:S \to S$ given by:

$f_a(s) = a \ast s$.

I daresay you *will* encounter constructions like these and it will be to your advantage to at least *recognize* what is going on.