Вопросы по дискретной математике

[AndreyXYZ]

Верны ли следующие утверждения? Почему?
1) Пусть $G$ --- полугруппа, $g \in G.$ Тогда $ord<g>=|<g>|\ge ord\,g.$
Я всегда считал, что по определению $ord\,g=|<g>|.$
2) Любая конечная группа изоморфна группе подстановок с двумя образующими.
3) Почти все подгруппы $G\le S_n$ при $n \to \infty$ порождаются двумя образующими.
Мне кажется, что третье утверждение противоречит второму.
4) $|\mathbb{Z}_m^*|=\varphi(m)$. Насколько я понял, $\varphi(m)$ --- число делителей $m$, а что может означать запись $\mathbb{Z}_m^*?$

[ИСН]

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

[AndreyXYZ]

ИСН в сообщении #222675 писал(а):

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

Распише, пожалуйста, $\mathbb{Z}_6^*.$

Добавляю 5-й вопрос:
5) Верно ли, что любая группа преобразований множества $X,$ такого что $|X|=n,$ является подгруппой симметрической группы преобразований $S_n?$

[ИСН]

$\mathbb{Z}_6^*$? Извольте:
1*1 = 1
1*5 = 5
5*5 = 1
Это всё.

[Xaositect]

AndreyXYZ в сообщении #222764 писал(а):

Распише, пожалуйста, $\mathbb{Z}_6^*.$

Если $R$ - это кольцо, то $R^{*}$ - это группа всех его обратимых элементов с операцией умножения.
Т.е. $\mathbb{Z}_6^{*} = \{1, 5\} \cong \mathbb{Z}_2$

[AndreyXYZ]

С этим понятно, но остальные вопросы остаются нерешенными.

[VAL]

AndreyXYZ в сообщении #222665 писал(а):

Верны ли следующие утверждения? Почему?
2) Любая конечная группа изоморфна группе подстановок с двумя образующими.
3) Почти все подгруппы $G\le S_n$ при $n \to \infty$ порождаются двумя образующими.
Мне кажется, что третье утверждение противоречит второму.

Не вижу, чем третье противоречит второму. А вот то, что второе не является верным, по-моему, очевидно.

[AndreyXYZ]

Известно, что симметрическая группа подстановок $S_n$ порождается транспозицией $(1,2)$ и подстановкой циклического сдвига $(1,2,\ldots,n),$ т.е. двумя образующими.
Второе утверждение является следствием вышесказанного. Вы можете привести контрпример?

А вот третье утверждение вызывает у меня сомнения. Я думаю, что все (а не почти все) подгруппы $S_n$ порождаются двумя образующими.

[mkot]

Имеет место следующее утверждение:
Теорема Кэли. Любая конечная группа порядка $n$ изоморфна некоторой подгруппе симметрической группы $S_n$.
Доказательство можно найти в Введении в алгебру Кострикина (если издание 77 года, то страница 159).

-- Чт июн 18, 2009 01:31:08 --

Или под словами "группа подстановок" вы не подразумеваете симметрическую группу?

[VAL]

AndreyXYZ в сообщении #222907 писал(а):

Известно, что симметрическая группа подстановок $S_n$ порождается транспозицией $(1,2)$ и подстановкой циклического сдвига $(1,2,\ldots,n),$ т.е. двумя образующими.

Я бы даже сказал: широко известно!

Цитата:

Второе утверждение является следствием вышесказанного.

Никоим образом!

Цитата:

Вы можете привести контрпример?

Конечно! Возьмите $G=Z_2\times Z_2\times Z_2$

Цитата:

А вот третье утверждение вызывает у меня сомнения. Я думаю, что все (а не почти все) подгруппы $S_n$ порождаются двумя образующими.

Во-первых, если верно, что "все", то верно, что и "почти все". А во-вторых, не все.

-- 18 июн 2009, 01:45 --

mkot в сообщении #222909 писал(а):

Имеет место следующее утверждение:
Теорема Кэли. Любая конечная группа порядка $n$ изоморфна некоторой подгруппе симметрической группы $S_n$.
Доказательство можно найти в Введении в алгебру Кострикина (если издание 77 года, то страница 159).

... и во многих других источниках. Но отсюда никоим образом не следует милое сердцу AndreyXYZ'а утверждение 2.

[AndreyXYZ]

Спасибо. Что такое порядок элемента $g$ в полугруппе $G$?

[bot]

В группе порядок элемента $g$ - это порядок циклической подгруппы, порождённой этим элементом. Умножение на $g$ элементов этой полугруппы представляет собой цикл. Однопорождённая полугруппа, хотя и называется циклической, но больше похожа на "петлическую". Судя по первой задаче порядок элемента - это число элементов циклической части петли. Иначе говоря, порядок элемента $g$ в полугруппе - это порядок наибольшей подгруппы в циклической подполугруппе, порождённой элементом $g$. Вряд ли это общепринято, но другого в голову не приходит.

mkot в сообщении #222909 писал(а):

Или под словами "группа подстановок" вы не подразумеваете симметрическую группу?

Дык, так и есть, под группой подстановок разумеют не всю симметрическую группу, а любую её подгруппу. В утверждении 2, надо выбросить последние два слова и получится теорема Кэли.

[AndreyXYZ]

Спасибо, разобрался.