Берлин Илья Михайлович

Ответ на « »

Пусть Е- множество из n элементов. Можно считать, что E={1;2;3;...;n}. Рассмотрим произведение EхE={ <n; m > | nєE, mєE}. Каждому отношению эквивалентности на множестве Е соответствует подмножество Φ в EхE, которое содержит диагональ Δ и симметрично относительно неё. Диагональ разбивает EхE на два множества Fˈи F: EхE=FˈU ΔU F; причём
F={ <n; m > | nєE, mєE, n > m }, а Fˈ симметрично F относительно диагонали Δ.

Аналогично, отношение эквивалентности Φ на множестве Е также делится диагональю Δ на две симметричные части G´ и G: Φ =G´ U ΔU G; причём
G ={ <n; m > є Φ | n > m }, G подмножество в F. Поэтому число всех отношений эквивалентности на множестве Е равно числу всех подмножеств множества F. Элементами F являются пары чисел <n; m > є EхE. Всего таких пар (nхn – n)/2=
(n²- n)/2. Если в множестве s элементов, то у него 2 в степени s подмножеств.
Ответ: 2 в степени(n²- n)/2.