# 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))$.

1. Verify that the structure $(V,\in^\sigma)$ satisfies all the axioms of ZF except possibly for Foundation.
2. By taking $\sigma$ to be the transposition which interchanges $\emptyset$ and $\{\emptyset\}$ (and fixes everything else), show that Foundation may fail.
3. 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\}$.
1. 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)))$$

2. We get $\emptyset\in\emptyset$, isn't that enough already?

3. 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?

• Your verification to union axiom is correct. We just need an existence of some set so $\sigma(t)$ in your sentence is not a problem. – Hanul Jeon Feb 22 '16 at 16:07
• For 2, showing $\varnothing\in\varnothing$ is enough to negating foundation, since the axiom of foundation implies there is no $x$ such that $x\in x$. – Hanul Jeon Feb 22 '16 at 16:08
• I get that $(\exists t)(\sigma(t)\in^\sigma x\land z\in^\sigma \sigma(t))$ would be as good as $(\exists t)(t\in^\sigma x\land z\in^\sigma t)$ but in fact I get $(\exists t)(\sigma(t)\in^\sigma x\land z\in^\sigma t)$. Isn't it problematic that $\sigma(t)$ and $t$ can be entirely different sets? That genuinely changes the formula doesn't it? – akkarin Feb 23 '16 at 11:28
• In general changing variables might be problematic, but in that case this is not a problem. The thing we want is the existence of some set. Thus the shape of the set is not relevant since we just need the existence, not the exact form of a set. – Hanul Jeon Feb 23 '16 at 11:42
• Hmkay I trust you but I don't fully understand it. I thought we need to show that the union axiom where $\in$ is replaced by $\epsilon^\sigma$ holds in the new structure. Just as we did for the other axioms. But I can't see how to resolve the issue that both $\sigma(t)$ and $t$ appear in the formula (where instead it should be the same set twice). – akkarin Feb 23 '16 at 12:55

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:

1. $x$ contains a element of rank 0.

2. $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)$.

• Sorry for the late reply. How do you know that your hierarchy covers the entire universe even though you start with an arbitrary set $a$? – akkarin Mar 8 '16 at 13:00
• @akkarin we can not cover whole universe for arbitrary $a$. If our $a$ is empty then the hierarchy would be the collection of all well-founded sets but our universe has a ill-founded one. I assume $a$ as the set you referred in the question. – Hanul Jeon Mar 8 '16 at 13:03
• So what is the rank of an $x$ that isn't covered? – akkarin Mar 8 '16 at 13:32
• @akkarin It never happens. Elements in $a$ only permuted by $\sigma$, so $x\cap a=\varnothing$ implies every elements of $x$ are fixed by $\sigma$. Hence the ordinary relationship and the modified relationship agree over $x$. – Hanul Jeon Mar 9 '16 at 17:36
• @akkarin It is possible, but not a problem. In case 3 such $y$ is not in $x$. When we discuss the $\in$-minimality over $x$ we only consider the elements of $x$. Let me restate the axiom of regularity: it says that if $x$ is nonempty, then $\exists y\in x \forall z\in x: z\notin y$. – Hanul Jeon Mar 9 '16 at 17:48