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?
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?
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.
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?
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.
Oops, I see that now. (Red face.) Thanks.
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.
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.
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$.