Кортеж - Tuple

В математика, а кортеж конечный упорядоченный список (последовательность) элементы. An ппара это последовательность (или упорядоченный список) п элементы, где п неотрицательный целое число. Есть только один 0-кортеж, называемый пустой кортеж. An п-часть определяется индуктивно используя конструкцию упорядоченная пара.

Математики обычно пишут кортежи, перечисляя элементы в круглых скобках "( )"и разделенные запятыми; например, (2, 7, 4, 1, 7) обозначает 5-кортеж. Иногда для окружения элементов используются другие символы, например квадратные скобки «[]» или угловые скобки «⟨⟩». Фигурные скобки «{}» используются только при определении массивов в некоторых языках программирования, но не в математических выражениях, поскольку они являются стандартными обозначениями для наборы. Период, термин кортеж может часто возникать при обсуждении других математических объектов, таких как векторов.

В Информатика, кортежи бывают разных форм. Наиболее типизированный функциональное программирование языки реализуют кортежи напрямую как виды продукции,^[1] тесно связан с алгебраические типы данных, сопоставление с образцом, и деструктуризация.^[2] Многие языки программирования предлагают альтернативу кортежам, известную как типы записей, с неупорядоченными элементами, доступными по метке.^[3] Несколько языков программирования объединяют упорядоченные типы кортежей и неупорядоченные типы записей в единую конструкцию, как в Структуры C и записи Haskell. Реляционные базы данных могут официально идентифицировать свои ряды (записи) как кортежи.

Кортежи также встречаются в реляционная алгебра; при программировании семантическая сеть с Структура описания ресурсов (RDF); в лингвистика;^[4] И в философия.^[5]

Этимология

Термин возник как абстракция последовательности: одиночный, пара / двойной, тройной, четверной, пятиместный, шестиместный, семикратный, восьмеричный, ..., п‑Tuple, ..., где префиксы берутся из латинский названия цифр. Уникальный 0-кортеж называется нулевым кортежем или пустым кортежем. Кортеж из 1 называется одиночным (или одноэлементным), кортеж из двух элементов называется упорядоченной парой или парой, а набор из трех элементов называется тройкой (или тройкой). Номер п может быть любым неотрицательным целое число. Например, комплексное число может быть представлен как набор из двух вещественных чисел, кватернион может быть представлен в виде 4-кратного кортежа, октонион можно представить в виде восьмерки, а седенион можно представить в виде 16-кратного кортежа.

Хотя эти способы лечения Двойник в качестве суффикса исходный суффикс был ‑Ple как «тройной» (тройной) или «десятичный» (десятикратный). Это происходит из средневековая латынь плюс (что означает "больше"), связанных с Греческий ‑Πλοῦς, пришедший на смену классическому и позднему античному Комплекс (что означает «сложенный»), как «дуплекс».^[6][а]

Имена кортежей определенной длины

Длина кортежа, ${ displaystyle n}$	Имя	Альтернативные названия
0	пустой кортеж	нулевой кортеж / пустая последовательность / единица
1	монумент	Один / одиночка / монада
2	пара	двойной / заказанная пара / двухплюсный / двойной / двойной / двойной
3	тройной	тройка / тройка / тройка / упорядоченная тройка
4	четырехместный	четырехугольник / четырехугольник
5	пятиместный	пятиместный / квинт / пентада
6	шестерка	шестерка
7	семеро	семеро
8	восьмерка	окта / октет
9	неполный
10	девяносто
11	необъятный	девичник
12	двенадцатиперстный
13	Tredecuple
14	четверка
15	пятерка
16	секс
17	семерка
18	восьмидесятилетний
19	новый
20	маршал
21	однотипный
22	двойник
23	Trevigintuple
24	четырехместный
25	пятиместный
26	секс
27	семерка
28	восьмиугольник
29	ночь
30	тройной
31	беспричинный
40	четырехместный
41	одноквадратный
50	пятерка
60	секс
70	семидесятилетний
80	восьмидесятник
90	многократный
100	сотка
1,000	миллиард

Характеристики

Общее правило идентичности двоих п-tuples есть

${ displaystyle (a_ {1}, a_ {2}, ldots, a_ {n}) = (b_ {1}, b_ {2}, ldots, b_ {n})}$ если и только если ${ displaystyle a_ {1} = b_ {1}, { text {}} a_ {2} = b_ {2}, { text {}} ldots, { text {}} a_ {n} = b_ {n}.}$

Таким образом, кортеж имеет свойства, которые отличают его от кортежа. набор.

1. Кортеж может содержать несколько экземпляров одного и того же элемента, поэтому
   кортеж ${ Displaystyle (1,2,2,3) neq (1,2,3)}$; но установить ${ Displaystyle {1,2,2,3 } = {1,2,3 }}$.
2. Элементы кортежа упорядочены: кортеж ${ Displaystyle (1,2,3) neq (3,2,1)}$, но установить ${ Displaystyle {1,2,3 } = {3,2,1 }}$.
3. Кортеж состоит из конечного числа элементов, а набор или мультимножество может иметь бесконечное количество элементов.

Определения

Есть несколько определений кортежей, которые придают им свойства, описанные в предыдущем разделе.

Кортежи как функции

Если мы имеем дело с множествами, п-набор можно рассматривать как функция, F, домен которого является неявным набором индексов элементов кортежа, Икс, и чей домен, Y, - это набор элементов кортежа. Формально:

${ Displaystyle (а_ {1}, а_ {2}, точки, а_ {п}) эквив (X, Y, F)}$

куда:

${ displaystyle { begin {align} X & = {1,2, dots, n } = {i in mathbb {N} mid 1 leq i leq n } Y & = {a_ {1}, a_ {2}, ldots, a_ {n} } F & = {(1, a_ {1}), (2, a_ {2}), ldots, (n, a_ {n}) }. конец {выровнено}}}$

В несколько менее формальных обозначениях это говорит:

${ displaystyle (a_ {1}, a_ {2}, dots, a_ {n}): = (F (1), F (2), dots, F (n)).}$

Используя это определение ${ displaystyle n}$-наборы, то есть только один ${ displaystyle 0}$-часть, пустая функция.

Кортежи как вложенные упорядоченные пары

Другой способ моделирования кортежей в Теории множеств - вложенный заказанные пары. Этот подход предполагает, что понятие упорядоченной пары уже определено; таким образом, 2-кортеж

1. 0-кортеж (т.е. пустой кортеж) представлен пустым набором ${ displaystyle emptyset}$.
2. An ппара, с п > 0, можно определить как упорядоченную пару из его первой записи и (п − 1)-tuple (который содержит оставшиеся записи, когда п > 1):

   ${ displaystyle (a_ {1}, a_ {2}, a_ {3}, ldots, a_ {n}) = (a_ {1}, (a_ {2}, a_ {3}, ldots, a_ { n}))}$

Это определение можно рекурсивно применить к (п − 1)-набор:

${ displaystyle (a_ {1}, a_ {2}, a_ {3}, ldots, a_ {n}) = (a_ {1}, (a_ {2}, (a_ {3}, ( ldots, (а_ {п}, emptyset) ldots))))}$

Так, например:

${ Displaystyle { begin {align} (1,2,3) & = (1, (2, (3, emptyset))) (1,2,3,4) & = (1, (2 , (3, (4, emptyset)))) конец {выровнен}}}$

Вариант этого определения начинается с «отслаивания» элементов с другого конца:

1. 0-кортеж - это пустой набор ${ displaystyle emptyset}$.
2. За п > 0:

   ${ displaystyle (a_ {1}, a_ {2}, a_ {3}, ldots, a_ {n}) = ((a_ {1}, a_ {2}, a_ {3}, ldots, a_ { n-1}), a_ {n})}$

Это определение можно применить рекурсивно:

${ displaystyle (a_ {1}, a_ {2}, a_ {3}, ldots, a_ {n}) = (( ldots ((( emptyset, a_ {1}), a_ {2}), a_ {3}), ldots), a_ {n})}$

Так, например:

${ displaystyle { begin {align} (1,2,3) & = ((( emptyset, 1), 2), 3) (1,2,3,4) & = (((( emptyset, 1), 2), 3), 4) конец {выровнен}}}$

Кортежи как вложенные наборы

С помощью Представление Куратовского для упорядоченной пары, второе определение, приведенное выше, может быть переформулировано в терминах чистого теория множеств:

1. 0-кортеж (т.е. пустой кортеж) представлен пустым набором ${ displaystyle emptyset}$;
2. Позволять ${ displaystyle x}$ быть ппара ${ Displaystyle (а_ {1}, а_ {2}, ldots, а_ {п})}$, и разреши ${ Displaystyle х rightarrow b эквив (a_ {1}, a_ {2}, ldots, a_ {n}, b)}$. Потом, ${ Displaystyle х rightarrow б эквив { {х }, {х, б } }}$. (Стрелка вправо, ${ displaystyle rightarrow}$, можно прочитать как «примыкающий к».)

В этой формулировке:

${ displaystyle { 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}}}$

п-наборы м-наборы

В дискретная математика, особенно комбинаторика и конечный теория вероятности, п-кортежи возникают в контексте различных задач подсчета и более неформально рассматриваются как упорядоченные списки длины п.^[7] п-кортежи, записи которых происходят из набора м элементы также называются аранжировки с повторением, перестановки мультимножества а в некоторой неанглоязычной литературе вариации с повторением. Количество п-наборы м-сет м^п. Это следует из комбинаторной правило продукта.^[8] Если S конечный набор мощность м, это число является мощностью п-складывать Декартова степень S × S × ... S. Кортежи являются элементами этого набора продуктов.

Теория типов

В теория типов, обычно используется в языки программирования, кортеж имеет Тип продукта; это фиксирует не только длину, но и базовые типы каждого компонента. Формально:

${ displaystyle (x_ {1}, x_ {2}, ldots, x_ {n}): { mathsf {T}} _ {1} times { mathsf {T}} _ {2} times ldots times { mathsf {T}} _ {n}}$

и прогнозы конструкторы терминов:

${ displaystyle pi _ {1} (x): { mathsf {T}} _ {1}, ~ pi _ {2} (x): { mathsf {T}} _ {2}, ~ ldots, ~ pi _ {n} (x): { mathsf {T}} _ {n}}$

Кортеж с помеченными элементами, используемый в реляционная модель имеет тип записи. Оба эти типа можно определить как простые расширения просто типизированное лямбда-исчисление.^[9]

Понятия кортежа в теории типов и теории множеств связаны следующим образом: если мы рассмотрим естественные модель теории типов и используйте скобки Скотта для обозначения семантической интерпретации, тогда модель состоит из нескольких наборов ${ Displaystyle S_ {1}, S_ {2}, ldots, S_ {n}}$ (примечание: здесь используется курсив, который отличает наборы от типов), так что:

${ displaystyle [! [{ mathsf {T}} _ {1}] !] = S_ {1}, ~ [! [{ mathsf {T}} _ {2}] !] = S_ {2}, ~ ldots, ~ [! [{ Mathsf {T}} _ {n}] !] = S_ {n}}$

а толкование основных терминов таково:

${ displaystyle [! [x_ {1}] !] in [! [{ mathsf {T}} _ {1}] !], ~ [! [x_ {2}] !] in [! [{ mathsf {T}} _ {2}] !], ~ ldots, ~ [! [x_ {n}] !] in [! [{ mathsf {T }} _ {n}] !]}$.

В п-набор теории типов имеет естественную интерпретацию как п-набор теории множеств:^[10]

${ displaystyle [! [(x_ {1}, x_ {2}, ldots, x_ {n})] !] = (, [! [x_ {1}] !], [! [x_ {2}] !], ldots, [! [x_ {n}] !] ,)}$

В тип единицы имеет семантическую интерпретацию 0-кортежа.

Смотрите также

• Arity
• Экспоненциальный объект
• Формальный язык
• OLAP: многомерные выражения
• основной kпара
• Отношение (математика)
• Последовательность
• Кортеж

Примечания

Рекомендации

Источники

• Д'Анджело, Джон П .; Запад, Дуглас Б. (2000), Математическое мышление / Решение проблем и доказательства (2-е изд.), Прентис-Холл, ISBN  978-0-13-014412-6
• Кейт Девлин, Радость наборов. Springer Verlag, 2-е изд., 1993, ISBN  0-387-94094-4, стр. 7–8
• Авраам Адольф Френкель, Иегошуа Бар-Гилель, Азриэль Леви, Основы школьной теории множеств, Elsevier Исследования в области логики Vol. 67, 2-е издание, переработанное, 1973 г., ISBN  0-7204-2270-1, п. 33
• Гайси Такеути, В. М. Заринг, Введение в аксиоматическую теорию множеств, Springer GTM 1, 1971, ISBN  978-0-387-90024-7, п. 14
• Джордж Дж. Турлакис, Конспект лекций по логике и теории множеств. Том 2: Теория множеств, Cambridge University Press, 2003 г., ISBN  978-0-521-75374-6, стр. 182–193

внешняя ссылка

• Словарное определение кортеж в Викисловарь