3
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Just to clarify: Suppose $M$ is an arbitrary model of ZF, and $x$ and $y$ are elements of $M$. When you talk about "a bijection between $x$ and $y$", do you mean a bijection between $\{z\in M\mid M\models z\in x\}$ and $\{z\in M\mid M\models z\in y\}$? $\endgroup$ Commented Jun 30, 2020 at 17:36
  • $\begingroup$ @AlexKruckman, Yes! $\endgroup$
    – Zuhair
    Commented Jun 30, 2020 at 17:53
  • 4
    $\begingroup$ By the way, I did not cast the downvote or the close vote. It's a very reasonable question! $\endgroup$ Commented Jun 30, 2020 at 17:54
  • 1
    $\begingroup$ @AlexKruckman Indeed, and the answer to this question in fact can be fruitfully traced back to a basic rule in our semantics. I suspect the negative response is from someone unfamiliar with the topic. $\endgroup$ Commented Jun 30, 2020 at 17:56

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ As written, this depends being able to express "There is a bijection between $A$ and $B$" in first-order logic. That's no problem in set theory, where we can quantify over functions, but it doesn't work in general structures. I think the more general explanation is that if $A$ and $B$ are definable (with parameters) sets and $f\colon A\to B$ is a definable (with parameters) function, and if $M\models $"$f$ is a bijection ", then $\widehat{f}$ is actually a bijection. $\endgroup$ Commented Jun 30, 2020 at 17:59
  • $\begingroup$ @AlexKruckman Yes, I was being sloppy. I'll edit for clarity. $\endgroup$ Commented Jun 30, 2020 at 18:00
  • $\begingroup$ @AlexKruckman I've edited to clarify. Let me know if this doesn't address your concern. $\endgroup$ Commented Jun 30, 2020 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .