4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Hanul Jeon Feb 22 '16 at 16:07
  • $\begingroup$ 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$. $\endgroup$ – Hanul Jeon Feb 22 '16 at 16:08
  • $\begingroup$ 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? $\endgroup$ – akkarin Feb 23 '16 at 11:28
  • $\begingroup$ 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. $\endgroup$ – Hanul Jeon Feb 23 '16 at 11:42
  • $\begingroup$ 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). $\endgroup$ – akkarin Feb 23 '16 at 12:55
3
$\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:

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – akkarin Mar 8 '16 at 13:00
  • 1
    $\begingroup$ @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. $\endgroup$ – Hanul Jeon Mar 8 '16 at 13:03
  • $\begingroup$ So what is the rank of an $x$ that isn't covered? $\endgroup$ – akkarin Mar 8 '16 at 13:32
  • 1
    $\begingroup$ @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$. $\endgroup$ – Hanul Jeon Mar 9 '16 at 17:36
  • 1
    $\begingroup$ @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$. $\endgroup$ – Hanul Jeon Mar 9 '16 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.