Кортеж

В математике кортеж — это конечная последовательность или упорядоченный список или чисел , в более общем смысле, математические объекты , которые называются элементами кортежа. 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$ -кортежей таково:

(a_{1},a_{2},\ldots ,a_{n})=(b_{1},b_{2},\ldots ,b_{n})

тогда и только тогда, когда

a_{1}=b_{1},{\text{ }}a_{2}=b_{2},{\text{ }}\ldots ,{\text{ }}a_{n}=b_{n}

.

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

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

Определения

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

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

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

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

с доменом

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

и с кодоменом

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

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

F(i):=a_{i}.

То есть, $F$ это функция, определяемая

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

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

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

обязательно держится.

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

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

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

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

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

0-кортеж (т.е. пустой кортеж) представлен пустым набором $\emptyset$ .
n $-$ кортеж с $n > 0$ может быть определен как упорядоченная пара его первой записи и $(n - 1)$ -кортежа (который содержит остальные записи, когда $n > 1)$ :
$(a_{1},a_{2},a_{3},\ldots ,a_{n})=(a_{1},(a_{2},a_{3},\ldots ,a_{n}))$

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

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

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

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

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

0-кортеж — это пустой набор $\emptyset$ .
Для $n > 0$ :
$(a_{1},a_{2},a_{3},\ldots ,a_{n})=((a_{1},a_{2},a_{3},\ldots ,a_{n-1}),a_{n})$

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

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

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

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

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

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

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

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

{\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$ -кратной декартовой степени $\times S \times \dots \times S.$ S Кортежи являются элементами этого набора продуктов.

Теория типов

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

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

а проекции являются конструкторами термов:

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

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

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

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

и интерпретация основных терминов такова:

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

.

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

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

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

См. также

Примечания

^ Сравните этимологию слова «плоидность » от греческого слова «-складка».

Ссылки

^ «Алгебраический тип данных — HaskellWiki» . wiki.haskell.org .
^ «Деструктуризация задания» . Веб-документы MDN . 18 апреля 2023 г.
^ «Гарантирует ли JavaScript порядок свойств объекта?» . Переполнение стека .
^ Мэтьюз, PH, изд. (январь 2007 г.). «N-кортеж» . Краткий Оксфордский лингвистический словарь . Издательство Оксфордского университета. 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: Теория множеств , Издательство Кембриджского университета, 2003 г., ISBN 978-0-521-75374-6 , стр. 182–193

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

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

[7] Сравните этимологию слова «плоидность » от греческого слова «-складка».

[1] «Алгебраический тип данных — HaskellWiki» . wiki.haskell.org .

[2] «Деструктуризация задания» . Веб-документы MDN . 18 апреля 2023 г.

[3] «Гарантирует ли JavaScript порядок свойств объекта?» . Переполнение стека .

[4] Мэтьюз, PH, изд. (январь 2007 г.). «N-кортеж» . Краткий Оксфордский лингвистический словарь . Издательство Оксфордского университета. ISBN 9780199202720 . Проверено 1 мая 2015 г.

[5] Блэкберн, Саймон (1994). «упорядоченный n-кортеж». Оксфордский философский словарь . Краткий справочник Оксфордских рекомендаций (3-е изд.). Оксфорд: Издательство Оксфордского университета (опубликовано в 2016 г.). п. 342. ИСБН 9780198735304 . Проверено 30 июня 2017 г. упорядоченный n-кортеж[:] Обобщение понятия [...] упорядоченной пары на последовательности из n объектов.

[6] OED , св «тройной», «четверной», «пятерной», «десятеричный»

[8] Д'Анджело и Уэст 2000 , с. 9

[9] Д'Анджело и Уэст 2000 , с. 101

[pierce2002-10] Пирс, Бенджамин (2002). Типы и языки программирования . МТИ Пресс. стр. 126–132 . ISBN 0-262-16209-1 .

[11] Стив Аводи, От наборов к типам, к категориям, к наборам , 2009, препринт

[1]

[2]

[3]

[4]

[5]

[6]

[а]

[7]

[8]

[9]

[10]

v т и Теория множеств
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo