Editing Tuple

{{short description|Finite ordered list of elements}}
{{hatnote group|{{for|the musical term|Tuplet}}{{redirect|Octuple|the boat|Octuple scull}}{{redirect|Duodecuple|the musical technique|Twelve-tone technique}}{{redirect|Sextuple|the sporting achievement of association football|Sextuple (association football)}}
}}

In [[mathematics]], a '''tuple''' is a finite [[sequence]] or ''ordered list'' of [[number]]s or, more generally, [[mathematical object]]s, which are called the ''elements'' of the tuple. An '''{{mvar|n}}-tuple''' is a tuple of {{mvar|n}} elements, where {{mvar|n}} is a non-negative [[integer]]. There is only one 0-tuple, called the ''empty tuple''. A 1-tuple and a 2-tuple are commonly called a [[singleton (mathematics)|singleton]] and an [[ordered pair]], respectively. The term ''"infinite tuple"'' is occasionally used for ''"infinite sequences"''.

Tuples are usually written by listing the elements within parentheses "{{math|( )}}" and separated by commas; for example, {{math|(2, 7, 4, 1, 7)}} denotes a 5-tuple. Other types of brackets are sometimes used, although they may have a different meaning.{{efn|[[Square bracket]]s are used for [[matrix (mathematics)|matrices]], including [[row vector]]s. [[Braces (punctuation)|Braces]] are used for [[set (mathematics)|set]]s. Each [[programming language]] has its own convention for the different brackets.}}

An {{mvar|n}}-tuple can be formally defined as the [[image (function)|image]] of a [[function (mathematics)|function]] that has the set of the {{mvar|n}} first [[natural number]]s as its [[domain of a function|domain]]. Tuples may be also defined from ordered pairs by a [[recurrence relation|recurrence]] starting from an [[ordered pair]]; indeed, an {{mvar|n}}-tuple can be identified with the ordered pair of its {{math|(''n'' − 1)}} first elements and its {{mvar|n}}th element, for example, <math>
\left( \left( \left( 1,2 \right),3 \right),4 \right)=\left( 1,2,3,4 \right)</math>.

In [[computer science]], tuples come in many forms. Most typed [[functional programming]] languages implement tuples directly as [[product type]]s,<ref>{{cite web|url=https://wiki.haskell.org/Algebraic_data_type|title=Algebraic data type - HaskellWiki|website=wiki.haskell.org}}</ref> tightly associated with [[algebraic data type]]s, [[pattern matching]], and [[Assignment (computer science)#Parallel assignment|destructuring assignment]].<ref>{{cite web|url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment|title=Destructuring assignment|website=MDN Web Docs|date=18 April 2023 }}</ref> Many programming languages offer an alternative to tuples, known as [[Record (computer science)|record types]], featuring unordered elements accessed by label.<ref>{{cite web|url=https://stackoverflow.com/q/5525795 |title=Does JavaScript Guarantee Object Property Order?|website=Stack Overflow}}</ref> A few programming languages combine ordered tuple product types and unordered record types into a single construct, as in [[struct (C programming language)|C structs]] and Haskell records. [[Relational database]]s may formally identify their [[Row (database)|rows]] (records) as ''tuples''.

Tuples also occur in [[relational algebra]]; when programming the [[semantic web]] with the [[Resource Description Framework]] (RDF); in [[linguistics]];<ref>{{cite encyclopedia|url= http://www.oxfordreference.com/view/10.1093/acref/9780199202720.001.0001/acref-9780199202720-e-2276|title= N-tuple|encyclopedia=The Concise Oxford Dictionary of Linguistics|date= January 2007|publisher= Oxford University Press|isbn= 9780199202720|editor-first=P. H.|editor-last=Matthews|access-date= 1 May 2015}}</ref> and in [[philosophy]].<ref>
{{cite book
| last1 = Blackburn
| first1 = Simon
| author-link1 = Simon Blackburn
| year = 1994
| chapter = ordered n-tuple
| title = The Oxford Dictionary of Philosophy
| url = https://books.google.com/books?id=Mno8CwAAQBAJ
| edition = 3
| location = Oxford
| publisher = Oxford University Press
| publication-date = 2016
| page = 342
| series = Oxford guidelines quick reference
| isbn = 9780198735304
| access-date = 2017-06-30
| quote = ordered n-tuple[:] A generalization of the notion of an [...] ordered pair to sequences of n objects.
}}
</ref>

==Etymology==
The term originated as an abstraction of the sequence: single, couple/double, triple, quadruple, quintuple, sextuple, septuple, octuple, ..., {{math|''n''}}‑tuple, ..., where the prefixes are taken from the [[Latin]] names of the numerals. The unique 0-tuple is called the ''null tuple'' or ''empty tuple''. A 1‑tuple is called a ''single'' (or ''singleton''), a 2‑tuple is called an ''ordered pair'' or ''couple'', and a 3‑tuple is called a ''triple'' (or ''triplet''). The number {{math|''n''}} can be any nonnegative [[integer]]. For example, a [[complex number]] can be represented as a 2‑tuple of reals, a [[quaternion]] can be represented as a 4‑tuple, an [[octonion]] can be represented as an 8‑tuple, and a [[sedenion]] can be represented as a 16‑tuple.

Although these uses treat ''‑tuple'' as the suffix, the original suffix was ''‑ple'' as in "triple" (three-fold) or "decuple" (ten‑fold). This originates from  [[medieval Latin]]  ''plus'' (meaning "more") related to [[Greek language|Greek]] ‑πλοῦς, which replaced the classical and late antique ''‑plex'' (meaning "folded"), as in "duplex".<ref>''OED'', ''s.v.'' "triple", "quadruple", "quintuple", "decuple"</ref>{{efn|Compare the etymology of [[ploidy]], from the Greek for -fold.}}

==Properties==
The general rule for the identity of two {{math|''n''}}-tuples is
: <math>(a_1, a_2, \ldots, a_n) = (b_1, b_2, \ldots, b_n)</math> [[if and only if]] <math>a_1=b_1,\text{ }a_2=b_2,\text{ }\ldots,\text{ }a_n=b_n</math>.

Thus a tuple has properties that distinguish it from a [[Set (mathematics)|set]]:
# A tuple may contain multiple instances of the same element, so <br/>tuple <math>(1,2,2,3) \neq (1,2,3)</math>; but set <math>\{1,2,2,3\} = \{1,2,3\}</math>.
# Tuple elements are ordered: tuple <math>(1,2,3) \neq (3,2,1)</math>, but set <math>\{1,2,3\} = \{3,2,1\}</math>.
# A tuple has a finite number of elements, while a set or a [[multiset]] may have an infinite number of elements.

==Definitions==

There are several definitions of tuples that give them the properties described in the previous section.

===Tuples as functions===
The <math>0</math>-tuple may be identified as the [[Function (mathematics)#General properties|empty function]]. For <math>n \geq 1,</math> the <math>n</math>-tuple <math>\left(a_1, \ldots, a_n\right)</math> may be identified with the ([[Surjective function|surjective]]) [[Function (mathematics)#Definition|function]] 
:<math>F ~:~ \left\{ 1, \ldots, n \right\} ~\to~ \left\{ a_1, \ldots, a_n \right\}</math>

with [[Domain of a function|domain]] 
:<math>\operatorname{domain} F = \left\{ 1, \ldots, n \right\} = \left\{ i \in \N : 1 \leq i \leq n\right\}</math>

and with [[codomain]] 
:<math>\operatorname{codomain} F = \left\{ a_1, \ldots, a_n \right\},</math>

that is defined at <math>i \in \operatorname{domain} F = \left\{ 1, \ldots, n \right\}</math> by
:<math>F(i) := a_i.</math>

That is, <math>F</math> is the function defined by
:<math>\begin{alignat}{3}
1  \;&\mapsto&&\;  a_1 \\
   \;&\;\;\vdots&&\;      \\
n  \;&\mapsto&&\;  a_n \\
\end{alignat}</math>

in which case the equality 

:<math>\left(a_1, a_2, \dots, a_n\right) = \left(F(1), F(2), \dots, F(n)\right)</math>

necessarily holds.

;Tuples as sets of ordered pairs

Functions are commonly identified with their [[Graph of a function|graphs]], which is a certain set of ordered pairs. 
Indeed, many authors use graphs as the definition of a function. 
Using this definition of "function", the above function <math>F</math> can be defined as:

:<math>F ~:=~ \left\{ \left(1, a_1\right), \ldots, \left(n, a_n\right) \right\}.</math>

===Tuples as nested ordered pairs===
Another way of modeling tuples in set theory is as nested [[ordered pair]]s. This approach assumes that the notion of ordered pair has already been defined.
# The 0-tuple (i.e. the empty tuple) is represented by the empty set <math>\emptyset</math>.
# An {{math|''n''}}-tuple, with {{math|''n'' > 0}}, can be defined as an ordered pair of its first entry and an {{math|(''n'' − 1)}}-tuple (which contains the remaining entries when {{math|''n'' > 1)}}:
#: <math>(a_1, a_2, a_3, \ldots, a_n) = (a_1, (a_2, a_3, \ldots, a_n))</math>
This definition can be applied recursively to the {{math|(''n'' − 1)}}-tuple:
: <math>(a_1, a_2, a_3, \ldots, a_n) = (a_1, (a_2, (a_3, (\ldots, (a_n, \emptyset)\ldots))))</math>

Thus, for example:
: <math>
    \begin{align}
         (1, 2, 3) & = (1, (2, (3, \emptyset)))      \\
      (1, 2, 3, 4) & = (1, (2, (3, (4, \emptyset)))) \\
    \end{align}
  </math>

A variant of this definition starts "peeling off" elements from the other end:
# The 0-tuple is the empty set <math>\emptyset</math>.
# For {{math|''n'' > 0}}:
#: <math>(a_1, a_2, a_3, \ldots, a_n) = ((a_1, a_2, a_3, \ldots, a_{n-1}), a_n)</math>
This definition can be applied recursively:
: <math>(a_1, a_2, a_3, \ldots, a_n) = ((\ldots(((\emptyset, a_1), a_2), a_3), \ldots), a_n)</math>

Thus, for example:
: <math>
    \begin{align}
         (1, 2, 3) & = (((\emptyset, 1), 2), 3)      \\
      (1, 2, 3, 4) & = ((((\emptyset, 1), 2), 3), 4) \\
    \end{align}
  </math>

===Tuples as nested sets===
Using [[ordered pair#Kuratowski's definition|Kuratowski's representation for an ordered pair]], the second definition above can be reformulated in terms of pure [[set theory]]:
# The 0-tuple (i.e. the empty tuple) is represented by the empty set <math>\emptyset</math>;
# Let <math>x</math> be an {{math|''n''}}-tuple <math>(a_1, a_2, \ldots, a_n)</math>, and let <math>x \rightarrow b \equiv (a_1, a_2, \ldots, a_n, b)</math>. Then, <math>x \rightarrow b \equiv \{\{x\}, \{x, b\}\}</math>.  (The right arrow, <math>\rightarrow</math>, could be read as "adjoined with".)

In this formulation:
: <math>
   \begin{array}{lclcl}
     ()      & &                     &=& \emptyset                                    \\
             & &                     & &                                              \\
     (1)     &=& ()    \rightarrow 1 &=& \{\{()\},\{(),1\}\}                          \\
             & &                     &=& \{\{\emptyset\},\{\emptyset,1\}\}            \\
             & &                     & &                                              \\
     (1,2)   &=& (1)   \rightarrow 2 &=& \{\{(1)\},\{(1),2\}\}                        \\
             & &                     &=& \{\{\{\{\emptyset\},\{\emptyset,1\}\}\},     \\
             & &                     & & \{\{\{\emptyset\},\{\emptyset,1\}\},2\}\}    \\
             & &                     & &                                              \\
     (1,2,3) &=& (1,2) \rightarrow 3 &=& \{\{(1,2)\},\{(1,2),3\}\}                    \\
             & &                     &=& \{\{\{\{\{\{\emptyset\},\{\emptyset,1\}\}\}, \\
             & &                     & & \{\{\{\emptyset\},\{\emptyset,1\}\},2\}\}\}, \\
             & &                     & & \{\{\{\{\{\emptyset\},\{\emptyset,1\}\}\},   \\
             & &                     & & \{\{\{\emptyset\},\{\emptyset,1\}\},2\}\},3\}\}                                       \\
    \end{array}
  </math>

=={{anchor|n-tuple}}{{math|''n''}}-tuples of {{math|''m''}}-sets ==

In [[discrete mathematics]], especially [[combinatorics]] and finite [[probability theory]], {{math|''n''}}-tuples arise in the context of various counting problems and are treated more informally as ordered lists of length {{math|''n''}}.<ref>{{harvnb|D'Angelo|West|2000|p=9}}</ref> {{math|''n''}}-tuples whose entries come from a set of {{math|''m''}} elements are also called ''arrangements with repetition'', ''[[Permutation#Permutations_of_multisets|permutations of a multiset]]'' and, in some non-English literature, ''variations with repetition''. The number of {{math|''n''}}-tuples of an {{math|''m''}}-set is {{math|''m''<sup>''n''</sup>}}. This follows from the combinatorial [[rule of product]].<ref>{{harvnb|D'Angelo|West|2000|p=101}}</ref> If {{math|''S''}} is a finite set of [[cardinality]] {{math|''m''}}, this number is the cardinality of the {{math|''n''}}-fold [[Cartesian product#n-ary Cartesian power|Cartesian power]] {{math|''S'' × ''S'' × ⋯ × ''S''}}. Tuples are elements of this product set.

== Type theory ==
{{main|Product type}}

In [[type theory]], commonly used in [[programming language]]s, a tuple has a [[product type]]; this fixes not only the length, but also the underlying types of each component. Formally:
: <math>(x_1, x_2, \ldots, x_n) : \mathsf{T}_1 \times \mathsf{T}_2 \times \ldots \times \mathsf{T}_n</math>
and the [[Projection (mathematics)|projection]]s are term constructors:
: <math>\pi_1(x) : \mathsf{T}_1,~\pi_2(x) : \mathsf{T}_2,~\ldots,~\pi_n(x) : \mathsf{T}_n</math>

The tuple with labeled elements used in the [[relational model]] has a [[Record (computer science)|record type]]. Both of these types can be defined as simple extensions of the [[simply typed lambda calculus]].<ref name="pierce2002">{{cite book|last=Pierce|first=Benjamin|title=Types and Programming Languages|url=https://archive.org/details/typesprogramming00pier_207|url-access=limited|publisher=MIT Press|year=2002|isbn=0-262-16209-1|pages=[https://archive.org/details/typesprogramming00pier_207/page/n149 126]–132}}</ref>

The notion of a tuple in type theory and that in set theory are related in the following way: If we consider the natural [[model theory|model]] of a type theory, and use the Scott brackets to indicate the semantic interpretation<!-- do not link; that article needs to be a dab first-->, then the model consists of some sets <math>S_1, S_2, \ldots, S_n</math> (note: the use of italics here that distinguishes sets from types) such that:
: <math>[\![\mathsf{T}_1]\!] = S_1,~[\![\mathsf{T}_2]\!] = S_2,~\ldots,~[\![\mathsf{T}_n]\!] = S_n</math>
and the interpretation of the basic terms is:
: <math>[\![x_1]\!] \in [\![\mathsf{T}_1]\!],~[\![x_2]\!] \in [\![\mathsf{T}_2]\!],~\ldots,~[\![x_n]\!] \in [\![\mathsf{T}_n]\!]</math>.

The {{math|''n''}}-tuple of type theory has the natural interpretation as an {{math|''n''}}-tuple of set theory:<ref>Steve Awodey, [http://www.andrew.cmu.edu/user/awodey/preprints/stcsFinal.pdf ''From sets, to types, to categories, to sets''], 2009, [[preprint]]</ref>
: <math>[\![(x_1, x_2, \ldots, x_n)]\!] = (\,[\![x_1]\!], [\![x_2]\!], \ldots, [\![x_n]\!]\,)</math>
The [[unit type]] has as semantic interpretation the 0-tuple.

==See also==
* [[Arity]]
* [[Coordinate vector]]
* [[Exponential object]]
* [[Formal language]]
* [[Multidimensional Expressions#MDX data types|Multidimensional Expressions]] (OLAP)
* [[Prime k-tuple|Prime ''k''-tuple]]
* [[Relation (mathematics)]]
* [[Sequence]]
* [[Tuplespace]]
* [[:simple:Tuple_names|Tuple Names]]

==Notes==
{{notelist}}

==References==
{{Reflist}}

==Sources==
* {{citation|first1=John P.|last1=D'Angelo|first2=Douglas B.|last2=West|title=Mathematical Thinking/Problem-Solving and Proofs|year=2000|edition=2nd|publisher=Prentice-Hall|isbn=978-0-13-014412-6}}
* [[Keith Devlin]], ''The Joy of Sets''. Springer Verlag, 2nd ed., 1993, {{isbn|0-387-94094-4}}, pp. 7–8
* [[Abraham Adolf Fraenkel]], [[Yehoshua Bar-Hillel]], [[Azriel Lévy]], ''[https://books.google.com/books?id=ah2bwOwc06MC Foundations of school Set Theory]'', Elsevier Studies in Logic Vol. 67, 2nd Edition, revised, 1973, {{isbn|0-7204-2270-1}}, p. 33
* [[Gaisi Takeuti]], W. M. Zaring, ''Introduction to Axiomatic Set Theory'', Springer [[Graduate Texts in Mathematics|GTM]] 1, 1971, {{isbn|978-0-387-90024-7}}, p. 14
* George J. Tourlakis, ''[https://books.google.com/books?as_isbn=9780521753746 Lecture Notes in Logic and Set Theory. Volume 2: Set Theory]'', Cambridge University Press, 2003, {{isbn|978-0-521-75374-6}}, pp. 182–193

== External links ==
* {{Wiktionary-inline|tuple}}

{{Set theory}}
{{Authority control}}

[[Category:Data management]]
[[Category:Mathematical notation]]
[[Category:Sequences and series]]
[[Category:Basic concepts in set theory]]
[[Category:Type theory]]