# Non-constructible bijections in various set theories, do they exist?

Do there exist theorems of the form: "For every set theory there always exist at least two sets $$M$$ and $$N$$ between which there exists bijections and at least one bijection of those bijections cannot be explicitly constructed in that set theory."?

What I mean is, approximately, the following: If we have some set theory then that set theory is determined very much with the set of axioms of that set theory and with its notation.

So this question is really about: Could always $$M$$ and $$N$$ and bijections between them be found in concrete set theories but that they are such that, no matter how sophisticated the notation of that concrete set theory is, at least one bijection between $$M$$ and $$N$$ cannot be constructed explicitly in that set theory?

My expertise in set theory is mostly at the undergraduate level, and I wouldn´t be much surprised if theories dealing with questions like this one are already well-developed and constructed.

So, if you know how to easily explain to me the issues of this question and results of the form mentioned, like you would explain it to an average undergraduate, that would be nice.

• That is not true of "every" set theory. You need to further qualify which set theories you mean. Perhaps it works for set theories formulated in first order logic, that has infinite models. – Zuhair Al-Johar Nov 4 at 19:30
• An average undergraduate (and many professional mathematicians) might feel that the number of constructible real numbers is countable but the set of real numbers is uncountable. In that case not all bijections $x \mapsto x+r$ from the reals to itself are constructible. As noted below, within the “usual” universe of set theory (whatever that is) one can have a structure within which only things which can be constructed (sets, reals, bijections) exist. Then a bijection from the bigger “usual” universe might not be constructible in that inner constructible universe, but it wouldn’t exist there. – Aaron Meyerowitz Nov 4 at 19:52

The constructible universe is a set-theoretic universe built in a transfinite iterative cumulative hierarchy, in which sets are added to the hierarchy only because they are explicitly definable over what has been constructed earlier.

Gödel proved that all the usual ZFC axioms are true in the constructible universe, including the axiom of choice, as well as the continuum hypothesis and even the generalized continuum hypothesis. This universe is now intensely studied, and much is known about its fine structure.

But because every set in the constructible universe is in fact constructible, it seems to form a counterexample to the claim of your question. If two structures are isomorphic in the constructible universe, then the isomorphism is in fact constructible, since everything in this universe is constructible.

An interesting point to make about the constructible universe is the way that the axiom of choice is fulfilled in it. Namely, Gödel proved that the axiom of choice holds in the constructible universe $$L$$ precisely because everything is constructible, and so we can in effect make choices by choosing the simplest or earliest construction. In this set-theoretic universe, therefore, the axiom of choice holds precisely because things are totally regular and constructible, whereas some people have the idea that the axiom of choice is inherently about non-structured choices.

For example, in the constructible universe, there is a definable well-ordering of the real numbers $$\mathbb{R}$$, of complexity $$\Delta^1_2$$. See this related answer for an account of it.

• I can admit that I do not understand some of the terms in your answer, but, can it happen that $M$ and $N$ are constructible within some constructive universe but some bijection between them "lies outside" that universe, that is, that bijection is in some "larger" constructible universe, if you understand what I mean? – user147968 Nov 4 at 11:55
• Well, that kind of situation is also studied in set theory, and one can give many examples. For example, in any countable model of ZFC, one can find a larger model in which the previous versions of $\mathbb{Q}$ and $\mathbb{R}$ become order-isomorphic. Any set at all can be made countable by forcing. – Joel David Hamkins Nov 4 at 11:59
• Another counter-example is set theories with finite models, I mean standard finite models, those are so concrete. – Zuhair Al-Johar Nov 4 at 12:44