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 calle ...
) 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 calle ...
(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 language ...
. 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;
In word processing and digital typesetting, a non-breaking space, , also called NBSP, required space, hard space, or fixed space (though it is not of fixed width), is a space character that prevents an automatic line break at its position. In ...
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 Applied science, practical discipli ...
, tuples come in many forms. Most typed
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
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., t ...
s,
pattern matching
In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be ...
, and
destructuring assignment
In computer programming, an assignment statement sets and/or re-sets the value stored in the storage location(s) denoted by a variable name; in other words, it copies a value into the variable. In most imperative programming languages, the assi ...
. 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 algebra ...
; 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. Linguis ...
; 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. Some ...
.
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 the ...
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 language ...
. 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 form ...
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 quatern ...
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 have e ...
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 to ...
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
, 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), an English pronoun
* He (kana), the romanization of the Japanese kana へ
* He (letter), the fifth letter of many Semitic alphabets
* He (Cyrillic), a letter of the Cyrillic script called ''He'' ...
by
"; for example, "to quintuple" means "to multiply by 5". If
, 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
:
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 bicondi ...
.
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
; but set
.
# Tuple elements are ordered: tuple
, 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 e ...
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
-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 functi ...
. For
the
-tuple
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 i ...
)
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
:
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
* Do ...
:
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 the ...
:
that is defined at
by
:
That is,
is the function defined by
:
in which case the equality
:
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 discre ...
, 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
can be defined as:
:
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
.
# An -tuple, with , can be defined as an ordered pair of its first entry and an -tuple (which contains the remaining entries when :
#:
This definition can be applied recursively to the -tuple:
:
Thus, for example:
:
A variant of this definition starts "peeling off" elements from the other end:
# The 0-tuple is the empty set
.
# For :
#:
This definition can be applied recursively:
:
Thus, for example:
:
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 conce ...
:
# The 0-tuple (i.e. the empty tuple) is represented by the empty set
;
# Let
be an -tuple
, and let
. Then,
. (The right arrow,
, could be read as "adjoined with".)
In this formulation:
:
-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 continuous f ...
, 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 appl ...
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 o ...
, -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 counting principle (a.k.a. the fundamental principle of counting). Stated simply, it is the intuitive idea that if there are a ways of doing something and b ways of doin ...
. 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
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\tim ...
. 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 foundat ...
, 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 programming ...
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:
:
and the
projection
Projection, projections or projective may refer to:
Physics
* Projection (physics), the action/process of light, heat, or sound reflecting from a surface to another in a different direction
* The display of images by a projector
Optics, graphic ...
s are term constructors:
:
The tuple with labeled elements used in the
relational model
The relational model (RM) is an approach to managing data using a Structure (mathematical logic), structure and language consistent with first-order logic, first-order predicate logic, first described in 1969 by English computer scientist Edgar F. ...
has a
record type
Record type is a family of typefaces designed to allow medieval manuscripts (specifically those from England) to be published as near-facsimiles of the originals. The typefaces include many special characters intended to replicate the various s ...
. 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 interpretation of the lambda calculus with only one type constructor (\to) that builds function types. It is the canonical and simplest example of a typed lambda cal ...
.
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 Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
of a type theory, and use the Scott brackets to indicate the semantic interpretation, then the model consists of some sets
(note: the use of italics here that distinguishes sets from types) such that:
:
and the interpretation of the basic terms is:
:
.
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 versio ...
:
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. In ...
*
Coordinate vector
In linear algebra, a coordinate vector is a representation of a vector as an ordered list of numbers (a tuple) that describes the vector in terms of a particular ordered basis. An easy example may be a position such as (5, 2, 1) in a 3-dimensiona ...
*
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 ca ...
*
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 symb ...
*
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 calle ...
*
Tuplespace
Notes
References
Sources
*
*
Keith Devlin
Keith J. Devlin (born 16 March 1947) is a British mathematician and popular science writer. Since 1987 he has lived in the United States. He has dual British-American citizenship. , ''The Joy of Sets''. Springer Verlag, 2nd ed., 1993, , pp. 7–8
*
Abraham Adolf Fraenkel
Abraham Fraenkel ( he, אברהם הלוי (אדולף) פרנקל; February 17, 1891 – October 15, 1965) was a German-born Israeli mathematician. He was an early Zionist and the first Dean of Mathematics at the Hebrew University of Jerusalem. ...
,
Yehoshua Bar-Hillel
Yehoshua Bar-Hillel ( he, יהושע בר-הלל; 8 September 1915, in Vienna – 25 September 1975, in Jerusalem) was an Israeli philosopher, mathematician, and linguist. He was a pioneer in the fields of machine translation and formal linguis ...
,
Azriel Lévy
Azriel Lévy (Hebrew: עזריאל לוי; born c. 1934) is an Israeli mathematician, logician, and a professor emeritus at the Hebrew University of Jerusalem.
Biography
Lévy obtained his Ph.D. at the Hebrew University of Jerusalem in 1958, und ...
,
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 to study under Kurt Gödel.
He later became a professor at the University of Illinois at Urbana–Champaign. Takeu ...
, 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