Results 1 to 8 of 8

Math Help - extensionality

  1. #1
    Member
    Joined
    Aug 2010
    Posts
    130

    extensionality

    To say that a relation R is extensional, so that R^{-1}[x] \neq 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    No. Consider the membership relation \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2010
    Posts
    130
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2010
    Posts
    130
    Quote Originally Posted by emakarov View Post
    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.

    Quote Originally Posted by emakarov View Post
    {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 \in {0} \in {{0}} \rightarrow 0 \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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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 z\in y \in X \rightarrow z\in X.

    The set is not an ordinal because the \epsilon relation is not transitive inside the set. That is, there are elements y,z,w\in X with y\in z\in w but y\notin w.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2010
    Posts
    130
    Thanks, emakarov and DrSteve. I was not aware of the distinctions, and am grateful to you to point them out to me.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Extensionality and well-founded
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 13th 2011, 09:16 AM

Search Tags


/mathhelpforum @mathhelpforum