В математике множество мощности (или powerset ) множества S — это множество всех подмножеств S , включая пустое множество и само S. [1] В аксиоматической теории множеств (развитой, например, в аксиомах ZFC ) существование множества мощности любого множества постулируется аксиомой множества мощности . [ 2] Множество мощности S обозначается по-разному как P ( S ) , 𝒫 ( S ) , P ( S ) , или 2 S . [a] Любое подмножество P ( S ) называется семейством множеств над S .
Если S — это множество { x , y , z } , то все подмножества S — это
и, следовательно, множество мощности S равно {{}, { x }, { y }, { z }, { x , y }, { x , z }, { y , z }, { x , y , z }} . [3]
Если S — конечное множество с мощностью | S | = n (т. е. число всех элементов множества S равно n ), то число всех подмножеств S равно | P ( S ) | = 2 n . Этот факт, а также причина обозначения 2 S для множества мощности P ( S ) продемонстрированы ниже.
Диагональный аргумент Кантора показывает, что множество мощности множества (бесконечного или нет) всегда имеет строго большую мощность, чем само множество (или неформально, множество мощности должно быть больше исходного множества). В частности, теорема Кантора показывает, что множество мощности счетно бесконечного множества является несчетно бесконечным. Множество мощности множества натуральных чисел можно поставить во взаимно однозначное соответствие с множеством действительных чисел (см. Мощность континуума ).
Множество степеней множества S вместе с операциями объединения , пересечения и дополнения является Σ-алгеброй над S и может рассматриваться как прототипический пример булевой алгебры . Фактически, можно показать, что любая конечная булева алгебра изоморфна булевой алгебре множества степеней конечного множества. Для бесконечных булевых алгебр это уже не так, но каждая бесконечная булева алгебра может быть представлена как подалгебра булевой алгебры множества степеней (см. теорему Стоуна о представлении ).
Множество степеней множества S образует абелеву группу , если рассматривать его с помощью операции симметрической разности (пустое множество является единичным элементом, а каждое множество является своим собственным обратным), и коммутативный моноид, если рассматривать его с помощью операции пересечения (все множество S является единичным элементом). Следовательно, можно показать, доказав дистрибутивные законы , что множество степеней, рассматриваемое вместе с обеими этими операциями, образует булево кольцо .
В теории множеств X Y — это обозначение , представляющее множество всех функций от Y до X. Поскольку « 2 » можно определить как {0, 1} (см., например, ординалы фон Неймана ), 2 S (т. е. {0, 1} S ) — это множество всех функций от S до {0, 1} . Как показано выше, 2 S и множество мощности S , P ( S ) , считаются идентичными с точки зрения теории множеств.
Эту эквивалентность можно применить к примеру выше, в котором S = { x , y , z } , чтобы получить изоморфизм с двоичными представлениями чисел от 0 до 2 n − 1 , где n — число элементов в наборе S или | S | = n . Во-первых, определяется перечисленный набор { ( x , 1), ( y , 2), ( z , 3) } , в котором число в каждой упорядоченной паре представляет позицию парного элемента S в последовательности двоичных цифр, такой как { x , y } = 011 (2) ; x из S находится в первой справа этой последовательности, а y — во второй справа, и 1 в последовательности означает, что элемент S, соответствующий его позиции в последовательности, существует в подмножестве S для последовательности, в то время как 0 означает, что его там нет.
Для всего множества степеней S получаем:
Такое инъективное отображение из 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 элементами.
Например, набор мощности набора из трех элементов имеет:
Используя это соотношение, мы можем вычислить | 2 S | по формуле:
Следовательно, можно вывести следующее тождество, предполагая | S | = n :
Если S — конечное множество , то рекурсивное определение P ( S ) выполняется следующим образом :
Проще говоря:
Множество подмножеств S мощности , меньшей или равной κ, иногда обозначается как P κ ( S ) или [ S ] κ , а множество подмножеств с мощностью, строго меньшей κ, иногда обозначается как P < κ ( S ) или [ S ] < κ . Аналогично, множество непустых подмножеств S может обозначаться как P ≥1 ( S ) или P + ( S ) .
Множество можно рассматривать как алгебру, не имеющую нетривиальных операций или определяющих уравнений. С этой точки зрения, идея множества мощности X как множества подмножеств X естественным образом обобщается на подалгебры алгебраической структуры или алгебры.
Множество элементов множества, упорядоченное включением, всегда является полной атомной булевой алгеброй, и каждая полная атомная булева алгебра возникает как решетка всех подмножеств некоторого множества. Обобщение на произвольные алгебры состоит в том, что множество подалгебр алгебры, снова упорядоченное включением, всегда является алгебраической решеткой , и каждая алгебраическая решетка возникает как решетка подалгебр некоторой алгебры. Так что в этом отношении подалгебры ведут себя аналогично подмножествам.
Однако есть два важных свойства подмножеств, которые не переносятся на подалгебры в целом. Во-первых, хотя подмножества множества образуют множество (а также решетку), в некоторых классах может быть невозможно организовать подалгебры алгебры как саму алгебру в этом классе, хотя их всегда можно организовать как решетку. Во-вторых, в то время как подмножества множества находятся во взаимной однозначности с функциями из этого множества в множество {0, 1} = 2 , нет никакой гарантии, что класс алгебр содержит алгебру, которая может играть роль 2 таким образом.
Некоторые классы алгебр обладают обоими этими свойствами. Первое свойство встречается чаще; случай наличия обоих свойств относительно редок. Один класс, который обладает обоими свойствами, — это класс мультиграфов. Для двух мультиграфов G и H гомоморфизм h : G → H состоит из двух функций , одна из которых отображает вершины в вершины, а другая — ребра в ребра. Множество H G гомоморфизмов из G в H может быть организовано как граф, вершинами и ребрами которого являются соответственно функции вершин и ребер, появляющиеся в этом множестве. Более того, подграфы мультиграфа G находятся во взаимной однозначности с гомоморфизмами графов из G в мультиграф Ω, определяемый как полный ориентированный граф на двух вершинах (следовательно, четыре ребра, а именно две петли и еще два ребра, образующие цикл), дополненный пятым ребром, а именно второй петлей в одной из вершин. Поэтому мы можем организовать подграфы G как мультиграф Ω G , называемый объектом мощности G .
Особенностью мультиграфа как алгебры является то, что его операции являются унарными. Мультиграф имеет два вида элементов, образующих множество V вершин и E ребер, и имеет две унарные операции s , t : E → V , дающие исходную (начальную) и целевую (конечную) вершины каждого ребра. Алгебра, все операции которой являются унарными, называется предпучком . Каждый класс предпучков содержит предпучок Ω , который играет для подалгебр ту же роль, что 2 играет для подмножеств. Такой класс является частным случаем более общего понятия элементарного топоса как категории , которая замкнута (и, более того, декартово замкнута ) и имеет объект Ω , называемый классификатором подобъектов . Хотя термин «объект мощности» иногда используется как синоним экспоненциального объекта Y X , в теории топосов Y требуется, чтобы был Ω .
Существует как ковариантный, так и контравариантный функтор степенного множества , P : Set → Set и P : Set op → Set . Ковариантный функтор определяется проще. как функтор, который переводит множество S в P ( S ) и морфизм f : S → T (здесь, функцию между множествами) в морфизм образа. То есть, для . В другом месте этой статьи степенной набор был определен как набор функций S в множество с 2 элементами. Формально это определяет естественный изоморфизм . Контравариантный функтор степенного множества отличается от ковариантной версии тем, что он переводит f в морфизм прообраза , так что если . Это происходит потому, что общий функтор переводит морфизм в предкомпозицию по h , поэтому функция , которая переводит морфизмы из b в c и переводит их в морфизмы из a в c , через b через h . [4]
В теории категорий и теории элементарных топосов квантор всеобщности можно понимать как правый сопряженный функтор между степенными множествами, обратный функтор образа функции между множествами; аналогично, квантор существования является левым сопряженным функтором . [5 ]
