| Ordered Pair |
Article Index for Ordered |
Website Links For Pair |
Information AboutOrdered Pair |
| CATEGORIES ABOUT ORDERED PAIR | |
| basic concepts in set theory | |
| order theory | |
|
(The notation (''a'', ''b'') is also used to denote an Open Interval on the Real Number Line ; context should make it clear which meaning is meant. To distinguish the two meanings, the ordered pair is sometimes written as .) Two ordered pairs (''a''1, ''b''1) and (''a''2, ''b''2) are equal if and only if ''a''1 = ''a''2 and ''b''1 = ''b''2. The Set of all ordered pairs whose first element is in some set ''X'' and second element in some set ''Y'' is called the Cartesian Product of ''X'' and ''Y'', and written ''X'' × ''Y''. Subset s of ''X'' × ''Y'' can be used to define a Binary Relation . Ordered triples and s. This approach is mirrored in programming languages: It is possible to represent a List of elements as a construction of 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. In Axiomatic Set Theory , where all mathematical objects are given set-theoretic definitions, the ordered pair (''a'', ''b'') is usually defined as the Kuratowski pair (''a'', ''b'')K := : ∀ ''Y'' ∈ ''p'' : ''x'' ∈''Y'' and that ''x'' is the second element of ''p'' as : (∃ ''Y'' ∈ ''p'' : ''x'' ∈ ''Y'') ∧ (∀ ''Y''1 ∈ ''p'', ∀ ''Y''2 ∈ ''p'' : ''Y''1 ≠ ''Y''2 → (''x'' ∉ ''Y''1 ∨ ''x'' ∉ ''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 (∀ ''Y''1 ∈ ''p'', ∀ ''Y''2 ∈ ''p'' : ''Y''1 ≠ ''Y''2 → (''x'' ∉ ''Y''1 ∨ ''x'' ∉ ''Y''2)) is trivially true, since it is never the case that ''Y''1 ≠ ''Y''2. 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'')01:= { {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 in set theory sometimes defined as the set { 0, 1 } = { {}, {0} }, this would mean that 2 is a pair, 2 = (0,0)short. The first set theoretical definition of the ordered pair was given by Norbert Wiener in 1914: he defined as and observed that this would allow all the types of Principia Mathematica to be expressed using sets alone (relations of all arities were primitive in that work). For a more general treatment, see Product (category Theory) . Category Theory tells us that although many objects may play the role of pairs, they are all equivalent in the sense of being categorically Isomorphic . Proofs of the characteristic property of ordered pairs :(a,b)K:= (a,b)K=(c,d)K. If a=b, (a,b)K=={ {a} }, and then (c,d)K=={ {a} }. Thus, {c}={a}={c,d}, or c=d=a=b. If a≠b, =. If {c,d}={a}, c=d=a, or ==={ {a} }. If {c}={a,b}, a=b=c, and it's a contradiction that a≠b. Therefore {c}={a}, or c=a, and {c,d}={a,b}. And if d=a, {c,d}={a,a}={a}≠{a,b}. So d=b. Thus, a=c and b=d. Conversely, If a=c and b=d, . Thus, (a,b)K=(c,d)K. :(a,b)reverse:= (a,b)reverse===(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, =. Thus, (a,b)reverse=(c,d)reverse. ROSSER DEFINITION In ''Logic'' ( 1953 ), Rosser uses a different definition (ultimately due to Willard Van Orman Quine ), one which requires that a definition of the Natural Number s be in place. Let ''Nn'' be the set of natural numbers, and define : That is, φ(''x'') contains the successor of every natural number in ''x'', together with all the non-numbers from ''x''. In particular, it does not contain the number 0, so that for any sets ''A'' and ''B'', . Then the ordered pair (''A'',''B'') may be defined by adjoining 0 to each element of φ(''B''), and uniting the result with φ(''A''): : The component ''A'' may be recovered from the pair by extracting all the elements of the pair that do not contain 0, and vice-versa for ''B''. It is important to note that this pair is the same type as its projections in a simple typed theory of sets, which is useful in the context of New Foundations . MORSE DEFINITION In his ''A theory of sets'', Morse defined an ordered pair suitable for use in a theory with Proper Class es, such as Morse-Kelley Set Theory . He first defined the pair for sets only using the usual definition of Kuratowski, then ''redefined'' the pair ''(x,y)'' as (where the component cartesian products are defined in terms of the usual pair on sets). This second pair has the property that pairs of classes are defined as easily as pairs of sets. Rosser's definition will also work with proper classes. REFERENCES
|
|
|