2
$\begingroup$

Given $f$ and $g$

$\forall x y. f(x) = f(y) \Longrightarrow f(g(x)) = f(g(y))$

Or equivalently

$ker\ f \subseteq ker\ (f \circ g)$.

Note: if $f$ is injective then this holds for any $g$.

Explanation/motivation: I'm a CompSci who is trying to become more theoretical, and have been playing with recursive functions. I've discovered that a useful property about fixpoints is entailed by the above property, (namely that $\exists h. f(\mu g) = \mu h$,) and I'm wondering:

  1. What has been discovered around functions of this shape.
  2. More generally, what area of maths should I be investigating to learn more.
Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Your initial statement is false. For example, if $f(x)=|x|$ and $g(x)=x+1$, then $f(x)=f(y)$ but $f(g(x))\neq f(g(y))$ for $x=1$ and $y=-1$. $\endgroup$
    – GH from MO
    Commented Jul 13, 2013 at 18:28
  • 1
    $\begingroup$ GH, I think you misunderstood; the text before the note is not an asserted proposition, it's a condition on $(f, g)$ that the OP wishes to consider. (Surely this could have been stated more clearly though.) $\endgroup$
    – Todd Trimble
    Commented Jul 13, 2013 at 20:30
  • 1
    $\begingroup$ Todd is right on both counts. $\endgroup$
    – Will
    Commented Nov 19, 2013 at 15:39

2 Answers 2

Reset to default
3
$\begingroup$

This question reminds me of Peter Freyd's work on fixed points. I forget the reference for that but Google will show you some of the follow-up work that other people have done since.

Fixed points of this nature live in domains, which live in categories that do not have pullbacks and equalisers, so the notion of kernel is not going to help you.

Be warned, however: there are results in this area that are extremely clever tricks, but such tricks are possibly only discovered once per decade. In the meantime, you will cover thousands of pages with calculations that lead to absolutely nothing.

The two examples I had in mind were Pataraia's and Bekić's fixed point theorems. (The late Georgian Dito) Pataraia's theorem is that in a DCPO $P$ with $\bot$, every monotone $f:P\to P$ has a least fixed point. As the comments indicate, the proof is very clever, very short and available in various places on the Web, though Pataraia never published it in a journal.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Your warning reminds me that I first learned Pataraia's fixed-point theorem through your book, Paul, and a beautiful gem of mathematical reasoning it is. A mathematical analogue of a truly great poem! $\endgroup$
    – Todd Trimble
    Commented Jul 13, 2013 at 20:35
  • $\begingroup$ I had exactly Pataraia's proof in mind when I gave my "warning", because I really kicked myself when I first heard it. I had thought of every single step of his argument myself beforehand, but had failed to put these steps together in the right order! $\endgroup$
    – Paul Taylor
    Commented Nov 19, 2013 at 16:56
  • $\begingroup$ I think I've spotted you -- maybe on the categories mailing list? -- also decrying the (perhaps all too typical?) approaches to fixed point theorems based on transfinite iteration. Is it correct to say, however, that big chunks of theory that you worked out on developing transfinite induction and recursion constructively, and that appear in your book, might not have been developed at all had you not missed Pataraia's proof at the time? (Not sure I've phrased all this optimally.) $\endgroup$
    – Todd Trimble
    Commented Nov 19, 2013 at 18:27
  • $\begingroup$ I'm not sure what your first sentence means, Todd, but the second one is correct. Also, it was a design principle of the book that everything that is done for categories is first done for posets in Chapter III. Curiously, some of it is more difficult, if not impossible, in particular my attempts to define well founded coalgebras for monotone functions. $\endgroup$
    – Paul Taylor
    Commented Nov 19, 2013 at 18:48
  • $\begingroup$ Well, what I had in mind in my first sentence is what you wrote here: mta.ca/~cat-dist/catlist/1999/harvey-friedman (post dated 30 Jan 1998). If I may: "For several years I was trying to prove (in an elementary topos, in particular without excluded middle, or the axiom of collection, which seems to me to be set-theoretic hocus pocus): Let (X, <=) be a poset with least element and directed joins, and s:X->X a monotone (not necessarily Scott continuous) function. Then s has a least fixed point... Because of my set-theoretic indoctrination, much as I rebelled against it, I set (cont.) $\endgroup$
    – Todd Trimble
    Commented Nov 19, 2013 at 19:40
2
$\begingroup$

Let me advertise clone theory.

Pick an underlying set A,and consider a family of functions f_i from (powers of) A to A, perhaps of different arities. If this family contains the projections (like the primitive recursive functions do) and is closed under function composition (as is the case with PR functions), the family is a clone of A.

One can study clones which preserve finitary relations R (so R becomes a subalgebra of A^n when augmented by this family of functions), as well as commuting functions, as well as studying relations between their kernels.

I think (from my limited point of view) a proper study of recursive clone theory has yet to be undertaken, and that your question fits into such a study.

The only published source I have read on clone theory exists in chapters 3 and 4 of "Algebras, Lattices, Varieties" by McKenzie, McNulty, and Taylor. There may be more appropriate treatments in the computer science literature, but you might find the general algebraic perspective of value.

Gerhard "Ask Me About System Design" Paseman, 2013.06.13

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .