Набор мощности

Информацию о разработчике поисковой системы см. в Powerset (компания) .

Набор мощности

Элементы набора степеней { x , y , z } упорядочены относительно включения .
Тип	Установить операцию
Поле	Теория множеств
Заявление	Набор мощности — это набор, который содержит все подмножества данного набора.
Символическое заявление	$x\in P(S)\iff x\subseteq S$

В математике набор мощности (или набор мощности ) набора S — набор всех подмножеств S это , включая пустой набор и S. сам В аксиоматической теории множеств (развитой, например, в аксиомах ZFC ) существование степенного множества любого множества постулируется аксиомой степенного множества . Набор степеней S по-разному обозначается как P ( S ) , 𝒫 ( S ) , P ( S ) , $\mathbb {P} (S)$, $\wp (S)$, или 2 ^С . Любое подмножество P ( S ) называется множеств над S. семейством

Пример

Если S — это набор { x , y , z } , то все подмножества S являются

• {} (также обозначается $\varnothing$ или $\emptyset$, пустой набор или нулевой набор)
• { х }
• { и }
• { С }
• { х , у }
• { х , z }
• { y , z }
• { Икс , у , z }

и, следовательно, набор степеней S равен {{}, { х }, { у }, { з }, { х , у }, { х , z }, { y , z }, { Икс , у , z }} .

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

Если S — конечное множество мощности | С | = n (т. е. число всех элементов в множестве S равно n ), то число всех подмножеств S равно | П ( С ) | = 2 ^н . Этот факт, а также причина обозначения 2 ^С обозначающие набор мощности P ( S ), показаны ниже.

Индикаторная функция или характеристическая функция подмножества A множества S мощности | С | = n — это функция из S в набор из двух элементов {0, 1} , обозначаемая как I _A : S → {0, 1} ли элемент S , и она указывает, принадлежит A или нет; Если x в S принадлежит A , то I _A ( x ) = 1 и 0 в противном случае. Каждое подмножество A из S идентифицируется индикаторной функцией I _A или эквивалентно ей , а {0,1} ^С поскольку набор всех функций от S до {0, 1} состоит из всех индикаторных функций всех подмножеств S . Другими словами, {0, 1} ^С эквивалентен или биективен множеству степеней P ( S ) . Поскольку каждый элемент в S соответствует либо 0 , либо 1 при любой функции из {0, 1} ^С , количество всех функций в {0, 1} ^С 2 ​ ^н . Поскольку число 2 можно определить как {0, 1} (см., например, ординалы фон Неймана ), P ( S ) также обозначается как 2 ^С . Очевидно | 2 ^С | = 2 ^{| С |} держит. Вообще говоря, Х ^И — набор всех функций от Y до X и | Х ^И | = | Х | ^{| И |} .

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

Набор степеней множества S вместе с операциями объединения , пересечения и дополнения является Σ-алгеброй над S и может рассматриваться как прототип булевой алгебры . Фактически, можно показать, что любая конечная булева алгебра изоморфна булевой алгебре степенного множества конечного множества. Для бесконечных булевых алгебр это уже не так, но каждая бесконечная булева алгебра может быть представлена ​​как подалгебра булевой алгебры степенного множества (см. теорему Стоуна о представлении ).

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

Представление подмножеств как функций

В множеств теории X ^И представляющее набор всех функций от Y до X. — это обозначение , Поскольку « 2 » можно определить как {0, 1} (см., например, ординалы фон Неймана ), 2 ^С (т. е. {0, 1} ^С ) — это набор всех функций от S до {0, 1} . Как показано выше , 2 ^С и набор мощности S , P ( S ) считаются идентичными с точки зрения теории множеств.

Эту эквивалентность можно применить к приведенному выше примеру , в котором S = { x , y , z } , чтобы получить изоморфизм с двоичными представлениями чисел от 0 до 2. ^н − 1 , где n — количество элементов в множестве S или | С | = п . Во-первых, определяется нумерованный набор { ( x , 1), ( y , 2), ( z , 3) ​​} , в котором число в каждой упорядоченной паре представляет положение парного элемента S в последовательности двоичных цифр, такой как как { Икс , у } знак равно 011 ₍₂₎ ; x из S расположен первым справа в этой последовательности, а y — вторым справа, а 1 в последовательности означает, что элемент S, соответствующий его положению в последовательности, существует в подмножестве S для последовательность, а 0 означает, что это не так.

Для всего набора мощности S мы получаем:

Подмножество	Последовательность двоичных цифр	Двоичный интерпретация	Десятичный эквивалент
{ }	0, 0, 0	000 (2)	0 (10)
{ х }	0, 0, 1	001 (2)	1 (10)
{ и }	0, 1, 0	010 (2)	2 (10)
{ х , у }	0, 1, 1	011 (2)	3 (10)
{ С }	1, 0, 0	100 (2)	4 (10)
{ х , z }	1, 0, 1	101 (2)	5 (10)
{ y , z }	1, 1, 0	110 (2)	6 (10)
{ Икс , у , z }	1, 1, 1	111 (2)	7 (10)

Такое инъективное отображение P не является уникальным , ( S ) в целые числа является произвольным, поэтому это представление всех подмножеств S но порядок сортировки нумерованного множества не меняет его мощности. (Например, { ( y , 1), ( z , 2), ( x , 3) ​​} можно использовать для построения другого инъективного отображения из P ( S ) в целые числа без изменения количества взаимно однозначных соответствий. )

Однако такое конечное двоичное представление возможно только в том случае, если S можно пронумеровать. (В этом примере x , y и z нумеруются с 1 , 2 и 3 соответственно как позиции последовательностей двоичных цифр.) Перечисление возможно, даже если S имеет бесконечную мощность (т. е. количество элементов в S бесконечно), например, набор целых или рациональных чисел, но это невозможно, например, если S — набор действительных чисел, и в этом случае мы не можем перечислить все иррациональные числа.

Связь с биномиальной теоремой

Биномиальная теорема тесно связана с набором степеней. Комбинация k -элементов из некоторого набора — это другое название подмножества k -элементов, поэтому количество комбинаций , обозначаемое как C( n , k ) (также называемое биномиальным коэффициентом ), представляет собой количество подмножеств с k элементами в наборе с n элементов; другими словами, это количество наборов с k элементами, которые являются элементами набора мощности набора с n элементами.

Например, силовой набор набора из трех элементов имеет:

• C(3, 0) = 1 подмножество с 0 элементами (пустое подмножество),
• C(3, 1) = 3 подмножества с 1 элементом (одноэлементные подмножества),
• C(3, 2) = 3 подмножества по 2 элемента (дополнения одноэлементных подмножеств),
• C(3, 3) = 1 подмножество с 3 элементами (сам исходный набор).

Используя это соотношение, мы можем вычислить | 2 ^С | используя формулу: $$\left|2^{S}\right|=\sum _{k=0}^{|S|}{\binom {|S|}{k}}$$

Поэтому можно вывести следующее тождество, полагая | С | = п : $$\left|2^{S}\right|=2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}$$

Рекурсивное определение

Если S — конечное множество , то рекурсивное определение P : ( S ) происходит следующим образом

• Если S = ​​{} , то P ( S ) = { {} } .
• В противном случае пусть e ∈ S и T = S ∖ { e } ; тогда п ( S ) знак равно п ( Т ) ∪ { т ∪ { е } : т ∈ п ( Т )} .

Словами:

• Набор мощности пустого набора — это синглтон , единственным элементом которого является пустой набор.
• Для непустого множества S пусть $e$ быть любым элементом множества и T его относительным дополнением ; тогда набор степеней S представляет собой объединение набора степеней T и набора степеней T , каждый элемент которого расширен элементом e .

Подмножества ограниченной мощности

Множество подмножеств S мощности κ меньше или равной иногда обозначается P _или ( S ) [ S ] κ ^Мистер , а множество подмножеств с мощностью строго меньше κ иногда обозначается P _{< κ} ( S ) или [ S ] ^{< κ} . Аналогично, множество непустых подмножеств S можно обозначить P _≥1 ( S ) или P ⁺ ( С ) .

Силовой объект

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

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

Однако есть два важных свойства подмножеств, которые не передаются на подалгебры вообще. Во-первых, хотя подмножества множества образуют множество (а также решетку), в некоторых классах может оказаться невозможным организовать подалгебры алгебры как алгебры этого класса, хотя их всегда можно организовать как решетка. Во-вторых, поскольку подмножества набора находятся в биекции с функциями из этого набора в набор {0, 1} = 2 , нет никакой гарантии, что класс алгебр содержит алгебру, которая может играть роль 2 таким образом. .

Некоторые классы алгебр обладают обоими этими свойствами. Первое свойство более распространено; случай наличия обоих относительно редок. Один класс, который имеет и то, и другое, — это класс мультиграфов . Учитывая два мультиграфа G и H , гомоморфизм h : G → H состоит из двух функций: одна отображает вершины в вершины, а другая отображает ребра в ребра. Набор Н ^Г гомоморфизмов из G в H затем можно организовать в виде графа, вершины и ребра которого являются соответственно функциями вершин и ребер, появляющимися в этом множестве. Более того, подграфы мультиграфа G находятся в биекции с гомоморфизмами графов из G в мультиграф Ω, определяемый как полный ориентированный граф на двух вершинах (следовательно, четыре ребра, а именно две петли и еще два ребра, образующие цикл), дополненный пятое ребро, а именно второй самоцикл в одной из вершин. Поэтому мы можем организовать подграфы группы G как мультиграф Ω ^Г называемый энергетическим объектом G , .

Особенностью мультиграфа как алгебры является то, что его операции унарные. Мультиграф имеет два типа элементов, образующих набор V вершин и E ребер, и имеет две унарные операции s , t : E → V, задающие исходную (начальную) и целевую (конечную) вершины каждого ребра. Алгебра, все операции которой унарные, называется предпучком . Каждый класс предпучков содержит предпучок Ω , который играет роль для подалгебр, которую 2 играет для подмножеств. Такой класс является частным случаем более общего понятия элементарного топоса как категории , которая замкнута (и более того, декартово замкнута ) и имеет объект Ω , называемый классификатором подобъектов . Хотя термин «объект власти» иногда используется как синоним экспоненциального объекта Y. ^Х , в теории топоса Y должно быть Ω .

Функторы и кванторы

Существует как ковариантный, так и контравариантный функтор множества мощности : P : Set → Set и P : Set. ^на → Установить . Ковариантный функтор определяется проще. как функтор, который переводит множество S в P ( S ) и морфизм f : S → T (здесь функция между множествами) в морфизм изображения. То есть для $A=\{x_{1},x_{2},...\}\in {\mathsf {P}}(S),{\mathsf {P}}f(A)=\{f(x_{1}),f(x_{2}),...\}\in {\mathsf {P}}(T)$. В другом месте этой статьи набор мощности определялся как набор функций S в наборе из двух элементов. Формально это определяет естественный изоморфизм ${\overline {\mathsf {P}}}\cong {\text{Set}}(-,2)$. Функтор контравариантного степенного множества отличается от ковариантной версии тем, что он отправляет f в морфизм предизображения , так что если $f(A)=B\subseteq T,{\overline {\mathsf {P}}}f(B)=A$. Это происходит потому, что общий функтор ${\text{C}}(-,c)$ принимает морфизм $h:a\rightarrow b$ к предварительной композиции по h , поэтому функция $h^{*}:C(b,c)\rightarrow C(a,c)$, который переводит морфизмы из b в c и переводит их в морфизмы из a в c через b через h .

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

См. также

• Теорема Кантора
• Семейство наборов
• Поле наборов
• Комбинация

Библиография

• Девлин, Кейт Дж. (1979). Основы современной теории множеств . Университеттекст. Спрингер-Верлаг . ISBN  0-387-90441-7 . Збл   0407.04003 .
• Халмос, Пол Р. (1960). Наивная теория множеств . Университетская серия по математике для студентов. Компания Ван Ностранд. Збл   0087.04403 .
• Мак Лейн, Сондерс ; Мурдейк, Ике (1992), Пучки в геометрии и логике , Springer-Verlag, ISBN  0-387-97710-4
• Пунтамбекар, А.А. (2007). Теория автоматов и формальных языков . Технические публикации. ISBN  978-81-8431-193-8 .
• Вайсштейн, Эрик В. «Набор мощности» . mathworld.wolfram.com . Архивировано из оригинала 6 апреля 2023 г. Проверено 05 сентября 2020 г.

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

• Мощность установлена ​​в PlanetMath .
• Мощность, установленная в n Lab
• Энергетический объект в n Lab
• Алгоритм набора мощности на C++