Научная статья на тему «О классе дискретных функций, принимающих на каждой последовательности значение, равное одному из ее членов»

Такие множества естественным образом возникают в теории принятия решений (decision theory) при применении предложенного С. Шелахом в [11] клонового подхода к кругу вопросов, связанных с известной теоремой («парадоксом») К. Эрроу (о теореме Эрроу см. [6], [7], [10], [12]). Математический контекст этих вопросов состоит в следующем. Пусть даны непустые конечные множества «участников голосования»  и «альтернатив» . «Индивидуальной системой предпочтений» каждого участника называется некоторая -функция выбора на множестве А, где  есть некоторое положительное натуральное число, не превосходящее , а под -функцией выбора понимается произвольная функция  из множества  всех -элементных подмножеств множества  в множество , которая удовлетворяет условию  для каждого множества  из своей области определения. Профилем (или -профилем) участников называется произвольная функция  из множества  в множество  всех -функций выбора на множестве . Правилом голосования (или -правило голосования) называется функция, которая каждому -профилю  ставит в соответствие некоторую -функцию выбора  на множестве . Последняя называется «коллективной системой предпочтений». Правило голосования называется простым, существует такая функция , что для каждого профиля  и множества  имеет место равенство

Будем в этом случае говорить, что функция  определяет -правило голосования (2). Легко заметить, что функции с условием (1) и только они определяют -правила голосования (2) для каждого натурального числа . Функции, удовлетворяющие условию (1), будем называть функциями голосования, а множество всех функций голосования (от любого числа переменных) на произвольном множестве , будем обозначать символом  или просто , если контекст не допускает двусмысленности.

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

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

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

Клоном на множестве  называется любое (функционально) замкнутое подмножество множества , которое содержит все проекции (о клонах и функционально замкнутых множествах см., например, [2], [4], [5] или [9]). Подчеркнем, что каждое функционально замкнутое множество вместе с каждой функцией  содержит все функции, которые отличаются от нее только несущественными переменными.

В литературе можно найти другие определения понятия клон. В [1] клоном  называется любое подмножество множества , которое содержит все проекции, и для всех натуральных  вместе с каждой функцией  и функциями ,,…, содержит функцию

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

Подклоном клона  называется любое подмножество множества , которое является клоном. Ограничением  клона  на множестве  на множество , назовем множество . Множество  называется носителем клона . Множество , для которого ограничение  является клоном (т.е. содержит только функции из ) назовем подносителем клона  и множество всех подносителей клона  обозначим символом . Минимальный по включению клон  на множестве , содержащий все функции из некоторого множества  называется порожденным множеством  (или функциями из ). Изоморфизмом  клонов  и  на множествах  и  соответственно будем называть такую биекцию , что алгебраические структуры  и  являются моделями некоторой сигнатуры , и  есть изоморфизм этих структур. Клоны на двухэлементных множествах (каждый из которых изоморфен некоторому постовскому классу) мы будем называть бинарными. Постовскую классификацию и элементарные свойства бинарных функций (см. [3], [8]) мы будем использовать без специальных ссылок.

Клон функций голосования на конечном множестве. Легко проверить, что множество  всех функций голосования на любом множестве  замкнуто относительно постовских операций и содержит все селекторные функции, т.е. является клоном. Каждый поклон множества  будем называть клоном голосования. Если множество  есть , то клон  в точности является постовским классом  булевых функций, сохраняющих  и . Этот класс порождается множеством функций  и содержит счетное число неизоморфных подклассов. Таким образом, каждый бинарный клон голосования изоморфен некоторому подклассу класса . Множество всех таких подклассов, описанное Постом, среди прочего, в [8], обозначим символом .

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

Пусть  – некоторое подмножество множества  всех подмножеств множества , и для каждого  определен клон голосования  на множестве , причем для всех множеств

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

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

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

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

Теорема 1. Пусть дано конечное множество  мощности . Тогда любой клон голосования  на множестве  удовлетворяет условию  тогда и только тогда, когда он является свободной склейкой некоторого семейства бинарных клонов .

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

Индукцией по мощности множества  докажем, что для любой допустимой на множестве  функции  клон  содержит такую функцию , что  (из чего теорема немедленно следует в другую сторону).

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