# Axiom of pairing

Printable View

• June 15th 2011, 12:33 PM
VonNemo19
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.
• June 15th 2011, 12:40 PM
Plato
Re: Axiom of pairing
Quote:

Originally Posted by VonNemo19
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?
• June 15th 2011, 01:42 PM
MoeBlee
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.
• June 15th 2011, 01:52 PM
bryangoodrich
Re: Axiom of pairing
Quote:

Originally Posted by VonNemo19
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.
• June 15th 2011, 01:55 PM
MoeBlee
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.
• June 15th 2011, 05:16 PM
Also sprach Zarathustra
Re: Axiom of pairing
Quote:

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)$
• June 16th 2011, 10:09 AM
VonNemo19
Re: Axiom of pairing
Quote:

Originally Posted by MoeBlee
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. :)
• June 16th 2011, 10:12 AM
VonNemo19
Re: Axiom of pairing
Quote:

Originally Posted by Plato

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.
• June 16th 2011, 10:26 AM
bryangoodrich
Re: Axiom of pairing
Quote:

Originally Posted by MoeBlee
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.
• June 16th 2011, 10:47 AM
MoeBlee
Re: Axiom of pairing
Quote:

Originally Posted by bryangoodrich

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
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
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
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
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.
• June 16th 2011, 10:51 AM
MoeBlee
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.
• June 16th 2011, 02:25 PM
bryangoodrich
Re: Axiom of pairing
Quote:

Originally Posted by MoeBlee
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
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
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
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
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
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).
• June 16th 2011, 03:07 PM
MoeBlee
Re: Axiom of pairing
Quote:

Originally Posted by bryangoodrich
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
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
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
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
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
I'll just say implies next time.

Fair enough.

Quote:

Originally Posted by bryangoodrich
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
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
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.

Quote:

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.
All times are GMT -8. The time now is 09:09 AM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 6, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9483859539031982, "perplexity_flag": "middle"}