Tuple

Last updated

In mathematics, a tuple is a finite sequence or ordered list of numbers or, more generally, mathematical objects, which are called the elements of the tuple. An n-tuple is a tuple of n elements, where 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".

Contents

Tuples are usually written by listing the elements within parentheses "( )" and separated by commas; for example, (2, 7, 4, 1, 7) denotes a 5-tuple. Other types of brackets are sometimes used, although they may have a different meaning. [lower-alpha 1]

An n-tuple can be formally defined as the image of a function that has the set of the n first natural numbers as its domain. Tuples may be also defined from ordered pairs by a recurrence starting from ordered pairs; indeed, an n-tuple can be identified with the ordered pair of its (n − 1) first elements and its nth element.

In computer science, tuples come in many forms. Most typed functional programming languages implement tuples directly as product types, [1] tightly associated with algebraic data types, pattern matching, and destructuring assignment. [2] Many programming languages offer an alternative to tuples, known as record types, featuring unordered elements accessed by label. [3] 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; [4] and in philosophy. [5]

Etymology

The term originated as an abstraction of the sequence: single, couple/double, triple, quadruple, quintuple, sextuple, septuple, octuple, ..., 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 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 ‑πλοῦς, which replaced the classical and late antique ‑plex (meaning "folded"), as in "duplex". [6] [lower-alpha 2]

Properties

The general rule for the identity of two n-tuples is

if and only if .

Thus a tuple has properties that distinguish it from a set:

  1. A tuple may contain multiple instances of the same element, so
    tuple ; but set .
  2. Tuple elements are ordered: tuple , but set .
  3. 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 -tuple may be identified as the empty function. For the -tuple may be identified with the (surjective) function

with domain

and with codomain

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, 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 pairs. This approach assumes that the notion of ordered pair has already been defined.

  1. The 0-tuple (i.e. the empty tuple) is represented by the empty set .
  2. An n-tuple, with n > 0, can be defined as an ordered pair of its first entry and an (n − 1)-tuple (which contains the remaining entries when n > 1):

This definition can be applied recursively to the (n − 1)-tuple:

Thus, for example:

A variant of this definition starts "peeling off" elements from the other end:

  1. The 0-tuple is the empty set .
  2. For n > 0:

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:

  1. The 0-tuple (i.e. the empty tuple) is represented by the empty set ;
  2. Let be an n-tuple , and let . Then, . (The right arrow, , could be read as "adjoined with".)

In this formulation:

n-tuples of m-sets

In discrete mathematics, especially combinatorics and finite probability theory, n-tuples arise in the context of various counting problems and are treated more informally as ordered lists of length n. [7] n-tuples whose entries come from a set of m elements are also called arrangements with repetition, permutations of a multiset and, in some non-English literature, variations with repetition. The number of n-tuples of an m-set is mn. This follows from the combinatorial rule of product. [8] If S is a finite set of cardinality m, this number is the cardinality of the n-fold Cartesian power S × S × ⋯ × S. Tuples are elements of this product set.

Type theory

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:

and the projections are term constructors:

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. [9]

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 (note: the use of italics here that distinguishes sets from types) such that:

and the interpretation of the basic terms is:

.

The n-tuple of type theory has the natural interpretation as an n-tuple of set theory: [10]

The unit type has as semantic interpretation the 0-tuple.

See also

Notes

  1. 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.
  2. Compare the etymology of ploidy, from the Greek for -fold.

Related Research Articles

In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.

<span class="mw-page-title-main">Cardinal number</span> Size of a possibly infinite set

In mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore a natural number. For dealing with the case of infinite sets, the infinite cardinal numbers have been introduced, which are often denoted with the Hebrew letter (aleph) marked with subscript indicating their rank among the infinite cardinals.

<span class="mw-page-title-main">Basis (linear algebra)</span> Set of vectors used to define coordinates

In mathematics, a set B of vectors in a vector space V is called a basis if every element of V may be written in a unique way as a finite linear combination of elements of B. The coefficients of this linear combination are referred to as components or coordinates of the vector with respect to B. The elements of a basis are called basis vectors.

<span class="mw-page-title-main">Ordered pair</span> Pair of mathematical objects

In mathematics, an ordered pair, denoted (a, b), is a pair of objects in which their order is significant. The ordered pair (a, b) is different from the ordered pair (b, a), unless a = b. In contrast, the unordered pair, denoted {a, b}, equals the unordered pair {b, a}.

<span class="mw-page-title-main">Power set</span> Mathematical set containing all subsets of a given set

In mathematics, the power set (or powerset) of a set S is the set of all subsets of S, including the empty set and S itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is postulated by the axiom of power set. The powerset of S is variously denoted as P(S), 𝒫(S), P(S), , , or 2S. Any subset of P(S) is called a family of sets over S.

<span class="mw-page-title-main">Set (mathematics)</span> Collection of mathematical objects

In mathematics, a set is a collection of different things; these things are called elements or members of the set and are typically mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. A set may have a finite number of elements or be an infinite set. There is a unique set with no elements, called the empty set; a set with a single element is a singleton.

A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for structuring the other symbols that occur in a formula. As formulas are entirely constituted with symbols of various types, many symbols are needed for expressing all mathematics.

In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X is called the domain of the function and the set Y is called the codomain of the function.

In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coproduct of a family of objects is essentially the "least specific" object to which each object in the family admits a morphism. It is the category-theoretic dual notion to the categorical product, which means the definition is the same as the product but with all arrows reversed. Despite this seemingly innocuous change in the name and notation, coproducts can be and typically are dramatically different from products within a given category.

In the foundations of mathematics, von Neumann–Bernays–Gödel set theory (NBG) is an axiomatic set theory that is a conservative extension of Zermelo–Fraenkel–choice set theory (ZFC). NBG introduces the notion of class, which is a collection of sets defined by a formula whose quantifiers range only over sets. NBG can define classes that are larger than sets, such as the class of all sets and the class of all ordinals. Morse–Kelley set theory (MK) allows classes to be defined by formulas whose quantifiers range over classes. NBG is finitely axiomatizable, while ZFC and MK are not.

In number theory, natural density, also referred to as asymptotic density or arithmetic density, is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the desired subset when combing through the interval [1, n] as n grows large.

In programming languages and type theory, parametric polymorphism allows a single piece of code to be given a "generic" type, using variables in place of actual types, and then instantiated with particular types as needed. Parametrically polymorphic functions and data types are sometimes called generic functions and generic datatypes, respectively, and they form the basis of generic programming.

This article examines the implementation of mathematical concepts in set theory. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC and in NFU, the version of Quine's New Foundations shown to be consistent by R. B. Jensen in 1969.

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

In category theory, monoidal functors are functors between monoidal categories which preserve the monoidal structure. More specifically, a monoidal functor between two monoidal categories consists of a functor between the categories, along with two coherence maps—a natural transformation and a morphism that preserve monoidal multiplication and unit, respectively. Mathematicians require these coherence maps to satisfy additional properties depending on how strictly they want to preserve the monoidal structure; each of these properties gives rise to a slightly different definition of monoidal functors

In universal algebra, a basis is a structure inside of some (universal) algebras, which are called free algebras. It generates all algebra elements from its own elements by the algebra operations in an independent manner. It also represents the endomorphisms of an algebra by certain indexings of algebra elements, which can correspond to the usual matrices when the free algebra is a vector space.

The entropic vector or entropic function is a concept arising in information theory. It represents the possible values of Shannon's information entropy that subsets of one set of random variables may take. Understanding which vectors are entropic is a way to represent all possible inequalities between entropies of various subsets. For example, for any two random variables , their joint entropy is at most the sum of the entropies of and of :

In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a family of real numbers, indexed by the set of integers, is a collection of real numbers, where a given function selects one real number for each integer as indexing.

<span class="mw-page-title-main">Cartesian product</span> Mathematical set formed from two given sets

In mathematics, specifically set theory, the Cartesian product of two sets A and B, denoted A × B, is the set of all ordered pairs (a, b) where a is in A and b is in B. In terms of set-builder notation, that is

The finite promise games are a collection of mathematical games developed by American mathematician Harvey Friedman in 2009 which are used to develop a family of fast-growing functions , and . The greedy clique sequence is a graph theory concept, also developed by Friedman in 2010, which are used to develop fast-growing functions , and .

References

  1. "Algebraic data type - HaskellWiki". wiki.haskell.org.
  2. "Destructuring assignment". MDN Web Docs. 18 April 2023.
  3. "Does JavaScript Guarantee Object Property Order?". Stack Overflow.
  4. Matthews, P. H., ed. (January 2007). "N‐tuple". The Concise Oxford Dictionary of Linguistics. Oxford University Press. ISBN   9780199202720 . Retrieved 1 May 2015.
  5. Blackburn, Simon (1994). "ordered n-tuple". The Oxford Dictionary of Philosophy. Oxford guidelines quick reference (3 ed.). Oxford: Oxford University Press (published 2016). p. 342. ISBN   9780198735304 . Retrieved 2017-06-30. ordered n-tuple[:] A generalization of the notion of an [...] ordered pair to sequences of n objects.
  6. OED, s.v. "triple", "quadruple", "quintuple", "decuple"
  7. D'Angelo & West 2000 , p. 9
  8. D'Angelo & West 2000 , p. 101
  9. Pierce, Benjamin (2002). Types and Programming Languages . MIT Press. pp.  126–132. ISBN   0-262-16209-1.
  10. Steve Awodey, From sets, to types, to categories, to sets, 2009, preprint

Sources