Example of a model in set theory where the axiom of extensionality does not hold?

I recently started a course in set theory and it was said that a model of set theory consists of a nonempty collection $U$ of elements and a nonempty collection $E$ of ordered pairs $(u,v)$, the components of which belong to $U$. Then the elements of $U$ are sets in the model and a set $u$ is interpreted as an element of $v$ if $(u,v) \in E$. It was also said that $U$ can also be a set and then $E$ is a relation in the set $U$ so that the ordered pair $(U,E)$ is a directed graph and reversely, any ordered graph $(U,E)$ can be used as a model of set theory.

There have been examples of different models now where some of the axioms of ZFC do not hold and some do, but the axiom of extensionality has always held and I for some reason don't seem to comprehend enough of that axiom and its usage. Can someone tell an example of some collections $E$ and $U$ where the axiom of extensionality wouldn't hold?

• Terminology: Any ordered graph can be an interpretation of the language of set theory. It is only a model if every axiom is true under the interpretation. – Henning Makholm Sep 12 '11 at 15:24
• Though they may not be models of ZFC without the axiom of extensionality, one does on occasion consider set theories with so-called "urelements", i.e. "objects" that are not "the" empty set, but rather do not contain any elements, yet differ from each other and are well distinguishable. (In many ways such set theories come closer to the everyday notion of what a set is.) I'm just wondering how you would formulate some of the axioms in a system of ZFC without extensionality (and why) ? Kind regards - Stephan F. Kroneck. – bonnbaki Sep 12 '11 at 15:30

The axiom of extensionality says:

$$\forall x\forall y\left(x=y\leftrightarrow \forall z\left(z\in x\leftrightarrow z\in y\right)\right)$$

Obviously, if two sets are the same then they have the same elements. So in order to violate this axiom we need to have different sets which the model would think have the same elements.

If you just want a model of sets in which the axiom of extensionality does not hold, consider for $a\neq b$ the following: $$\left(U=\Big\{\{a,b\},\{a\},a\Big\}, \in\right)$$

We have that $a\in\{a\}$, and $a\in\{a,b\}$. Since $a\neq b$ we have that $\{a\}\neq\{a,b\}$, however for all $x\in U$ we have $x\in\{a\}\leftrightarrow x\in\{a,b\}$.

This is because $U$ does not know about $b$. It just knows that $\{a,b\}$ and $\{a\}$ are two distinct beings. It is unable to say why, in terms of $\in$ relation.

The problems begins when you want more axioms. The more axioms you would want to have, the more complicated your universe will have to get.

• I was wondering how $x \in \{a,b\} \rightarrow x \in\{a\}$ if $\{a,b\}$ is not a subset of $\{a\}$? Is it because we only consider $a$ in $\{a,b\}$since $a$ is being treated as a "set" in the model? – K.M Nov 10 '18 at 5:12
• Note that $b$ is not an element of $U$. So it is not part of that model. – Asaf Karagila Nov 10 '18 at 10:19
• (Also, it is generally not okay to edit an answer that you didn't understand in such a significant way. What is appropriate is to ask for clarification as you have in the comment.) – Asaf Karagila Nov 10 '18 at 12:08
• Extensionality means that $\in$ is enough to define equality. Think about an arbitrary partial order. So, a linear order is extensional, if two points are different then there is something witnessing that; but $\subsetneq$ on $\mathcal P(\Bbb N)$ is not extensional since $\{0\}$ and $\{1\}$ both have only $\varnothing$ as a proper subset, but they are not equal. The same goes here. In the model $U$, as described $\in$ is not extensional. – Asaf Karagila Nov 10 '18 at 18:53
• The point is that in order to say $b\in\{a,b\}$ you need to have $b$ and $\{a,b\}$ in the universe of the model. $U$ does not know $b$. So it is a meaningless statement to ask if $b\in\{a,b\}$ from the perspective of $U$. However, since $\{a\}$ and $\{a,b\}$ are distinct objects, and $U$ recognizes equality, $U$ knows that the two are different. It is unable to characterize this inequality using $\in$, though, because it is not familiar with "enough" objects. – Asaf Karagila Nov 10 '18 at 20:35

(This answer does not construct a model of ZFC - Extensionality. Instead, it discusses the purpose of the axiom of extensionality and its relationship to first order logic with equality.)

The point of the axiom of extensionality is to avoid the situation where the way in which the set is defined, not just its members, affects which sets contain the set. So to make extensionality fail you will just need a model in which there are two sets $A,B$ which have the same elements but are not equal.

The easiest way to do this is to take any set $A$, make a copy of it, color one copy red, and color the other copy blue. Declare that any set that was a member of $A$ is a member of both red-$A$ and blue-$A$, and that any set which contained $A$ contains both red-$A$ and blue-$A$. Then the resulting thing will still be a model of ZFC in the language with just $\in$ (without $=$ yet).

The point of the axiom of extensionality is then to say that this situation does not occur: there are not two sets which are somehow different despite having all the same elements.

In fact, a modification of the axiom of extensionality lets us define $=$ in terms of $\in$, by declaring that two sets will be regarded as equal if they have all the same members. To make this work, we rewrite the axiom of extensionality without $=$ as:

$$(\forall x)(x \in A \Leftrightarrow x \in B) \Rightarrow (\forall y)(A \in y \Leftrightarrow B \in y)$$ Then we can define $$A = B \Leftrightarrow (\forall x)(x \in A \Leftrightarrow x \in B)$$ and we can prove the substitution axioms for equality in terms of the equality-free axiom of extensionality and the definition of $=$.

This can be done in any model of ZFC in the language with just $\in$ (satisfying the modified version of extensionality) to obtain a model of ZFC in the language ($\in$, $=$), including the usual axiom of extensionality. But here $=$ may not be interpreted as the true equality relation, for example if the original model had red sets and blue sets. If we want the $=$ symbol to be interpreted as actual equality, we have to mod out by the equivalence relation induced by the interpretation of $=$ in our model. In the setting where $=$ is treated as a logical symbol which must be interpreted as true equality, the point of the axiom of extensionality is to ensure that this modding-out has already been performed: if we would define to sets to be "equal" in this indirect way, then they are already equal.

• This doesn't quite work. Your described model won't satisfy Pairing, for instance, since Pairing says there must be a set whose only element is red-$A$, but in your model every set that contains red-$A$ also contains blue-$A$. – Eric Wofsey Jun 11 '17 at 21:12
• Thanks for reading this old post. The usual way of stating the axiom of pairing is $(\forall R)(\forall B)(\exists X)(\forall Z)[Z \in X \leftrightarrow (Z = A \lor Z = B)]$. In the model I described, if we let $R$ be red-$A$ and $B$ be blue-$A$ then the model satisfies $R = B$, and so it also satisfies $\{R\} = \{B\} = \{R,B\}$. As far as the model can tell that is a one-element set whose only element is $R$. Here $=$ is not true equality but is the equivalence relation induced by the $\in$ relation of the model, which is how we need to read the pairing axiom if we don't take $=$ for granted. – Carl Mummert Jun 11 '17 at 22:51
• The usual statements of the axioms of ZFC use the symbol $=$, not "the equivalence relation induced by $\in$". So the $=$ appearing in Pairing is the same as the $=$ appearing in Extensionality. If $R\neq B$ for the purposes of failing Extensionality, then $R\neq B$ for the purposes of Pairing, so Pairing fails as well. – Eric Wofsey Jun 11 '17 at 22:54
• Of course it is possible to reformulate all the axioms of ZFC to not use the symbol $=$, but this is not the standard way to do things (and I don't think that's what most set theorists would assume "a model of ZFC - Extensionality" refers to). – Eric Wofsey Jun 11 '17 at 22:56
• In the answer I explicitly say that I am working in the language with just $\in$, that is, in first-order logic without equality. In fact, I pointed out that my model does satisfy ZFC including extensionality. I try, in the last several paragraphs, to explain how using logic with equality affects things, particularly in my last sentence. The key point is that there is an interplay between the axiom of extensionality and the semantics of first-order logic with equality. – Carl Mummert Jun 11 '17 at 22:56

I haven't checked all the details, but I expect it would work simply to take a model of ZFC and then remove the empty set from the universe. All other sets and their membership relations stay unchanged. The new model still has an empty set (namely the one that was formerly $\{ \emptyset\}$), and I think all of the other axioms except extensionality would still hold, though verifying this could be tedious.

However, the two individuals that used to be $\{\{\emptyset\}\}$ and $\{\emptyset,\{\emptyset\}\}$ now have the same elements -- but the set that used to be $\{\{\{\emptyset\}\}\}$ contains one but not the other, violating extensionality.

See Theorem 2 (p. 157) in the following paper, which is freely available on the internet:

Alexander Abian and Samuel LaMacchia, "On the consistency and independence of some set-theoretical axioms", Notre Dame Journal of Formal Logic 19 (1976), 155-158.

http://projecteuclid.org/euclid.ndjfl/1093888220

• I changed your link into a persistent one. Most article pages contain a link to themselves that is guaranteed to be stable, either using an internal linking system (like projecteuclid), or using the DOI system. – t.b. Sep 12 '11 at 16:46