Results 1 to 13 of 13

Math Help - Axiom of pairing

  1. #1
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,823

    Axiom of pairing

    Hello everyone, I'm just beginning set theory and I am having trouble understanding the signifigance of the axiom of pairing. I understand the axiom, but why do we need it? Can some of you guys/girls just elaborate on the axiom in the least technical way possible? I would appreciate it. I do not have a very specific question. I find that I learn best by simply talking about the topic at hand.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1

    Re: Axiom of pairing

    Quote Originally Posted by VonNemo19 View Post
    Hello everyone, I'm just beginning set theory and I am having trouble understanding the signifigance of the axiom of pairing. I understand the axiom, but why do we need it?
    Have you read this?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Axiom of pairing

    Just in general, if you have two sets x and y, wouldn't you want to be allowed to form the set whose only two members are x and y?

    Then, as you get down the road in set theory, even just a chapter or two away from where you are now, you'll see that certain mathematics formulated in set theory uses pairs of sets.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: Axiom of pairing

    Quote Originally Posted by VonNemo19 View Post
    I understand the axiom, but why do we need it?
    That is always a good question to ask when dealing with axiomatic theories, for if we did not need the axiom, why bother with it? Let me ask you this, as food for thought: without the axiom of pairs (i.e., with only the other axioms of ZF or ZFC), can you define the set that contains exactly the pair of sets A and B? Of course, even if we can achieve this by using other axioms, the axiom of pairing my simplify things, but then we can use it as a derived definition of a "set theoretic phenomena." This is why we don't need an axiom of intersections, yet we have an axiom of unions.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Axiom of pairing

    Just as a techical note (and the previous post somewhat alludes to this also): In ZF we don't need the pairing axiom, since it is derivable from the axiom schema of replacement. But of course, we do need (in some suitable sense of 'need') to be able to form pairs, whether as derived as a theorem from the replacement schema or, without the replacement schema, as an axiom itself.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Axiom of pairing

    I understand the axiom, but why do we need it?
    The axiom:
    To all x and y Exist set A that x,y her two elements.

    With that axiom we can prove (by induction):

    \left \{ \varnothing  \right \}, \left \{ \left \{ \varnothing  \right \} \right \},\left \{ \left \{ \left \{ \varnothing  \right \} \right \} \right \},...

    Are different groups.


    Also, you can prove using the axiom the theorem:


    \forall a \exists \exist c \forall b (b\in c \leftrightarrow  b=a)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,823

    Re: Axiom of pairing

    Quote Originally Posted by MoeBlee View Post
    Just in general, if you have two sets x and y, wouldn't you want to be allowed to form the set whose only two members are x and y?

    Then, as you get down the road in set theory, even just a chapter or two away from where you are now, you'll see that certain mathematics formulated in set theory uses pairs of sets.
    Awesome. I'm trying to see this...and I will. Thanks for your input.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,823

    Re: Axiom of pairing

    Quote Originally Posted by Plato View Post
    Yes. It reads like my book, my friend. Can you speak on this topic yourself? What does this wiki page mean to you? I would just like to hear your thoughts on the topic.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: Axiom of pairing

    Quote Originally Posted by MoeBlee View Post
    In ZF we don't need the pairing axiom, since it is derivable from the axiom schema of replacement.
    Are you sure about this? Doesn't the axiom schema of replacement define the range of a definable bijection to be a set? To make the definable bijection we require what the axiom of pairing provides (e.g., cartesian products). The benefit to the axiom of pairing is to be able to build from (albeit, finitely) known sets to things like: the singlton, the pairs, the ordered pairs, and n-tuples. Even if the axiom of replacement (with others) can satisfy the axiom of pairing, it should be noted that it would be like using a hatchet for a scalpel. The axiom schema of replacement is a very powerful axiom (and with the axiom of existence, can be used to satisfy the axiom of extensionality).

    For the interested reader, a good read.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Axiom of pairing

    Quote Originally Posted by bryangoodrich View Post
    Are you sure about this?
    Yes, the pairing axiom is not needed in ZF. It can be derived as a theorem from the axioms of ZF without the pairing axiom.

    Quote Originally Posted by bryangoodrich View Post
    Doesn't the axiom schema of replacement define the range of a definable bijection to be a set?
    There are different formulations of the axiom schema of replacement (some stronger than others), but, most basically, the axiom schema of replacement tells us, somewhat loosely speaking here, that if we have a given set and a "class function" with that set as its domain, then the "class range" is a set. There's no need to involve the notion of bijection.

    Quote Originally Posted by bryangoodrich View Post
    Even if the axiom of replacement (with others) can satisfy the axiom of pairing,
    I don't know what you mean by a set of axioms "satisfying" something. A model satisfies a set of axioms; I don't know what would be meant by a set of axioms satisfying something. In any case, ZF without the pairing axiom proves the pairing axiom.

    Quote Originally Posted by bryangoodrich View Post
    it should be noted that it would be like using a hatchet for a scalpel.
    I'm not making any claims about what would be heuristically preferred. I'm merely pointing out a certain mathematical fact.

    Quote Originally Posted by bryangoodrich View Post
    The axiom schema of replacement is a very powerful axiom (and with the axiom of existence, can be used to satisfy the axiom of extensionality).
    I don't know what you mean by "the axiom of existence" nor what you mean by axioms satisfying anything. In any case, the axiom of extensionality is independent of the rest of the axioms of ZF.

    EDIT: Perhaps by 'axiom of existence' you mean the principle that there exists at least one set. Sometimes such a principle is mentioned, however, from a technical point of view, it is superfluous, since by identity theory alone we get Ex x=x, and moreover, from the axiom schema of separation (either as an axiom or as derived from the axiom schema of replacement) we get ExAy ~yex, i.e., that there is at least one empty set.
    Last edited by MoeBlee; June 16th 2011 at 12:21 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Axiom of pairing

    To be even more specific: One instance of the axiom schema of replacement and the power set axiom together prove the pairing axiom. Moreover, we could even derive pairing if all we would had are an appropriate instance of the axiom schema of replacement and an "axiom" that there exist an x and y such that x not equal y.
    Last edited by MoeBlee; June 16th 2011 at 12:32 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: Axiom of pairing

    Quote Originally Posted by MoeBlee View Post
    Yes, the pairing axiom is not needed in ZF.
    The Wikipedia article to which Plato referred does articulate this. They do, however, indicate that the use of the axiom of replacement is restricted to sets of at least cardinality 2. The use of other axioms (existence/empty set, power set, or infinity) can be used to build up to sets of cardinality 2. That seems an important point, I believe.

    Quote Originally Posted by MoeBlee View Post
    There are different formulations of the axiom schema of replacement (some stronger than others), but, most basically, the axiom schema of replacement tells us, somewhat loosely speaking here, that if we have a given set and a "class function" with that set as its domain, then the "class range" is a set. There's no need to involve the notion of bijection.
    As you indicate "class functions" you have to realize the needed restriction to having sets (not proper classes) in ZFC. The Wikipedia article points out the need for definable bijections. (Thus, the classes need to be "small enough" so the bijection defines a set.) If we have "paradoxical sets" that are too "large" you will end up with something like the "set of all sets." Hrbacek and Jech Introduction to Set Theory (3rd ed.) define it such that it "is intuitively obvious that the set F[A] is "no larger than" the set A," (p. 113). They go on to indicate any problematic definitions of such functions will produce proper classes, basically. Therefore, In ZFC we do end up having class functions that are definable bijections.

    Quote Originally Posted by MoeBlee View Post
    I'm not making any claims about what would be heuristically preferred.
    Nor was I claiming that you were; hence my use of "it should be noted ..." to indicate a tangential statement about the topic I was making.

    Quote Originally Posted by MoeBlee View Post
    I don't know what you mean by a set of axioms "satisfying" something.
    A model of a sentence is an interpretation in which the sentence comes out true. Thus, \Gamma implies \mathcal{D} if every model of \Gamma is a model of \mathcal{D} (taken from Boolos, et al. Computability and Logic 5th., p. 137). I was speaking loosely that a model of ZF* is a model (i.e., satisfies) the sentence expressing the axiom of pairing, where ZF* is clearly indicating the theory of ZF excluding pairing. I apologize if my usage was confusing. I'll just say implies next time.

    Quote Originally Posted by MoeBlee View Post
    the axiom of extensionality is independent of the rest of the axioms of ZF.
    Too right. I meant to say the axiom schema of specification. This is demonstrated on the Replacement Wiki referenced above.

    Quote Originally Posted by MoeBlee View Post
    I don't know what you mean by "the axiom of existence" ... [maybe] you mean the principle that there exists at least one set. Sometimes such a principle is mentioned, however, from a technical point of view, it is superfluous, since by identity theory alone we get Ex x=x, and moreover, from the axiom schema of separation (either as an axiom or as derived from the axiom schema of replacement) we get ExAy ~yex, i.e., that there is at least one empty set.
    First, I don't see how a logical expression can satisfy the existence of a set. It begs the question what the existential quantifier is quantified over: what is the universe of discourse? If you assume sets or a set of all sets by which to reference, you've begged the question. This is why an axiomatic treatment of set theory needs an existence axiom. This can be tentatively assumed until one uses the far richer Infinity axiom (e.g., Halmos does this in Naive Set Theory, making an official assumption that "there exists a set" on page 8). It can also be defined explicitly as an axiom of empty set as Hrbacek and Jech do (p. 7; it is an empty set axiom, but they call it Existence).
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Axiom of pairing

    Quote Originally Posted by bryangoodrich View Post
    the use of the axiom of replacement is restricted to sets of at least cardinality 2.
    There is no mention of such a restriction in the axiom schema. Of course for sets of cardinality less than 2, I suspect there's not much need for the schema. But I don't know what relevance this matter of cardinality has here.

    Maybe you mean that proving pairing with the axiom schema of replacement requires that we already have two different sets? Yes, I mentioned that above. From the axiom schema of replacement and the power set axiom, we do get that there exist at least two distinct sets.

    Quote Originally Posted by bryangoodrich View Post
    The use of other axioms (existence/empty set, power set, or infinity) can be used to build up to sets of cardinality 2. That seems an important point, I believe.
    When I said "from the axiom schema of replacement" I should have been clear to say that I mean from the axiom schema of replacement along with whatever other needed axioms of ZF not including the pairing axiom. I thought that might be taken for granted in context, but I agree that to be explicit we should mention it. However, the empty set axiom is itself derivable from the axiom schema of replacement (the version of replacement that I mentioned) and the axiom of infinity is not needed here either. All we need is replacement and power set from among the ordinary axioms.

    Quote Originally Posted by bryangoodrich View Post
    As you indicate "class functions" you have to realize the needed restriction to having sets (not proper classes) in ZFC.
    Of course, and that is why I said that part was "loosely stated" (or whatever words I used). It is quite customary to use talk of proper classes in ZFC with the proviso that such talk can be reduced back down to talk that does not avail of proper classes. Indeed, some texts that use ZFC use proper classes all over the place, since such mentions of proper classes can be "resolved" to some statement in which proper classes are not mentioned.

    Quote Originally Posted by bryangoodrich View Post
    The Wikipedia article points out the need for definable bijections. (Thus, the classes need to be "small enough" so the bijection defines a set.)
    Wikipedia can point out whatever it wants, but you see that in the version of the axiom schema of replacement that I posted there is not a mention or requirement of any bijection. And, offhand, among other formulations of replacement, I can't think of one that mentions anything about bijection.

    Quote Originally Posted by bryangoodrich View Post
    If we have "paradoxical sets" that are too "large" you will end up with something like the "set of all sets."
    Such considerations are reasonable, but you can see that the actual formulation of replacement doesn't require mentioning anything about bijection.

    Quote Originally Posted by bryangoodrich View Post
    I'll just say implies next time.
    Fair enough.

    Quote Originally Posted by bryangoodrich View Post
    I meant to say the axiom schema of specification.
    I lost what point we were on in that regard, but the axiom schema of separation is also derivable from a suitable formulation (such as the one I gave) of the axiom schema of replacement.

    Quote Originally Posted by bryangoodrich View Post
    I don't see how a logical expression can satisfy the existence of a set.
    Neither do I; indeed I didn't mention such a thing.

    Quote Originally Posted by bryangoodrich View Post
    what is the universe of discourse?
    There are two separate but connected matters: (1) In the syntax of ordinary first order logic with identity (such as the logic for ordinary set theory), we prove Ex x=x, irrespective of any semantics about universes for models. (2) However, that proof syntax does "match" our ordinary semantics, since our ordinary semantics requires that any universe of a model is non-empty.

    But with the proof that there exists an empty set, we don't even need identity theory. The axiom schema of separation alone, with just first order logic (not even involving identity theory) proves ExAy ~yex. And again, the syntax of proof "matches" the semantics. Even without identity. Given ANY 1-place predicate symbol (or adjusted suitably for any n-place predicate symbol), we prove, for example, Ex(Px -> Px), and thus matching the semantics that requires that a universe for a model is non-empty.

    Halmos does this in Naive Set Theory, making an official assumption that "there exists a set".
    Note that Halmos is not working in a formal context. However, sometimes authors who work even in a formal context do include such existence axioms. Some of those authors mention that they do that only for purposes of convenience since we really don't need such an axiom. Other authors who adopt such an axiom don't even bother discussing it much. But in any case, whether included as a formal axiom or not, it is superfluous, as is the empty set axiom, when we have the axiom schema of separation either as a theorem schema from the axiom schema of replacement or as its own independent axiom schema.
    Last edited by MoeBlee; June 16th 2011 at 04:24 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What is a word (side pairing elements)
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: May 28th 2010, 07:32 AM
  2. inverting the Pairing function
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 22nd 2009, 12:04 PM
  3. Pairing Senators
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2009, 11:23 PM
  4. Stats - pairing or unknown o?
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: February 7th 2009, 10:56 PM
  5. Golf pairing algorithm challenge
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 13th 2008, 08:10 PM

Search Tags


/mathhelpforum @mathhelpforum