Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Ordered pair

From Wikipedia, the free encyclopedia
Pair of mathematical objects
Analytic geometry associates to each point in theEuclidean plane an ordered pair. The redellipse is associated with the set of all pairs (x,y) such that⁠x2/4⁠ +y2 = 1.

Inmathematics, anordered pair, denoted (a,b), is a pair of objects in which their order is significant. The ordered pair (a,b) is different from the ordered pair (b,a), unlessa =b. In contrast, theunordered pair, denoted {a,b}, always equals the unordered pair {b,a}.

Ordered pairs are also called2-tuples, orsequences (sometimes, lists in a computer science context) of length 2. Ordered pairs ofscalars are sometimes called 2-dimensionalvectors. (Technically, this is an abuse ofterminology since an ordered pair need not be an element of avector space.)The entries of an ordered pair can be other ordered pairs, enabling therecursive definition of orderedn-tuples (ordered lists ofn objects). For example, the ordered triple (a,b,c) can be defined as (a, (b,c)), i.e., as one pair nested in another.

In the ordered pair (a,b), the objecta is called thefirst entry, and the objectb thesecond entry of the pair. Alternatively, the objects are called the first and secondcomponents, the first and secondcoordinates, or the left and rightprojections of the ordered pair.

Cartesian products andbinary relations (and hencefunctions) are defined in terms of ordered pairs, cf. picture.

Generalities

[edit]

Let(a1,b1){\displaystyle (a_{1},b_{1})} and(a2,b2){\displaystyle (a_{2},b_{2})} be ordered pairs. Then thecharacteristic (ordefining)property of the ordered pair is:(a1,b1)=(a2,b2) if and only if a1=a2 and b1=b2.{\displaystyle (a_{1},b_{1})=(a_{2},b_{2}){\text{ if and only if }}a_{1}=a_{2}{\text{ and }}b_{1}=b_{2}.}

Theset of all ordered pairs whose first entry is in some setA and whose second entry is in some setB is called theCartesian product ofA andB, and writtenA ×B. Abinary relation between setsA andB is asubset ofA ×B.

The(a,b) notation may be used for other purposes, most notably as denotingopen intervals on thereal number line. In such situations, the context will usually make it clear which meaning is intended.[1][2] For additional clarification, the ordered pair may be denoted by the variant notation⟨a,b⟩{\textstyle \langle a,b\rangle }, but this notation also has other uses.

The left and rightprojection of a pairp is usually denoted byπ1(p) andπ2(p), or byπℓ(p) andπr(p), respectively.In contexts where arbitraryn-tuples are considered,πn
i(t) is a common notation for thei-th component of ann-tuplet.

Informal and formal definitions

[edit]

In some introductory mathematics textbooks an informal (or intuitive) definition of ordered pair is given, such as

For any two objectsa andb, the ordered pair(a,b) is a notation specifying the two objectsa andb, in that order.[3]

This is usually followed by a comparison to a set of two elements; pointing out that in a seta andb must be different, but in an ordered pair they may be equal and that while the order of listing the elements of a set doesn't matter, in an ordered pair changing the order of distinct entries changes the ordered pair.

This "definition" is unsatisfactory because it is only descriptive and is based on an intuitive understanding oforder. However, as is sometimes pointed out, no harm will come from relying on this description and almost everyone thinks of ordered pairs in this manner.[4]

A more satisfactory approach is to observe that the characteristic property of ordered pairs given above is all that is required to understand the role of ordered pairs in mathematics. Hence the ordered pair can be taken as aprimitive notion, whose associated axiom is the characteristic property. This was the approach taken by theN. Bourbaki group in itsTheory of Sets, published in 1954. However, this approach also has its drawbacks as both the existence of ordered pairs and their characteristic property must be axiomatically assumed.[3]

Another way to rigorously deal with ordered pairs is to define them formally in the context of set theory. This can be done in several ways and has the advantage that existence and the characteristic property can be proven from the axioms that define the set theory. One of the most cited versions of this definition is due to Kuratowski (see below) and his definition was used in the second edition of Bourbaki'sTheory of Sets, published in 1970. Even those mathematical textbooks that give an informal definition of ordered pairs will often mention the formal definition of Kuratowski in an exercise.

Defining the ordered pair using set theory

[edit]

If one agrees thatset theory is an appealingfoundation of mathematics, then all mathematical objects must be defined assets of some sort. Hence if the ordered pair is not taken as primitive, it must be defined as a set.[5] Several set-theoretic definitions of the ordered pair are given below (see also Diepert).[6]

Wiener's definition

[edit]

Norbert Wiener proposed the first set theoretical definition of the ordered pair in 1914:[7](a,b):={{{a},∅},{{b}}}.{\displaystyle \left(a,b\right):=\left\{\left\{\left\{a\right\},\,\emptyset \right\},\,\left\{\left\{b\right\}\right\}\right\}.}He observed that this definition made it possible to define thetypes ofPrincipia Mathematica as sets.Principia Mathematica had taken types, and hencerelations of all arities, asprimitive.

Wiener used {{b}} instead of {b} to make the definition compatible withtype theory where all elements in a class must be of the same "type". Withb nested within an additional set, its type is equal to{{a},∅}{\displaystyle \{\{a\},\emptyset \}}'s.

Hausdorff's definition

[edit]

About the same time as Wiener (1914),Felix Hausdorff proposed his definition:(a,b):={{a,1},{b,2}}{\displaystyle (a,b):=\left\{\{a,1\},\{b,2\}\right\}}"where 1 and 2 are two distinct objects different from a and b."[8]

Kuratowski's definition

[edit]

In 1921Kazimierz Kuratowski offered the now-accepted definition[9][10]of the ordered pair (a,b):(a, b)K:= {{a}, {a, b}}.{\displaystyle (a,\ b)_{K}\;:=\ \{\{a\},\ \{a,\ b\}\}.}When the first and the second coordinates are identical, the definition obtains:(x, x)K={{x},{x, x}}={{x}, {x}}={{x}}{\displaystyle (x,\ x)_{K}=\{\{x\},\{x,\ x\}\}=\{\{x\},\ \{x\}\}=\{\{x\}\}}

Given some ordered pairp, the property "x is the first coordinate ofp" can be formulated as:∀Y∈p:x∈Y.{\displaystyle \forall Y\in p:x\in Y.}The property "x is the second coordinate ofp" can be formulated as:(∃Y∈p:x∈Y)∧(∀Y1,Y2∈p:(x∈Y1∧x∈Y2)→Y1=Y2).{\displaystyle (\exists Y\in p:x\in Y)\land (\forall Y_{1},Y_{2}\in p:(x\in Y_{1}\land x\in Y_{2})\rightarrow Y_{1}=Y_{2}).}In the case that the left and right coordinates are identical, the rightconjunct(∀Y1,Y2∈p:(x∈Y1∧x∈Y2)→Y1=Y2){\displaystyle (\forall Y_{1},Y_{2}\in p:(x\in Y_{1}\land x\in Y_{2})\rightarrow Y_{1}=Y_{2})} is trivially true, sinceY1=Y2{\displaystyle Y_{1}=Y_{2}} is the case.

Ifp=(x,y)={{x},{x,y}}{\displaystyle p=(x,y)=\{\{x\},\{x,y\}\}} then:

⋂p=⋂{{x},{x,y}}={x}∩{x,y}={x},{\displaystyle \bigcap p=\bigcap {\bigg \{}\{x\},\{x,y\}{\bigg \}}=\{x\}\cap \{x,y\}=\{x\},}
⋃p=⋃{{x},{x,y}}={x}∪{x,y}={x,y}.{\displaystyle \bigcup p=\bigcup {\bigg \{}\{x\},\{x,y\}{\bigg \}}=\{x\}\cup \{x,y\}=\{x,y\}.}

This is how we can extract the first coordinate of a pair (using theiterated-operation notation forarbitrary intersection andarbitrary union):π1(p)=⋃⋂p=⋃{x}=x.{\displaystyle \pi _{1}(p)=\bigcup \bigcap p=\bigcup \{x\}=x.}

This is how the second coordinate can be extracted:π2(p)=⋃{a∈⋃p|⋃p≠⋂p→a∉⋂p}=⋃{a∈{x,y}|{x,y}≠{x}→a∉{x}}=⋃{y}=y.{\displaystyle \pi _{2}(p)=\bigcup \left\{\left.a\in \bigcup p\,\right|\,\bigcup p\neq \bigcap p\rightarrow a\notin \bigcap p\right\}=\bigcup \left\{\left.a\in \{x,y\}\,\right|\,\{x,y\}\neq \{x\}\rightarrow a\notin \{x\}\right\}=\bigcup \{y\}=y.}

(ifx≠y{\displaystyle x\neq y}, then the set{y}{\displaystyle \{y\}} could be obtained more simply:{y}={a∈{x,y}|a∉{x}}{\displaystyle \{y\}=\{\left.a\in \{x,y\}\,\right|\,a\notin \{x\}\}}, but the previous formula also takes into account the case whenx=y{\displaystyle x=y}.)

Note thatπ1{\displaystyle \pi _{1}} andπ2{\displaystyle \pi _{2}} aregeneralized functions, in the sense that their domains and codomains areproper classes.

Variants

[edit]

The above Kuratowski definition of the ordered pair is "adequate" in that it satisfies the characteristic property that an ordered pair must satisfy, namely that(a,b)=(x,y)↔(a=x)∧(b=y){\displaystyle (a,b)=(x,y)\leftrightarrow (a=x)\land (b=y)}. In particular, it adequately expresses 'order', in that(a,b)=(b,a){\displaystyle (a,b)=(b,a)} is false unlessb=a{\displaystyle b=a}. There are other definitions, of similar or lesser complexity, that are equally adequate:

Thereverse definition is merely a trivial variant of the Kuratowski definition, and as such is of no independent interest. The definitionshort is so-called because it requires two rather than three pairs ofbraces. Proving thatshort satisfies the characteristic property requires theZermelo–Fraenkel set theoryaxiom of regularity.[12] Moreover, if one usesvon Neumann's set-theoretic construction of the natural numbers, then 2 is defined as the set {0, 1} = {0, {0}}, which is indistinguishable from the pair (0, 0)short. Yet another disadvantage of theshort pair is the fact that, even ifa andb are of the same type, the elements of theshort pair are not. (However, ifa = b then theshort version keeps having cardinality 2, which is something one might expect of any "pair", including any "ordered pair".)

Proving that definitions satisfy the characteristic property

[edit]

Prove: (a,b) = (c,d)if and only ifa =c andb =d.

Kuratowski:
If. Ifa =c andb =d, then {{a}, {a,b}} = {{c}, {c,d}}. Thus (a, b)K = (c,d)K.

Only if. Two cases:a =b, anda ≠b.

Ifa =b:

(a, b)K = {{a}, {a,b}} = {{a}, {a,a}} = {{a}}.
{{c}, {c,d}} = (c,d)K = (a,b)K = {{a}}.
Thus {c} = {c,d} = {a}, which impliesa =c anda =d. By hypothesis,a =b. Henceb =d.

Ifa ≠b, then (a,b)K = (c,d)K implies {{a}, {a,b}} = {{c}, {c,d}}.

Suppose {c,d} = {a}. Thenc =d =a, and so {{c}, {c,d}} = {{a}, {a,a}} = {{a}, {a}} = {{a}}. But then {{a}, {a, b}} would also equal {{a}}, so thatb =a which contradictsa ≠b.
Suppose {c} = {a,b}. Thena =b =c, which also contradictsa ≠b.
Therefore {c} = {a}, so thatc = a and {c,d} = {a,b}.
Ifd =a were true, then {c,d} = {a,a} = {a} ≠ {a,b}, a contradiction. Thusd =b is the case, so thata =c andb =d.

Reverse:
(a, b)reverse = {{b}, {a, b}} = {{b}, {b, a}} = (b, a)K.

If. If (a, b)reverse = (c, d)reverse,(b, a)K = (d, c)K. Therefore,b = d anda = c.

Only if. Ifa = c andb = d, then {{b}, {a, b}} = {{d}, {c, d}}.Thus (a, b)reverse = (c, d)reverse.

Short:[13]

If: Ifa = c andb = d, then {a, {a, b}} = {c, {c, d}}. Thus (a, b)short = (c, d)short.

Only if: Suppose {a, {a, b}} = {c, {c, d}}.Thena is in the left hand side, and thus in the right hand side.Because equal sets have equal elements, one ofa = c ora = {c, d} must be the case.

Ifa = {c, d}, then by similar reasoning as above, {a, b} is in the right hand side, so {a, b} =c or {a, b} = {c, d}.
If {a, b} =c thenc is in {c, d} =a anda is inc, and this combination contradicts the axiom of regularity, as {a, c} has no minimal element under the relation "element of."
If {a, b} = {c, d}, thena is an element ofa, froma = {c, d} = {a, b}, again contradicting regularity.
Hencea = c must hold.

Again, we see that {a, b} =c or {a, b} = {c, d}.

The option {a, b} =c anda = c implies thatc is an element ofc, contradicting regularity.
So we havea = c and {a, b} = {c, d}, and so: {b} = {a, b} \ {a} = {c, d} \ {c} = {d}, sob =d.

Quine–Rosser definition

[edit]

Rosser (1953)[14] employed a definition of the ordered pair due toQuine which requires a prior definition of thenatural numbers. LetN{\displaystyle \mathbb {N} } be the set of natural numbers and define firstσ(x):={x,if x∉N,x+1,if x∈N.{\displaystyle \sigma (x):={\begin{cases}x,&{\text{if }}x\notin \mathbb {N} ,\\x+1,&{\text{if }}x\in \mathbb {N} .\end{cases}}}The functionσ{\displaystyle \sigma } increments its argument if it is a natural number and leaves it as is otherwise; the number 0 does not appear in the range ofσ{\displaystyle \sigma }.Asx∖N{\displaystyle x\setminus \mathbb {N} } is the set of the elements ofx{\displaystyle x} not inN{\displaystyle \mathbb {N} } go on withφ(x):=σ[x]={σ(α)∣α∈x}=(x∖N)∪{n+1:n∈(x∩N)}.{\displaystyle \varphi (x):=\sigma [x]=\{\sigma (\alpha )\mid \alpha \in x\}=(x\setminus \mathbb {N} )\cup \{n+1:n\in (x\cap \mathbb {N} )\}.}This is theset image of a setx{\displaystyle x} underσ{\displaystyle \sigma },sometimes denoted byσ″x{\displaystyle \sigma ''x} as well. Applying functionφ{\displaystyle \varphi } to a setx simply increments every natural number in it. In particular,φ(x){\displaystyle \varphi (x)} never contains contain the number 0, so that for any setsx andy,φ(x)≠{0}∪φ(y).{\displaystyle \varphi (x)\neq \{0\}\cup \varphi (y).}Further, defineψ(x):=σ[x]∪{0}=φ(x)∪{0}.{\displaystyle \psi (x):=\sigma [x]\cup \{0\}=\varphi (x)\cup \{0\}.}By this,ψ(x){\displaystyle \psi (x)} does always contain the number 0.

Finally, define the ordered pair (A,B) as the disjoint union(A,B):=φ[A]∪ψ[B]={φ(a):a∈A}∪{φ(b)∪{0}:b∈B}.{\displaystyle (A,B):=\varphi [A]\cup \psi [B]=\{\varphi (a):a\in A\}\cup \{\varphi (b)\cup \{0\}:b\in B\}.}(which isφ″A∪ψ″B{\displaystyle \varphi ''A\cup \psi ''B} in alternate notation).

Extracting all the elements of the pair that do not contain 0 and undoingφ{\displaystyle \varphi } yieldsA. Likewise,B can be recovered from the elements of the pair that do contain 0.[15]

For example, the pair({{a,0},{b,c,1}},{{d,2},{e,f,3}}){\displaystyle (\{\{a,0\},\{b,c,1\}\},\{\{d,2\},\{e,f,3\}\})} is encoded as{{a,1},{b,c,2},{d,3,0},{e,f,4,0}}{\displaystyle \{\{a,1\},\{b,c,2\},\{d,3,0\},\{e,f,4,0\}\}} provideda,b,c,d,e,f∉N{\displaystyle a,b,c,d,e,f\notin \mathbb {N} }.

Intype theory and in outgrowths thereof such as the axiomatic set theoryNF, the Quine–Rosser pair has the same type as its projections and hence is termed a "type-level" ordered pair. Hence this definition has the advantage of enabling afunction, defined as a set of ordered pairs, to have a type only 1 higher than the type of its arguments. This definition works only if the set of natural numbers is infinite. This is the case inNF, but not intype theory or inNFU.J. Barkley Rosser showed that the existence of such a type-level ordered pair (or even a "type-raising by 1" ordered pair) implies theaxiom of infinity. For an extensive discussion of the ordered pair in the context of Quinian set theories, see Holmes (1998).[16]

Cantor–Frege definition

[edit]

Early in the development of the set theory, before paradoxes were discovered, Cantor followed Frege by defining the ordered pair of two sets as the class of all relations that hold between these sets, assuming that the notion of relation is primitive:[17](x,y)={R:xRy}.{\displaystyle (x,y)=\{R:xRy\}.}

This definition is inadmissible in most modern formalized set theories and is methodologically similar to defining thecardinal of a set as the class of all sets equipotent with the given set.[18]

Morse definition

[edit]

Morse–Kelley set theory makes free use ofproper classes.[19]Morse defined the ordered pair so that its projections could be proper classes as well as sets. (The Kuratowski definition does not allow this.) He first defined ordered pairs whose projections are sets in Kuratowski's manner. He thenredefined the pair(x,y)=({0}×s(x))∪({1}×s(y)){\displaystyle (x,y)=(\{0\}\times s(x))\cup (\{1\}\times s(y))}where the component Cartesian products are Kuratowski pairs of sets and wheres(x)={∅}∪{{t}∣t∈x}{\displaystyle s(x)=\{\emptyset \}\cup \{\{t\}\mid t\in x\}}

This renders possible pairs whose projections are proper classes. The Quine–Rosser definition above also admitsproper classes as projections. Similarly the triple is defined as a 3-tuple as follows:(x,y,z)=({0}×s(x))∪({1}×s(y))∪({2}×s(z)){\displaystyle (x,y,z)=(\{0\}\times s(x))\cup (\{1\}\times s(y))\cup (\{2\}\times s(z))}

The use of the singleton sets(x){\displaystyle s(x)} which has an inserted empty set allows tuples to have the uniqueness property that ifa is ann-tuple and b is anm-tuple anda =b thenn =m. Ordered triples which are defined as ordered pairs do not have this property with respect to ordered pairs.

Category theory

[edit]
Commutative diagram for the set productX1×X2.

A category-theoreticproductA ×B in acategory of sets represents the set of ordered pairs, with the first element coming fromA and the second coming fromB. In this context the characteristic property above is a consequence of theuniversal property of the product and the fact that elements of a setX can be identified with morphisms from 1 (a one element set) toX. While different objects may have the universal property, they are allnaturally isomorphic.

See also

[edit]

References

[edit]
  1. ^Lay, Steven R. (2005),Analysis / With an Introduction to Proof (4th ed.), Pearson / Prentice Hall, p. 50,ISBN 978-0-13-148101-5
  2. ^Devlin, Keith (2004),Sets, Functions and Logic / An Introduction to Abstract Mathematics (3rd ed.), Chapman & Hall / CRC, p. 79,ISBN 978-1-58488-449-1
  3. ^abWolf, Robert S. (1998),Proof, Logic, and Conjecture / The Mathematician's Toolbox, W. H. Freeman and Co., p. 164,ISBN 978-0-7167-3050-7
  4. ^Fletcher, Peter; Patty, C. Wayne (1988),Foundations of Higher Mathematics, PWS-Kent, p. 80,ISBN 0-87150-164-3
  5. ^Quine has argued that the set-theoretical implementations of the concept of the ordered pair is a paradigm for the clarification of philosophical ideas (see "Word and Object", section 53).The general notion of such definitions or implementations are discussed in Thomas Forster "Reasoning about theoretical entities".
  6. ^Randall R. Dipert (Jun 1982), "Set-Theoretical Representations of Ordered Pairs and Their Adequacy for the Logic of Relations",Canadian Journal of Philosophy,12 (2):353–374,doi:10.1080/00455091.1982.10715803,JSTOR 40231262
  7. ^Wiener's paper "A Simplification of the logic of relations" is reprinted, together with a valuable commentary on pages 224ff in van Heijenoort, Jean (1967),From Frege to Gödel: A Source Book in Mathematical Logic, 1979–1931, Harvard University Press, Cambridge MA,ISBN 0-674-32449-8 (pbk.). van Heijenoort states the simplification this way: "By giving a definition of the ordered pair of two elements in terms of class operations, the note reduced the theory of relations to that of classes".
  8. ^cf introduction to Wiener's paper in van Heijenoort 1967:224
  9. ^cf introduction to Wiener's paper in van Heijenoort 1967:224. van Heijenoort observes that the resulting set that represents the ordered pair "has a type higher by 2 than the elements (when they are of the same type)"; he offers references that show how, under certain circumstances, the type can be reduced to 1 or 0.
  10. ^Kuratowski, Casimir (1921)."Sur la notion de l'ordre dans la Théorie des Ensembles".Fundamenta Mathematicae.2 (1):161–171.doi:10.4064/fm-2-1-161-171.
  11. ^This differs from Hausdorff's definition in not requiring the two elements 0 and 1 to be distinct froma andb.
  12. ^Tourlakis, George (2003)Lectures in Logic and Set Theory. Vol. 2: Set Theory. Cambridge Univ. Press. Proposition III.10.1.
  13. ^For a formalMetamath proof of the adequacy ofshort, seehere (opthreg). Also see Tourlakis (2003), Proposition III.10.1.
  14. ^J. Barkley Rosser, 1953.Logic for Mathematicians. McGraw–Hill.
  15. ^Holmes, M. Randall:On Ordered Pairs, on: Boise State, March 29, 2009. The author usesσ1{\displaystyle \sigma _{1}} forφ{\displaystyle \varphi } andσ2{\displaystyle \sigma _{2}} forψ{\displaystyle \psi }.
  16. ^Holmes, M. Randall (1998)Elementary Set Theory with a Universal SetArchived 2011-04-11 at theWayback Machine. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this monograph via the web.
  17. ^Frege, Gottlob (1893). "144".Grundgesetze der Arithmetik(PDF). Jena: Verlag Hermann Pohle. Archived fromthe original(PDF) on 2016-10-21. Retrieved2017-09-14.
  18. ^Kanamori, Akihiro (2007).Set Theory From Cantor to Cohen(PDF). Elsevier BV. p. 22, footnote 59
  19. ^Morse, Anthony P. (1965).A Theory of Sets. Academic Press.


General
Theorems (list)
 and paradoxes
Logics
Traditional
Propositional
Predicate
Set theory
Types ofsets
Maps and cardinality
Set theories
Formal systems (list),
language and syntax
Example axiomatic
systems (list)
Proof theory
Model theory
Computability theory
Related
Overview
Venn diagram of set intersection
Axioms
Operations
  • Concepts
  • Methods
Set types
Theories
Set theorists
Types by domain and codomain
Classes/properties
Constructions
Generalizations
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ordered_pair&oldid=1310007848"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp