2
$\begingroup$

Given two sets $A$ and $B$ we define $B^A$ to be the set of all functions from $A$ to $B$.

Question. Is there a set $X$ with $X=X^X$?

One may ask the question: Why the hell do I have to ask this question twice? Yes, I already asked this question on math.stackexchange and I got an answer. The argument for proving that there is not a set $X$ with $X=X^X$ goes as follows:

Recall that a function $X\to X$ is really a subset $f\subseteq X\times X$ satisfying the requirement $$\forall a\in X.\ \exists! b\in X.\ (a, b)\in X.$$ Also, note that a pair $(a, b)$ is defined as the set $\{\{a\}, \{a, b\}\}$.

Now, suppose there is an $X$ with $X=X^X$. Since $\emptyset$ is obviously not the same as the set $\emptyset^{\emptyset}=\{\mathrm{id}_\emptyset\}$ and for $X$ with $|X| \geq 2$ we have $|X^X| \geq |2^X|> |X|$ and therefore $X\not = X^X$, we can infer that $|X|=1$. Let $X=\{\bullet\}$. This unique element $\bullet\in X$ has to be equal to the function $\mathrm{id}_X$ because we supposed $X$ to be the same as $X^X = \{\mathrm{id}_X\}$. According to our definitions $$\mathrm{id}_X=\{(\bullet, \bullet)\}=\{\{\{\bullet\}, \{\bullet, \bullet\}\}\}=\{\{\{\bullet\}\}\}.$$ But we have already said that $\mathrm{id}_X=\bullet$. Hence $\bullet=\{\{\{\bullet\}\}\}$ which is forbidden by the axiom of regularity.

Conclusion: If one codes functions as special subsets of the cartesian product and pairs as special sets, my question has an easy solution with the help of the axiom of regularity.
But in my opinion, these encodings are unnatural and do not convey the true nature of functions and pairs. That is why I wonder how to answer my question above when one regards functions and pairs as non-sets, that is to say as objects that are not sets.


Remark. I was not able to edit my old question because I asked it with a quest account and I got automatically logged out.

By the way: In his book "Analysis 1", Terry Tao proposed a natural axiom system of set theory with non-sets and in particular he comments:

"Strictly speaking, functions are not sets, and sets are not functions"

My question also can be viewed as asking if the problem whether there is a set $X$ with $X=X^X$ is decidable in the axiom system proposed by Terry Tao.

$\endgroup$
  • 1
    $\begingroup$ Is this answer insufficient? math.stackexchange.com/questions/1722182/… $\endgroup$ – Andres Mejia Apr 4 '16 at 17:35
  • $\begingroup$ @AndresMejia: The given answer in the thread you hyperlinked is correct but not what I am searching for. In this stackexchange question right here I am asking for an answer to my question when one treats functions and pairs as urelements. $\endgroup$ – Halteproblem Apr 4 '16 at 17:38
  • $\begingroup$ "But these encodings are unnatural and do not convey the true nature of functions and pairs" Here you have to define what you mean by "natural". I can only imagine you "taste". $\endgroup$ – Gustavo Apr 4 '16 at 17:40
  • $\begingroup$ @Gustavo: I thought one would instantly understand that this is only my opinion. I will clarify this in my question. Thanks for this comment. $\endgroup$ – Halteproblem Apr 4 '16 at 17:41
  • 1
    $\begingroup$ I can't understand why people are disliking my question without telling me what they do not like about my question or how I can improve my question ;-( I mean, I would willingly edit my question if there would be criticism. $\endgroup$ – Halteproblem Apr 4 '16 at 18:35
5
$\begingroup$

It all depends on how you axiomatize your primitive function objects, of course, buf if your formalism is okay enough with ill-foundedness to allow a function that solves $$ f : \{f\}\to\{f\} \text{ where } f(f) = f $$ then $\{f\}$ will work as your $X$.

On the other hand, it is also easy to see that if the set-theory part of your formalism is strong enough to allow Cantor's diagonalization argument to work, then the above $\{f\}$ is the only way to solve $X=X^X$.

$\endgroup$
  • $\begingroup$ Could you please explain the "easy to see"-part? $\endgroup$ – Halteproblem Apr 4 '16 at 17:47
  • 2
    $\begingroup$ @Halteproblem: $X=\varnothing$ clearly doesn't work, and if $X$ has at least two different elements, then Cantor's theorem concludes that no function $X\to X^X$ can be surjective. If $X=X^X$ then the identity function on $X$ would be such a surjection. Thus, $X$ must be a singleton, and its element must be the unique function from $X$ to $X$, which is exactly what the displayed condition says. $\endgroup$ – Henning Makholm Apr 4 '16 at 17:51
  • $\begingroup$ Ah, I understand. I thought you meant something more sophisticated when you said "if the set-theory part of your formalism is strong enough to allow Cantor's diagonalization argument to work, then the above $\{f\}$ is the only way to solve $X=X^X$". $\endgroup$ – Halteproblem Apr 4 '16 at 17:55
  • $\begingroup$ @Halteproblem: The hidden point here is that there are some set theories (most famously NF) where the diagonalization argument is not valid, and since I don't know which precise axioms you envisage for ensuring the existence such-and-such functions, I felt a need to hedge a bit. $\endgroup$ – Henning Makholm Apr 4 '16 at 17:58
  • 1
    $\begingroup$ @Halteproblem: If you want functions to be urelements (though "non-sets" would be a better description, since the name "urelement" tends to imply they have no observable properties other than identity), you need to furnish some axioms and logical vocabulary for applying and constructing functions, and I don't know how that is going to look. $\endgroup$ – Henning Makholm Apr 4 '16 at 18:01
2
$\begingroup$

Is there any reason that a cardinality argument doesn't work? If $|X|=0$ then $|X^X|=1>|X|$. If $|X|=1$ then $|X^X|=1=|X|$. Otherwise $|X| \geq 2$ so $|X^X| \geq |2^X|>|X|$. (Here I assume your set theory proves Cantor's theorem; this question is different in, say, Quine's NF.) So the only question is whether a function from a singleton set to itself can be the element of that singleton set. I don't think there is any way to avoid the regularity question in this case.

$\endgroup$
  • $\begingroup$ You write "So the only question is whether a function from a singleton set to itself can be the same as the singleton set itself". I think you actually mean: "So the only question is whether a function from a singleton set to itself can be the unique element of this singleton set" $\endgroup$ – Halteproblem Apr 4 '16 at 17:51
  • $\begingroup$ @Halteproblem That's right, I screwed up a bracket. $\endgroup$ – Ian Apr 4 '16 at 17:52

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.