2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вопросы по дискретной математике
Сообщение16.06.2009, 22:24 
Аватара пользователя
Верны ли следующие утверждения? Почему?
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^*?$

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

 
 
 
 Re: Вопросы по дискретной математике
Сообщение17.06.2009, 13:04 
Аватара пользователя
ИСН в сообщении #222675 писал(а):
Много непонятных букв, поэтому начну с конца. Это может означать
группу целых чисел по умножению mod m, а фи - функция Эйлера (нет, не
число делителей, а как бы даже наоборот).

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

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

 
 
 
 Re: Вопросы по дискретной математике
Сообщение17.06.2009, 13:20 
Аватара пользователя
$\mathbb{Z}_6^*$? Извольте:
1*1 = 1
1*5 = 5
5*5 = 1
Это всё.

 
 
 
 Re: Вопросы по дискретной математике
Сообщение17.06.2009, 13:21 
Аватара пользователя
AndreyXYZ в сообщении #222764 писал(а):
Распише, пожалуйста, $\mathbb{Z}_6^*.$

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

 
 
 
 Re: Вопросы по дискретной математике
Сообщение17.06.2009, 15:18 
Аватара пользователя
С этим понятно, но остальные вопросы остаются нерешенными.

 
 
 
 Re: Вопросы по дискретной математике
Сообщение17.06.2009, 20:32 
AndreyXYZ в сообщении #222665 писал(а):
Верны ли следующие утверждения? Почему?
2) Любая конечная группа изоморфна группе подстановок с двумя образующими.
3) Почти все подгруппы $G\le S_n$ при $n \to \infty$ порождаются двумя образующими.
Мне кажется, что третье утверждение противоречит второму.
Не вижу, чем третье противоречит второму. А вот то, что второе не является верным, по-моему, очевидно.

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

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

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

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

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

 
 
 
 Re: Вопросы по дискретной математике
Сообщение17.06.2009, 23:41 
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.

 
 
 
 Re: Вопросы по дискретной математике
Сообщение18.06.2009, 16:33 
Аватара пользователя
Спасибо. Что такое порядок элемента $g$ в полугруппе $G$?

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

mkot в сообщении #222909 писал(а):
Или под словами "группа подстановок" вы не подразумеваете симметрическую группу?

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

 
 
 
 Re: Вопросы по дискретной математике
Сообщение19.06.2009, 18:30 
Аватара пользователя
Спасибо, разобрался.

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group