Кортеж

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

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

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

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

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

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

Этимология

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

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

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

Общее правило идентичности двух 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. Кортеж может содержать несколько экземпляров одного и того же элемента, поэтому
   tuple ; но поставил . ${\displaystyle (1,2,2,3)\neq (1,2,3)}$ ${\displaystyle \{1,2,2,3\}=\{1,2,3\}}$
2. Элементы кортежа упорядочены: tuple , но set . ${\displaystyle (1,2,3)\neq (3,2,1)}$ ${\displaystyle \{1,2,3\}=\{3,2,1\}}$
3. Кортеж имеет конечное число элементов, тогда как набор или мультимножество могут иметь бесконечное число элементов.

Определения

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

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

-tuple может быть идентифицирован как пустая функция . Ибо -кортеж можно отождествить с ( сюръективной ) функцией ${\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. 0-кортеж — это пустое множество . ${\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 -кортежи из m -множеств

В дискретной математике , особенно в комбинаторике и теории конечных вероятностей , 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. Сравните этимологию слова « плоидность » от греческого слова «-складка».

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

1. «Алгебраический тип данных — HaskellWiki» . wiki.haskell.org .
2. «Задание по деструктуризации». Веб-документы MDN . 18 апреля 2023 г.
3. «Гарантирует ли JavaScript порядок свойств объекта?» Переполнение стека .
4. "N-кортеж". N-кортеж - Оксфордский справочник. Издательство Оксфордского университета. Январь 2007 г. ISBN. 9780199202720. Проверено 1 мая 2015 г. {{cite book}}: |work=игнорируется ( помощь )
5. Блэкберн, Саймон (1994). «упорядоченный n-кортеж». Оксфордский философский словарь. Краткий справочник Оксфордских рекомендаций (3-е изд.). Оксфорд: Издательство Оксфордского университета (опубликовано в 2016 г.). п. 342. ИСБН 9780198735304. Проверено 30 июня 2017 г. упорядоченный n-кортеж[:] Обобщение понятия [...] упорядоченной пары на последовательности из n объектов.
6. OED , св «тройной», «четверной», «пятерной», «десятеричный»
7. Д'Анджело и Уэст 2000, с. 9
8. Д'Анджело и Уэст 2000, с. 101
9. Пирс, Бенджамин (2002). Типы и языки программирования . МТИ Пресс. стр. 126–132. ISBN 0-262-16209-1.
10. Стив Аводи, От наборов к типам, к категориям, к наборам, 2009, препринт .

Источники

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

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

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