Trying to understand pathological solution(s) to $f:f\rightarrow f$

So here’s a really weird “functional equation” I came up with. Since a function $$g:X\rightarrow Y$$ can be defined as a subset $$g\subseteq X \times Y$$ such that for all $$x \in X$$, there is a unique $$y\in Y$$ such that $$(x,y)\in g$$. Since a function is then just a set, we could feasibly have a function who’s domain and range is itself. So I wanted to find a function $$f: f\rightarrow f$$.

The first example that comes to mind is $$\emptyset : \emptyset \rightarrow \emptyset$$, which works, but is kind of boring. For a while, I thought that might be the only solution. But then I came up with a really pathological set that I’m not sure what to make of, but I think it works.

Let $$A_0=\{0\}$$, we’ll say $$A_{n+1}=A_n \times A_n$$. So:

$$A_1=\{(0,0)\}$$ $$A_2=\big\{\big((0,0),(0,0)\big)\big\}$$ $$A_3=\Big\{\Big(\big((0,0),(0,0)\big),\big((0,0),(0,0)\big)\Big)\Big\}$$ $$\vdots$$

None of these satisfy the functional equation as $$A_n\not \subseteq A_n \times A_n = A_{n+1}$$. However, I did come up with a weird idea: could there be an $$A_\infty$$ that does satisfy the functional equation? It would look something like this:

$$A_\infty = \{(((\cdots(((0,0),(0,0)),((0,0),(0,0))),\cdots,(0,0)))\cdots)))\}$$

Where it has a sort of “infinite binary tree” structure to it.

Another way to interpret it, is that if $$a\in A_\infty$$ is the sole element of $$A_\infty$$, then $$A_\infty=\{a\}=\{(a,a)\}$$. Though one thing I don’t like about using this as a definition is that it ignores the $$0$$s “at the end” of the ordered pairs (whatever that means.) My other issue with it is that it seems to hinge on the assumption that $$A_\infty$$ exists, because it doesn’t construct $$A_\infty$$ directly.

I can’t really wrap my head around this set, and it doesn’t feel especially rigorous, but if it does seem to satisfy my functional equation. Since $$A_\infty=\{a\}=\{(a,a)\}$$, it seems to be the case that $$A_\infty = A_\infty \times A_\infty$$. Therefore, $$A_\infty : A_\infty \rightarrow A_\infty$$ seems to be a valid solution to the functional equation.

I don’t know what to make of this. While the solution to the functional equation $$f=\emptyset$$ makes complete sense to me, I can’t even tell if I’ve created a well-defined object with $$A_\infty$$. Is there a way to put this set on firm ground, or is it just complete nonsense?

I’m also curious about other solutions to this functional equation. I don’t think there are any other “normal” solutions besides $$\emptyset$$. We’d need the really weird property that $$f\subseteq f\times f$$, and I can’t think of any other sets that work. What other sets, if any, work?

• You may want to learn about the axiom of regularity, as a part of the most widely accepted set theory. Sep 10, 2021 at 17:38
• @Noah The specific solution the OP constructs is forbidden by regularity. However the current only answer circumvents it. Sep 10, 2021 at 17:43
• @Trebor Can you explain how I’ve violated the axiom? To my understanding, the axiom seems to say that all sets A contain an element x such that $A\cap a=\emptyset$. However, my set contains an ordered pair, not another set, and I’m not sure how to interpret the intersection of a set and an ordered pair. Sep 10, 2021 at 17:50
• An ordered pair (a,b) is encoded as the set {a,{a,b}} Sep 10, 2021 at 18:07
• @DavidLui ah, that makes sense. Thank you! Sep 10, 2021 at 18:08

Suppose $$f \subseteq f \times f$$. By the definition of $$\subseteq$$,

$$\forall x \in f \quad x \in f \times f$$

Thus

$$\forall x \in f \quad \exists a, b \in f \quad x = \langle a, b \rangle$$

The rank of a Kuratowski ordered pair is strictly greater than the rank of its elements. Thus

$$\forall x \in f \quad \exists a, b \in f \quad \operatorname{rank} x > \operatorname{rank} a$$

That is,

$$\forall x \in f \quad \exists a \in f \quad \operatorname{rank} a < \operatorname{rank} x$$

Thus, if there exists an element of $$f$$, there exists an infinite sequence of elements of $$f$$ with strictly decreasing rank. But ranks are well-ordered. Thus $$f$$ is empty.

Here's a well-defined solution. Define a sequence of sets as follows:

$$A_1 = \{0\}$$

$$A_{n+1} =\bigcup_{k=1}^n A_n\times A_k$$

And finally, define

$$A_{\infty} = \bigcup_{k=1}^\infty A_k$$

The set $$A_{\infty}$$ has the nice property that for all $$a,b\in A_{\infty}$$, the ordered pair $$(a,b)\in A_{\infty}$$. This implies that $$A_\infty\times A_\infty \subset A_{\infty}$$. So since any function $$f:A_{\infty} \to A_{\infty}$$ is defined as a subset of $$A_{\infty} \times A_{\infty}$$ with certain constraints, we have that $$f\subset A_{\infty}$$ and $$f:f\to f$$.

Now you can define any function you want from $$A_\infty$$ to itself! Some easy examples are

$$f_1(a) = 0$$

$$f_2(a)=a$$

$$f_3(a)=(a,a)$$

• Note that this is very different from what the OP suggests (their idea has $\vert A_\infty\vert=1$). Sep 10, 2021 at 17:42
• @NoahSchweber Good point. Maybe someone can supplement by adding an answer using the axiom of regularity to explain why the OP's construction is ill-founded. Sep 10, 2021 at 17:44
• This certainly provides a nontrivial setting in which you might hope to find solutions, but don't you also need the condition $f(f) \subset f$ to be satisfied in order to actually have $f:f \to f$? As far as I can tell none of your proposed functions meet that.
– jxnh
Sep 10, 2021 at 18:41
• In fact, there are no nontrivial solutions produced by this construction. More precisely than the condition $f(f) \subset f$ we need $f \subset f \times f$. The element of $A_\infty$ can be thought of as finite binary trees, and $f \subset f \times f$ is never true for any nonempty subset of $A_\infty$ because a tree of minimum height in $f$ is not in $f \times f$.
– jxnh
Sep 10, 2021 at 19:32

Working without Regularity, there may exist sets $$x=\{x\}$$.

Then under Kuratowski's definition of ordered pairs, $$(x,x)=\{\{x\},\{x,x\}\}=\{\{x\}\}=\{x\}=x\in\{x\}=x$$

So $$x:x\to x$$ sending $$x\mapsto x$$ would be a function: $$x\times x=\{(x,x)\}=\{x\}=x$$ and $$x\times x$$ itself is a function from $$x$$ to $$x$$.

In your construction, if you take $$A_0=x$$ instead of $$A_0=\{0\}$$, then $$A_\infty=x$$ as well.

Using the definition for ordered pairs from above, we can visualise the sets $$A_n$$ as trees.

For example, here is $$A_1$$, where an arrow $$x\to y$$ stands for $$y\in x$$:

and for $$A_{n+1}$$ we have a tree that looks identical if we don't expand the sets $$A_n$$:

When we do expand the sets $$A_n$$, we get a more complex tree:

We can describe this operation of going from $$A_n$$ to $$A_{n+1}$$ as taking the tree for $$A_1$$, and replacing each bottom node of the tree $$A_n$$ with a copy of $$A_1$$. If we use $$T_n$$ to name the tree for $$A_n$$, then it is clear that we can embed the tree $$T_n$$ into $$T_{n+1}$$. Therefore, without loss of generality we can find some trees $$S_n$$ isomorphic to $$T_n$$ such that $$S_0\subset S_1\subset S_2\subset S_3\subset\dots$$.

This way we can formalise what it means to construct $$T_\infty$$, namely we can let $$T_\infty$$ be the tree $$\bigcup_{n\in\Bbb N} S_n$$, which is probably the "infinite binary tree" that you refer to in your question.

To see why it's impossible to associate a set to such a tree $$T_\infty$$ when we assume the Axiom of Regularity, note that there exist an infinite branch in $$T_\infty$$: starting from the root of the tree (the top node in my pictures), going all the way down.

Let's take such a branch $$x_0\to x_1\to x_2\to x_3\to\cdots$$, then by $$x\to y$$ being equivalent to $$y\in x$$, we see that we get an infinite chain $$\cdots \in x_3\in x_2\in x_1\in x_0$$. Hence, the set $$X=\{x_n\mid n\in\Bbb N\}$$ has no $$\in$$-minimal element, since $$x_{n+1}\in x_n\cap X$$ for every $$n\in\Bbb N$$.

(I know, the above pictures can be simplified a lot, by noting that $$\{0,0\}=\{0\}$$, thus $$(0,0)=\{\{0\}\}$$, but I only remembered that when I was halfway through drawing them...)

Inspired by user76284:

Suppose that we have some set $$f \subseteq f \times f$$. I claim $$f$$ is empty. That is, I claim that for all $$x$$, $$x \notin f$$.

This can be proved by $$\in$$-induction. The precise statement of the induction will be $$\forall x, x \notin f \land x \cap f = \emptyset$$.

Suppose that for all $$y \in x$$, $$y \notin f$$ and $$y \cap f = \emptyset$$. Then clearly $$x \cap f = \emptyset$$. So it remains to show that $$x \notin f$$.

Suppose $$x \in f$$. Then we can write $$x = (a, b) = \{\{a\}, \{a, b\}\}$$ for some $$a, b \in f$$. Then we have $$\{a\} \cap f \neq \emptyset$$. But $$\{a\} \in f$$; contradiction. Therefore, $$x \notin f$$.

If you take another definition of ordered pairs as $$(a, b) = \{a, \{a, b\}\}$$, the proof is even shorter. As long as you take a definition of ordered pairs such that for all $$a, b$$, there is some sequence $$s_1, s_2, ..., s_n$$ such that $$a \in s_1 \in s_2 \in ... \in s_n \in (a, b)$$, this proof goes through (in a modified fashion).