Кортеж

Чтобы узнать о музыкальном термине, см. Туплет . «Восьмерка» перенаправляется сюда. Чтобы узнать о лодке, см. Восьмеричный череп . «Duodecuple» перенаправляется сюда. Чтобы узнать о музыкальной технике, см. «Техника двенадцати тонов» . «Секступл» перенаправляется сюда. Чтобы узнать о спортивных достижениях футбольных ассоциаций, см. Sextuple (футбол ассоциаций) .

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

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

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

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

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

Этимология

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

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

Свойства

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

Определения

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

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

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\}.$

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

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

1. 0-кортеж (т.е. пустой кортеж) представлен пустым набором $\emptyset$.
2. 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}}$

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

1. 0-кортеж — это пустой набор $\emptyset$.
2. Для 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}}$

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

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

1. 0-кортеж (т.е. пустой кортеж) представлен пустым набором $\emptyset$;
2. Позволять $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 . n -кортежи, записи которых происходят из набора из m элементов, также называются композициями с повторением , перестановками мультимножества и, в некоторой неанглоязычной литературе, вариациями с повторением . Число n -кортежей в m -множестве равно m. ^н . Это следует из комбинаторного правила произведения . Если S — конечное множество мощности m , это число является мощностью n -кратной декартовой степени × S × ⋯ × 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}$

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

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

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

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

См. также

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

Источники

• Д'Анджело, Джон П.; Уэст, Дуглас Б. (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

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

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