I'm working my way through Enderton's Elements of Set Theory, and one of the theorems from the book has a final note that is giving me some trouble. The theorem is found on page 60, and is as follows:

Theorem 3Q Assume that $R$ is an equivalence relation on $A$ and that $F\colon A\to A$. If $F$ is compatible with $R$, then there exists a unique $\hat{F}\colon A/R\to A/R$ such that $$ (*)\qquad \hat{F}([x])=[F(x)]\quad\text{for all $x\in A$.} $$ If $F$ is not compatible with $R$, then no such $\hat{F}$ exists. Analogous results apply to functions from $A\times A$ into $A$.

For $F\colon A\to A$, we say $F$ is compatible with $R$ if for all $x,y\in A$, $$ xRy\implies F(x)RF(y). $$

I'm trying to formulate and prove the mentioned analogous results for $F\colon A\times A\to A$. I imagine the corresponding theorem would be

Theorem 3Q' Assume that $R$ is an equivalence relation on $A$ and that $F\colon A\times A\to A$. If $F$ is compatible with $R$, then there exists a unique $\hat{F}\colon A/R\times A/R\to A/R$ such that $$ (**)\qquad \hat{F}([x],[y])=[F(x,y)]\quad\text{for all $x,y\in A$.} $$ If $F$ is not compatible with $R$, then no such $\hat{F}$ exists.

but of course I may be wrong! I suppose the definition of compatibility requires some retooling, and the only sensible formulation I could think of was $F$ and $R$ are compatible if for any $x,y\in A$, $$ xRy\implies F(x,y)RF(y,x). $$

This is what I have so far, but as a warning, I don't think it really goes anywhere.

Based on this, I try to show that if $F$ is compatible with $R$, then such a $\hat{F}$ exists. Since $(**)$ requires that $(([x],[y]), [F(x,y)])\in\hat{F}$, I try to define $\hat{F}$ as $$ \hat{F}=\{(([x],[y]), [F(x,y)])\ |\ x,y\in A\}. $$ I want $\hat{F}$ to indeed be a function, so I consider the pairs $(([x],[y]), [F(x,y)])$ and $(([u],[v]), [F(u,v)])$ in $\hat{F}$. I would then like to have the implications \begin{align*} ([x],[y])=([u],[v]) &\implies [x]=[u]\wedge [y]=[v] \newline &\implies xRu\wedge yRv\newline &\implies F(x,u)RF(u,x)\wedge F(y,v)RF(v,y)\newline &\implies [F(x,u)]=[F(u,x)]\wedge [F(y,v)]=[F(v,y)]\newline &\implies \underline{\hspace{1in}} \newline &\implies [F(x,y)]=[F(u,v)] \end{align*}

However, I don't know what to put in the blank to make the desired implication follows, so perhaps my idea of compatibility or something else is wrong. Can someone please explain how to get to the proper formulation of the analogous results? Thanks!

  • 1
    $\begingroup$ I think the definition you are looking for says that $F: A \times A \to A$ is compatible with $R$ if for every pair $(a, b)$ and pair $(c, d)$ such that $a \, R \, c$ and $b \, R \, d$, $F(a, b) \, R \, F(c, d)$. $\endgroup$ – Zhen Lin Jan 3 '11 at 1:13
  • $\begingroup$ Thanks Zhen Lin, that certainly makes things work. $\endgroup$ – yunone Jan 3 '11 at 5:17

Your Theorem 3Q' is fine, but the condition you want is is not that $xRy\Longrightarrow F(x,y)RF(y,x)$.

Going back to the original Theorem 3Q, it might help to think about it this way: You have a map $F\colon A\to A$, and also a map $A\to A/R$. So we have a diagram: $$\begin{array}{ccc} A & \stackrel{F}{\longrightarrow} & A\\ \downarrow & & \downarrow\\ A/R & & A/R \end{array}$$ The compatibility condition means that you are able to put a function on the bottom row and get a commutative diagram: any two compositions of functions that start in the same place and end in the same place are equal. This is what gives the condition that two elements of $A$ that map to the same thing "going down" ($a$ and $x$ such that $[a]=[x]$) must map to the same thing if we go "forward then down" (so $F(a)RF(x)$ should hold).

Now consider the situation in 3Q'. Now you have a map $A\times A \to A$, and corresponding to it two maps: $A\to A/R$, and also $A\times A\to (A/R)\times(A/R)$ (the latter given by $(x,y)\mapsto ([x],[y])$. We now have: $$\begin{array}{ccc} A\times A & \stackrel{F}{\longrightarrow} & A\\ \downarrow & & \downarrow\\ (A/R)\times(A/R) & & A/R \end{array}$$ By analogy, the compatibility condition should be that any two pairs $(a,b)$ and $(x,y)$ that map to the same thing under $A\times A\to (A/R)\times (A/R)$ (that is, if $([a],[b])=([x],[y])$) should map to the same thing if we go "forward and down" (that is, $F(a,b)RF(x,y)$). This should suggest what condition to put down: note that $([a],[b]) = ([x],[y])$ if and only if $[a]=[x]$ and $[b]=[y]$. This is clearly necessary, then you need to show it will be sufficient.

From this, you should be able to write down a Theorem 3Q'' for an $n$-ary function (or even infinite arity).

  • $\begingroup$ Thank you Arturo, your diagrams were helpful in thinking about this in the more general case. $\endgroup$ – yunone Jan 3 '11 at 5:18

I discussed compatibility of operations with an equivalence relation in a post only a few hours old. Perhaps this algebraic perspective (congruences) may provide further motivational background.

  • $\begingroup$ Thanks Bill for your earlier post, thankfully it seems to be at a level I can understand. $\endgroup$ – yunone Jan 3 '11 at 5:20

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.