В математике набор мощности (или набор мощности ) набора S — это набор всех подмножеств S , включая пустой набор и сам S. [1] В аксиоматической теории множеств (развитой, например, в аксиомах ZFC ) существование степенного множества любого множества постулируется аксиомой степенного множества . [2] Набор степеней S по-разному обозначается как P ( S ) , 𝒫 ( S ) , P ( S ) , , или 2 S . Обозначение 2 S , означающее набор всех функций от S до заданного набора из двух элементов (например, {0, 1} ), используется, потому что набор степеней S может быть отождествлен с, эквивалентен или биективен с множество всех функций из S в заданный двухэлементный набор. [1]
Любое подмножество P ( S ) называется семейством множеств над S.
Если S — это набор { x , y , z } , то все подмножества S являются
и, следовательно, набор степеней S равен {{}, { x }, { y }, { z }, { x , y }, { x , z }, { y , z }, { x , y , z }} . [3]
Если S — конечное множество мощности | С | = n (т. е. число всех элементов в множестве S равно n ), то число всех подмножеств S равно | П ( С ) | = 2 н . Этот факт, а также причина обозначения 2 S , обозначающего набор мощности P ( 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 или | С | = п . Во-первых, определяется нумерованный набор { ( x , 1), ( y , 2), ( z , 3) } , в котором число в каждой упорядоченной паре представляет положение парного элемента S в последовательности двоичных цифр, такой как как { Икс , у } знак равно 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 — конечное множество , то рекурсивное определение 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 должно быть Ω .
В теории категорий и теории элементарных топосов квантор универсальности можно понимать как правый сопряженный функтор между степенными множествами, функтор обратного образа функции между множествами; аналогично, квантор существования является левым сопряженным . [4]
