1. ## extensionality

To say that a relation R is extensional, so that $\displaystyle R^{-1}$[x]$\displaystyle \neq$$\displaystyle R^{-1}$[y] for all distinct x and y in the range of R, isn't this the same as merely stipulating that the relation be a function?

2. No. Consider the membership relation $\displaystyle \in$ between some set A (where |A| > 1) and the powerset of A. It is extensional since subsets are determined by their members, but it is not a function. On the other hand, functions are extensional viewed as relations.

3. Thank you, emakarov. While I have your attention, may I pose an even more elementary question on the same topic? Or should I re-post?

I suspect I am applying the Mostowski collapse F(x) = {F(y) : y R x} incorrectly.
Suppose a,b,c,d are atoms, and on the set {a,b,c,d,e,f,g} a relationship is defined by the following ordered pairs:
<a,e>, <b,e>, <c,f>, <d,f>, <e,g>,<f,g>. [Annabel and Bob give birth to Eleanor; Charlie and Dana give birth to Francis, and Francis and Eleanor give birth to George. The relation is "parent of". ] As far as I see, this satisfies the conditions (that R be set-like, well-founded, and extensional).

Then F(a) = F(b) = F(c) = F(d) = F(0)= 0,
F(e) = {F(a), F(b)} = {0, 0}) = {0}
similarly F(f) ={0}
F(g) = {F(e),F(f)} = {{0},{0}}={{0}}
It is at this point that I note that something is wrong, since [0, {0}, {{0}}] is not transitive under set membership, and it doesn't look very isomorphic to the original structure. What am I doing wrong?

4. This relation is not extensional because it has distinct atoms (whose pre-images are all empty sets). F indeed maps the set onto {0, {0}, {{0}}}. The latter set is transitive because every element is also a subset. The Wikipedia article about the Mostowski collapse lemma says that F is a homomorphism, which is indeed the case here. F is an isomorphism iff the original relation is extensional, which it is not in this example.

5. Originally Posted by emakarov
This relation is not extensional because it has distinct atoms (whose pre-images are all empty sets)..
Oops, I see that now. (Red face.) Thanks.

Originally Posted by emakarov
{0, {0}, {{0}}}.... is transitive because every element is also a subset.
This makes it transitive under the subset relation. However, it does not make it transitive under set membership, for which you would need
0 $\displaystyle \in${0}$\displaystyle \in${{0}} $\displaystyle \rightarrow$ 0 $\displaystyle \in${{0}},
which is not the case. So although I cannot expect an isomorphism any more, I still have the following puzzling statement out of the Wiki article you cited:
"A mapping F such that F(x) = {F(y) : y R x} for all x in X can be defined for any well-founded set-like relation R on X by well-founded recursion. It provides a homomorphism of R onto a (non-unique, in general) transitive class. "
In my example, although R is not extensional, it is nonetheless well-founded and set-like. The transitivity referred to in this quote is on the membership relation, not the subset relation. So I am still puzzled.

6. By definition, a set A is transitive if x ∈ y and y ∈ A imply x ∈ A. The largest entity of the three (x, y and A) here is A, the set itself. The fact that A is transitive does not mean that (A, ∈) is transitive (i.e., that ∈ is a transitive relation on A), as this example shows.

In fact, it would be nice if somebody confirmed the relationship between these things: (1) A is transitive, (2) (A, ∈) is transitive, and (3) A is hereditarily transitive. It just takes me too much time to think about nested sets.

7. Nomadreid, i think you're confusing showing that the set is transitive with showing that the set is an ordinal. The set is in fact transitive. Every element of the set is a subset of the set. That is, if we call the set X, then $\displaystyle z\in y \in X \rightarrow z\in X$.

The set is not an ordinal because the $\displaystyle \epsilon$ relation is not transitive inside the set. That is, there are elements $\displaystyle y,z,w\in X$ with $\displaystyle y\in z\in w$ but $\displaystyle y\notin w$.

8. Thanks, emakarov and DrSteve. I was not aware of the distinctions, and am grateful to you to point them out to me.