Can we have a converse Skolem paradox

Question

My information about models is not that great, so the question here is elementary in that field.

Can we have a model of ZF or ZF-regularity, in which there are two sets $x,y$ and such that no bijection exists between them, i.e. externally speaking, but at the same time we have the statement of existence of a bijection between them is satisfied in it?

I'm asking that because what is seen from outside of a model can conflict with what's satisfied in it! So for example a countable model of ZF does have a bijection between every set in it and the set $\omega$ of all finite von Neumann ordinals, and $\omega$ is a set in it also, but still the model does fulfill Cantor's theorem, and so it satisfy the statement that MOST sets are uncountable! While in fact (externally speaking) All of them are countable! This is the Skolem paradox. The explanation given is that the bijection is seen externally and it exists, but it is not in the model, i.e. its a subset of the model but not an element of the model. I'm asking if the converse can also happen? That's why I call it converse Skolem paradox.

My own personal guess is that NO such a paradox can exist. But I'm not sure of the satisfaction conditions in Models, and my knowledge about those is indeed trivial. That's why I asked this rather trivial question.

Answer 1

No, this cannot happen. And in fact this has nothing to do with $\mathsf{ZF}$: more broadly, if $M$ is any structure and $A,B$ are definable-with-parameters subsets of $M$, then if $M\models$ "There is a bijection between $A$ and $B$" we in fact have a bijection between $A$ and $B$.

(Note that this addresses the "translation" issue Alex Kruckman mentions in his comment above: if $M$ is an $\{\in\}$-structure, each $x\in M$ corresponds to the definable-in-$x$ set $\{y\in M: M\models y\in x\}$. Also note that when talking about $\{\in\}$-structures, the word "set" is dangerously overloaded since it can refer to elements of $M$ or to subsets of $M$ in the external sense. It's the latter meaning which is used here when I talk about "definable sets.")

The precise statement is:

Suppose $M$ is a structure, $A,B$ are definable-with-parameters subsets of $M$, and $\varphi$ is a formula with parameters in $M$ such that $$M\models\forall x\in A\exists!y\in B(\varphi(x,y))$$ and $$M\models\forall x_1,x_2\in A, y\in B(\varphi(x_1,y)\wedge\varphi(x_2,y)\rightarrow x_1=x_2).$$ Then in reality there is a bijection from $A$ to $B$.

And the proof is quite quick:

Consider the map sending $a\in A$ to the unique $b\in B$ such that $M\models \varphi(a, b)$.

This may seem slippery - what exactly are we using to conclude this? Well, we're using the fact that "$=$" is always interpreted as actual equality in a structure. If we allow structures which are allowed to interpret the $=$-symbol as an arbitrary equivalence relation (so: first-order logic without built-in equality), then this argument breaks down and indeed structures can think bijections exist when in fact they do not. E.g. such a structure can think that there is a bijection between a truly-two-element-set and a truly-one-element-set by virtue of thinking that the two elements of the truly-two-element-set are equal when they are in fact not.