HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, a tuple is a finite ordered list (sequence) of elements. An -tuple is a
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
(or ordered list) of elements, where is a non-negative
integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Roman Re ...
. 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...

ordered pair
. Mathematicians usually write tuples by listing the elements within parentheses "" and separated by commas; for example, denotes a 5-tuple. Sometimes other symbols are used to surround the elements, such as square brackets "
nbsp; In word processing In linguistics Linguistics is the science, scientific study of language. It encompasses the analysis of every aspect of language, as well as the methods for studying and modeling them. The traditional areas of li ...
or angle brackets "⟨ ⟩". Braces "" are used to specify
array ARRAY, also known as ARRAY Now, is an independent distribution company launched by film maker and former publicist Ava DuVernay Ava Marie DuVernay (; born August 24, 1972) is an American filmmaker. She won the directing award in the U.S. dram ...
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 Vector may refer to: Biology *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism; a disease vector *Vector (molecular biology), a DNA molecule used as a vehicle to artificially carr ...
. In
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of computation, automation, a ...
, tuples come in many forms. Most typed
functional programming In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...
languages implement tuples directly as
product type In programming language A programming language is a formal language comprising a Instruction set architecture, set of instructions that produce various kinds of Input/output, output. Programming languages are used in computer programming to impl ...
s, tightly associated with
algebraic data type In computer programming, especially functional programming and type theory, an algebraic data type is a kind of Data type#Composite types, composite type, i.e., a type formed by combining other types. Two common classes of algebraic types are prod ...
s,
pattern matching In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algor ...
, 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 digital database In , a database is an organized collection of stored and accessed electronically from a . Where databases are more complex they are often developed using formal techniques. The (DBMS) is the tha ...
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 has been introduced by Edgar F. Codd. The main application of relational ...
; when programming the
semantic web The Semantic Web (sometimes known as Web 3.0) is an extension of the World Wide Web The World Wide Web (WWW), commonly known as the Web, is an information system An information system (IS) is a formal, sociotechnical Sociotechnica ...

semantic web
with the
Resource Description Framework The Resource Description Framework (RDF) is a family of World Wide Web Consortium (W3C) specifications originally designed as a metadata data model. It has come to be used as a general method for conceptual description or modeling of information t ...
(RDF); in
linguistics Linguistics is the scientific study of language A language is a structured system of communication Communication (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo ...

linguistics
; and in
philosophy Philosophy (from , ) is the study of general and fundamental questions, such as those about Metaphysics, existence, reason, Epistemology, knowledge, Ethics, values, Philosophy of mind, mind, and Philosophy of language, language. Such questio ...

philosophy
.


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 languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Roman Republic, it became ...

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 can be any nonnegative
integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Roman Re ...
. For example, a
complex number In mathematics, a complex number is an element of a number system that contains the real numbers and a specific element denoted , called the imaginary unit, and satisfying the equation . Moreover, every complex number can be expressed in the for ...

complex number
can be represented as a 2‑tuple of reals, a
quaternion In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...

quaternion
can be represented as a 4‑tuple, an
octonion In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
can be represented as an 8‑tuple, and a
sedenion In abstract algebra In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), ...
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 Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share ...
''plus'' (meaning "more") related to
Greek#REDIRECT Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is approximately 10.7 million as of ...
‑πλοῦς, 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 object He or HE may refer to: Language * He (pronoun) In Modern English, ''he'' is a Grammatical number, singular, Grammatical gender, masculine, Grammatical person, third-person personal pronoun, pronoun. Morphology In Standard English, Standard M ...
by 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 multiple 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 Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents st ...
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: # 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
. For n \geq 1, the n-tuple \left(a_1, \ldots, a_n\right) may be identified with the (
surjective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

surjective
)
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...

function
:F ~:~ \left\ ~\to~ \left\ with
domain Domain may refer to: Mathematics *Domain of a function In mathematics, the domain of a Function (mathematics), function is the Set (mathematics), set of inputs accepted by the function. It is sometimes denoted by \operatorname(f), where is th ...
:\operatorname F = \left\ = \left\ and with
codomain In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

codomain
:\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) In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (ge ...

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 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...

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 \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 Set (mathematics), 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, i ...
: # 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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geom ...
, especially
combinatorics Combinatorics is an area of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geom ...
and finite
probability theory Probability theory is the branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are containe ...
, -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 In combinatorics, the rule of product or multiplication principle is a basic combinatorial principles, counting principle (a.k.a. the fundamental principle of counting). Stated simply, it is the idea that if there are a ways of doing something and ...
. If is a finite set of
cardinality In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, this number is the cardinality of the -fold Cartesian power . Tuples are elements of this product set.


Type theory

In
type theory In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...
, commonly used in
programming language A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
s, a tuple has a
product type In programming language A programming language is a formal language comprising a Instruction set architecture, set of instructions that produce various kinds of Input/output, output. Programming languages are used in computer programming to impl ...
; 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) for database In computing, a database is an organized collection of Data (computing), data stored and accessed electronically from a computer system. Where databases are more complex they are often developed using form ...
has a
record type File:Patent Roll 1201 Record Commission.jpg, upright=1.3, Extract from the Patent Rolls, Patent Roll for Regnal years of English monarchs, 3 John, King of England, John (1201–2), as published by the Record Commission in 1835 using record type R ...
. Both of these types can be defined as simple extensions of the
simply typed lambda calculus The simply typed lambda calculus (\lambda^\to), a form of type theory, is a typed lambda calculus, typed interpretation of the lambda calculus with only one type constructor (\to) that builds function types. It is the canonical and simplest example ...
. 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 In general, 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. ...
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 review, peer-reviewed scholarly or scientific journal. The preprint may be available, often as a non-typ ...
: ![(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 In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logo ...
*
Coordinate vector In linear algebra, a coordinate vector is a representation of a vector as an ordered list of numbers that describes the vector in terms of a particular ordered basis. Coordinates are always specified relative to an ordered basis. Bases and their a ...
*
Exponential object In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
*
Formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science), alphabet and are well-formedness, well-formed a ...
* OLAP: Multidimensional Expressions * Prime ''k''-tuple *
Relation (mathematics) Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...
*
Sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

Sequence
* Tuplespace


Notes


References


Sources

* *
Keith Devlin Keith J. Devlin (born 16 March 1947) is a British mathematician and popular science Popular science (also called pop-science or popsci) is an interpretation of science intended for a general audience. While science journalism focuses on recent ...
, ''The Joy of Sets''. Springer Verlag, 2nd ed., 1993, , pp. 7–8 * Abraham Adolf Fraenkel,
Yehoshua Bar-Hillel Yehoshua Bar-Hillel ( he, יהושע בר-הלל; 8 September 1915, in Vienna – 25 September 1975, in Jerusalem) was an Israeli philosopher, mathematician, and linguistics, linguist. He was a pioneer in the fields of machine translation and forma ...
, Azriel Lévy,
Foundations of school Set Theory
', Elsevier Studies in Logic Vol. 67, 2nd Edition, revised, 1973, , p. 33 *
Gaisi Takeuti was a Japanese mathematician, known for his work in proof theory. After graduating from Tokyo University, he went to Princeton University, Princeton to study under Kurt Gödel. He later became a professor at the University of Illinois at Urban ...
, 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{{Commons This category is for the foundational concepts of naive set theory, in terms of which contemporary mathematics is typically expressed. Mathematical concepts ...
Type theory