View source for Tuple

{{short description|Finite ordered list of elements}}
{{About|the mathematical concept|the musical term|Tuplet}}
{{Redir|Octuple|the type of rowing boat|Octuple scull}}
{{Redir|Duodecuple|the term in music|Twelve-tone technique}}

In [[mathematics]], a '''tuple''' is a finite ordered list (sequence) of [[Element (mathematics)|elements]].  An '''{{math|''n''}}-tuple''' is a [[sequence]] (or ordered list) of {{math|''n''}} elements, where {{math|''n''}} is a non-negative [[integer]]. There is only one 0-tuple, an empty sequence, or empty tuple, as it is referred to. An {{math|''n''}}-tuple is [[Recursive definition|defined inductively]] using the construction of an [[ordered pair]].

Mathematicians usually write 'tuples' by listing the elements within parentheses "<math>(\text{ })</math>" and separated by commas; for example, <math>(2, 7, 4, 1, 7)</math> denotes a 5-tuple. Sometimes other symbols are used to surround the elements, such as square brackets "[ ]" or angle brackets "⟨ ⟩". Braces "{ }" are only used in defining arrays in some programming languages such as [[C++]] and [[Java (programming language)|Java]], but not in mathematical expressions, as they are the standard notation for [[Set (mathematics)|sets]]. The term ''tuple'' can often occur when discussing other mathematical objects, such as [[Vector (mathematics and physics)|vectors]].

In [[computer science]], tuples come in many forms. In [[Dynamic programming language|dynamically typed languages]], such as [[Lisp (programming language)|Lisp]], lists are commonly used as tuples.{{citation needed|date =May 2017}} 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|author=|date=|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|author=|date=|website=MDN Web Docs}}</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?|author=|date=|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 web|url= http://www.oxfordreference.com/view/10.1093/acref/9780199202720.001.0001/acref-9780199202720-e-2276|title= N‐tuple - Oxford Reference|work= oxfordreference.com|accessdate= 1 May 2015}}</ref> and in [[philosophy]].<ref>
{{cite book
| last1 = Blackburn
| first1 = Simon
| author-link1 = Simon Blackburn
| orig-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 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 ''‑uple'' 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.}}

===Names for tuples of specific lengths===
{{cot|Table of names and variants for specific lengths}}
{| class="wikitable"
|-
! Tuple length, <math>n</math> !! Name !! Alternative names
|-
| align="right" | 0 || empty tuple || null tuple / empty sequence / unit
|-
| align="right" | 1 || monuple || single / [[Singleton (mathematics)|singleton]] / monad
|-
| align="right" | 2 || couple || double / ordered pair / two-ple / duad / twin / dual
|-
| align="right" | 3 || triple || treble / triplet / triad
|-
| align="right" | 4 || quadruple || quad / tetrad
|-
| align="right" | 5 || quintuple || pentuple / quint / pentad
|-
| align="right" | 6 || sextuple ||hextuple
|-
| align="right" | 7 || septuple ||heptuple
|-
| align="right" | 8 || octuple || 
|-
| align="right" | 9 || nonuple || 
|-
| align="right" | 10 || decuple || 
|-
| align="right" | 11 || undecuple || hendecuple
|-
| align="right" | 12 || duodecuple || 
|-
| align="right" | 13 || tredecuple || 
|-
| align="right" | 14 || quattuordecuple || 
|-
| align="right" | 15 || quindecuple ||
|-
| align="right" | 16 || sexdecuple ||
|-
| align="right" | 17 || septendecuple ||
|-
| align="right" | 18 || octodecuple ||
|-
| align="right" | 19 || novemdecuple ||
|-
| align="right" | 20 || vigintuple ||
|-
| align="right" | 21 || unvigintuple ||
|-
| align="right" | 22 || duovigintuple ||
|-
| align="right" | 23 || trevigintuple ||
|-
| align="right" | 24 || quattuorvigintuple ||
|-
| align="right" | 25 || quinvigintuple ||
|-
| align="right" | 26 || sexvigintuple ||
|-
| align="right" | 27 || septenvigintuple ||
|-
| align="right" | 28 || octovigintuple ||
|-
| align="right" | 29 || novemvigintuple ||
|-
| align="right" | 30 || trigintuple ||
|-
| align="right" | 31 || untrigintuple ||
|-
| align="right" | 40 || quadragintuple ||
|-
| align="right" | 41 || unquadragintuple ||
|-
| align="right" | 50 || quinquagintuple ||
|-
| align="right" | 60 || sexagintuple ||
|-
| align="right" | 70 || septuagintuple ||
|-
| align="right" | 80 || octogintuple ||
|-
| align="right" | 90 || nongentuple ||
|-
| align="right" | 100 || centuple ||
|-
| align="right" | 1,000 || milluple ||
|-
|}
{{cob}}

==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===
If we are dealing with sets, an {{math|''n''}}-tuple can be regarded as a [[Function (mathematics)#Definition|function]], {{math|''F''}},  whose domain is the tuple's implicit set of element indices, {{math|''X''}}, and whose codomain, {{math|''Y''}}, is the tuple's set of elements. Formally:
: <math>(a_1, a_2, \dots, a_n) \equiv (X,Y,F)</math>
where:
: <math>
    \begin{align}
      X & = \{1, 2, \dots, n\} = \{i\in\mathbb N\mid 1\leq i\leq n\}                       \\
      Y & = \{a_1, a_2, \ldots, a_n\}                \\
      F & = \{(1, a_1), (2, a_2), \ldots, (n, a_n)\}. \\
    \end{align}
  </math>
In slightly less formal notation this says:
:<math> (a_1, a_2, \dots, a_n) := (F(1), F(2), \dots, F(n)).</math>

Using this definition of <math>n</math>-tuples, it follows that there is only one <math>0</math>-tuple, the [[Function_(mathematics)#General_properties|empty function]].

===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; thus a 2-tuple 
# 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 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#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|publisher=MIT Press|year=2002|isbn=0-262-16209-1|pages=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]]
* [[Exponential object]]
* [[Formal language]]
* [[Multidimensional Expressions#MDX data types|OLAP: Multidimensional Expressions]]
* [[Prime k-tuple]]
* [[Relation (mathematics)]]
* [[Tuplespace]]

==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]]