Число классов изоморфных структур на множестве из двух элем.

[SpiderHulk]

$(\left\lbrace 0, 1 \right\rbrace; \ast) { \simeq} (\left\lbrace 0, 1 \right\rbrace; \circ)$

Преподаватель поставил два вопроса и я даже не уверен, разные ли это вопросы?

Вопрос 1: Сколько в классе изоморфизма структур?

Вопрос уже от меня: что такое класс изоморфизма? Это совокупность некоторого числа изоморфных друг другу алгебраических структур (при этом алгебраическая структура не изоморфная никакой другой образует собственный класс) ? Или нечто иное?

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

Верно?

Вопрос 2: Найти число классов изоморфных структур на множестве из двух элементов и одной бинарной операцией

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

Верно?

[Xaositect]

SpiderHulk в сообщении #1352201 писал(а):

Вопрос уже от меня: что такое класс изоморфизма? Это совокупность некоторого числа изоморфных друг другу алгебраических структур (при этом алгебраическая структура не изоморфная никакой другой образует собственный класс) ? Или нечто иное?

Это максимальная совокупность изоморфных структур. Или, что эквивалентно, совокупность всех структур, изоморфных некоторой фиксированной структуре.

SpiderHulk в сообщении #1352201 писал(а):

Поэтому в классе изоморфизма на множестве из двух элементов не менее одной и не более двух алгебраических структур?

Верно.

SpiderHulk в сообщении #1352201 писал(а):

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

Нет, некоторые из классов содержат две изоморфные структуры, значит всего различных классов меньше 16.

[SpiderHulk]

Xaositect в сообщении #1352206 писал(а):

Нет, некоторые из классов содержат две изоморфные структуры, значит всего различных классов меньше 16

Тогда 8, на множестве из двух элементов транспозиция возможна всегда
Например, если бинарная операция в исходной алгебраической структуре задаётся таблицей Кэли

×| 0 1
0| 1 0
1| 0 0

то в структуре изоморфной исходной (изоморфизм - транспозиция) бинарная операция будет задаваться таблицей

°| 0 1
0| 1 1
1| 1 0

Верно?

[arseniiv]

Но некоторые структуры переходят в себя при транспозиции. Посмотрите на операцию $x*y = y$, например.

[SpiderHulk]

arseniiv в сообщении #1352269 писал(а):

Но некоторые структуры переходят в себя при транспозиции

10

Структуры

×| 0 1
0| 1 0
1| 1 0

×| 0 1
0| 0 1
1| 0 1

×| 0 1
0| 1 1
1| 0 0

×| 0 1
0| 0 0
1| 1 1

при транспозиции переходят сами в себя

[Munin]

Интересный вопрос.

$\begin{array}{|c|cc|}\hline \circ & 0 & 1 \\ \hline 0 & a & b \\ 1 & c & d \\ \hline \end{array}$

При изоморфизме у нас могут переставиться $0\leftrightarrow 1.$ Значит, надо смотреть на соотношения между $a,b,c,d,$ не зависящие от перестановки. А при перестановке переставляются друг с другом $a\leftrightarrow d,\quad b\leftrightarrow c.$

$a\stackrel{?}{=}d.$
Варианты:

$a=d$ - среди элементов есть выделенный $q,\quad\forall\,x\colon x^2=q.$
$a\ne d,\quad x^2=x$ - элементы идемпотенты, выделенного нет.
$a\ne d,\quad x^2\ne x$ - я не уверен, что есть такое слово, но назовём это "антиидемпотенты". Выделенного нет.

$b\stackrel{?}{=}c.$
Варианты:

$b=c$ - один элемент поглощает другой, есть выделенный $s,$ такой что при $x\ne s\colon xs=sx=s.$
$b\ne c$ - здесь можно выделить подварианты "левый элемент поглощает правый" и "правый элемент поглощает левый".

Итого, получаются такие сочетания:

$\begin{array}{|c||c|c|c|}\hline & a=d=q & a\ne d, x^2=x & a\ne d, x^2\ne x\\ \hline \hline b=c=s & s=q (2),s\ne q (2) & +(2) & +(2) \\ \hline b\ne c,lr=l & +(2) & + & + \\ \hline b\ne c,lr=r & +(2) & + & + \\ \hline \end{array}$

Итого, 10 классов изоморфизма. В каждой клетке, где есть некий выделенный элемент, он может быть или $0,$ или $1,$ и класс эквивалентности изоморфизма насчитывает 2 структуры (помечено $(2)$). В остальных классах по одной структуре. Всего получается 16 - всё сходится.

-- 07.11.2018 21:29:00 --

Расставлю здесь известные мне бинарные функции:

$\begin{array}{|c||c|c|c|}\hline (l\circ r) & a=d=q & a\ne d, x^2=x & a\ne d, x^2\ne x\\ \hline \hline b=c=s & \operatorname{const}0, \operatorname{const}1/\mathrm{XOR,EQ} & \mathrm{AND,OR} & \mathrm{NOR,NAND} \\ \hline b\ne c,lr=l & \lnot(l\to r),l\gets r & l & \lnot r \\ \hline b\ne c,lr=r & \lnot(l\gets r),l\to r & r & \lnot l \\ \hline \end{array}$

-- 07.11.2018 21:32:13 --

Замечание: если позволить вместе с изоморфизмом антиизоморфизм (меняющий местами левые и правые операнды), то вторая и третья строчки сливаются, и получается 7 классов.

-- 07.11.2018 21:38:16 --

$\begin{array}{|c|ccc|}\hline \circ & 0 & 1 & 2 \\ \hline 0 & a & b & c \\ 1 & d & f & g \\ 2 & h & i & j \\ \hline \end{array}$

Хм-м-м...

[arseniiv]

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