Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Функции и классы.

Пусть D и R – конечные множества. Рассмотрим функции, определенные на D, со значениями в R; другими словами, рассмотрим отображения D в R. Множество всех таких функций обозначим через R^D. Число элементов в множестве R^D равно ½R½^½D½, поскольку если мы хотим построить функцию f, то мы имеем для каждого элемента dÎD ½R½возможностей выбрать f(d), и эти выборы независимы.

Далее предположим, что нам дана группа G множества D. Эта группа вводит отношение эквивалентности в R^D: две функции f₁ и f₂ (обе из R^D) называют эквивалентными (обозначим f₁~f₂), если существует элемент gÎG, такой, что

f₁(gd)= f₂(d) для всех dÎD. (8)

Соотношение (8) может быть кратко записано так: f₁g= f₂, ибо f₁g обозначает сложное отображение “сначала g потом f₁”. Легко установить обычные условия эквивалентности: 1) f~f; 2) если f₁~f₂, то f₂~f₁; 3) если f₁~f₂ и f₂~f₃, то f₁~f₃. Первое условие следует из того, что тождественная подстановка принадлежит G; второе условие следует из того, что если gÎG, то обратная подстановка g^-1 принадлежит G; и третье – из того, что если g₁ÎG, g₂ÎG, то g₁g₂ÎG.

Таким образом, ~ есть отношение эквивалентности, с помощью которого R^D разбивается на классы эквивалентности.

Пример 8. Пусть D – множество, состоящее из всех шести граней куба, и пусть G – группа всех подстановок D, которые могут быть получены вращениями куба (см. пример 3). Пусть R состоит из двух слов: красный и белый. Элемент fÎR^D может быть рассмотрен как способ окрашивания куба (так что каждая грань красная, либо белая). Это может быть сделано 2⁶ способами. Если два таких куба, расположенных параллельно окрашены различно, то может случиться, что один из них можно повернуть так, что кубы перестанут казаться различными. В этом случае они принадлежат одному классу эквивалентности.

В нашем примере десять классов эквивалентности, которые могут быть описаны следующим образом (в скобках – число функций в каждом классе эквивалентности): (а) все грани красные (1); (б) пять граней красные, одна белая (6); (в) две противоположные грани белые, остальные четыре красные (3); (г) две смежные грани белые, остальные четыре красные (12); (д) три грани, имеющие общую вершину, красные, остальные белые (8); (е) две противоположные и одна из оставшихся красные, три остальные белые (12); (ж), (з), (и), (к) получаются из (г), (в), (б), (а) заменой слов ‘красный’ на ‘белый’. В качеств примера заметим, что

1+6+3+12+8+12+12+3+6+1=2⁶.

Пример 9. Пусть D – множество, состоящее из трех элементов {1,2,3}, и пусть G – симметрическая группа всех перестановок из D и пусть R состоит из двух элементов x и y. В этом случае восемь функций, а классов эквивалентности четыре. Классы эквивалентности можно обозначить символами x³, x²y, xy², у³ соответственно. Например, x²y представляет класс отображений f, таких, что два из значений f(1), f(2), f(3) равны x и одно у. Класс эквивалентности x³ состоит только из одной функции, которая определена так:

f(1)=f(2)=f(3)=x.

Полезно рассмотреть также x и y как независимые переменные и поставить в соответствие каждой функции f произведение f(1)f(2)f(3), которое не зависит от порядка сомножителей. Другими словами, так как симметрическая группа дана, то говорить, что две функции f₁ и f₂ эквивалентны, – это то же, что сказать, что произведение f₁(1)f₁(2)f₁(3) и f₂(1)f₂(2)f₂(3) тождественны. Поэтому классы эквивалентности характеризуются возможными значениями произведений, а именно одночленами x³, x²y, xy², у³.