Suppose I have the set

$X = \{\varnothing ,\{ \varnothing\} ,\{\{\varnothing\}\} , \{\{\{\varnothing\}\}\} , ..., x_n , \{x_n\}, ... \}$

My book asks which finite and which infinite subsets are models of extensionality? If $Y \subseteq X$ then $Y \vDash$ extensionality iff $Y \cap ((x\setminus y) \cup (y\setminus x)) \ne \varnothing$ for all distinct $x, y \in Y$. It seems to me that all non-empty subsets are models of extensionality, whether they are finite or infinite (except that finite sets must have at least two elements). If $x=x_m$ and $y=x_n$ (the $m$ and $n$ indicate the number of braces around the empty set), then $x_m \setminus x_n = x_{m-n-1} \ne \varnothing$ for $m > n$; and $x_m \setminus x_n = x_m \ne \varnothing$ for $m < n$.


Note that extensionality holds when $(x\setminus y) \cup (y\setminus x)$ is not empty for $Y$ for $x\ne y$, that means that if $y\ne x$, then there exists some $z\in Y(!)$ such that $z\in x\setminus y$ or $z\in y\setminus x$.

Take $Y=\{\emptyset,\{\{\emptyset\}\}\}$ for example, in this case both $\emptyset$ and $\{\{\emptyset\}\}$ contains no elements in $Y$, so both are empty sets for $Y$, and so if $x=\emptyset,y=\{\{\emptyset\}\}$, we have $\left((x\setminus y) \cup (y\setminus x)\right)^Y$ is empty so extensionality does not hold.

  • $\begingroup$ And I see that this argument would fail if I had chosen the set of von Neumann natural numbers $X = \{ 0, 1, 2, ... \}$ with $Y=\{ 0, 2 \}$ since $0 \in 2$. Is this why the original $X$ (above) was abandoned as a model for the natural numbers in favor of von Neumann? $\endgroup$ – Robert Singleton Apr 13 '19 at 13:28
  • $\begingroup$ @RobertSingleton one of the reasons, in general transitive sets are extremely nice(like $\in$ well ordering the set) $\endgroup$ – ℋolo Apr 13 '19 at 13:56
  • $\begingroup$ I'm beginning to appreciate transitive sets. In general, it seems that if a subset of $X$ is not transitive, then it will not model extensionality. I'm now trying to prove that the only subsets of $X$ that model extensionality are transitive. $\endgroup$ – Robert Singleton Apr 13 '19 at 14:06

After thinking about @Holo's reply, I have the full answer to my question (I think):

  • The only finite subsets of $X$ that model extensionality are the sequential subsets $Y=\{x_0, x_1, ..., x_n \}$ where $x_0=\varnothing$ and $x_{m+1}=\{x_m\}$. If an element $x_m$ for $m < n$ is missing from $Y$, then $x_m \notin Y$ but $x_{m+1}\in Y$, in which case $Y \cap (x_{m+1} \setminus x_0) = Y \cap x_{m+1} = \varnothing$ (and $x_0 \setminus x_{m+1}$ is itself empty).

  • The only infinite subset of $X$ that models extensionality is $X$ itself. Again, this is because the elements must be sequential as in the finite argument.

  • 1
    $\begingroup$ This answer assumes $x_0=\varnothing\in Y$. Any set of the form $\{x_k,x_{k+1},\dots, x_n\}$ also satisfies extensionality. $\endgroup$ – Alex Kruckman Apr 13 '19 at 18:17
  • $\begingroup$ @AlexKruckman By the same token, any infinite set of the form $\{x_k, x_{k+1}, .... \}$ satisfies extensionality? $\endgroup$ – Robert Singleton Apr 14 '19 at 14:02
  • $\begingroup$ Yes. And now you have all of them. $\endgroup$ – Alex Kruckman Apr 14 '19 at 15:47

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.