HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a tuple is a finite ordered list (
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
) of elements. An -tuple is a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
(or ordered list) of elements, where is a non-negative
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defined inductively using the construction of an
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
. Mathematicians usually write tuples by listing the elements within parentheses "" and separated by a comma and a space; for example, denotes a 5-tuple. Sometimes other symbols are used to surround the elements, such as square brackets " nbsp; or angle brackets "⟨ ⟩". Braces "" are used to specify
array An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
s in some programming languages but not in mathematical expressions, as they are the standard notation for sets. The term ''tuple'' can often occur when discussing other mathematical objects, such as vectors. In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (inclu ...
, tuples come in many forms. Most typed
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
languages implement tuples directly as
product type In programming languages and type theory, a product of ''types'' is another, compounded, type in a structure. The "operands" of the product are types, and the structure of a product type is determined by the fixed order of the operands in the prod ...
s, tightly associated with
algebraic data type In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite type, i.e., a type formed by combining other types. Two common classes of algebraic types are product types (i.e. ...
s, pattern matching, and destructuring assignment. Many programming languages offer an alternative to tuples, known as record types, featuring unordered elements accessed by label. 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 database A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...
s may formally identify their rows (records) as ''tuples''. Tuples also occur in
relational algebra In database theory, relational algebra is a theory that uses algebraic structures with a well-founded semantics for modeling data, and defining queries on it. The theory was introduced by Edgar F. Codd. The main application of relational alge ...
; when programming the semantic web with the
Resource Description Framework The Resource Description Framework (RDF) is a World Wide Web Consortium (W3C) standard originally designed as a data model for metadata. It has come to be used as a general method for description and exchange of graph data. RDF provides a variety of ...
(RDF); in
linguistics Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Lingui ...
; and in
philosophy Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such questions are often posed as problems to be studied or resolved. ...
.


Etymology

The term originated as an abstraction of the sequence: single, couple/double, triple, quadruple, quintuple, sextuple, septuple, octuple, ..., ‑tuple, ..., where the prefixes are taken from the
Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally a dialect spoken in the lower Tiber area (then known as Latium) around present-day Rome, but through the power of ...
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 can be any nonnegative
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
. For example, a
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the fo ...
can be represented as a 2‑tuple of reals, a
quaternion In mathematics, the quaternion number system extends the complex numbers. Quaternions were first described by the Irish mathematician William Rowan Hamilton in 1843 and applied to mechanics in three-dimensional space. Hamilton defined a quat ...
can be represented as a 4‑tuple, an
octonion In mathematics, the octonions are a normed division algebra over the real numbers, a kind of hypercomplex number system. The octonions are usually represented by the capital letter O, using boldface or blackboard bold \mathbb O. Octonions hav ...
can be represented as an 8‑tuple, and a
sedenion In abstract algebra, the sedenions form a 16- dimensional noncommutative and nonassociative algebra over the real numbers; they are obtained by applying the Cayley–Dickson construction to the octonions, and as such the octonions are isomorphic ...
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 Medieval Latin was the form of Literary Latin used in Roman Catholic Western Europe during the Middle Ages. In this region it served as the primary written language, though local languages were also written to varying degrees. Latin functioned ...
''plus'' (meaning "more") related to
Greek Greek may refer to: Greece Anything of, from, or related to Greece, a country in Southern Europe: *Greeks, an ethnic group. *Greek language, a branch of the Indo-European language family. **Proto-Greek language, the assumed last common ancestor ...
‑πλοῦς, which replaced the classical and late antique ''‑plex'' (meaning "folded"), as in "duplex".


Names for tuples of specific lengths

Note that for n \geq 3, the tuple name in the table above can also function as a verb meaning "to multiply he direct objectby n"; for example, "to quintuple" means "to multiply by 5". If n = 2, then the associated verb is "to double". There is also a verb "sesquiple", meaning "to multiply by 3/2". Theoretically, "monuple" could be used in this way too.


Properties

The general rule for the identity of two -tuples is : (a_1, a_2, \ldots, a_n) = (b_1, b_2, \ldots, b_n)
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bico ...
a_1=b_1,\texta_2=b_2,\text\ldots,\texta_n=b_n. Thus a tuple has properties that distinguish it from a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
: # A tuple may contain multiple instances of the same element, so
tuple (1,2,2,3) \neq (1,2,3); but set \ = \. # Tuple elements are ordered: tuple (1,2,3) \neq (3,2,1), but set \ = \. # A tuple has a finite number of elements, while a set or a
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that ...
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 0-tuple may be identified as the
empty function In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the func ...
. For n \geq 1, the n-tuple \left(a_1, \ldots, a_n\right) may be identified with the (
surjective In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
) function :F ~:~ \left\ ~\to~ \left\ with
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined ** Domain of definition of a partial function ** Natural domain of a partial function ** Domain of holomorphy of a function * ...
:\operatorname F = \left\ = \left\ and with
codomain In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either t ...
:\operatorname F = \left\, that is defined at i \in \operatorname F = \left\ by :F(i) := a_i. That is, F is the function defined by :\begin 1 \;&\mapsto&&\; a_1 \\ \;&\;\;\vdots&&\; \\ n \;&\mapsto&&\; a_n \\ \end in which case the equality :\left(a_1, a_2, \dots, a_n\right) = \left(F(1), F(2), \dots, F(n)\right) necessarily holds. ;Tuples as sets of ordered pairs Functions are commonly identified with their
graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...
, 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 F can be defined as: :F ~:=~ \left\.


Tuples as nested ordered pairs

Another way of modeling tuples in Set Theory is as nested
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
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 \emptyset. # An -tuple, with , can be defined as an ordered pair of its first entry and an -tuple (which contains the remaining entries when : #: (a_1, a_2, a_3, \ldots, a_n) = (a_1, (a_2, a_3, \ldots, a_n)) This definition can be applied recursively to the -tuple: : (a_1, a_2, a_3, \ldots, a_n) = (a_1, (a_2, (a_3, (\ldots, (a_n, \emptyset)\ldots)))) Thus, for example: : \begin (1, 2, 3) & = (1, (2, (3, \emptyset))) \\ (1, 2, 3, 4) & = (1, (2, (3, (4, \emptyset)))) \\ \end A variant of this definition starts "peeling off" elements from the other end: # The 0-tuple is the empty set \emptyset. # For : #: (a_1, a_2, a_3, \ldots, a_n) = ((a_1, a_2, a_3, \ldots, a_), a_n) This definition can be applied recursively: : (a_1, a_2, a_3, \ldots, a_n) = ((\ldots(((\emptyset, a_1), a_2), a_3), \ldots), a_n) Thus, for example: : \begin (1, 2, 3) & = (((\emptyset, 1), 2), 3) \\ (1, 2, 3, 4) & = ((((\emptyset, 1), 2), 3), 4) \\ \end


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 Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
: # The 0-tuple (i.e. the empty tuple) is represented by the empty set \emptyset; # Let x be an -tuple (a_1, a_2, \ldots, a_n), and let x \rightarrow b \equiv (a_1, a_2, \ldots, a_n, b). Then, x \rightarrow b \equiv \. (The right arrow, \rightarrow, could be read as "adjoined with".) In this formulation: : \begin () & & &=& \emptyset \\ & & & & \\ (1) &=& () \rightarrow 1 &=& \ \\ & & &=& \ \\ & & & & \\ (1,2) &=& (1) \rightarrow 2 &=& \ \\ & & &=& \ \\ & & & & \\ (1,2,3) &=& (1,2) \rightarrow 3 &=& \ \\ & & &=& \ \\ \end


-tuples of -sets

In
discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuo ...
, especially
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
and finite
probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
, -tuples arise in the context of various counting problems and are treated more informally as ordered lists of length . -tuples whose entries come from a set of elements are also called ''arrangements with repetition'', '' permutations of a multiset'' and, in some non-English literature, ''variations with repetition''. The number of -tuples of an -set is . This follows from the combinatorial rule of product. If is a finite set of
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
, this number is the cardinality of the -fold Cartesian power . Tuples are elements of this product set.


Type theory

In
type theory In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a founda ...
, commonly used in
programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programmin ...
s, a tuple has a
product type In programming languages and type theory, a product of ''types'' is another, compounded, type in a structure. The "operands" of the product are types, and the structure of a product type is determined by the fixed order of the operands in the prod ...
; this fixes not only the length, but also the underlying types of each component. Formally: : (x_1, x_2, \ldots, x_n) : \mathsf_1 \times \mathsf_2 \times \ldots \times \mathsf_n and the projections are term constructors: : \pi_1(x) : \mathsf_1,~\pi_2(x) : \mathsf_2,~\ldots,~\pi_n(x) : \mathsf_n The tuple with labeled elements used in the
relational model The relational model (RM) is an approach to managing data using a structure and language consistent with first-order predicate logic, first described in 1969 by English computer scientist Edgar F. Codd, where all data is represented in terms of ...
has a record type. Both of these types can be defined as simple extensions of the simply typed lambda calculus. 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 A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models ...
of a type theory, and use the Scott brackets to indicate the semantic interpretation, then the model consists of some sets S_1, S_2, \ldots, S_n (note: the use of italics here that distinguishes sets from types) such that: : ![\mathsf_1!.html"_;"title="mathsf_1.html"_;"title="![\mathsf_1">![\mathsf_1!">mathsf_1.html"_;"title="![\mathsf_1">![\mathsf_1!=_S_1,~[\![\mathsf_2.html" ;"title="mathsf_1">![\mathsf_1!.html" ;"title="mathsf_1.html" ;"title="![\mathsf_1">![\mathsf_1!">mathsf_1.html" ;"title="![\mathsf_1">![\mathsf_1!= S_1,~[\![\mathsf_2">mathsf_1">![\mathsf_1!.html" ;"title="mathsf_1.html" ;"title="![\mathsf_1">![\mathsf_1!">mathsf_1.html" ;"title="![\mathsf_1">![\mathsf_1!= S_1,~[\![\mathsf_2!] = S_2,~\ldots,~[\![\mathsf_n]\!] = S_n and the interpretation of the basic terms is: : [\![x_1]\!] \in ! mathsf_1!~ ![x_2!.html"_;"title="_2.html"_;"title="![x_2">![x_2!">_2.html"_;"title="![x_2">![x_2!\in_[\![\mathsf_2.html" ;"title="_2">![x_2!.html" ;"title="_2.html" ;"title="![x_2">![x_2!">_2.html" ;"title="![x_2">![x_2!\in [\![\mathsf_2">_2">![x_2!.html" ;"title="_2.html" ;"title="![x_2">![x_2!">_2.html" ;"title="![x_2">![x_2!\in [\![\mathsf_2!],~\ldots,~[\![x_n]\!] \in [\![\mathsf_n]\!]. The -tuple of type theory has the natural interpretation as an -tuple of set theory:Steve Awodey
''From sets, to types, to categories, to sets''
2009,
preprint In academic publishing, a preprint is a version of a scholarly or scientific paper that precedes formal peer review and publication in a peer-reviewed scholarly or scientific journal. The preprint may be available, often as a non-typeset vers ...
: ![(x_1,_x_2,_\ldots,_x_n)!.html" ;"title="x_1,_x_2,_\ldots,_x_n).html" ;"title="![(x_1, x_2, \ldots, x_n)">![(x_1, x_2, \ldots, x_n)!">x_1,_x_2,_\ldots,_x_n).html" ;"title="![(x_1, x_2, \ldots, x_n)">![(x_1, x_2, \ldots, x_n)!= (\,[\![x_1]\!], ![x_2!], \ldots, [\![x_n]\!]\,) The unit type has as semantic interpretation the 0-tuple.


See also

*
Arity Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
* Coordinate vector *
Exponential object In mathematics, specifically in category theory, an exponential object or map object is the categorical generalization of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed ...
*
Formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sy ...
* OLAP: Multidimensional Expressions * Prime ''k''-tuple *
Relation (mathematics) In mathematics, a relation on a set may, or may not, hold between two given set members. For example, ''"is less than"'' is a relation on the set of natural numbers; it holds e.g. between 1 and 3 (denoted as 1 is an asymmetric relation, but ...
*
Sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
* Tuplespace


Notes


References


Sources

* * Keith Devlin, ''The Joy of Sets''. Springer Verlag, 2nd ed., 1993, , pp. 7–8 * Abraham Adolf Fraenkel, Yehoshua Bar-Hillel, Azriel Lévy,
Foundations of school Set Theory
', Elsevier Studies in Logic Vol. 67, 2nd Edition, revised, 1973, , p. 33 * Gaisi Takeuti, W. M. Zaring, ''Introduction to Axiomatic Set Theory'', Springer GTM 1, 1971, , p. 14 * George J. Tourlakis,
Lecture Notes in Logic and Set Theory. Volume 2: Set Theory
', Cambridge University Press, 2003, , pp. 182–193


External links

* {{Authority control Data management Mathematical notation Sequences and series Basic concepts in set theory Type theory