Ordered pair

In mathematics, an ordered pair is a collection of two distinguishable objects, one of which is identified as the first coordinate (or the first entry or left projection) and the other as the second coordinate (second entry, right projection). Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics and its applications a coordinate system is a system for assigning an n - Tuple of Numbers or scalars to each point The usual notation for an ordered pair is (a, b), with first coordinate a and second coordinate b. (This notation could be confused with that of an open interval on the real number line; the variant $\left \langle a,b\right \rangle$ can be used to remove this ambiguity. In Mathematics, an interval is a set of Real numbers with the property that any number that lies between two numbers in the set is also included in the set In Mathematics, the real line is simply the set R of singleton Real numbers However this term is usually used when R is to be treated as a ) The pair is "ordered" in the sense that (a, b) is different from (b, a), unless a and b are the same.

1 Generalities
2 Set theoretic definitions of the ordered pair
3 References

Generalities

Let (a₁, b₁) and (a₂, b₂) be two ordered pairs. Then the characteristic or defining property of ordered pairs is

(a₁, b₁) = (a₂, b₂) ↔ (a₁ = a₂ & b₁ = b₂). In Logic and/or Mathematics, logical conjunction or and is a two-place Logical operation that results in a value of true if both of

Ordered pairs can have other ordered pairs as entries. Hence the ordered pair enables the recursive definition of ordered n-tuples (ordered lists of n terms). In Mathematics, a tuple is a Sequence (also known as an "ordered list" of values called the components of the tuple For example, the ordered triple (a,b,c) can be defined as (a, (b,c) ), as one pair nested in another. In Mathematics a triple is an n-tuple with n being 3. A triple is a sequence of three elements This approach is mirrored in computer programming languages, where it is possible to construct a list of elements from nested ordered pairs. For example, the list (1 2 3 4 5) becomes (1, (2, (3, (4, (5, {} ))))). The Lisp programming language uses such lists as its primary data structure. Lisp (or LISP) is a family of Computer Programming languages with a long history and a distinctive fully parenthesized syntax

The notion of ordered pair is crucial for the definition of Cartesian product and relation. Cartesian square redirects here For Cartesian squares in Category theory, see Cartesian square (category theory. This article sets out the set-theoretic notion of relation For a more elementary point of view see Binary relations and Triadic relations

Set theoretic definitions of the ordered pair

The characteristic property of ordered pairs mentioned in the preceding section is all that is necessary to understand the way ordered pairs are used in the mathematical literature. However, for purposes of foundations of mathematics it has been considered desirable to express the definition of every type of mathematical object in terms of sets, and for ordered pairs this has been done in several ways.

Wiener's definition

Norbert Wiener proposed the first set theoretical definition of the ordered pair in 1914:

(x,y) := {{{x},{}}, { {y} }}. Norbert Wiener ( November 26, 1894, Columbia Missouri – March 18, 1964, Stockholm, Sweden) was an American

He observed that this definition would allow all the types of Principia Mathematica to be expressed using sets alone. The Principia Mathematica is a 3-volume work on the Foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell (In Principia Mathematica, relations of all arities were primitive. This article sets out the set-theoretic notion of relation For a more elementary point of view see Binary relations and Triadic relations )

The standard Kuratowski definition

In axiomatic set theory, the ordered pair (a,b) is usually defined as the Kuratowski pair:

(a,b)_K := {{a}, {a,b}}. Kazimierz Kuratowski ( Warsaw, February 2, 1896 &ndash June 18, 1980) was a Polish Mathematician and Logician

The statement that x is the first element of an ordered pair p can then be formulated as

$\forall{Y}{\in}{p}:{x}{\in}{Y}$

and that x is the second element of p as

$(\exist{Y}{\in}{p}:{x}{\in}{Y})\and(\forall{Y_{1},Y_{2}}{\in}{p}:Y_{1}\ne Y_{2}\rarr ({x}{\notin}{Y_{1}}\or{x}{\notin}{Y_{2}}))$ .

Note that this definition is still valid for the ordered pair p = (x,x) = { {x}, {x,x} } = { {x}, {x} } = { {x} }; in this case the statement $(\forall{Y_{1},Y_{2}}{\in}{p}:Y_{1}\ne Y_{2}\rarr ({x}{\notin}{Y_{1}}\or{x}{\notin}{Y_{2}}))$ is trivially true, since it is never the case that Y₁ ≠ Y₂.

Variant definitions

The above definition of an ordered pair is "adequate", in the sense that it satisfies the characteristic property that an ordered pair must have (namely: if (a,b)=(x,y), then a=x and b=y), but also arbitrary, as there are many other definitions which are no more complicated and would also be adequate. Examples for other possible definitions include

(a,b)_reverse:= { {b}, {a,b} }
(a,b)_short:= { a, {a,b} }
(a, b)₀₁:= { {0,a}, {1,b} }

The "reverse" pair is almost never used, as it has no obvious advantages (nor disadvantages) over the usual Kuratowski pair. The "short" pair has the disadvantage that the proof of the characteristic pair property (see above) is more complicated than for the Kuratowski pair (the axiom of regularity has to be used); moreover, as the number 2 is often defined as the set { 0, 1 } = { {}, {0} }, this would mean that 2 is the pair (0,0)_short. In mathematics the axiom of regularity (also known as the axiom of foundation) is one of the axioms of Zermelo-Fraenkel set theory and was introduced by.

Proving the characteristic property of ordered pairs

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

Kuratowski:

If a=b:

(a,b)_K = {{a}, {a,b}} = {{a}, {a,a}} = { {a} },

and (c,d)_K = {{c},{c,d}} = { {a} }.

Thus {c} = {c,d} = {a}, and c=d=a=b.

If a≠b, then {{a}, {a,b}} = {{c},{c,d}}.

Suppose {c,d} = {a}. Then c=d=a, and so {{c},{c,d}} = {{a}, {a,a}} = {{a}, {a}} = { {a} }. But then {{a}, {a,b}} would also equal { {a} }, so b=a, which contradicts a≠b.

Suppose {c} = {a,b}. Then a=b=c, which contradicts a≠b.

Therefore {c} = {a}, or c=a, and {c,d} = {a,b}.

If it were true that d=a, then {c,d} = {a,a} = {a} ≠ {a,b}, a contradiction. So d=b. Thus a=c and b=d.

Conversely, if a=c and b=d, then {{a},{a,b} = {{c},{c,d}}. Thus (a,b)_K = (c,d)_K.

Reverse: (a,b)_reverse = {{b},{a,b}} = {{b},{b,a}} = (b,a)_K.

If (a,b)_reverse = (c,d)_reverse, (b,a)_K = (d,c)_K. Therefore b=d and a=c.

Conversely, if a=c and b=d, then {{b},{a,b}} = {{d},{c,d}}. Thus (a,b)_reverse = (c,d)_reverse.

Quine-Rosser definition

Rosser (1953) made extensive use of a definition of the ordered pair due to Willard van Orman Quine. John Barkley Rosser Sr (1907–1989 was an American Logician, a student of Alonzo Church, and known for his part in the Church-Rosser theorem Willard Van Orman Quine (June 25 1908 Akron, Ohio &ndash December 25 2000 (known to intimates as "Van" The Quine-Rosser definition requires a prior definition of the natural numbers. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an Let $\N$ be the set of natural numbers, and define

$\varphi(x) = (x \setminus \N) \cup \{n+1 : n \in (x \cap \N) \}.$

Applying this function simply increments every natural number in x. In particular, $\varphi(x)$ does not contain the number 0, so that for any sets x and y,

$\varphi(x) \not= \{0\} \cup \varphi(y)$ .

Define the ordered pair (A,B) as

$(A,B) = \{\varphi(a) : a \in A\} \cup \{\varphi(b) \cup \{0\} : b \in B \}$

Extracting all the elements of the pair that do not contain 0 and undoing $\varphi$ yields A. Likewise, B can be recovered from the elements of the pair that do contain 0.

This definition of the ordered pair has a single advantage. In type theory, and in set theories such as New Foundations that are outgrowths of type theory, this pair is of the same type as its projections (and hence is termed a "type-level" ordered pair). In Mathematics, Logic and Computer science, type theory is any of several Formal systems that can serve as alternatives to Naive set theory In Mathematical logic, New Foundations ( NF) is an Axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of Hence a function, defined as a set of ordered pairs, has a type only 1 higher than the type of its arguments. For an extensive discussion of ordered pairs in the context of Quinian set theories, see Holmes (1998).

Morse definition

Morse-Kelley set theory, set out in Morse (1965), makes free use of proper classes. In the Foundation of mathematics, Kelley–Morse (KM or Morse–Kelley (MK set theory is a first order Axiomatic set theory that is closely In Set theory and its applications throughout Mathematics, a class is a collection of sets (or sometimes other mathematical objects that can be unambiguously Morse defined the ordered pair so as to allow its projections to 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 then redefined the pair (x,y) as $(x \times \{0\}) \cup (y \times \{1\})$ , where the component Cartesian products are Kuratowski pairs on sets. This second step renders possible pairs whose projections are proper classes. The Rosser definition in the preceding section also admits proper classes as projections.

Category theory

Product is the category theoretic notion most similar to that of ordered pair. In Category theory, the product of two (or more objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets While a number of objects may play the role of pairs, they are all equivalent in the sense of being categorically isomorphic. In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective

References

Holmes, Randall, 1998. Elementary Set Theory with a Universal Set. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this monograph via the web. Copyright is reserved.
Morse, Anthony P. , 1965. A Theory of Sets. Academic Press
J. Barkley Rosser, 1953. John Barkley Rosser Sr (1907–1989 was an American Logician, a student of Alonzo Church, and known for his part in the Church-Rosser theorem Logic for mathematicians. McGraw-Hill.

Dictionary

-noun

(set theory) A set containing exactly two elements in a fixed order, so that, when the elements are different, exchanging them gives a different set. Notation: (a, b) or <math>\langle a, b\rangle</math>

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents