Определение изоморфизма

[oleg.k]

Пусть даны две алгебраические структуры $(M, \circ)$ и $(N, \bullet)$. Говорят, что структура $(M, \circ)$ изоморфна структуре $(N, \bullet)$, если существует биективное отображение $f:M \to N$ такое, что $(\forall a, b \in M) f(a \circ b) = f(a) \bullet f(b)$.

Отношение $(M, \circ) \cong (N, \bullet)$ между структурами я читаю как "$(M, \circ)$ изоморфна $(N, \bullet)$" (а не как: "$(M, \circ)$ и $(N, \bullet)$ изоморфны"). Понятно дело, что если $(M, \circ)$ изоморфна $(N, \bullet)$, то $(N, \bullet)$ изоморфна $(M, \circ)$, но я понимаю это как теорему, а само отношение изоморфизма (как и любое другое отношение) упорядочено. Правильно ли я понимаю этот момент?

Если на первый вопрос ответ положительный, то у меня возникает другая проблема. Я меня есть некий неформальный образ, связанный с изоморфизмом. Когда $(M, \circ)$ изоморфна $(N, \bullet)$, я представляю себе структуру $(N, \bullet)$ как "оригинал", а структуру $(M, \circ)$ как "репродукцию". Это представление отражает то "неравноправие" (т.е. упорядоченность) в определении отношения изоморфизма. Иными словами, неформальный образ примерно такой: "картинка из интернета с Мона Лизой изоморфна оригинальной картине Леонардо да Винчи, висящей в Лувре". Понятно, что оригинальная картина тоже изоморфна картинке из интернета, но тогда по смыслу отношения "эталоном" в этом отношении будет картинка из интернета, а не оригинал. Проблема в том, что такой неформальный образ конфликтует с самим определением изоморфизма. В определении мы берем пару $(a, b)$ точек из "репродукции" и результат $a \circ b$ применения операции $\circ$ отображается в точку оригинала. И это нелогично. А логично должно быть так:

Говорят, что структура $(M, \circ)$ изоморфна структуре $(N, \bullet)$, если существует биективное отображение $f:M \to N$ такое, что $(\forall a, b \in N) f[f^{-1}(a) \circ f^{-1}(b)] = a \bullet b$.

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

Эквивалентно ли "мое" определение изоморфизма общепринятому? (я проверил, по-моему эквивалентно, но хотелось бы в этом убедиться)

[arseniiv]

oleg.k в сообщении #1441691 писал(а):

Отношение $(M, \circ) \cong (N, \bullet)$ между структурами я читаю как "$(M, \circ)$ изоморфна $(N, \bullet)$" (а не как: "$(M, \circ)$ и $(N, \bullet)$ изоморфны"). Понятно дело, что если $(M, \circ)$ изоморфна $(N, \bullet)$, то $(N, \bullet)$ изоморфна $(M, \circ)$, но я понимаю это как теорему, а само отношение изоморфизма (как и любое другое отношение) упорядочено. Правильно ли я понимаю этот момент?

Да, только не говорят «упорядочено» в таком смысле. Ну а после того как доказано, что отношение симметрично, можно и слова вольнее употреблять, нужды читать всегда «(1) изоморфна (2)» вместо «(1) и (2) изоморфны» уже не будет.

oleg.k в сообщении #1441691 писал(а):

Если на первый вопрос ответ положительный, то у меня возникает другая проблема. Я меня есть некий неформальный образ, связанный с изоморфизмом. Когда $(M, \circ)$ изоморфна $(N, \bullet)$, я представляю себе структуру $(N, \bullet)$ как "оригинал", а структуру $(M, \circ)$ как "репродукцию". Это представление отражает то "неравноправие" (т.е. упорядоченность) в определении отношения изоморфизма. Иными словами, неформальный образ примерно такой: "картинка из интернета с Мона Лизой изоморфна оригинальной картине Леонардо да Винчи, висящей в Лувре". Понятно, что оригинальная картина тоже изоморфна картинке из интернета, но тогда по смыслу отношения "эталоном" в этом отношении будет картинка из интернета, а не оригинал. Проблема в том, что такой неформальный образ конфликтует с самим определением изоморфизма. В определении мы берем пару $(a, b)$ точек из "репродукции" и результат $a \circ b$ применения операции $\circ$ отображается в точку оригинала. И это нелогично.

Ну тут вы во-первых слишком идёте на поводу у естественного языка и во-вторых забываете, что в определении-то биекция. Да и даже не важно, биекция ли, если после того как мы определили изоморфность, мы докажем, что она симметрична, и увидим потому, что копия настолько хороша, что сам оригинал для неё копия. То есть исходное представление должно будет уступить новому, ровно как во множестве других случаев, когда сначала нам язык намекает на одно, а потом мы узнаём, что он нанамекал больше (или меньше) чем надо.

oleg.k в сообщении #1441691 писал(а):

Эквивалентно ли "мое" определение изоморфизма общепринятому? (я проверил, по-моему эквивалентно, но хотелось бы в этом убедиться)

Да, конечно, биекция же.

Можно ещё такое более симметричное определение $M\cong N$ взять, по-моему оно предпочтительнее в плане поиска эстетики:

$$\forall a, b, c\in M.\; a\circ b = c\Leftrightarrow f(a)\bullet f(b) = f(c).$$

Можно ещё подкрутить, воспринимая функцию как частный случай отношения:

$$\forall(a,a'), (b,b'), (c,c')\in f.\; a\circ b = c\Leftrightarrow a'\bullet b' = c'.$$

(Удивлюсь, если последнее не понравится.)

Ещё один выход — определить всё же сначала (гомо)морфизм, а потом определить изоморфизм как морфизм, имеющий обратное отображение, которое тоже морфизм. Это и в духе теорката: любой «вручную классически определённый» изоморфизм обладает таким свойством, если мы правильно определили просто морфизм.

(UPD: обобщения)

Последние две формулы заодно намекают, как определять изоморфизм для более общего (но не самого конечно общего, поднимаемого теоркатом) случая алгебраической системы с разноместными операциями, отношениями и потенциально несколькими носителями: мы просто сначала каждую операцию $a\colon A_1\times\ldots\times A_n\to B_1\times\ldots\times B_m$ превратим в отношение $r$ такое, что $a(x_1,\ldots,x_n) = (y_1,\ldots,y_m) \Leftrightarrow r(x_1,\ldots,x_n,y_1,\ldots,y_m)$, а потом для каждого отношения $r\colon A_1\times\ldots\times A_n$ запишем по условию

$$\forall x_1\in A_1\ldots\forall x_n\in A_n.\; r(x_1,\ldots, x_n)\Leftrightarrow r(f_{A_1}(x_1),\ldots,f_{A_n}(x_n)),$$

где $f_A$ — кусок биекции из одного из носителей первой структуры в соответствующий носитель второй. Изоморфизм будет кортежем из биекций для каждого носителя, или же биекцией из прямой суммы носителей первой в прямую сумму носителей второй, не отображающей элементы одного слагаемого в «неправильные». (Второе может быть удобно тем, что композиция изоморфизмов не требует особого определения.)

[Alexzord]

Добавлю 5 копеек. Изоморфность -- это не просто отношение, а отношение эквивалентности. Это та теорема, о которой вы говорите. Поэтому не особо-то оно "упорядочено" в силу свойства симметричности.

[oleg.k]

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

(Удивлюсь, если последнее не понравится.)

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

Alexzord в сообщении #1441720 писал(а):

Поэтому не особо-то оно "упорядочено" в силу свойства симметричности.

Да, это понятно. Но отношение все же из упорядоченных пар состоит как никак. Да и пишем и читаем мы слева направо. Вобщем, понятно в каком смысле я имел в виду упорядоченность.

-- 27.02.2020, 00:09 --

Вот мне бы лично больше бы понравилось определение со словами "существуют отображения $f:M \to N$ и $g:N \to M$ такие, что...", а потом показывалось бы, что из существования одного вытекает существование другого. Да, определение получится избыточным. Но почему это плохо?

-- 27.02.2020, 00:19 --

(Оффтоп)

По пути возник вопрос об избыточности определений. Почему всегда так стараются уменьшить кол-во требований? Взять ту же метрику. Если должным образом постулировать неравенство треугольника, то требований будет не 3, а 2. И какой профит от этого? Имхо определение должно быть как можно ближе к интуиции и неформальным образам, а в качестве критериев можно уже доказывать что угодно.

[arseniiv]

oleg.k в сообщении #1441724 писал(а):

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

Ну ведь это ни в каком смысле кроме формального не выйдет.

oleg.k в сообщении #1441724 писал(а):

Вот мне бы лично больше бы понравилось определение со словами "существуют отображения $f:M \to N$ и $g:N \to M$ такие, что...", а потом показывалось бы, что из существования одного вытекает существование другого. Да, определение получится избыточным. Но почему это плохо?

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

-- Чт фев 27, 2020 02:33:13 --

(Про избыточность)

oleg.k в сообщении #1441724 писал(а):

По пути возник вопрос об избыточности определений. Почему всегда так стараются уменьшить кол-во требований? Взять ту же метрику. Если должным образом постулировать неравенство треугольника, то требований будет не 3, а 2. И какой профит от этого? Имхо определение должно быть как можно ближе к интуиции и неформальным образам, а в качестве критериев можно уже доказывать что угодно.

Можно предположить, что некоторые авторы чересчур увлекаются без полезной для учебника цели, а некоторые приводят минимальные аксиоматизации для интереса как дополнение к какой-нибудь не такой минимальной. Ну и иногда усилия на преобразования «то будем считать аксиомами, а это доказываемыми критериями» минимальны, как в случае 2↔3 аксиом метрического пространства, так что вопрос нередко мелкий.

[Munin]

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

а потом определить изоморфизм как морфизм, имеющий обратное отображение, которое тоже морфизм.

Этого недостаточно. Этот морфизм должен быть обратным морфизмом, а не просто обратным отображением.

[arseniiv]

Ну я и написал «которое тоже морфизм».

[Munin]

Обратный морфизм - это такой, что $\varphi^{-1}\varphi=\varphi\varphi^{-1}=1$ - тождественный морфизм. (В категорном смысле, но в вашем случае - и в алгебраическом.)

Следует ли из "обратное отображение, которое тоже морфизм" - "обратный морфизм"?

[arseniiv]

Но ведь тождественное отображение [алгебраических структур — хотя конечно и много чего ещё] всегда морфизм. Обратная функция тоже должна быть и левой, и правой обратной, так что всё нормально.

Кстати говоря $\varphi^{-1}\varphi=\varphi\varphi^{-1}=1$ можно написать только в случае, когда мы говорим об эндоморфизмах, потому что иначе первое выражение даёт тождественный морфизм одного объекта и второе — другого.

[oleg.k]

У Винберга в "Курсе алгебры" нашел такую фразу:

Винберг писал(а):

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

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

[Padawan]

Кстати, гомоморфизм, являющийся биекцией не обязан быть изоморфизмом. Это верно только в случае операций. В случае произвольных отношений это неверно. Например, взаимно однозначный гомоморфизм чумов ($a\leq b$ следует $f(a)\leq f(b)$) не обязательно изоморфизм. В области определения все элементы просто могут быть не сравнимы или ещё что-то подобное.

[Someone]

oleg.k в сообщении #1441809 писал(а):

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

Пусть у нас есть алгебраическая система $M$, в которой есть некоторый набор алгебраических операций и отношений (как минимум, отношение равенства там есть). В алфавите есть символы для переменных (бесконечное количество) и констант (например, в поле есть две константы: $0$ и $1$).
1) Если $t$ — константа или переменная, то $t$ — терм.
2) Если $t_1,t_2,\ldots,t_n$ — термы, $K$ — $n$-арная операция, то $K(t_1,t_2,\ldots,t_n)$ — терм.
Термы нужно рассматривать как имена элементов алгебраической системы.
3) Если $t_1,t_2,\ldots,t_n$ — термы, $R$ — $n$-арное отношение, то $R(t_1,t_2,\ldots,t_n)$ — формула.
4) Если $\Phi$ и $\Psi$ — формулы, то $\neg(\Phi)$, $(\Phi)\vee(\Psi)$, $(\Phi)\wedge(\Psi)$ и $(\Phi)\Rightarrow(\Psi)$ — формулы.
5) Если $\Phi$ — формула, $x$ — переменная, то $\forall x(\Phi)$ и $\exists x(\Phi)$ — формулы.
Формула — это и есть формальное выражение того, что Винберг называет "высказыванием".

Замечания по поводу пункта 5).
Чтобы не морочить себе голову с переименованиями переменных, считаем, что область действия переменной $x$ в кванторе ограничена скобками вокруг формулы $\Phi$, и снаружи эта переменная невидима. Такая переменная называется связанной. Вместо связанной переменной нельзя ничего подставлять. Снаружи области действия квантора может встретиться другая переменная с тем же именем; в таком случае это именно другая переменная, никак не сообщающаяся с одноимённой переменной в области действия квантора. В математике обычно избегают таких совпадений имён, но в языках программирования это обычная практика (глобальные и локальные переменные).
Для "навешивания" квантора по переменной $x$ не требуется, чтобы эта переменная фактически входила в формулу $\Phi$ в качестве свободной, но пользы от таких кванторов нет, и их обычно избегают.
Если переменная в формуле не является связанной, то она называется свободной и видна снаружи, и вместо неё можно подставлять любой терм.
При интерпретации формулы, содержащей свободные переменные, обычно считается, что все свободные переменные связаны кванторами всеобщности $\forall$.

[oleg.k]

Someone в сообщении #1441821 писал(а):

$K$ — $n$-арная операция

А можно так: $K$ - $n$-арный ($n \geqslant 1$) функциональный символ из сигнатуры нашего логико-математического языка первого порядка? А то тут операция и в алгебраической структуре алгебраическая операция. Создается путаница.

Someone в сообщении #1441821 писал(а):

$R$ — $n$-арное отношение

Здесь мне было бы удобнее говорить так: $R$ — $n$-арный ($n \geqslant 0$) предикатный символ из сигнатуры нашего логико-математического языка первого порядка. Так верно?

Someone в сообщении #1441821 писал(а):

Формула — это и есть формальное выражение того, что Винберг называет "высказыванием".

Допустим, есть теория групп - формальная теория первого порядка с сигнатурой $\Omega = (e, \cdot, =)$. В ней есть какие то термы и формулы. А Винберг утверждает, что если у нас есть две группы $(M, \circ)$ и $(N, \bullet)$, изоморфные относительно групповой операции, то "любое утверждение, формулируемое только в терминах заданных операций, будет справедливым в одной из этих структур тогда и только тогда, когда оно справедливо в другой". Если я все правильно понимаю, в формальной теории групп нету двух групп. И изоморфизма там нету. Да, формулы формальной теории групп - это формальное выражение того, что Винберг называет высказыванием о группе. Но тут то ведь другая ситуация. Я этот момент не понимаю.

Someone в сообщении #1441821 писал(а):

Чтобы не морочить себе голову с переименованиями переменных, считаем, что область действия переменной $x$ в кванторе ограничена скобками вокруг формулы $\Phi$, и снаружи эта переменная невидима. Такая переменная называется связанной. Вместо связанной переменной нельзя ничего подставлять. Снаружи области действия квантора может встретиться другая переменная с тем же именем; в таком случае это именно другая переменная, никак не сообщающаяся с одноимённой переменной в области действия квантора. В математике обычно избегают таких совпадений имён, но в языках программирования это обычная практика (глобальные и локальные переменные).

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

[arseniiv]

oleg.k в сообщении #1441832 писал(а):

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

Ну да, именно высказывания об элементах только одной группы. Можно считать, что мы определяем на этом языке внутренние свойства группы. Язык можно усложнить, но для этого лучше иметь требующие этого примеры, а то так можно будет застрять в абстрагировании.

oleg.k в сообщении #1441832 писал(а):

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

Тут дело в том, что из-за возможности переименовывать связанные вхождения нет смысла считать, что это вхождения тех же переменных, что и какие-либо другие (даже связанные другим квантором), кроме того совпадение имён таких разных вхождений усложняет некоторые манипуляции (некоторые замены оказываются запрещёнными без переименования), так что прозрачнее или считать, что каждый квантор навешивается на уникальную среди всех высказываний, которые нам вообще попадутся, переменную, или например принять конвенцию индексов де Брёйна. Но это всё мимо текущей темы.

[oleg.k]

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

кроме того совпадение имён таких разных вхождений усложняет некоторые манипуляции (некоторые замены оказываются запрещёнными без переименования)

Замена - это подстановка? Я читал, что подстановка для формул относится только к свободным вхождениям переменных. Некоторые термы $t$ оказываются свободными для переменной $x$ в формуле $A$ (это когда все свободные вхождения $x$ в $A$ не находятся в области действия кванторов по переменным, входящим в терм $t$); некоторые подстановки оказываются свободными для формул (это когда каждый терм в формуле свободен для соответствующей переменной). Далее в книге говорилось, что с логической точки зрения подстановка терма $t$ вместо $x$ в формулу $A$ является правильной и осмысленной, только если $t$ свободен для $x$ в $A$. Это я все к тому, что получается очень прозрачная картина.

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

Ну да, именно высказывания об элементах только одной группы.

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