Permutation of ZF model
I want to make sure I understand how these work. Can someone please check my answers to the following exercise // answer my questions. :)
Let $(V, \in)$ be a model of ZF, and let $\sigma$ be a permutation of $V$. We define a new binary relation $\in^\sigma$ on $V$ by $(x\in^\sigma y)\iff(x\in \sigma(y))$.
- Verify that the structure $(V,\in^\sigma)$ satisfies all the axioms of ZF except possibly for Foundation.
- By taking $\sigma$ to be the transposition which interchanges $\emptyset$ and $\{\emptyset\}$ (and fixes everything else), show that Foundation may fail.
- More generally, let $a$ be a set none of whose members is a singleton, and let $\sigma$ be the permutation which interchanges $x$ and $\{x\}$ for each $x\in a$. Show that $(V,\in^\sigma)$ satisfies a weak version of Foundation which says that every nonempty set $x$ has a member $y$ satisfying either $x\cap y=\emptyset$ or $y=\{y\}$.
Extension: $$(\forall x)(\forall y)[(\forall z)(z\in\sigma(x) \iff z\in \sigma(y))\implies \sigma(x)=\sigma(y)]$$ And $\sigma(x)=\sigma(y)$ implies $x=y$ as $\sigma$ is a permutation.
Separation: $$(\forall t_1)\ldots(\forall t_n)(\forall x)(\exists y)(\forall z)[z\in\sigma(y)\iff (z\in\sigma(x)\land \phi)]$$
Empty set: $$(\exists x)(\forall y)(\neg (y\in\sigma(x)))$$
Pair set: $$(\forall x)(\forall y)(\exists z)(\forall t)[t\in\sigma(z)\iff(t=x\lor t=y)]$$
Union: $$(\forall x)(\exists y)(\forall z)[z\in\sigma(y)\iff(\exists t)(\sigma(t)\in\sigma(x)\land z\in\sigma(t)]$$ I get $(\forall x)(\exists y)(\forall z)[z\in^\sigma y\iff(\exists t)(\sigma(t)\in^\sigma x\land z\in^\sigma t]$ which is not quite the union axiom ($\sigma(t)$ instead of $t$). How do I fix this?
Power set: $$(\forall x)(\exists y)(\forall z)(z\in\sigma(y)\iff z\subseteq x)$$
Infinity: $$(\exists x)(\emptyset \in\sigma(x))\land(\forall y)(y \in\sigma(x)\implies y\cup\{y\}\in \sigma(x))$$
Replacement: $$(\forall w_1,\ldots,w_n)((\forall y,y')((\phi\land\phi[y'/y])\implies(y=y'))\implies((\forall u)(\exists v)((\forall y)(y\in \sigma(v))\iff(\exists x)((x\in \sigma(u))\land\phi)))$$
We get $\emptyset\in\emptyset$, isn't that enough already?
For a given set $x$, if none of its members has been in $a$ in the previous structure then there must be a $y$ satisfying $x\cap y=\emptyset$ since $(V,\in)$ satisfies ZF. So we can find a $y\in^\sigma x$ with $y\in a$. But does that mean $y=\{y\}$? I struggle to apply extensionality in the new structure. On the one hand we have $y\in^\sigma y$ and $z\not\in^\sigma y$ for all $z\neq y$ which looks like $y = \{ y\}$. On the other hand there are elements $z\in^\sigma\{y\}$ with $z\neq y$, namely the elements of $y$ in the original structure. Is equality not symmetric any more after applying the permutation?
1 Answer
$\begingroup$Continuing from my comments, I would say that other proofs except 3 looks fine.
For 3, I think your argument against to sets with empty intersection with $a$ seems incomplete, because $(V,\in)\models \mathsf{regularity}$ seems not to imply your statement, that a set $x$ containing no elements in $a$ has some element $y$ such that $x\cap y = \varnothing$. The "transitive closure" of $x$ might be containing some elements in $a$ though $x$ itself is not.
My suggestion to proving 3 is defining a hierarchy of the universe and define a rank from the hierarchy. I am going to describe the detail at below:
$V_0(a) = a$
$V_{\alpha+1}(a) = \mathcal{P}^{(V,\in^\sigma)}(V_\alpha)$.
$V_{\alpha}(a) = \bigcup^{(V,\in^\sigma)}\{V_\xi : \xi<\alpha\}$ for limit $\alpha$.
where $\mathcal{P}^{(V,\in^\sigma)}$ and $\bigcup^{(V,\in^\sigma)}$ are power set operation and union operation relativized to the model $(V,\in^\sigma)$ ― their definitions are same as that of ordinary power set and union, except that $\in$ is replaced to $\in^\sigma$.
For each $x$, define a rank $\rho(x)$ as follow: $$\rho(x) = 1+\min\{\alpha:x\subseteq^\sigma V_\alpha(a)\}.$$ For example, ranks of the empty set and elements in $a$ are 0. Now divide the case:
$x$ contains a element of rank 0.
$x$ has no element of rank 0.
In case 2, though every element has non-zero rank, some element in $x$ has minimal rank. Now consider such set $y$. You can see that if $z\in^\sigma y$ then $\rho(z)\le \rho(y)$ and the inequality is strict if $\rho(y)>0$. From this you can complete the proof.
I realize that there is a more simple direct proof. Here is a detail: We divide the cases. For given $x$,
Case 1. If $(x\in a)^{(V,\in)}$, take $y=x$.
Case 2. If $(x\cap a\neq\varnothing)^{(V,\in)}$, we can find some $y$ such that $(y\in x\cap a)^{(V,\in)}$. Take such $y$.
Case 3. If $x$ satisfies none of the conditions described above, Neither elements in $x$ nor $x$ itself are permuted by $\sigma$. If $y$ is a $\in$-minimal element of $x = \sigma(x)$ then $\sigma(y)=y$. Thus if $z\in\sigma(x)$ then $z\notin y = \sigma(y)$.
$\endgroup$ 17
