# Y combinator, function composition

I am trying to understand Y combinators. Could you please explain why the following are equivalent

(Y (f ∘ g))
(f (Y (g ∘ f)))


(Y is a fixed point combination)

It depends on the notion of equivalence you are using.

Suppose we compare these terms according to their denotational semantics, on $\omega$-CPO domains. Denote with $F,G$ the semantics of the terms $f,g$. Thus, $F,G$ are Scott-continuous functions. Then, we have that the semantics of $Y(f \circ g)$ is, according to the Kleene's fixed point theorem

$$(1) = [\![ Y(f\circ g) ]\!] = \bigsqcup\{ \bot, F(G(\bot)),F(G(F(G(\bot)))),\ldots\}$$ where $\bigsqcup$ denotes the supremum / least upper bound.

Similarly, we get

$$(2) = [\![ f(Y(g\circ f) ]\!] = F(\bigsqcup\{ \bot, G(F(\bot)),G(F(G(F(\bot)))),\ldots\})$$

By continuity, we get $$(2) = \bigsqcup\{ F(\bot), F(G(F(\bot))),F(G(F(G(F(\bot))))),\ldots\}$$

One can then prove that $(1)=(2)$ by observing that any element of any one chain is bounded above by some element of the other chain. Indeed, we have $$\bot \sqsubseteq F(\bot), F(G(\bot)) \sqsubseteq F(G(F(\bot))), \ldots$$ estabilishing that $(1)\sqsubseteq(2)$. Further, $$F(\bot) \sqsubseteq F(G(\bot)), F(G(F(\bot))) \sqsubseteq F(G(F(G(\bot)))), \ldots$$ estabilishing that $(2)\sqsubseteq(1)$, concluding the proof.

Much less formally, the term $Y(f \circ g)$ expresses the infinite application $$f(g(f(g(\ldots))))$$ and, similarly, $Y(g \circ f)$ expresses $$g(f(g(f(\ldots))))$$ It is fairly natural, then, that applying a single $f$ on top of the second one results in the first one. The above domain-theoretic proof provides a formal justification of that.
{"ft_lang_label":"__label__en","ft_lang_prob":0.83143115,"math_prob":1.0000005,"size":2002,"snap":"2020-34-2020-40","text_gpt3_token_len":581,"char_repetition_ratio":0.11961962,"word_repetition_ratio":0.17880794,"special_character_ratio":0.3171828,"punctuation_ratio":0.12311558,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000007,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-09-21T09:49:51Z\",\"WARC-Record-ID\":\"<urn:uuid:639cb596-18cc-4316-b378-4011f2514cf6>\",\"Content-Length\":\"147714\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2f45311f-a8a0-40a9-b956-219728200a27>\",\"WARC-Concurrent-To\":\"<urn:uuid:ceb5be5d-f80c-46ad-87dc-9dee4d5fe1ab>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/84721/y-combinator-function-composition\",\"WARC-Payload-Digest\":\"sha1:QPOGNR6RDF4U5VHXL2PE3CXU3KU3VEU6\",\"WARC-Block-Digest\":\"sha1:CTUROKDHKON6ZCCYA2MTF62INYAQU43L\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-40/CC-MAIN-2020-40_segments_1600400201601.26_warc_CC-MAIN-20200921081428-20200921111428-00412.warc.gz\"}"}