декартово произведение это что

Декартово произведение множеств

Прямое или декартово произведение множеств — множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств. Данное понятие употребляется не только в теории множеств, но также в алгебре, топологии и прочих разделах математики благодаря тому, что прямое произведение часто наследует структуры (алгебраические, топологические и т. д.), существующие на перемножаемых множествах.

Содержание

Прямое произведение в теории множеств

Произведение двух множеств

Произведение множества <в, и, к> на множество цветов радуги
в	в	в	в	в	в	в	в
и	и	и	и	и	и	и	и
к	к	к	к	к	к	к	к

Отображения произведения множеств в его множители ( и ) называют координатными функциями.

Аналогично строятся произведения нескольких множеств.

Декартова степень

Прямое произведение семейства множеств

Прямое произведение отображений

Аналогично вышеизложенному, данное определение обобщается на многократные и бесконечные произведения.

Воздействие на математические структуры

Прямое произведение групп

Это определение распространяется на произвольное конечное число перемножаемых групп; ассоциативность декартова произведения следует из ассоциативности операций перемножаемых групп.

Прямое произведение других алгебраических структур

Аналогично произведению групп, можно определить произведения колец, алгебр, модулей и линейных пространств, причём в определении прямого произведения 1_i (см. выше) следует заменить нулём. Однако, как правило, произведения этих структур называют прямой суммой.

Прямое произведение топологических пространств

Топология бесконечного произведения будет задаваться базой, составленной из всевозможных пересечений конечного числа открытых цилиндров (такая топология аналогична компактно-открытой топологии пространств отображений если считать индексное множество I имеющим дискретную топологию).

Теорема Тихонова утверждает компактность произведений любого количества компактных пространств; однако для бесконечных произведений её не удаётся доказать без использования аксиомы выбора (или равносильных ей утверждений теории множеств).

Также, теорема Александрова показывает, что любое топологическое пространство можно вложить в (бесконечное) произведение связных двоеточий, если только выполнена аксиома Колмогорова (а иные пространства и не рассматриваются).

Прямое произведение графов

Множество вершин прямого произведения двух графов G и H задаётся как произведение вершин графов сомножителей. Рёбрами будут соединены следующие па́ры вершин:

Иначе говоря, множество рёбер произведения графов является объединением двух произведений: рёбер первого на вершины второго, и вершин первого на рёбра второго.

Вариации и обобщения

Источник

Декартово произведение

Содержание

Прямое произведение в теории множеств

Произведение двух множеств

Произведение множества <в, и, к> на множество цветов радуги
в	в	в	в	в	в	в	в
и	и	и	и	и	и	и	и
к	к	к	к	к	к	к	к

Отображения произведения множеств в его множители ( и ) называют координатными функциями.

Аналогично строятся произведения нескольких множеств.

Декартова степень

Прямое произведение семейства множеств

Прямое произведение отображений

Аналогично вышеизложенному, данное определение обобщается на многократные и бесконечные произведения.

Воздействие на математические структуры

Прямое произведение групп

Прямое произведение других алгебраических структур

Прямое произведение топологических пространств

Прямое произведение графов

Вариации и обобщения

Источник

Декартово (прямое) произведение множеств

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. СООТВЕТСТВИЯ, ФУНКЦИИ, ОТНОШЕНИЯ

ЦЕЛЬ ЛЕКЦИИ – изучение свойств декартова произведения множеств, и связанных с ним соответствий, функций и отношений.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Помимо рассмотренных в первой лекции традиционных операций над множествами существуют и другие действия с множествами, которые позволяют решать много задач, имеющих практическое применение. В частности, к таким действиям относится декартово (прямое) произведение множеств. Свое название декартово произведение получило оттого, что предложенное Декартом координатное представление точек плоскости, являлось исторически первым примером прямого произведения.

Декартово (прямое) произведение множеств

Декартово (прямое) произведение множеств Х и – это множество, обозначаемое , элементами которого являются упорядоченные пары , первая компонента которых принадлежит множеству Х, а вторая множеству .

Согласно определению элементами прямого произведения множеств являются упорядоченные пары, составленные из элементов исходных множеств. В этих парах первый элемент (компонента) всегда принадлежит первому множеству, а второй элемент (компонента) второму. Порядок множеств определяется исходной записью и, если , то , так как в упорядоченной паре компонента имеет номер 1, а компонента – номер 2, но в упорядоченной паре : – номер 1, а – номер 2.

Множество содержит mn элементов, где m и n – количество элементов Хи соответственно.

Геометрическое представление этого множества приведено на рис. 2.1, а.

Пример 2.2. Пусть A и B – отрезки вещественной оси. Прямое произведение изобразится заштрихованным прямоугольником, показанным на рис. 2.1, б.

Пример 2.3. Найти декартово произведение множеств и .

Решение. A × B .

Порядок перечисления элементов безразличен, важен только порядок элементов в паре (упорядоченная пара).

B × A .

Из приведенных примеров видно, что свойства прямого произведения отличаются от свойств обычного произведения в арифметическом смысле. В частности, прямое произведение изменяется при изменении порядка сомножителей, то есть , следовательно, декартово произведение не коммутативно. При этом он не только не коммутативно, но и не ассоциативно, но дистрибутивно относительно объединения, пересечения и симметрической разности множеств

;

Прямое произведение множеств – операция многоместная

В результате получаются множества, состоящие из упорядоченной последовательности вида

, где ; ;…; .

Такие последовательности называются кортежами или векторами.

Кортеж длины – конечная последовательность элементов , в которой каждый элемент занимает определенное место в соответствии с записью исходных множеств декартова произведения.

Сами элементы при этом называются компонентами (координатами) кортежа, которые нумеруются слева направо (первая компонента, вторая компонента и т.д.).

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

Основные отличия понятий кортежа (вектора) и множества заключаются в следующем:

1) в множестве порядок элементов не играет роли, а кортежи, отличающиеся порядком элементов, различны, даже в случае, когда они имеют одинаковый состав;

2) в множестве все элементы различны, а в кортеже координаты могут повторяться.

Таким образом, в отличии от обычного множества в кортеже (векторе) могут быть одинаковые компоненты: два одинаковых слова в фразе, одинаковые численные значения координат точки на плоскости и т.п.

Таким образом, декартово произведение позволяет получать вектора любых размерностей. Эта операция отличается от операций объединения и пересечения тем, что в результате перемножения прямым способом получаются объекты, содержащие элементы, отличающиеся по своей природе от элементов исходных множеств.

Если перемножить n раз одно и то же множество, то получится множество , называемое степенью множества

Степенью декартового произведения называется число множеств n, входящих в это декартово произведение.

Источник

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ

Смотреть что такое «ДЕКАРТОВО ПРОИЗВЕДЕНИЕ» в других словарях:

декартово произведение — Декартовым (или прямым) произведением называется выборка всех возможных комбинаций строк из двух таблиц. Оно получается, если единственное существующее отношение между двумя таблицами деактивизируется, а затем выполняется запрос, использующий… … Справочник технического переводчика

Декартово произведение — Прямое или декартово произведение множеств множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств. Данное понятие употребляется не только в теории множеств, но также в алгебре, топологии и прочих … Википедия

Декартово произведение множеств — [cartesian product] произведение множеств A ´ B, рассматриваемое как множество всех упорядоченных пар элементов (a, b), из которых a принадлежит множеству A, b множеству B. Порядок следования пар может быть любым, но расположение элементов в… … Экономико-математический словарь

декартово произведение двух множеств — Прямое или декартово произведение множеств, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств. Данное понятие широко благодаря тому, что прямое произведение часто наследует структуры (алгебраические,… … Справочник технического переводчика

Декартово произведение групп — Прямое или декартово произведение множеств множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств. Данное понятие употребляется не только в теории множеств, но также в алгебре, топологии и прочих … Википедия

Декартово произведение множеств — Прямое или декартово произведение множеств множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств. Данное понятие употребляется не только в теории множеств, но также в алгебре, топологии и прочих … Википедия

Произведение (теория категорий) — Произведение двух или более объектов это обобщение в теории категорий таких понятий, как декартово произведение множеств, прямое произведение групп и произведение топологических пространств. Произведение семейства объектов это в… … Википедия

Произведение мер — в функциональном анализе, теории вероятностей и смежных дисциплинах формальный способ построить меру на декартовом произведении двух пространств с мерами. Содержание 1 Построение 2 Замечания 3 Пример … Википедия

Источник

Лекция 2. Декартово произведение. Мощность множества

п.2. Декартово произведение. Мощность множества.

2.1. Декартово произведение множеств.

Упорядоченная пара интуитивно определяется как совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке. Две пары и считаются равными тогда и только тогда, когда x=u и y=v.

Определение 2.1. Пусть A и B – два множества. Прямым (декартовым) произведением двух множеств A и B называется множество всех упорядоченных пар, в котором первый элемент каждой пары принадлежит A, а второй принадлежит B:

Пример. Пусть и . Тогда

Пример. На координатной плоскости построить следующее множество:

Решение. Первое множество помещаем на оси OX, второе на оси OY. Множество всех пар, т. е. декартово произведение, изображается точками заштрихованного прямоугольника, но без левой и нижней стороны.

Как вы знаете, точка на плоскости может быть задана упорядоченной парой координат, то есть двумя точками на координатных осях. Поэтому координатную плоскость можно задать в виде . Метод координат ввел в употребление Рене Декарт (), отсюда и название «декартово произведение».

Понятие прямого произведения допускает обобщение.

Прямое произведение множеств

Степенью множества A называется его прямое произведение самого на себя. Обозначение:

Соответственно, и вообще .

Решение. Множество Bn состоит из последовательностей нулей и единиц длины n. Они называются строкой бит или битовой строкой длины n.

Альберт Эйнштейн как-то говорил: «Не все, что можно сосчитать, сосчитано, и не все, что сосчитано, можно сосчитать». Хотя это высказывание не очень воодушевляет, попытаемся заняться подсчетами.

Говорят, что между множествами A и B установлено взаимно однозначное соответствие, если каждому элементу множества A соответствует один и только один элемент множества B и каждому элементу множества B соответствует некоторый элемент множества A. В этом случае говорят также, что множества A и B изоморфны и используют обозначение A

Определение 2.2. Два множества A и B называются эквивалентными, или равномощными, если между этими множествами может быть установлено взаимно однозначное соответствие. В этом случае пишут: A

Пример. 1) Множество десятичных цифр равномощно множеству пальцев на руках человека.

Пример 2.5. В компьютере все множества реальных объектов конечны: множество адресуемых ячеек памяти, множество исполнимых программ, множество тактов работы процессора.

Множества, которые не являются конечными, называются бесконечными. Если некоторое множество A равномощно множеству N, т. е. A

N, то множество A называется счетным (в зарубежной литературе: множество называются счетным, если оно конечно или счетно бесконечно). Счетное множество A – это такое множество, все элементы которого могут быть занумерованы в бесконечную последовательность a1, a2, …, an, …, так, чтобы при этом каждый элемент получил лишь один номер n и каждое натуральное число n было бы номером лишь одного элемента множества A. Мощность счетного множества принято обозначать через ( – первая буква древнееврейского алфавита, называемая «алеф», символ читается: «алеф-нуль»). В частности |N|=.

На первый взгляд, кажется, что это множество невозможно перенумеровать. Однако эту нумерацию можно осуществить, применив следующую хитрость: двигаясь не в одном направлении, а все время менять его. Иными словами, будем нумеровать так: числу 0 дадим номер 1, числу 1 – номер 2, числу —1 – номер 3, числу 2 – номер 4, числу —2 – номер 5, и т. д. Таким образом, получаем взаимно однозначное соответствие между множеством Z и N. А значит, множество Z счетно.

Множество A называется несчетным, если его мощность больше мощности множества N. В таком случае множество A называется континуальным или континуумом. Мощность континуума обозначается . Следующую теорему примем без доказательства.

2.3. Теоремы сложения и умножения.

Формула включений и исключений.

Чтобы подсчитать число элементов конечного множества, образованного в результате объединения или пересечения некоторых конечных множеств, используется комбинаторный анализ. Мы рассмотрим теоремы сложения и умножения, а так же формулу включений и исключений.

Теорема 2.2. (Теорема сложения)

Пусть – конечные попарно непересекающиеся множества, т. е. . Тогда

(2.3.1.)

Теорема 2.3. (Теорема умножения)

Пусть заданы конечные множества . Тогда

(2.3.2.)

т. е. число элементов декартова произведения множеств равно произведению количеств элементов сомножителей.

Пример. Сколько существует целых чисел между 0 и 1000, содержащих ровно одну цифру 6?

S1 – множество, которое содержит число, состоящее из одной цифры, и эта цифра 6;

S2 – множество, содержащее двузначные числа ровно с одной цифрой, равной 6;

S3 – множество, содержащее трехзначные числа ровно с одной цифрой, равной 6.

В множестве S2 каждый элемент, содержащей 6, имеет ее либо первой, либо второй цифрой. Если 6 – вторая цифра, то существует 8 различных чисел, которые будут стаять на первом месте, поскольку первое число не может быть 0 или 6. Если 6 – первая цифра, то таких чисел 9, поскольку вторая цифра не может быть 6. Таким образом, S2 содержит 8+9=17 элементов, т. е. | S2|=17.

Элемент из S3 содержит 6 как первою, вторую или третью цифру. Если 6 – первая цифра, то существует 9 вариантов выбора второй цифры и 9 вариантов выбора третьей цифры. Согласно комбинаторному принципу умножения, S3 содержит 9 ´9=81 чисел с первой цифрой. Если 6 – вторая цифра, то имеются 9 вариантов выбора третьей цифры и 8 вариантов выбора первой цифры, поскольку первая цифра не может быть нулем. Следовательно, S3 содержит 9´8=72 числа, у которых 6 – вторая цифра. Аналогично, S3 содержит 72 числа, у которых 6 – третья цифра. Следовательно, всего S3 содержит 81+72+72=225 элементов, т. е. |S3|=225.

Поскольку и множества S1, S2 и S3 попарно непересекающиеся, то

Поставим задачу подсчитать число элементов в объединении

конечных множеств , которые могут иметь непустые пересечения между собой, т. е. объединение может быть не разбиением. В общем случае имеет место следующая теорема, которую нетрудно доказать методом математической индукции.

Теорема 2.4. (Формула включений и исключений).

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

(2.3.3.)

В частности для двух множеств эта формула примет вид:

Для трех множеств формула включений и исключений примет вид:

Название этой теоремы подчеркивает использование последовательных включений и исключений элементов подмножеств.

X1 – множество положительных целых чисел, которые делятся на 2. Число элементов или мощность этого множества равно .

X2 – множество положительных целых чисел, которые делятся на 3. Число элементов или мощность этого множества равно .

X3 – множество положительных целых чисел, которые делятся на 5. Число элементов или мощность этого множества равно .

Тогда множество X1ÇX2 – множество положительных целых чисел, которые делятся на 2 или 3. Число элементов или мощность этого множества равно . Множество X1ÇX3 – множество положительных целых чисел, которые делятся на 2 или 5. Число элементов или мощность этого множества равно . Множество X2ÇX3 – множество положительных целых чисел, которые делятся на 3 или 5. Число элементов или мощность этого множества равно .

Множество X1ÇX2ÇX3 – множество положительных целых чисел, которые делятся на 2, 3 или 5. Число элементов или мощность этого множества равно .

Воспользуемся формулой включения и исключения, чтобы найти число элементов множества X. Получаем

2.4. Представление множеств в компьютере.

Термин «представление» примените-льно к программированию означает следующее. Задать представление какого-либо объекта (в данном случае множества) – значит, описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции. Предполагается, что в используемой системе программирования доступны такие общеупотребительные структуры данных, как массивы, структуры (или записи) и указатели. Таким образом, применительно к множествам определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введенных операций.

Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программиро-вания. Хороший программист отлича-ется тем, что он знает много разных способов представления и умело выбирает наиболее подходящий.

Тем, кто желает больше узнать о различных способах представления множества в компьютерах, можно порекомендовать следующую книгу:

Новиков математика для программистов. Учебник для вузов. 2-е изд. – СПб.: Питер, 2006.

Используя данный источник, рассмотрим один из способов представления множеств в компьютере: реализация операций над множествами заданного универсума.

Пусть задан конечный универсум U, и число элементов в нем не превосходит разрядности компьютера, . Элементы универсума нумеруются:

где – это i-й разряд кода C.

Код пересечения множеств A и B есть поразрядное логическое произведение кода множества A и кода множества B. Код объединения множеств A и B есть поразрядная логическая сумма кода множества A и кода множества B. Код дополнения множества A есть инверсия кода множества A. В большинстве компьютеров для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно. В некоторых языках программирования, например в Паскале, это представление множеств непосредственно включено в состав типов данных языка.

Если мощность универсума превосходит размер машинного слова, но не очень велико, то для представления множеств используются массивы битовых шкал. В этом случае операции над множествами реализуются с помощью циклов по элементам массива.

Источник

Читайте также: что означает родинка над верхней губой слева у мужчин