Tuple

{{For|the musical term|Tuplet}} {{Redirect|Octuple|the boat|Octuple scull}} {{Redirect|Sextuple|the sports achievement in association football|Sextuple (association football)}}

In mathematics, a '''tuple''' is a finite sequence (or ordered list) of numbers. More generally, it is a sequence of mathematical objects, 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'' 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 brackets are used for matrices, including row vectors. Braces are used for sets. Each programming language has its own convention for the different brackets.}}

An {{mvar|n}}-tuple can be formally defined as the image of a function that has the set of the first {{mvar|n}} natural numbers as its domain ({{math|1, 2, ..., ''n''}}). Tuples may be also defined from ordered pairs by a 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 types,<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 types, pattern matching, and 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 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 C structs and Haskell records. Relational databases may formally identify their 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 ‑πλοῦς, 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: # 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 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 :<math>F ~:~ \left\{ 1, \ldots, n \right\} ~\to~ \left\{ a_1, \ldots, a_n \right\}</math>

with 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 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 pairs. 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 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'', ''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 power {{math|''S'' × ''S'' × ⋯ × ''S''}}. Tuples are elements of this product set.

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

In type theory, commonly used in programming languages, 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 projections 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 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 of a type theory, and use the Scott brackets to indicate the semantic interpretation, 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.

For a list of tuple types in programming languages, see Product type#Product types in programming languages.

==Notes== {{notelist}}

==References== {{Reflist}}

==Sources== * {{citation|author1-link=John D'Angelo|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 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}}

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