Конечный упорядоченный список элементов
В математике кортеж — это конечная последовательность или упорядоченный список чисел или , в более общем смысле, математические объекты , которые называются элементами кортежа. 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}=b_{1},{\text{ }}a_{2}=b_{2},{\text{ }}\ldots ,{\text{ }}a_{n}=b_ {н}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Таким образом, кортеж обладает свойствами, которые отличают его от множества :
- Кортеж может содержать несколько экземпляров одного и того же элемента, поэтому
tuple ; но поставил .![{\displaystyle (1,2,2,3)\neq (1,2,3)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{1,2,2,3\}=\{1,2,3\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Элементы кортежа упорядочены: tuple , но set .
![{\displaystyle (1,2,3)\neq (3,2,1)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{1,2,3\}=\{3,2,1\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Кортеж имеет конечное число элементов, тогда как набор или мультимножество могут иметь бесконечное число элементов.
Определения
Существует несколько определений кортежей, которые придают им свойства, описанные в предыдущем разделе.
Кортежи как функции
-tuple может быть идентифицирован как пустая функция . Ибо -кортеж можно отождествить с ( сюръективной ) функцией![{\displaystyle 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle n \ geq 1,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle п}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F~:~\left\{1,\ldots,n\right\}~\to ~\left\{a_{1},\ldots,a_{n}\right\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
с доменом
![{\displaystyle \operatorname {domain} F=\left\{1,\ldots,n\right\}=\left\{i\in \mathbb {N}:1\leq i\leq n\right\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
и с кодоменом
![{\displaystyle \operatorname {codomain} F=\left\{a_{1},\ldots,a_{n}\right\},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
который определяется в![{\displaystyle я\в \operatorname {домен} F =\left\{1,\ldots,n\right\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F(i):=a_{i}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
То есть, является ли функция, определяемая![{\displaystyle F}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\begin{alignedat}{3}1\;&\mapsto &&\;a_{1}\\\;&\;\;\vdots &&\;\\n\;&\mapsto &&\; a_{n}\\\end{alignedat}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
в этом случае равенство
![{\displaystyle \left(a_{1},a_{2},\dots,a_{n}\right)=\left(F(1),F(2),\dots,F(n)\right) }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
обязательно держится.
- Кортежи как наборы упорядоченных пар
Функции обычно идентифицируются по их графикам , которые представляют собой определенный набор упорядоченных пар. Действительно, многие авторы используют графики в качестве определения функции. Используя это определение «функции», вышеуказанную функцию можно определить как:![{\displaystyle F}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F~:=~\left\{\left(1,a_{1}\right),\ldots,\left(n,a_{n}\right)\right\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Кортежи как вложенные упорядоченные пары
Другой способ моделирования кортежей в теории множеств — это вложение упорядоченных пар . Этот подход предполагает, что понятие упорядоченной пары уже определено.
- 0-кортеж (т.е. пустой кортеж) представлен пустым набором .
![{\displaystyle \emptyset }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- 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_{ н)))}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Это определение можно рекурсивно применить к ( n − 1) -кортежу:
![{\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=(a_{1},(a_{2},(a_{3},(\ldots , (a_{n},\emptyset )\ldots ))))}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Так, например:
![{\displaystyle {\begin{aligned}(1,2,3)&=(1,(2,(3,\emptyset )))\\(1,2,3,4)&=(1,(2 ,(3,(4,\emptyset ))))\\\end{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Вариант этого определения начинает «отслаивать» элементы с другого конца:
- 0-кортеж — это пустое множество .
![{\displaystyle \emptyset }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Для n > 0 :
![{\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=((a_{1},a_{2},a_{3},\ldots ,a_{ n-1}),a_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Это определение можно применять рекурсивно:
![{\displaystyle (a_{1},a_{2},a_{3},\ldots,a_{n})=((\ldots (((\emptyset,a_{1}),a_{2}), a_{3}),\ldots ),a_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Так, например:
![{\displaystyle {\begin{aligned}(1,2,3)&=(((\emptyset,1),2),3)\\(1,2,3,4)&=((((\ пустой набор,1),2),3),4)\\\end{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Кортежи как вложенные множества
Используя представление Куратовского для упорядоченной пары , второе определение выше можно переформулировать в терминах чистой теории множеств :
- 0-кортеж (т.е. пустой кортеж) представлен пустым набором ;
![{\displaystyle \emptyset }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Пусть это n -кортеж и пусть . Затем, . (Стрелку вправо можно прочитать как «примыкающую к».)
![{\displaystyle х}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (a_{1},a_{2},\ldots,a_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x\rightarrow b\equiv (a_{1},a_{2},\ldots,a_{n},b)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x\rightarrow b\equiv \{\{x\},\{x,b\}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \rightarrow }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
В этой формулировке:
![{\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{массив}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
n -кортежи из m -множеств
В дискретной математике , особенно в комбинаторике и теории конечных вероятностей , n -кортежи возникают в контексте различных задач счета и трактуются более неформально как упорядоченные списки длины n . [7] n -кортежи, записи которых происходят из набора из m элементов, также называются композициями с повторением , перестановками мультимножества и, в некоторой неанглоязычной литературе, вариациями с повторением . Число n -кортежей в m -наборе равно m n . Это следует из комбинаторного правила произведения . [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}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
а проекции являются конструкторами термов:
![{\displaystyle \pi _{1}(x):{\mathsf {T}}_{1},~\pi _{2}(x):{\mathsf {T}}_{2},~\ ldots ,~\pi _{n}(x):{\mathsf {T}}_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Кортеж с помеченными элементами, используемый в реляционной модели, имеет тип записи . Оба этих типа можно определить как простые расширения просто типизированного лямбда-исчисления . [9]
Понятия кортежа в теории типов и теории множеств связаны следующим образом: если мы рассмотрим естественную модель теории типов и используем скобки Скотта для обозначения семантической интерпретации, то модель состоит из некоторых множеств ( примечание: здесь используется курсив, который отличает множества от типов), так что:![{\displaystyle S_{1},S_{2},\ldots,S_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle [\![{\mathsf {T}}_{1}]\!]=S_{1},~[\![{\mathsf {T}}_{2}]\!]=S_ {2},~\ldots ,~[\![{\mathsf {T}}_{n}]\!]=S_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
и интерпретация основных терминов такова:
.
n - кортеж теории типов имеет естественную интерпретацию как n -кортеж теории множеств: [10]
![{\displaystyle [\![(x_{1},x_{2},\ldots ,x_{n})]\!]=(\,[\![x_{1}]\!],[\! [x_{2}]\!],\ldots ,[\![x_{n}]\!]\,)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Тип единицы имеет семантическую интерпретацию 0-кортежа.
Смотрите также
Примечания
- ^ Сравните этимологию слова « плоидность » от греческого слова «-складка».
Рекомендации
- ^ «Алгебраический тип данных — HaskellWiki» . wiki.haskell.org .
- ^ «Задание по деструктуризации». Веб-документы MDN . 18 апреля 2023 г.
- ^ «Гарантирует ли JavaScript порядок свойств объекта?» Переполнение стека .
- ^ "N-кортеж". N-кортеж - Оксфордский справочник. Издательство Оксфордского университета. Январь 2007 г. ISBN. 9780199202720. Проверено 1 мая 2015 г.
- ^ Блэкберн, Саймон (1994). «упорядоченный n-кортеж». Оксфордский философский словарь. Краткий справочник Оксфордских рекомендаций (3-е изд.). Оксфорд: Издательство Оксфордского университета (опубликовано в 2016 г.). п. 342. ИСБН 9780198735304. Проверено 30 июня 2017 г.
упорядоченный n-кортеж[:] Обобщение понятия [...] упорядоченной пары на последовательности из n объектов.
- ^ OED , св «тройной», «четверной», «пятерной», «десятеричный»
- ^ Д'Анджело и Уэст 2000, с. 9
- ^ Д'Анджело и Уэст 2000, с. 101
- ^ Пирс, Бенджамин (2002). Типы и языки программирования . МТИ Пресс. стр. 126–132. ISBN 0-262-16209-1.
- ^ Стив Аводи, От наборов к типам, к категориям, к наборам, 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.
Внешние ссылки
Словарное определение кортежа в Викисловаре