Кортеж

Конечный упорядоченный список элементов

В математике кортеж — это конечная последовательность или упорядоченный список чисел или, в более общем смысле, математических объектов , которые называются элементами кортежа. Кортеж из n элементов — это кортеж из n элементов, где n — неотрицательное целое число . Существует только один кортеж из 0 элементов, называемый пустым кортежем . Кортеж из 1 элементов и кортеж из 2 элементов обычно называют синглтоном и упорядоченной парой соответственно. Термин «бесконечный кортеж» иногда используется для «бесконечных последовательностей» .

Кортежи обычно записываются путем перечисления элементов в скобках " ( ) " и разделяются запятыми; например, (2, 7, 4, 1, 7) обозначает 5-кортеж. Иногда используются и другие типы скобок, хотя они могут иметь иное значение. ^[a]

n -кортеж может быть формально определен как образ функции , которая имеет множество из n первых натуральных чисел в качестве своей области определения . Кортежи могут быть также определены из упорядоченных пар с помощью рекуррентности, начинающейся с упорядоченных пар ; действительно, n -кортеж может быть идентифицирован с упорядоченной парой его ( n − 1) первых элементов и его n -го элемента.

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

Кортежи также встречаются в реляционной алгебре , при программировании семантической сети с помощью Resource Description Framework (RDF), в лингвистике [ ^4] и в философии ^[5] .

Этимология

Термин возник как абстракция последовательности: single, couple/double, triple, quadruple, quintuple, sixtuple, septuple, octuple, ..., n ‑tuple, ..., где префиксы взяты из латинских названий цифр. Уникальный 0-кортеж называется нулевым кортежем или пустым кортежем . 1-кортеж называется сингленом ( или синглтоном ), 2-кортеж называется упорядоченной парой или парой , а 3-кортеж называется тройкой (или триплетом ). Число n может быть любым неотрицательным целым числом . Например, комплексное число можно представить как 2-кортеж вещественных чисел, кватернион можно представить как 4-кортеж, октонион можно представить как 8-кортеж, а седенион можно представить как 16-кортеж.

Хотя эти использования рассматривают ‑uple как суффикс, исходный суффикс был ‑ple , как в "triple" (тройной) или "decuple" (десятикратный). Это происходит от средневекового латинского plus (что означает "больше"), связанного с греческим ‑πλοῦς, который заменил классический и позднеантичный ‑plex (что означает "сложенный"), как в "duplex". ^{[6] [b]}

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

Общее правило для тождественности двух n -кортежей:

${\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. Кортеж имеет конечное число элементов, тогда как множество или мультимножество может иметь бесконечное число элементов.

Определения

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

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

-кортеж может быть идентифицирован как пустая функция . Для -кортежа может быть идентифицирован с ( сюръективной ) функцией ${\displaystyle 0}$ ${\displaystyle n\geq 1,}$ ${\displaystyle n}$ ${\displaystyle \left(a_{1},\ldots ,a_{n}\right)}$

${\displaystyle F~:~\left\{1,\ldots ,n\right\}~\to ~\left\{a_{1},\ldots ,a_{n}\right\}}$

с доменом

${\displaystyle \operatorname {domain} F=\left\{1,\ldots ,n\right\}=\left\{i\in \mathbb {N} :1\leq i\leq n\right\}}$

и с кодоменом

${\displaystyle \operatorname {codomain} F=\left\{a_{1},\ldots ,a_{n}\right\},}$

который определяется по ${\displaystyle i\in \operatorname {domain} F=\left\{1,\ldots ,n\right\}}$

${\displaystyle F(i):=a_{i}.}$

То есть, функция определяется как ${\displaystyle F}$

${\displaystyle {\begin{alignedat}{3}1\;&\mapsto &&\;a_{1}\\\;&\;\;\vdots &&\;\\n\;&\mapsto &&\;a_{n}\\\end{alignedat}}}$

в этом случае равенство

${\displaystyle \left(a_{1},a_{2},\dots ,a_{n}\right)=\left(F(1),F(2),\dots ,F(n)\right)}$

обязательно выполняется.

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

Функции обычно отождествляются с их графиками , которые являются определенным набором упорядоченных пар. Действительно, многие авторы используют графики в качестве определения функции. Используя это определение «функции», вышеуказанную функцию можно определить как: ${\displaystyle F}$

${\displaystyle F~:=~\left\{\left(1,a_{1}\right),\ldots ,\left(n,a_{n}\right)\right\}.}$

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}(1,2,3)&=(1,(2,(3,\emptyset )))\\(1,2,3,4)&=(1,(2,(3,(4,\emptyset ))))\\\end{aligned}}}$

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

1. Нулевой кортеж — это пустое множество . ${\displaystyle \emptyset }$
2. Для n > 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{aligned}(1,2,3)&=(((\emptyset ,1),2),3)\\(1,2,3,4)&=((((\emptyset ,1),2),3),4)\\\end{aligned}}}$

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

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

1. 0-кортеж (т.е. пустой кортеж) представлен пустым набором ; ${\displaystyle \emptyset }$
2. Пусть будет n -кортежом , и пусть . Тогда . (Правую стрелку , можно прочитать как «присоединенную с».) ${\displaystyle x}$ ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ ${\displaystyle x\rightarrow b\equiv (a_{1},a_{2},\ldots ,a_{n},b)}$ ${\displaystyle x\rightarrow b\equiv \{\{x\},\{x,b\}\}}$ ${\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}}}$

н-кортежим-наборы

В дискретной математике , особенно в комбинаторике и теории конечных вероятностей , n -кортежи возникают в контексте различных задач подсчета и рассматриваются более неформально как упорядоченные списки длины n . ^[7] n -кортежи, записи которых происходят из набора из m элементов, также называются расположениями с повторением , перестановками мультимножества и, в некоторой неанглоязычной литературе, вариациями с повторением . Количество n -кортежей m -множества равно m ⁿ . Это следует из комбинаторного правила произведения . ^[8] Если S — конечное множество мощности m , это число является мощностью n -кратной декартовой степени 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}]\!]}$.

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

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

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

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

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

Примечания

1. Квадратные скобки используются для матриц , включая векторы-строки . Фигурные скобки используются для множеств . Каждый язык программирования имеет свое собственное соглашение для различных скобок.
2. Сравните этимологию слова плоидность , от греческого слова -фолд.

Ссылки

1. "Алгебраический тип данных - HaskellWiki". wiki.haskell.org .
2. "Деструктуризация назначения". MDN Web Docs . 18 апреля 2023 г.
3. «Гарантирует ли JavaScript порядок свойств объекта?». Stack Overflow .
4. Matthews, PH, ed. (Январь 2007). "N-кортеж". Краткий Оксфордский словарь лингвистики . Oxford University Press. ISBN 9780199202720. Получено 1 мая 2015 г.
5. Блэкберн, Саймон (1994). "ordered n-tuple". Оксфордский философский словарь. Краткое руководство по Оксфорду (3-е изд.). Оксфорд: Oxford University Press (опубликовано в 2016 г.). стр. 342. ISBN 9780198735304. Получено 30.06.2017 . упорядоченный n-кортеж[:] Обобщение понятия [...] упорядоченной пары на последовательности из n объектов.
6. OED , св «тройной», «четверной», «пятерной», «десятеричный»
7. Д'Анджело и Уэст 2000, стр. 9
8. Д'Анджело и Уэст 2000, стр. 101
9. Пирс, Бенджамин (2002). Типы и языки программирования . MIT Press. С. 126–132. ISBN 0-262-16209-1.
10. Стив Аводей, От множеств к типам, к категориям, к множествам, 2009, препринт

Источники

• Д'Анджело, Джон П.; Уэст, Дуглас Б. (2000), Математическое мышление/решение проблем и доказательства (2-е изд.), Prentice-Hall, ISBN 978-0-13-014412-6
• Кит Девлин , Радость множеств . Springer Verlag, 2-е изд., 1993, ISBN 0-387-94094-4 , стр. 7–8 
• Авраам Адольф Френкель , Иегошуа Бар-Хиллель , Азриэль Леви , Основы школьной теории множеств , Elsevier Studies in Logic, том 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 

Внешние ссылки

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