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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 517. 925+531. 01
О ЗАМКНУТЫХ СИММЕТРИЧНЫХ КЛАССАХ ФУНКЦИЙ, СОХРАНЯЮЩИХ ЛЮБОЙ ОДНОМЕСТНЫЙ ПРЕДИКАТ
© 2013 Н. Л. Поляков, 1 М.В. Шамолин2
В работе дано эффективное описание симметричных замкнутых классов дискретных функций, сохраняющих любой одноместный предикат.
Ключевые слова: замкнутый класс, клон, соответствие Галуа, теория коллективного выбора.
Введение
Интерес к замкнутым классам дискретных функций, сохраняющих любой одноместный предикат, возникает в связи с некоторыми проблемами теории коллективного выбора (theory of social choice), связанными с теоремами о невозможности (см. [1- 2]). По существу, такие классы рассмотрены в работе [3]. В теории коллективного выбора рассматриваются системы предпочтений на множестве альтернатив A и правила голосования. Под системой предпочтений часто понимают произвольную функцию выбора на множестве A, а под правилом голосования в т. н. простом случае (см. [3]) — произвольную функцию f: An ^ A (1 ^ n & lt- ш), удовлетворяющую условию
J f (xo, Xl,.. ., xn-l) = Xi
i& lt-n
для всех xo, xi,…, xn-i G A. Легко заметить, что это условие эквивалентно тому, что функция f сохраняет любой одноместный предикат (об отношении сохранения функцией f предиката P см. ниже).
Естественной с точки зрения теории коллективного выбора является задача нахождения множества всех правил голосования F, которые сохраняют некоторое множество систем предпочтения D в том смысле, что для каждой n-местной функции f gF и функций ci, С2,…, cn G D функция c, определенная равенством
C (p) = f (Cl (p), C2 (p),. ., Cn (p))
для всех p G 2a{0}, принадлежит множеству D. Очевидно, для каждого множества систем предпочтений D множество всех сохраняющих его правил голосования
1 Поляков Николай Львович (gelvella@mail. ru), кафедра & quot-Математика-1"- Финансового университета при Правительстве Р Ф, 125 993, Российская Федерация, г. Москва, ул. Щербаковская, 38.
2Шамолин Максим Владимирович (shamolin@imec. msu. ru), Институт механики Московского государственного университета им. М. В. Ломоносова, 119 899, Российская Федерация, г. Москва, Мичуринский пр., 1.
F ззамкнуто относительно композиции и содержит все проекции, т. е. является клоном.
Обычно в теории коллективного выбора рассматривают симметричные множества предпочтений, т. е. такие множества D функций выбора на множестве A, которые для каждой функции c G D и перестановки a G Sa содержат функцию cCT, определенную равенством
(p) = a-i (c (ap))
для всех p G 2a{0}. Легко проверить, что множество F всех правил голосования, которые сохраняют симметричное множество функций выбора D, вместе с каждой функцией f содержит функцию fa, определенную равенством
f (a) = a-i (f (aa))
для всех a G dom f. Множества F конечноместных функций на множестве A (не обязательно состоящие из правил голосования), которые обладают этим свойством, мы будем называть симметричными. Симметричные замкнутые классы дискретных функций рассматривались рядом авторов в связи с задачами классификации, восходящими к работе Поста [4- 7]. В работе [5] найден критерий полноты для симметричных замкнутых классов и описаны все симметричные замкнутые классы, которые содержат все константы. Однако множество правил голосования при |A| ^ 2, напротив, не содержит ни одной константы, поэтому описание из [5] не охватывает симметричных клонов, сохраняющих все одноместные предикаты. Классификацию последних дает настоящая статья. Эта классификация может быть эффективно использована в теории коллективного выбора. По-стовскую классификацию и элементарные свойства замкнутых классов булевых функций (см., напр., [4- 6]) мы будем считать известными и будем использовать без дополнительных ссылок.
1. Основные определения и обозначения
Будем считать фиксированным конечное непустое множество A. Во избежание тривиальных рассуждений будем считать, что |A| ^ 2. Элементы декартовой степени A& quot-, n & lt- ш, отождествляются с последовательностями (ao, ai,…, an-i), ai G A, i & lt- n, т. е. с функциями a: {0,1,…, n- 1}^ A- поэтому для любой последовательности a G A& lt-w мы употребляем стандартные обозначения dom a и ran a соответственно для ее области определения и области значений. Будем использовать обозначение Am для множества {a G A& quot-: | rana| = m}. В естественном смысле будем использовать обозначения A& lt-m ^ U A& quot-, A& lt-'-mi ^ U Alk и т. п.
k& lt-m k& lt-m, l& lt-"-
Множество всех n-местных функций на множестве A обозначается символом O& quot-] (A) или просто O[& quot-]. Символом O обозначается множество U O& quot-. Для краткости для любого множества F С O и натурального числа n вместо F^O& quot- будем писать F[n]. Функция из множества On, которая для некоторого фиксированного натурального числа i & lt- n каждой последовательности a = (ao, ai,… an-1) G A& quot- ставит в соответствие элемент ai, называется (n-местной i-й) проекцией или селекторной функцией и обозначается символом e& quot-. При обозначении селекторных функций верхний индекс n мы будем опускать, если это не вызывает разночтений. Множество всех селекторных функций из O мы будем обозначать символом E. Операцией суперпозиции называется частичная операция на множестве O& lt-w, которая каждому кортежу (f, fo, fi,…, fm-i), где f есть m-местная, а fo, fi,… ,
fm-i суть n-местные функции из О, ставит в соответствие функцию h G O[n], обозначаемую символом f (fo, fi,., fm-i), заданную равенствами
h (a) = f (fo (a), fi (a),.., fm-i (a))
для всех a G An. Каждое множество F С О (A), содержащее все проекции и замкнутое относительно суперпозиции, называется клоном. Если множество F С O (A) есть клон, то множество A называется носителем клона F. Клоны F и G с носителями, соответственно, B и C называются эквивалентными, если алгебраические структуры (A, F) и (B, G) являются изоморфными моделями одной и той же сигнатуры.
Ограничением f P произвольной функции f GO на множество P называется функция f П (P х A). Если F есть произвольное подмножество множества O, то символом F P мы будем обозначать множество {f P: f G F}.
Функция f G O[n] сохраняет предикат P С Am, если для любых n кортежей
(aii, ai2,…, aim), (a2i, a22,. ., a^m),. ., (ani, an2,. ., anm), принадлежащих предикату P, кортеж
(f (aii, a2i, …, a"i), f (ai2, a22,. ., an2), …, f (aim, a2m,. ., anm)) также принадлежит предикату P. Хорошо известно [8], что отношение сохранения функцией f предиката P естественным образом порождает соответствие Галуа между булевыми решетками подмножеств множеств O и У 2A, причем
Галуа-замкнутые множества F С O суть в точности клоны. Легко проверить, что любая функция f GO сохраняет каждый одноместный предикат P С A тогда и только тогда, когда удовлетворяет условию
f (a) G ran a (*)
для всех a G dom f. Клон всех функций f G O, удовлетворяющих условию (*), мы будем обозначать символом V.
2. Основная теорема
Для каждого m G и + 1 и множества F С O обозначим для краткости символом F'-(m) множество F A& lt-m. Для множеств U С O^m) свойства замкнутости относительно композиции и симметричности определяются так же, как для множеств F СО. Для каждого множества U С V (m) будем обозначать символом U + множество всех функций f G V, удовлетворяющих условию f A& lt-m G U. Отметим, что множество F^m) замкнуто относительно композиции для каждого клона F С V. Обратно, если множество U С V (m) замкнуто относительно композиции, то U + есть подклон клона V. При этом, если множество U симметрично, то симметричным будет и клон U +.
Пусть F есть подклон V. Для каждого двухэлементного множества B С A множество F B& lt-w есть клон, эквивалентный некоторому постовскому классу П функций, сохраняющих 0 и 1. Если клон F симметричный, то класс П не зависит от выбора множества B. Мы будем обозначать такой постовский класс символом n (F). Очевидно, для каждого симметричного клона F С V класс n (F) вместе с каждой функцией f содержит двойственную к ней функцию.
Для каждого клона F С О, содержащего хотя бы одну неселекторную функцию, определим параметр r (F) равенством
r (F) = min{n & lt- и: F[n] = E[n]}.
Положим r (E) = ш. Заметим, что r (F) ^ 2 для всякого клона F С V. Вначале мы дадим описание симметричных клонов F С V с условием r (F) ^ 3.
Пусть дан постовский класс П самодвойственных функций, сохраняющих 0 и 1. Для каждого натурального числа n и функции h G П[п] определим функцию h a: A& lt-3 ^ A равенством
h^(a) = a-i h (aa)
для каждого a G А& lt-з, где a — произвольное инъективное отображение из ran a в {0,1}. Корректность определения легко проверяется. Обозначим символом Па множество {hA: h G П}. Легко проверить, что множество Па замкнуто относительно композиции и симметрично.
Напомним, что существует всего четыре постовских класса самодвойственных функций, сохраняющих ноль и единицу. Следуя обозначениям Поста, будем обозначать их символами Oi, Di, D2 и L4. Они, соответственно, порождаются функциями е (х) = х, w (x, у, z) = xyVxzVyz, д (х, у, z) = xyVyzVxz и 1{х, у, z) = хфуфг. Предложение 1. Пусть дан произвольный клон F С V. Пусть r = r (F) ^ 3. Тогда
(a) П^) G {Oi, Di, D2, L4} и F{3) = П (F)A-
(b) если r (F) ^ 4, то F® = ?® (в частности, П (F) = Oi).
Доказательство. Покажем, что имеет место следующий факт:
пусть дана последовательность a = aoai. . an-i G A& lt-r, функция f G F[n] и функция a: A ^ A. Тогда f (aa) = af (a).
Действительно, сначала заметим, что факт верен, если функция f селекторная. Пусть, далее, b = (bo, bi,…, bt-1) есть некоторая инъективная последовательность всех различных элементов из ran a. Положим т = b-ia. Рассмотрим функцию f '- = f (etT {0), etr (i),…, etr (n-i)) G F[t]. Поскольку t & lt- r, из условия следует, что f'- есть селекторная функция. Тогда имеем
af (a) = af '-(b) = f '-(ab) = f (etT (o)(ab), eT (i) (ab), …, e^ (n_i)(ab)) = f (aa). Факт доказан.
Без ограничения общности будем считать, что множество A содержит элементы 0 и 1. Для каждой функции f gF положим f * = f {0,1}& lt-3. В силу включения F CV множество {f *: f G F}, т. е. множество F {0,1}& lt-3, есть клон c носителем {0,1}, а следовательно, постовский класс. Обозначим его символом П^). Вновь из включения F С V следует, что каждая функция f *, f G F, сохраняет 0 и 1. Рассмотрим нетождественную биекцию a: {0,1} ^ {0,1}. Из доказанного факта следует, что функция f * самодвойственная. Кроме того, из доказанного факта следует равенство f A& lt-3 = fA для любой функции f G F. Это доказывает пункт (a).
Пусть теперь t ^ 4. Для доказательства утверждения (b), заметим, что если П^) = Oi, то класс П^) содержат неселекторные функции от трех переменных, что, конечно, остается верным и для клона F. Следовательно, в рассматриваемом случае класс П^) состоит только из селекторных функций. Пусть f есть произвольная функция из F[n] и i — такой номер, что f * = en. Для каждой последовательности a G A& lt-r выберем функцию a: A ^ A, для которой a (aj) = 1 и a (x) = 0 для всех x G A {ai}. По доказанному факту имеем af (a) = f (aa) = f *(aa) = 1, откуда /(a) = щ. Следовательно, / Ar^r G ?{r), пункт (b) доказан. ?
Замечание 2. Из предложения 1 следует, что для любого клона F С V либо r (F) = ш, либо r (F) ^ max{3, |A|}.
Функцию f € V[n] будем называть сильно. монотонной, если для всех последовательностей a = (ao, ai,…, an_i) € A& lt-3, b = (bo, bi,…, bn_ i) € An и элементов a € ran a, b € ran a выполнено
{i & lt- n: ai = a}C{ & lt- n: bi = b}- (f (a) = a — f (b) = b).
Пусть символ M обозначает множество всех сильно монотонных функций f €V. Предложение 3. Множество M есть симметричный подклон клона V, r (M) = = 3 и П (М) = D2.
Доказательство. Замкнутость множества M относительно композиции и его симметричность проверяются непосредственно. Включение E С M очевидно. Из определения множества M легко следует неравенство r (M) ^ 3. Классы L4 и Di содержат немонотонные функции, поэтому класс П (М) есть один из классов Oi, D2. Остается заметить, что любая функция f € V[3], для которой f f A& lt-3 = дд, сильно монотонна. ?
Для каждого клона F С O, не содержащегося в M, определим параметр m (F) равенством
m (F) = min{n & lt- ш: Fn? Mn}.
Если F С M, положим m (F) = ш. Очевидно, либо m (F) = ш, либо 2 ^ m (F) ^ |А| для каждого клона F С V. Кроме того, если n (F) € {L4,Di}, то m (F) = 2, если n (F) = Oi, то m (F) = r (F), а если r (F) & gt- 3 и n (F) = D2, то m (F) & gt- 3.
Пусть дан клон F С O и натуральное число r. Будем говорить, что клон F удовлетворяет условию
SEP®, если для каждой последовательности a € Arr, номера i & lt- r и элемента a €
r = er f Ar 1& lt-r ~ ei I A& lt-r-
€ ran a существует такая функция f € F[r], что f (a) = a и f f A& lt-r = er f A& lt-
Предложение 4. Пусть дан произвольный симметричный клон F CV. Пусть 3 ^ r = r (F) & lt-ш и m = m (F). Тогда выполнено одно из условий:
(a) П^ = D2, и клон F удовлетворяет условию SEP® —
(b) П^ = D2, и, если m & lt- ш, то клон F удовлетворяет условию SEP!
e
m'-
Доказательство. Пусть вначале г ^ 4. Тогда по предложению 1 каждая функция ] € Frr] совпадает с некоторой проекцией на множестве А& lt-г. По определению параметра г^) существуют номер ] & lt- г, функция д € F[r] и последовательность Ь € АГ, для которых /(Ь) = Ьу и / А& lt-г = ег А& lt-г. Тогда функцию / с требуемыми свойствами легко найти среди функций /а (еТ (о), ет (1),…, ет (г-1)), где, а € и т € Бг (упражнение).
Пусть теперь) = 3. Если П^) = О1, рассуждения аналогичны. Если П^) € {?4,^1}, то класс П (F) содержит функцию ?(х, у, г) = х ф у ф г. Каждую функцию д € Уэ], для которой д А& lt-з = ?а, назовем ?'--функцией. По предложению 1 (и учитывая включение ?4 С ^1) клон F содержит, по крайней мере, одну ?-функцию. Пользуясь симметричностью клона F для каждой последовательности, а = (ао, 0,1, 02) и номера г & lt- 2, можно найти ?-функцию д^ € F, для которой дДа) = = аI (например, если д (а) = ао, то можно положить до = д, д1 = д (о, 1)(е1,ео, е2) и д2 = д (о, 2)(е2,е1,ео)). Рассмотрим функции ео, до (ео, до, д1) и до (ео, до, д2). Они
принимают значения ao, ai, соответственно на последовательности, а и совпадают с проекцией eo на множестве А& lt-з. Далее нужно вновь воспользоваться симметричностью клона F.
Пусть теперь n (F) = D2 и m & lt- ш. Тогда для некоторого натурального числа n ^ m существуют функция g G F[n], последовательности, а = (ao, ai,…, an-i) G G АП, b = (b0,b1,…, bn-1) G Am и элементы a G ran a, b G ran b, для которых нарушено условие сильной монотонности. Поскольку все функции h G D2 монотонны, можно считать, что {i & lt- n: ai = a} = {i & lt- n: bi = b}. Тогда с помощью отождествления переменных легко найти функцию g'- G F, для которой существуют такой номер i & lt- m и такие последовательности c = (co, ci,…, cn-1) G (rana)™ и d = (d0, ddn-1) G (ranb)m, что g'-© = a, g'-(d) = b, {i & lt- m: ci = a} = {i} и di = b. В силу определения параметра m (F) имеем включение С из
которого немедленно следует равенство g'- Amim = e™ Am? m. Остается воспользоваться симметричностью клона F, как и в случае г ^ 4. ?
Бинарное отношение R на множестве А& lt- будем называть устойчивым справа, если для всех последовательностей а, b G А& lt- и натуральных чисел n выполнены условия:
1. aRb ^ dom, а = dom b,
2. aRb ^ атRbr для любой функции т: n ^ dom а.
Бинарное отношение R на множестве А& lt- будем называть устойчивым слева, если для всех последовательностей a, b G А& lt- выполнено условие
3. aRb ^ aaRab для любой перестановки a G Sa.
Будем говорить, что функция f GO действует как проекция на множестве Q С dom f, если f Q gE Q. Пусть дано устойчивое справа бинарное отношение R на множестве А& lt-. Обозначим символом Vr множество всех функций f G V, которые действуют как проекция на каждом множестве {a, b}, где a, b G dom f и (a, b) G R.
Для каждого клона F С O символом R (F) обозначим множество всех пар (a, b) G А& lt-ш х А& lt-ш, для которых dom, а = dom b и каждая функция f G F[dom a] действует как проекция на множестве {a, b}.
Последовательности a, b G А& lt- будем называть подобными, если существует перестановка a множества, А такая, что, а = ab. Отношение подобия на множестве А& lt- будем обозначать символом S.
Предложение 5. Пусть дано устойчивое справа бинарное отношение R на множестве А& lt-ш и клон F С V. Тогда
(a) множество Vr есть клон. Если отношение R устойчиво слева, клон Vr симметричный-
(b) отношения R (F) и R (F)HS устойчивы справа. Если клон F симметричный, отношения R (F) и R (F) П S устойчивы слева. Отношение R (F) П S есть отношение эквивалентности.
Доказательство. Непосредственной проверкой. ?
Теперь охарактеризуем клоны F С V с условием SEP®. Для доказательства нам понадобятся следующие технические определения. Пусть дано натуральное число n, последовательности а, b G Ап и клон F С V. Будем говорить, что F слабо отделяет, а от b в точке a G ran а, если существуют функции f 1, f 2 G F[n], для которых f1(a) = f2(a) = a и f1(b) = f2(b). Если F слабо отделяет, а от b или b от, а хотя бы в одной точке, будем просто говорить, что F слабо отделяет, а и b.
Будем говорить, что F сильно отделяет a от b в точке a G ran a, если для каждого элемента b G ran b существует функция f G F[n], для которой f (a) = = a Л f (b) = b.
Предложение 6. Пусть дан клон F С V, удовлетворяющий условию SEP® для некоторого натурального числа r ^ 3. Тогда F = F^ П Vr (f)ns ¦
Доказательство. Пусть дано натуральное число n ^ 1 и такие последовательности a, b G An, что max{| rana|, | ranb|} ^ r.
Лемма 7. Если | ran a| ^ | ran b| и F слабо отделяет a от b в точке a G ran a, то F сильно отделяет a от b в точке a.
Доказательство. Выберем произвольный элемент b G ran b. Допустим, что клон F не содержит такой функции g, что g (a) = a и g (b) = b. Выберем такие функции fо, f 1, f2 G F[n] и различные элементы c, d G ran b, что
fo (a) = fi (a) = a, fo (b) = c, fi (b) = d, f2(b) = b.
По сделанному допущению b / {c, d}. Выберем еще r — 3 функций fs, f4,…, fr-i из F так, чтобы последовательность b* = (c, d, b, fs (b), f4(b),…, fr-1(b)) была бы инъективной. Последовательность a* = (a, a, f2(a), fs (a), f4(a),…, fr-1(a)) принадлежит множеству A& lt-r. Выберем функцию f G F[r], для которой f (a*) = a и f (b*) = b. Рассмотрим функцию h = f (fo, fi,…, fr-1). Очевидно, h (a) = f (a*) = a и h (b) = /(b*) = 6, противоречие. ?
Лемма 8. Если (a, b) / R (F) П5, то для любых элементов a G ran a, b G ran b существует функция g G F[n], для которой g (a) = a и g (b) = b.
Доказательство. Заметим, что в условиях леммы клон F слабо отделяет a и b. Без ограничения общности будем считать, что | rana| ^ | ranb|. Легко проверить, что клон F слабо отделяет a от b в некоторой точке a G ran a. В силу леммы 7 достаточно показать, что клон F слабо отделяет a от b в любой точке a'- G ran a.
Выберем произвольный элемент a'- G ran a. Используя лемму 7, выберем такие функции fo, fi,…, fr-i G F, что fo (a) = a'-, fi (a) = f2(a) = … = fr-i (a) = a, и последовательность b* = (fo (b), fi (b), f2(b),…, fr-i (b)) инъективная. Последовательность a* = (a'-, a,…, a) принадлежит множеству A& lt-r. Выберем функцию f G F[r], для которой f (a*) = a'- и f (b*) = fo (b). Значения функций fo и h = = f (fo, fi, f2,…, fr-i) равны a'- на последовательности a и различны на последовательности b. ?
Теперь докажем предложение 6. Включение F С F^ nV-r^)nS очевидно. Следовательно, достаточно доказать, что для любого натурального числа n, множества Q С An и функции g G F^ nV-r^)ns ограничение g Q принадлежит F Q.
Индукция по мощности Q. Если |Q| = 1 или Q С A& lt-r, утверждение очевидно. Будем считать, что |Q| ^ 2, Q A& lt-r = 0, и утверждение доказано для всех множеств Q'- мощности, меньшей |Q|.
Пусть g есть произвольная функция из F^ nV-r (f)ns. Выберем такие различные последовательности a, b G Q, что ranb ^ r. По предположению индукции клон F содержит функции ga и gb, которые совпадают с функцией g соответственно на множествах Q{a} и Q{b}. Если gb (b) = g (b), шаг индукции доказан. В противном случае (a, b) / R (F)П5. Используя лемму 8, выберем r — 2 функций
g2, дз, •••, gr-1 из F, для которых g2(a) = дз (а) = … = gr-i (a) = g (a), a последовательность b* = (gb (b), g (b), g2(b), g3(b),…, gr-i (b)) инъективная. Выберем функцию f € F[r], которая совпадает с селекторной функцией е0 на множестве A& lt-r и принимает значение g (b) на последовательности b*. Положим
h = f (gb, ga, g2, g3,.., gr-i).
Очевидно,
h (a) = f (g (a), ga (a), g (a), g (a),…, g (a)) = g (a), h (b) = f (b*)= g (b), h (x) = f (g (x), g (x), g2(x), g3(x),.., gr-i (x)) = g (x) для всех последовательностей x? Q{a, b}. Шаг индукции доказан. ?
Дадим характеризацию симметричных клонов F С М • Предложение 9. Пусть дан симметричный клон F С М, удовлетворяющий условиям r (F) = 3 и n (F) = D2. Тогда F = МП Vr (f)nS ¦
Доказательство. Каждую функцию f € V[3], для которой f А& lt-з = будем называть д-функцией. Каждая д-функция f удовлетворяет тождествам f (x, x, y) = = f (x, y, x) = f (y, x, x) = x для всех x, y € A. Используя симметричность клона F, для каждой последовательности a € A3 и элемента a € ran a легко найти д-функцию f € F, для которой f (a) = a.
Пусть дано натуральное число n ^ 1 и последовательности a = = (a0, ai,…, an-i), b = (bo, bi,…, bn-i) € An.
Лемма 10. Если F слабо отделяет a от b в точке a € ran a, то F сильно отделяет a от b в точке a € ran a.
Доказательство. Лемма, очевидно, верна, если | ran b| ^ 2. Пусть, напротив, | ran b| ^ 3. Выберем произвольный элемент b € ran b. Допустим, что клон F не содержит такой функции g, что g (a) = a и g (b) = b. Выберем такие функции fо, f i, f2 €F[n] и различные элементы c, d € ran b, что
fo (a) = fi (a) = a, fo (b) = c, fi (b) = d, f2(b) = b.
По сделанному допущению b / {c, d}, т. е. (c, d, b) € A3. Выберем такую д-функцию f € F[3], что f (c, d, b) = b. Рассмотрим функцию h = f (fo, fi, f2). Очевидно, h (a) = = а и h (b) = 6, противоречие. ?
Будем говорить, что пара элементов (a, b) € ranaxranb связывает пару (a, b), если (Vi & lt- n) ai = a V bi = b. Если таких пар (a, b) не существует, последовательности a и b будем называть несвязанными.
Лемма 11. Пусть пара (a, b) связывает пару (a, b). Тогда:
(a) если | ranb| ^ 3, то F слабо отделяет a от b в точке a-
(b) f (a) = a V f (b) = b для любой функции f € M.
Доказательство. Пункт (a) проверяется непосредственно. Для проверки пункта (b), считая, что 2 С A, выберем такую последовательность c = (co, ci,…, cn-i) € 2n, что (Vi & lt- n) ci = 1 ^ ai = a. Тогда f © = 1 ^ f (a) = a и /© =0^/(b) = 6. ?
Лемма 12. Если последовательности a и b несвязанные и (a, b) G R (F) П5, то для любых элементов a G ran a, b G ran b существует функция g G F[n], для которой g (a) = a и g (b) = b.
Доказательство. Предположим, что клон F слабо (а по лемме 10 и сильно) отделяет a от b по крайней мере в двух различных точках. Тогда клон F слабо (а по лемме 10 и сильно) отделяет b от a в любой точке b G ran b, что доказывает лемму. Аналогично, лемма верна, если клон F слабо отделяет b от a по крайней мере в двух различных точках. Остается проверить, что оставшийся случай противоречит условию несвязанности последовательностей, а и Ь. ?
Теперь так же, как и в предложении 6, достаточно доказать, что для любого натурального числа n, множества Q С An и функции g G MnVjz (F)nS ограничение g Q принадлежит F Q.
Вновь индукция по мощности Q. Если |Q| = 1 или Q С A& lt-3, утверждение очевидно. Будем считать, что |Q| ^ 2, Q А& lt-з = 0, и утверждение доказано для всех множеств Q'- мощности, меньшей |Q|.
Пусть g есть произвольная функция из M. nVj (F)riS. Выберем такие различные последовательности a, b G Q, что ran b ^ 3. По предположению индукции клон F содержит функции ga и gb, которые совпадают с функцией g соответственно на множествах Q {a} и Q {b}. Если gb (b) = g (b), шаг индукции доказан. В противном случае (a, b) / R (F) П5. Кроме того, по лемме 11, пункт (b), если пара (a, b) связывает пару (a, b), то g (a) = a. Таким образом, по леммам 11, 12, пункт (a), и 10 клон F сильно отделяет a от b в точке g (a). Пусть gab есть такая функция из F, что ga, b (a) = g (a) и ga, b (b) = g (b). Выберем произвольную-функцию f GF[3] и положим h = f (gb, ga, ga, b). Очевидно,
h (a) = f (g (a), ga (a), g (a)) = g (a), h (b) = f (gb (b), g (b), g (b))= g (b),
h (x) = f (g (x), g (x), ga, b (x)) = g (x), для всех последовательностей x G Q {a, b}. Шаг индукции доказан. ?
Обратимся теперь к случаю r (F) = 2. Будем говорить, что клон F С O удовлетворяет условию
если для любых последовательностей a, b G с различными областями значений и элементов a G ran a, b G ran b существует такая функция f G F[2], что f (a) = a, f (b) = b и f (x, x) = x для всех x G A.
Предложение 13. Пусть дан такой клон F С V, что r (F) = 2. Пусть |А| ^ 5. Тогда клон F удовлетворяет условию
sep2.
Доказательство. Для каждого номера i G {0,1} обозначим символом & gt-j бинарное отношение на множестве A22, заданное формулой
a b ^ ((Vf G F[2])f (a) = ai ^ f (b) = b& lt-)
для всех последовательностей a = (ao, ai), b = (bo, bi) G A2.
Легко проверить, что для каждого номера i G {0,1}, последовательностей a, b G A2 и перестановки a G Sa выполнено:
(a) отношение & gt-j рефлексивно и транзитивно-
(b) a & gt-j b ^ aa & gt-j ab-
© a & gt-j b ^ b & gt-i_j a.
Допустим, что клон F не удовлетворяет условию SEP2. Тогда a & gt-j b для некоторого номера i G {0,1} и последовательностей a, b G A2 с различными областями значений. Пользуясь свойствами (a) и (b) (и условием |A| ^ 5), легко найти такие последовательности a*, b* G A2, что a* & gt-j b* и ran a* П ran b* = 0. Отсюда по тем же свойствам имеем & gt-j = х A|. По свойству © имеем & gt-i-j = х A|. Противоречие с условием t (F) = 2. ?
Клон F С V будем называть свободным, если он содержит все функции f G V, для которых f Б& lt-ш G F Б& lt-ш для каждого двухэлементного множества B С A (свободный клон F С V однозначно определяется функцией, которая каждому двухэлементному множеству Б С A ставит в соответствие постовский класс П, эквивалентный клону F Б& lt-ш).
Предложение 14. Пусть дан клон F С V, для которого выполнено условие SEP2. Тогда F есть свободный клон.
Доказательство. Пусть дано натуральное число n ^ 1. Для множества Q С An будем называть функцию f G V[n] допустимой на множестве Q, если f (Qn ПБП) G F (Q П Bn) для каждого двухэлементного множества Б С A. Достаточно показать, что для каждого множества Q каждая допустимая на множестве Q функция f gF принадлежит клону F.
Индукция по мощности множества Q. Если |Q| = 1 или Q С Бп для некоторого двухэлементного множества Б С A, утверждение очевидно. Будем считать, что оба этих условия не выполнены, и утверждение доказано для всех множеств Q'- мощности, меньшей |Q|.
Пусть g есть произвольная допустимая на множестве Q функция из V. По предположению индукции для каждой последовательности a G Q существует функция ga G F, которая совпадает с функцией g на множестве Q {a}. Если ga (a) = g (a) для некоторой последовательности a G Q, шаг индукции доказан.
Будем далее предполагать, что ga (a) = g (a) для любой последовательности a G Q. Для любой последовательности a G Q и элемента a G ran a обозначим символом ga a некоторую функцию из клона V, которая совпадает с функцией g на множестве Q {a} и принимает значение, а на последовательности a. Предположим, что некоторая функция ga a не допустима на множестве Q. Тогда | ran a| = 2 и h (a) = а для каждой функции h G F, которая совпадает с функцией g на множестве Q {a}, в частности, для h = ga. С другой стороны, а = g (a), поскольку функция g допустима на множестве Q. Отсюда ga (a) = g (a), что противоречит предположению.
Таким образом все функции ga a допустимы на множестве Q. По предположению индукции для каждой пары различных последовательностей a, b G Q и элемента, а G ran a клон F содержит функцию gb, a, a, которая принимает значение, а на последовательности a и совпадает с с функцией g на множестве Q {a, b}.
Теперь построим функцию h G F[n], для которой h Q = g Q.
Случай 1: {g (a), ga (a)} = {gb (b), g (b)} для некоторых различных последовательностей a, b G Q. Выберем такие последовательности a и b. Тогда можно положить h = f (gb, ga), где f G F[2] и
f (g (a), ga (a)) = g (a), f (gb (b), g (b)) = g (b).
Случай 2: ran a = ran b для некоторых последовательностей a, b G Q. Выберем такие последовательности a и b. Без ограничения общности будем считать, что ran a ran b = 0. Выберем элемент c G ran a ran b. Тогда можно положить h = = fo (gb, fl (ga, gb, a, c)), где fo, fl GF[2] и
fo (g (a), c) = g (a), fo (gb (b), g (b)) = g (b),
fl (fa (a), c) = a, fi (f (b), gb, a, c (b)) = g (b).
Случай 3: случаи 1−2 не выполнены. Обозначим множество ran a для некоторой (любой) последовательности a G Q символом Б. Заметим, что Б ^ 3.
Подслучай 3. 1: существуют такие различные последовательности a, b G Q, что g (a) = g (b). Выберем такие последовательности a и b. Обозначим символом a элемент g (a). Из невыполненности случая 1 следует, что ga (a) = gb (b) = b для некоторого элемента b G ranb {a}. Выберем элемент c G B {a, b}. Тогда можно положить h = fo (gb, fi (ga, gb, a, c)), где fo, fi gF[2] и
fo (a, c) = fo (b, a) = a, fi (b, c) = c, fi (a, gb, a, c (b)) = a.
Подслучай 3. 2: g (a) = g (b) для всех последовательностей a, b G Q. Пусть сначала множество Q состоит ровно из двух последовательностей a и b. Покажем, что для каждого элемента c G B, кроме, быть может, одного, существует такая функция hc G F[n], что hc (a) = c = hc (b). Действительно, поскольку a = b, существует такая проекция e G ?[n], что e (a) = e (b). Положим e (a) = u и e (b) = v. Пусть c G B {v}. Выберем такую проекцию e'- G ?[n], что e'-(a) = c, и такую функцию f G F[2], что f (u, c) = c и f (v, c) = v. Тогда в качестве hc подходит одна из функций e'- и f (e, e'-).
Положим g (a) = a и g (b) = b. Из невыполненности случая 1 следует, что ga (a) = b и gb (b) = a. Выберем элемент c G Б {b}, для которого определена функция hc с указанным свойством. Тогда можно положить h = fo (gb, fi (ga, hc)), где fo, fi GF и
fo (a, c) = a, fo (a, b) = b, fi (b, c) = c, fi (b, hc (b)) = b.
Пусть теперь Q ^ 3. Выберем различные последовательности a, b, c G Q. Пусть g (a) = a, g (b) = b и g© = c. Функции gab и gb, c допустимы на множестве Q и удовлетворяют условиям подслучая 3.2. Поэтому существуют функции ha, b, hb, c G F, которые на всем множестве Q соответственно совпадают с функциями ga b и gb, c. Тогда можно положить h = f (hajb, hb, c), где f gF[2] и
f (b, a) = a, f (b, c) = b. Шаг индукции доказан. ?
Свободный клон F С V, для которого все клоны F Б& lt-ш, Б С A и Б = = 2, эквивалентны одному и тому же постовскому классу П, будем обозначать символом П^. Очевидно, свободный клон F симметричен тогда и только тогда, когда F = П^ для некоторого постовского класса П, состоящего из функций, сохраняющих 0 и 1, и замкнутого относительно перехода к двойственной функции. Напомним, что помимо классов Oi, Di, D2, L4 этим свойством обладают только два: класс C4 всех булевых функций, сохраняющих 0 и 1, и класс A4 всех монотонных функций из C4.
Теперь сформулируем основную теорему, которая вытекает из доказанных предложений.
Теорема 15. Пусть дано конечное множество A. мощности не менее 5 и клон F на множестве A, состоящий из функций, сохраняющих все одноместные предикаты. Тогда клон F симметричен тогда и только тогда, когда существуют такие параметры r, m G {3, 4,…, |A|} U {w} и такое устойчивое слева и справа отношение эквивалентности RCS на множестве А& lt-ш, что имеет место один из случаев:
(a) F = CnV-r, где G есть один из клонов E+ry или П+ для некоторого класса П G {Di, L4}-
(b) F = П^ для некоторого класса П G {Oi, Di, D2, L4,A4,C4}.
Замечание Очевидно, если r (F) ^ 3, то отношение R (F) содержит подмножество (A& lt-^ х A& lt-<-3) nS, и имеют место равенства П^)+ ^Ущт) = П^)^ nV-r^). Кроме того, если r (F) = 2 и |A| ^ 5, то отношение R (F) совпадает с отношением равенства, и П^ = П^ П Vr (f)• Поэтому эквивалентную формулировку теоремы 15 можно получить, отбросив случай (b) и заменив в случае (a) слова & quot-… или П+ для некоторого класса П G {Di, L4}& quot- на & quot-… или П^ для некоторого класса П G{Oi, Di, D2, L4,A4,C4}& quot-.
Заметим еще, что несложно дать явное описание всех устойчивых слева и справа отношений эквивалентности RCS и продолжить классификацию на случай |A| ^ 4. Однако для многих следствий в теории коллективного выбора достаточно доказанной теоремы. В частности, из нее легко получить, что при |A| ^ 5 и k ^ 3 каждое симметричное непустое собственное подмножество D множества всех функций выбора из k-элементных подмножеств A сохраняется только проекциями.
Литература
[1] Arrow K. A difficulty in the theory of social welfare // J. of Political Economy. 1950. № 58. P. 328−346.
[2] Fishburn P. The Theory of Social Choice. Princeton: Princeton University Press, 1973.
[3] Shelah S. On the Arrow property // Advances in Applied Mathematics. 2005. № 34. P. 217−251. math. LO/112 213.
[4] Post E.L. Two-valued iterative systems of mathematical logic // Annal of Math. studies. 1941. V. 5.
[5] Нгуен Ван Хоа. О семействах замкнутых классов k-значной логики, сохраняемых всеми автоморфизмами // Дискретная математика. 1993. Т. 5. Вып. 4.
[6] Марченков С. С. Замкнутые классы булевых функций. М.: Физматлит, 2000.
[7] Марченков С. С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004.
[8] Теория Галуа для алгебр Поста / В. Г. Боднарчук [и др.] // Кибернетика, 1969. Вып. 3, 5.
Поступила в редакцию 22/III/2013- в окончательном варианте — 22/III/2013.
ON SYMMETRIC CLOSED CLASSES OF FUNCTION PRESERVING EVERY UNARY PREDICATE
© 2013 N.L. Polyakov? M.V. Shamolin4
The activity presents an efficient description of symmetric closed classes of discrete functions preserving every unary predicate.
Key words: closed class, clone, Galois correspondence, theory of collective choice.
Paper received 22/III/2013. Paper accepted 22/III/2013.
3Polyakov Nikolay Lvovich (gelvellaSmail. ru), the Dept. of Mathematics-1, Financial University under the Government of the Russian Federation, Moscow, 101 000, Russian Federation.
4Shamolin Maxim Vladimirovich (shamolinaimec. msu. ru), Institute of Mechanics, Lomonosov Moscow State University, Moscow, 119 192, Russian Federation.

ПоказатьСвернуть
Заполнить форму текущей работой