Editing Axiom of pairing

{{short description|Concept in axiomatic set theory}}
{{no footnotes|date=March 2013}}
In [[axiomatic set theory]] and the branches of [[logic]], [[mathematics]], and [[computer science]] that use it, the '''axiom of pairing''' is one of the [[axiom]]s of [[Zermelo–Fraenkel set theory]]. It was introduced by {{harvtxt|Zermelo|1908}} as a special case of his [[axiom of elementary sets]].

== Formal statement ==
In the [[formal language]] of the Zermelo–Fraenkel axioms, the axiom reads:
:<math>\forall A \, \forall B \, \exists C \, \forall D \, [D \in C \iff (D = A \lor D = B)]</math>

In words:
:[[Given any]] object ''A'' and any object ''B'', [[Existential quantification|there is]] a set ''C'' such that, given any object ''D'', ''D'' is a member of ''C'' [[if and only if]] ''D'' is [[equal (math)|equal]] to ''A'' [[logical disjunction|or]] ''D'' is equal to ''B''.

== Consequences ==
As noted, what the axiom is saying is that, given two objects ''A'' and ''B'', we can find a set ''C'' whose members are exactly ''A'' and ''B''.

We can use the [[axiom of extensionality]] to show that this set ''C'' is unique. We call the set ''C'' the ''pair'' of ''A'' and ''B'', and denote it {''A'',''B''}. Thus the essence of the axiom is:
:Any two objects have a pair.

The set {''A'',''A''} is abbreviated {''A''}, called the ''[[singleton (mathematics)|singleton]]'' containing ''A''. Note that a singleton is a special case of a pair. Being able to construct a singleton is necessary, for example, to show the non-existence of the infinitely descending chains <math>x=\{x\}</math> from the [[Axiom of regularity]].

The axiom of pairing also allows for the definition of [[ordered pairs]]. For any objects <math>a</math> and <math>b</math>, the [[ordered pair]] is defined by the following:

:<math> (a, b) = \{ \{ a \}, \{ a, b \} \}.\,</math>

Note that this definition satisfies the condition

:<math>(a, b) = (c, d) \iff a = c \land b = d. </math>

Ordered [[tuple|''n''-tuples]] can be defined recursively as follows:

:<math> (a_1, \ldots, a_n) = ((a_1, \ldots, a_{n-1}), a_n).\!</math>

== Alternatives ==
=== Non-independence ===
The axiom of pairing is generally considered uncontroversial, and it or an equivalent appears in just about any [[axiomatization]] of set theory. Nevertheless, in the standard formulation of the [[Zermelo–Fraenkel set theory]], the axiom of pairing follows from the [[axiom schema of replacement]] applied to any given set with two or more elements, and thus it is sometimes omitted. The existence of such a set with two elements, such as { {}, { {} } }, can be deduced either from the [[axiom of empty set]] and the [[axiom of power set]] or from the [[axiom of infinity]].

In the absence of some of the stronger ZFC axioms, the axiom of pairing can still, without loss, be introduced in weaker forms.

=== Weaker ===
In the presence of standard forms of the [[axiom schema of separation]] we can replace the axiom of pairing by its weaker version:
:<math>\forall A\forall B\exists C\forall D((D=A\lor D=B)\Rightarrow D\in C)</math>.

This weak axiom of pairing implies that any given objects <math>A</math> and <math>B</math> are members of some set <math>C</math>. Using the axiom schema of separation we can construct the set whose members are exactly <math>A</math> and <math>B</math>.

Another axiom which implies the axiom of pairing in the presence of the [[axiom of empty set]] is the [[axiom of adjunction]]
:<math>\forall A \, \forall B \, \exists C \, \forall D \, [D \in C \iff (D \in A \lor D = B)]</math>.
It differs from the standard one by use of <math>D \in A</math> instead of <math>D=A</math>. Using {} for ''A'' and ''x'' for B, we get {''x''} for C. Then use {''x''} for ''A'' and ''y'' for ''B'', getting {''x,y''} for C. One may continue in this fashion to build up any finite set. And this could be used to generate all [[hereditarily finite set]]s without using the [[axiom of union]].

=== Stronger ===
Together with the [[axiom of empty set]] and the [[axiom of union]], the axiom of 
pairing can be generalised to the following schema:
:<math>\forall A_1 \, \ldots \, \forall A_n \, \exists C \, \forall D \, [D \in C \iff (D = A_1 \lor \cdots \lor D = A_n)]</math>
that is:
:Given any [[finite set|finite]] number of objects ''A''<sub>1</sub> through ''A''<sub>''n''</sub>, there is a set ''C'' whose members are precisely ''A''<sub>1</sub> through ''A''<sub>''n''</sub>.
This set ''C'' is again unique by the [[axiom of extensionality]], and is denoted {''A''<sub>1</sub>,...,''A''<sub>''n''</sub>}.

Of course, we can't refer to a ''finite'' number of objects rigorously without already having in our hands a (finite) set to which the objects in question belong. Thus, this is not a single statement but instead a [[schema (logic)|schema]], with a separate statement for each [[natural number]] ''n''.
*The case ''n'' = 1 is the axiom of pairing with ''A'' = ''A''<sub>1</sub> and ''B'' = ''A''<sub>1</sub>.
*The case ''n'' = 2 is the axiom of pairing with ''A'' = ''A''<sub>1</sub> and ''B'' = ''A''<sub>2</sub>.
*The cases ''n'' > 2 can be proved using the axiom of pairing and the [[axiom of union]] multiple times.
For example, to prove the case ''n'' = 3, use the axiom of pairing three times, to produce the pair {''A''<sub>1</sub>,''A''<sub>2</sub>}, the singleton {''A''<sub>3</sub>}, and then the pair {{''A''<sub>1</sub>,''A''<sub>2</sub>},{''A''<sub>3</sub>}}.
The [[axiom of union]] then produces the desired result, {''A''<sub>1</sub>,''A''<sub>2</sub>,''A''<sub>3</sub>}. We can extend this schema to include ''n''=0 if we interpret that case as the [[axiom of empty set]].

Thus, one may use this as an [[axiom schema]] in the place of the axioms of empty set and pairing. Normally, however, one uses the axioms of empty set and pairing separately, and then proves this as a [[theorem]] schema. Note that adopting this as an axiom schema will not replace the [[axiom of union]], which is still needed for other situations.

== References ==
*[[Paul Halmos]], ''Naive set theory''. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. {{ISBN|0-387-90092-6}} (Springer-Verlag edition).
*Jech, Thomas, 2003. ''Set Theory: The Third Millennium Edition, Revised and Expanded''.  Springer. {{ISBN|3-540-44085-2}}.
*Kunen, Kenneth, 1980. ''Set Theory: An Introduction to Independence Proofs''. Elsevier. {{ISBN|0-444-86839-9}}.
*{{citation|authorlink=Ernst Zermelo|first=Ernst|last= Zermelo|year=1908|title=Untersuchungen über die Grundlagen der Mengenlehre I|journal=Mathematische Annalen |volume=65|issue=2|pages= 261–281|url = https://zenodo.org/records/1428264/files/article.pdf|doi=10.1007/bf01449999|s2cid=120085563 }}. English translation: {{citation|authorlink=Jean van Heijenoort|first=Jean van|last= Heijenoort |year=1967 |title= From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 |series=Source Books in the History of the Sciences |chapter=Investigations in the foundations of set theory|publisher=Harvard Univ. Press|pages=199–215|isbn= 978-0-674-32449-7}}.

{{Set theory}}

[[Category:Axioms of set theory]]

[[de:Zermelo-Fraenkel-Mengenlehre#Die Axiome von ZF und ZFC]]