В этой лекции мы представим вниманию читателя основные алгебраические структуры, с которыми мы встретимся при изложении курса и при решении задач. Детальное знакомство с ними будет происходить по мере нашего продвижения и накопления фактического материала. Преимущество работы с абстрактными математическими понятиями может быть оценено лишь при необходимости рассматривать многочисленные частные примеры.
Предмет алгебры существенно менялся с течением времени: арифметические действия над натуральными и положительными рациональными числами в глубокой древности (3 век н. э.); алгебраические уравнения первой и второй степени (9 век); появление алгебраической символики (15 - 17 века); к 18-му веку алгебра сложилась в том объеме, который сейчас принято называть "элементарной алгеброй"; в 18-19 веках алгебра - это прежде всего алгебра многочленов; с середины 19-го века центр тяжести алгебраических исследований перемещается на изучение произвольных алгебраических операций. Изучение алгебраических структур (т. е. множеств с определенными на них операциями) было подготовлено развитием числовых систем (построением комплексных чисел и кватернионов), созданием матричного исчисления, возникновением булевой алгебры, внешней алгебры Грассмана, исследованием групп подстановок. Таким образом,к 20-му веку сформировалась точка зрения на современную алгебру как на общую теорию алгебраических операций (под влиянием работ Д. Гильберта, Э. Артина, Э. Нетер и с выходом в 1930 г. монографии Б. Л. ван дер Вардена "Современная алгебра").
Если M - непустое множество, n - натуральное число, то через Mn обозначим множество упорядоченных последовательностей (m1,m2,...,mn), $$m_i\in M$$, $$1\le i\le n$$. Под n -арной алгебраической операцией на множестве M понимается отображение$$\omega : M^n\to M,$$
число $$n$$ называется n=2 ) и унарные операции ( n=1 ). Нульарные операции - это фиксированные элементы множества M, поскольку под M(0) понимается одноэлементное множество.
Непустое множество M с бинарной операцией $$\omega :M\times M\to M$$ называется группоидом. Иногда нам удобнее использовать обозначение$$m_1\mathbin{\omega} m_2=\omega((m_1,m_2)),\quad
m_1,m_2\in M.$$
Бинарная операция $$\omega : M\times M\to M$$ называется ассоциативной, если $$(m_1\mathbin{\omega} m_2)\mathbin{\omega} m_3=
m_1\mathbin{\omega} (m_2 \mathbin{\omega} m_3)
\ \ \text{для всех}\ \ m_1,m_2,m_3\in M$$,
и коммутативной, если $$m_1\mathbin{\omega} m_2=
m_2\mathbin{\omega} m_1
\ \ \text{для всех}\ \
m_1,m_2\in M$$.
Упражнение 1.2.1.
2.1) $${+}: N \times N \to N, \quad (m_1,m_2)\mapsto m_1+m_2$$ (сложение натуральных чисел); $${\cdot}: N \times N \to N,\quad (m_1,m_2)\mapsto m_1m_2$$ (умножение натуральных чисел);
2.2) пусть P(M) - множество всех подмножеств (включая пустое) множества M, $${\cap}: \mathcal P(M)\times\mathcal P(M)\to \mathcal P(M),\quad (A,B)\mapsto A\cap B$$ (пересечение подмножеств); $${\cup}: \mathcal P(M)\times\mathcal P(M)\to \mathcal P(M),\quad (A,B)\mapsto A\cup B$$ (объединение подмножеств); $${*}: \mathcal P(M)\times\mathcal P(M)\to \mathcal P(M),\\
(A,B)\mapsto A*B=(A\setminus B)\cup (B\setminus A)=(A\cup B)\setminus (A\cap B)
$$ (симметрическая разность подмножеств).
M в множество M,$${\circ}: M^M\times M^M\to M^M,\quad (f,g)\mapsto f\circ g,$$
где $$(f\circ g)(m)=f(g(m))$$ для $$m\in M$$ (композиция отображений). Тогда $$\circ$$ - ассоциативная операция (она является коммутативной тогда и только тогда, когда |M|=1, т. е. M - одноэлементное множество), подробнее см. задачу 1.7.1.(N,+) - подгруппоид в группоиде (Z,+) (здесь Z - целые числа);Z\{0} не является замкнутым в группоиде (Z,+) относительно операции сложения.Пусть $$(M_1,\omega_1)$$ и $$(M_2,\omega_2)$$ -
Лемма 1.2.2.
f1 и f2, где $$(M_1,\omega_1) \stackrel{f_1}{\longrightarrow}
(M_2,\omega_2) \stackrel{f_2}{\longrightarrow}
(M_3,\omega_3)$$,
являются f2f1, $$f_2f_1: (M_1,\omega_1)\to (M_3,\omega_3),\quad
(f_2f_1)(m_1)=f_2(f_1(m_1))$$,
также является Доказательство.
z=f(x), w=f(y), где $$x=f^{-1}(z),\allowbreak y=f^{-1}(w)\in M_1$$. Тогда $$f^{-1}(z\mathbin{\omega_2}w)=
f^{-1}(f(x)\mathbin{\omega_2}f(y))=
f^{-1}(f(x\mathbin{\omega_1}y))={}
\\
{}=x\mathbin{\omega_1}y=f^{-1}(z)\mathbin{\omega_1}f^{-1}(w)$$.Следствие 1.2.3. Отношение "быть изоморфными" является отношением эквивалентности на классе
Упражнение 1.2.4.
Упражнение 1.2.5. Следующие элементы являются нейтральными:
0 в $$(N\cup\{0\},+)$$, (Z,+), (Q,+), (R,+) ;1 в $$(N,\cdot)$$, $$(Z,\cdot)$$, $$(Q,\cdot)$$, $$(R,\cdot)$$ ;1M в $$(M^M,\circ)$$ ;M в $$(\mathcal P(M),\cap)$$ ;(N,+) нет нейтральных элементов (в России $$N=\{1,2,...\}$$ ).Лемма 1.2.6. Пусть $$(M,\omega)$$ - e и e' - нейтральные элементы. Тогда e=e' (другими словами, если в группоиде существует нейтральный элемент, то он единственный).
Доказательство. $$e=e\mathbin{\omega}e'=e'$$.
Замечание 1.2.7. В мультипликативных обозначениях операции $$\omega$$ в моноиде, $$m_1\mathbin{\omega}m_2=m_1m_2$$, нейтральный элемент часто называют единицей и используют для него обозначение 1=eM ; в аддитивных обозначениях, $$m_1\mathbin{\omega}m_2=m_1+m_2$$, нейтральный элемент обычно называют нулем и используют для него обозначение 0=0M.
Определение 1.2.8. e
Замечания 1.2.9.
eM.f(eM)=eM'. Ясно, что произведение гомоморфизмов Определение 1.2.10. Пусть $$(M,\cdot,e_M)$$ -
mm'=eM, называется m''m=eM, называется m m mm =eM=m m (в этом случае элемент m называется Лемма 1.2.11. Если в моноиде $$(M,\cdot,e_M)$$ элемент $$m\in M$$ имеет правый обратный m' и левый обратный m'', то m'=m'' и m является обратимым элементом.
Доказательство.
m'=eMm'=(m''m)m'=m''(mm')=m''eM=m''.
Следствие 1.2.12.
m m-1.m моноида $$(M,\cdot,e_M)$$ существует обратный элемент m-1, то (m-1})-1=m.x, y моноида $$(M,\cdot,e_M)$$ обратимы с обратными x-1 и y-1, то (xy)-1=y-1x-1.Действительно (при этом см. теорему 1.3.2), (y-1x-1)(xy)=y-1x-1xy=y-1eMy=y-1y=eM=yy-1=yeMy-1=xyy-1x-1=(xy)(y-1x-1).
Рассмотрим ассоциативную операцию * на множестве M, $$*: M\times M\to M$$, $$(a,b)\mapsto a*b\in M$$ для $$a,b\in M$$, при этом$$(a*b)*c=a*(b*c)\ \forall a,b,c\in M.$$
Для одного или двух сомножителей нет вопроса о различных расстановках скобок: a, a*b. Для трех сомножителей a, b, c существует всего две расстановки скобок (a*b)*c, a*(b*c), обозначающие применение бинарной операции * (каждый раз применяемой к двум элементам). На множестве из четырех элементов a1, a2, a3, a4 расстановок скобок уже значительно больше: ((a1*a2)*a3)*a4 (регулярная слева расстановка), (a1*a2)*(a3*a4), (a1*(a2*a3))*a4, a1*((a2*a3)*a4), a1*(a2*(a3*a4)) (регулярная справа расстановка).
Задача 1.3.1 (трудная).
Найти число всех различных расстановок скобок для применения бинарной операции на n сомножителях.
Определение ассоциативной бинарной операции ( (a*b)*c=a*(b*c) для всех $$a,b,c\in M$$ ) означает, что для трех сомножителей результат применения операции не зависит от расстановки скобок (т. е. порядка ее применения). Наша ближайшая цель - показать, что для ассоциативной бинарной операции это утверждение верно и для n сомножителей a1,a2,...,an (при всех расстановках скобок после соответствующего применения операции * мы получаем один и тот же элемент, который можно обозначить a1*a2*...*an, без указания расстановки скобок).
Теорема 1.3.2.
Пусть * - бинарная ассоциативная операция на множестве M $$(*: M\times M\to M$$, $$(a,b)\mapsto a*b$$ для $$a,b\in M$$, и $$(a*b)*c=a*(b*c)$$ для всех $$a,b,c\in M)$$, $$a_1,a_2,...,a_n\in M$$, $$n \ge 3$$. Тогда результат применения операции * к n сомножителям a1,a2,...,an не зависит от расстановки скобок.
Доказательство проведем индукцией по n по вполне упорядоченному множеству $$\{n\in N\mid n \ge 3\}$$, это означает, что любое непустое подмножество этого множества имеет наименьший элемент.
Начало индукции n=3 обеспечено определением ассоциативной операции.
Допустим, что утверждение верно для всех k, $$3 \le k<n$$. Рассмотрим произвольную расстановку скобок на n сомножителях a1,a2,...,an, соответствующую применениям бинарной операции * (каждый раз к двум элементам). Наша цель - доказать, что результат применения операции * для произвольной расстановки скобок совпадает с результатом применения для регулярной слева расстановки скобок (... ((a1*a2)*a3)*...)*an. При этом для n=2 имеем a1*a2, а для n=1 имеем a1.
В каждой расстановке скобок есть последнее применение операции * (например: $$(a * b)\circledast c$$ ; $$(a_1*a_2)\circledast (a_3*a_4)$$ ; $$((a_1*a_2)*a_3) \circledast (a_4*a_5)$$, здесь $$\circledast$$ обозначает последнее применение операции * в каждой из приведенных расстановок). Таким образом, последнее применение операции * происходит к произведению k сомножителей a1,a2,...,ak с некоторой расстановкой скобок и к произведению (n-k) сомножителей ak+1,...,an с некоторой расстановкой скобок, при этом $$1 \le k<n$$, $$1 \le n-k<n$$. Результат произведения операции * в левом и правом блоке не зависит от расстановки скобок (возможно, k=1 или k=2 ; возможно, n-k=1 или n-k=2 ; если $$3 \le k<n$$, то в силу индуктивного предположения; если $$3 \le n-k<n$$, то также в силу индуктивного предположения). Выберем в левом произведении регулярную слева расстановку скобок, а в правом произведении - регулярную справа расстановку скобок. Тогда имеем, применяя последовательно ассоциативность для трех сомножителей, [(... ((a1*a2)*a3)... ak-1)*ak]*[ak+1*(ak+2*(... (an-1*an)... ))]=[((... ((a1*a2)*a3)... ak-1)*ak)*ak+1]*[ak+2*(... (an-1*an)... )]=...= ((a1*a2)*a3)... an-1)*an
(в наших обозначениях, если k=1, то [a1]=a1 ; аналогично, если n-k=1, то [an]=an ).
Итак, результат применения операции * в соответствии с исходной (произвольной) расстановкой скобок совпал с результатом применения при регулярной слева расстановке скобок. Таким образом, результат применения ассоциативной операции не зависит от расстановки скобок.
Пусть U, V - непустые множества, $$f: U\to V$$ - (однозначное) отображение из множества U в множество V, т. е. каждому элементу $$u\in U$$ сопоставляется элемент $$f(u)\in V$$.
Замечание 1.4.1.
f к элементу $$u\in U$$ через f(u), т. е. f пишем слева от u. Возможно (а иногда и удобнее) было бы использовать обозначение uf.f=f', если для любого $$u\in U$$ имеем f(u)=f'(u).Set, в которой объекты - множества, морфизмы - отображения множеств, является одной из основных категорий в математике.Рассмотрим образ отображения $$f: U\to V$$$$\text{Im} f = \{v\in V\mid v=f(u),\ u\in U\}.$$
Можно рассмотреть также полезное отношение эквивалентности $$\tau_f$$ на множестве U, определяемое отображением $$f: U\to V$$,$$u_1\mathrel{\tau_f} u_2 \iff f(u_1)=f(u_2).$$
Определение 1.5.1.Отображение $$f: U\to V$$ называется:
U при отображении f переходят в разные элементы в V (т. е. $$u_1,u_2\in U,\ u_1\ne u_2 \Rightarrow f(u_1)\ne f(u_2)$$ )V является образом некоторого элемента из U (т. е. $$\forall v\in V\ \exists u\in U,\ v=f(u)$$, другими словами, $$\text{Im} f=V$$ )f инъективно и сюръективно (т. е. $$\forall v\in V\ \exists u\in U,\ v=f(u)$$ )Замечание 1.5.2.
f отображает множество U на множество V ".Задачи 1.5.3.
|U|=m, |V|=n. Доказать, что $$|\{f: U\to V\}|=n^m$$.|U|=m, L(U) - совокупность всех подмножеств множества U (включая пустое подмножество). Доказать, что |L(U)|=2m.Указание.
Для подмножества $$T\subseteq U$$ рассмотреть его характеристическую функцию $$C_T: U\to \{0,1\},\quad C_T(u)=\begin{cases} 1, u\in T,\\ 0, u\notin T. \end{cases} $$
Следствие
$$1+C_n^1+...+C_n^n=2^n$$.
|U|=m, |V|=n.Пример 1.5.4.
f: N -> N, f(n)=n+1, является инъективным, но не является сюръективным.f: N -> N, f(1)=1 и f(n)=n-1 для n>1, является сюръективным, но не является инъективным.1U(u)=u для всех $$u\in U$$, очевидно, является биекцией.Лемма 1.5.5. Пусть U - конечное множество, $$f: U\to U$$. Тогда равносильны условия:
f - инъективное отображение;f - сюръективное отображение.Доказательство.
$$1)\Rightarrow 2)$$ Пусть $$|U|=n<\infty$$. Так как $$f$$ - инъективное отображение, то $$|\text{Im} f|=n$$. Поскольку $$\text{Im} f\subseteq U$$, $$|\text{Im} f|=n=|U|$$, то $$\text{Im} f=U$$, т. е. f - сюръективное отображение.
$$2)\Rightarrow 1)$$ Допустим противное, т. е. что $$f$$ не является инъективным отображением. Тогда $$f(u_1)=f(u_2)$$ для некоторых $$u_1,u_2\in U$$, $$u_1\ne u_2$$. Следовательно, |Im f|<n=|U|, поэтому Im f<U, т. е. отображение f не является сюръективным, что приводит к противоречию.
Замечание 1.5.6.
Условие конечности множества U в лемме 1.5.5 существенно, как показывает пример 1.5.4. Более того, это соображение может быть использовано для характеризации конечных множеств в терминах отображений.
Определение 1.6.1.
Для диаграммы отображений$$U\xrightarrow{f} V \xrightarrow{g} W$$ определим произведение (иногда называемое композицией или суперпозицией) $$h=gf$$ отображений $$f$$ и $$g$$ следующим образом:$$h=gf: U\to W,\quad h(u)=g(f(u))$$ для $$u\in U$$.
Замечание 1.6.2.
Не любые два отображения можно перемножить!
Примеры 1.6.3.
U, $$1_V: V\to V$$ - тождественное отображение множества V, $$f: U\to V$$, то f1U=f=1Vf.f(k)=k+1 для $$1 \le k<n$$, f(n)=1, то fn=1U, где U={1,2,...,n}.Теорема 1.6.4 (об ассоциативности произведения отображений).
Для диаграммы отображений $$U\xrightarrow{f} V \xrightarrow{g} W \xrightarrow{h} Z$$ имеем h(gf)=(hg)f.
Доказательство. Ясно, что$$h(gf): U\to Z,\quad (hg)f: U\to Z.$$
Для любого $$u\in U$$ имеем (h(gf))(u)=h((gf)(u))=h(g(f(u))),
((hg)f)(u)=(hg)(f(u))=h(g(f(u))),
таким образом, (h(gf))(u)=((hg)f)(u) для всех $$u\in U$$, следовательно, h(gf)=(hg)f.
Пусть U - множество, $$T(U)=\{f: U\to U\}$$ - совокупность всевозможных отображений с операцией произведения отображений. В силу доказанной теоремы 1.6.4 эта операция ассоциативна. Нейтральным элементом относительно этой операции является тождественное отображение 1U. Итак, T(U) -
Задача 1.7.1.
T(U) множества U коммутативен тогда и только тогда, когда |U|=1 (т. е. множество U состоит из одного элемента).
Указание
Если $$a\in U$$, то рассмотрим отображение $$f_a: U\to U$$, fa(u)=a для всех $$u\in U$$. Если $$a\ne b$$, то $$f_af_b=f_a\ne f_b=f_bf_a$$.
Теорема 1.8.1.
Пусть $$f: U\to V$$ - отображение непустых множеств. Тогда:
f - инъективное отображение тогда и только тогда, когда существует отображение $$g: V\to U$$ такое, что gf=1U (т. е. существует левый обратный элемент для отображения f ),f - сюръективное отображение тогда и только тогда, когда существует отображение $$g: V\to U$$ такое, что fg=1V (т. е. существует правый обратный элемент для отображения f ),f - биективное отображение тогда и только тогда, когда существует отображение $$g: V\to U$$ такое, что gf=1U и fg=1V (т. е. существует левый и правый обратные для отображения f ).Доказательство.
1а) Пусть $$f: U\to V$$ - инъективное отображение. Построим отображение $$g: V\to U$$ следующим образом. Если $$v\in \text{Im} f\subseteq V$$ и v=f(u), $$u\in U$$, то этот элемент u определен единственным образом (в силу инъективности отображения f ). В этом случае положим g(v)=u.
Для всех элементов $$v\in V\setminus \text{Im} f$$ положим $$g(v)=u_0\in U$$, где u0 - некоторый фиксированный элемент в U. Тогда для всякого элемента $$u\in U$$ имеем (gf)(u)=g(f(u))=u=1U(u),
т. е. gf=1U.
1б) Если существует отображение $$g: V\to U$$ такое, что gf=1U, и f(u1)=f(u2) для $$u_1,u_2\in U$$, то u1=1U(u1)=(gf)(u1)=g(f(u1))=g(f(u2))=(gf)(u2)=1U(u2)=u2.
Итак, f - инъективное отображение.
2а) Пусть $$f: U\to V$$ - сюръективное отображение. Для каждого элемента $$v\in V$$ множество $$\{u\in U\mid f(u)=v\}$$ не является пустым. Выберем в нем один элемент uv (для интересующихся аксиоматикой теории множеств: это можно сделать в силу аксиомы выбора). Определим отображение $$g: V\to U$$, полагая g(v)=uv. Тогда (fg)(v)=f(g(v))=f(uv)=v=1V(v).
Таким образом, fg=1V.
2б) Если fg=1V для некоторого отображения $$g: V\to U$$, то для всякого $$v\in V$$ имеем v=1V(v)=(fg)(v)=f(g(v)),
т. е. v=f(u) для u=g(v), следовательно, $$f: U\to V$$ - сюръективное отображение.
3а) Если $$f: U\to V$$ - биекция, то для всякого элемента $$v\in V$$ существует, и единственный, элемент $$u\in U$$ такой, что v=f(u). В этом случае положим g(v)=u. Получим отображение $$g: V\to U$$, для которого: (gf)(u)=g(f(u))=u
для всякого $$u\in U$$, т. е. gf=1U ; (fg)(v)=f(g(v))=f(g(f(u)))=f(u)=v
для всякого $$v\in V$$, т. е. fg=1V.
Замечание 1.8.2. Можно было воспользоваться уже доказанными утверждениями 1а), 2а): из инъективности отображения $$f: U\to V$$ следует существование отображения $$g: V\to U$$, для которого gf=1U ; из сюръективности отображения $$f: U\to V$$ следует существование отображения $$g': V\to U$$, для которого fg'=1V ; но тогда g'=1Ug'=(gf)g'=g(fg')=g1V=g; таким образом, gf=1U, fg=1V.
3б) Если существует отображение $$g: V\to U$$, для которого gf=1U и fg=1V, то в силу 1б), f - f - сюръекция, т. е. f - биекция.
Замечание 1.8.3. Отображение g, для которого gf=1U, fg =1V, как мы показали, определено однозначно. Оно будет обозначаться $$g=f^{-1}$$.
Лемма 1.8.4. Пусть $$U\xrightarrow{f} V \xrightarrow{g} W$$.
f, g - gf - f, g - сюръекции, то gf - сюръекция.f, g - биекции, то gf - биекция.f - биекция, то отображение $$g=f^{-1}$$ - биекция.Доказательство.
gf - w=g(v) для некоторого $$v\in V$$ ; далее, v=f(u) для некоторого $$u\in U$$ ; поэтому w=g(f(u))=(gf)(u), т. е. отображение gf является сюръекцией.gf=1U, fg=1V, то $$f=g^{-1}$$, и поэтому $$g=f^{-1}$$ является биекцией.В этой лекции мы представим вниманию читателя основные алгебраические структуры, с которыми мы встретимся при изложении курса и при решении задач. Детальное знакомство с ними будет происходить по мере нашего продвижения и накопления фактического материала. Преимущество работы с абстрактными математическими понятиями может быть оценено лишь при необходимости рассматривать многочисленные частные примеры.
Предмет алгебры существенно менялся с течением времени: арифметические действия над натуральными и положительными рациональными числами в глубокой древности (3 век н. э.); алгебраические уравнения первой и второй степени (9 век); появление алгебраической символики (15 - 17 века); к 18-му веку алгебра сложилась в том объеме, который сейчас принято называть "элементарной алгеброй"; в 18-19 веках алгебра - это прежде всего алгебра многочленов; с середины 19-го века центр тяжести алгебраических исследований перемещается на изучение произвольных алгебраических операций. Изучение алгебраических структур (т. е. множеств с определенными на них операциями) было подготовлено развитием числовых систем (построением комплексных чисел и кватернионов), созданием матричного исчисления, возникновением булевой алгебры, внешней алгебры Грассмана, исследованием групп подстановок. Таким образом,к 20-му веку сформировалась точка зрения на современную алгебру как на общую теорию алгебраических операций (под влиянием работ Д. Гильберта, Э. Артина, Э. Нетер и с выходом в 1930 г. монографии Б. Л. ван дер Вардена "Современная алгебра").
Если M - непустое множество, n - натуральное число, то через Mn обозначим множество упорядоченных последовательностей (m1,m2,...,mn), $$m_i\in M$$, $$1\le i\le n$$. Под n -арной алгебраической операцией на множестве M понимается отображение$$\omega : M^n\to M,$$
число $$n$$ называется n=2 ) и унарные операции ( n=1 ). Нульарные операции - это фиксированные элементы множества M, поскольку под M(0) понимается одноэлементное множество.
Непустое множество M с бинарной операцией $$\omega :M\times M\to M$$ называется группоидом. Иногда нам удобнее использовать обозначение$$m_1\mathbin{\omega} m_2=\omega((m_1,m_2)),\quad
m_1,m_2\in M.$$
Бинарная операция $$\omega : M\times M\to M$$ называется ассоциативной, если $$(m_1\mathbin{\omega} m_2)\mathbin{\omega} m_3=
m_1\mathbin{\omega} (m_2 \mathbin{\omega} m_3)
\ \ \text{для всех}\ \ m_1,m_2,m_3\in M$$,
и коммутативной, если $$m_1\mathbin{\omega} m_2=
m_2\mathbin{\omega} m_1
\ \ \text{для всех}\ \
m_1,m_2\in M$$.
Упражнение 1.2.1.
2.1) $${+}: N \times N \to N, \quad (m_1,m_2)\mapsto m_1+m_2$$ (сложение натуральных чисел); $${\cdot}: N \times N \to N,\quad (m_1,m_2)\mapsto m_1m_2$$ (умножение натуральных чисел);
2.2) пусть P(M) - множество всех подмножеств (включая пустое) множества M, $${\cap}: \mathcal P(M)\times\mathcal P(M)\to \mathcal P(M),\quad (A,B)\mapsto A\cap B$$ (пересечение подмножеств); $${\cup}: \mathcal P(M)\times\mathcal P(M)\to \mathcal P(M),\quad (A,B)\mapsto A\cup B$$ (объединение подмножеств); $${*}: \mathcal P(M)\times\mathcal P(M)\to \mathcal P(M),\\
(A,B)\mapsto A*B=(A\setminus B)\cup (B\setminus A)=(A\cup B)\setminus (A\cap B)
$$ (симметрическая разность подмножеств).
M в множество M,$${\circ}: M^M\times M^M\to M^M,\quad (f,g)\mapsto f\circ g,$$
где $$(f\circ g)(m)=f(g(m))$$ для $$m\in M$$ (композиция отображений). Тогда $$\circ$$ - ассоциативная операция (она является коммутативной тогда и только тогда, когда |M|=1, т. е. M - одноэлементное множество), подробнее см. задачу 1.7.1.(N,+) - подгруппоид в группоиде (Z,+) (здесь Z - целые числа);Z\{0} не является замкнутым в группоиде (Z,+) относительно операции сложения.Пусть $$(M_1,\omega_1)$$ и $$(M_2,\omega_2)$$ -
Лемма 1.2.2.
f1 и f2, где $$(M_1,\omega_1) \stackrel{f_1}{\longrightarrow}
(M_2,\omega_2) \stackrel{f_2}{\longrightarrow}
(M_3,\omega_3)$$,
являются f2f1, $$f_2f_1: (M_1,\omega_1)\to (M_3,\omega_3),\quad
(f_2f_1)(m_1)=f_2(f_1(m_1))$$,
также является Доказательство.
z=f(x), w=f(y), где $$x=f^{-1}(z),\allowbreak y=f^{-1}(w)\in M_1$$. Тогда $$f^{-1}(z\mathbin{\omega_2}w)=
f^{-1}(f(x)\mathbin{\omega_2}f(y))=
f^{-1}(f(x\mathbin{\omega_1}y))={}
\\
{}=x\mathbin{\omega_1}y=f^{-1}(z)\mathbin{\omega_1}f^{-1}(w)$$.Следствие 1.2.3. Отношение "быть изоморфными" является отношением эквивалентности на классе
Упражнение 1.2.4.
Упражнение 1.2.5. Следующие элементы являются нейтральными:
0 в $$(N\cup\{0\},+)$$, (Z,+), (Q,+), (R,+) ;1 в $$(N,\cdot)$$, $$(Z,\cdot)$$, $$(Q,\cdot)$$, $$(R,\cdot)$$ ;1M в $$(M^M,\circ)$$ ;M в $$(\mathcal P(M),\cap)$$ ;(N,+) нет нейтральных элементов (в России $$N=\{1,2,...\}$$ ).Лемма 1.2.6. Пусть $$(M,\omega)$$ - e и e' - нейтральные элементы. Тогда e=e' (другими словами, если в группоиде существует нейтральный элемент, то он единственный).
Доказательство. $$e=e\mathbin{\omega}e'=e'$$.
Замечание 1.2.7. В мультипликативных обозначениях операции $$\omega$$ в моноиде, $$m_1\mathbin{\omega}m_2=m_1m_2$$, нейтральный элемент часто называют единицей и используют для него обозначение 1=eM ; в аддитивных обозначениях, $$m_1\mathbin{\omega}m_2=m_1+m_2$$, нейтральный элемент обычно называют нулем и используют для него обозначение 0=0M.
Определение 1.2.8. e
Замечания 1.2.9.
eM.f(eM)=eM'. Ясно, что произведение гомоморфизмов Определение 1.2.10. Пусть $$(M,\cdot,e_M)$$ -
mm'=eM, называется m''m=eM, называется m m mm =eM=m m (в этом случае элемент m называется Лемма 1.2.11. Если в моноиде $$(M,\cdot,e_M)$$ элемент $$m\in M$$ имеет правый обратный m' и левый обратный m'', то m'=m'' и m является обратимым элементом.
Доказательство.
m'=eMm'=(m''m)m'=m''(mm')=m''eM=m''.
Следствие 1.2.12.
m m-1.m моноида $$(M,\cdot,e_M)$$ существует обратный элемент m-1, то (m-1})-1=m.x, y моноида $$(M,\cdot,e_M)$$ обратимы с обратными x-1 и y-1, то (xy)-1=y-1x-1.Действительно (при этом см. теорему 1.3.2), (y-1x-1)(xy)=y-1x-1xy=y-1eMy=y-1y=eM=yy-1=yeMy-1=xyy-1x-1=(xy)(y-1x-1).
Рассмотрим ассоциативную операцию * на множестве M, $$*: M\times M\to M$$, $$(a,b)\mapsto a*b\in M$$ для $$a,b\in M$$, при этом$$(a*b)*c=a*(b*c)\ \forall a,b,c\in M.$$
Для одного или двух сомножителей нет вопроса о различных расстановках скобок: a, a*b. Для трех сомножителей a, b, c существует всего две расстановки скобок (a*b)*c, a*(b*c), обозначающие применение бинарной операции * (каждый раз применяемой к двум элементам). На множестве из четырех элементов a1, a2, a3, a4 расстановок скобок уже значительно больше: ((a1*a2)*a3)*a4 (регулярная слева расстановка), (a1*a2)*(a3*a4), (a1*(a2*a3))*a4, a1*((a2*a3)*a4), a1*(a2*(a3*a4)) (регулярная справа расстановка).
Задача 1.3.1 (трудная).
Найти число всех различных расстановок скобок для применения бинарной операции на n сомножителях.
Определение ассоциативной бинарной операции ( (a*b)*c=a*(b*c) для всех $$a,b,c\in M$$ ) означает, что для трех сомножителей результат применения операции не зависит от расстановки скобок (т. е. порядка ее применения). Наша ближайшая цель - показать, что для ассоциативной бинарной операции это утверждение верно и для n сомножителей a1,a2,...,an (при всех расстановках скобок после соответствующего применения операции * мы получаем один и тот же элемент, который можно обозначить a1*a2*...*an, без указания расстановки скобок).
Теорема 1.3.2.
Пусть * - бинарная ассоциативная операция на множестве M $$(*: M\times M\to M$$, $$(a,b)\mapsto a*b$$ для $$a,b\in M$$, и $$(a*b)*c=a*(b*c)$$ для всех $$a,b,c\in M)$$, $$a_1,a_2,...,a_n\in M$$, $$n \ge 3$$. Тогда результат применения операции * к n сомножителям a1,a2,...,an не зависит от расстановки скобок.
Доказательство проведем индукцией по n по вполне упорядоченному множеству $$\{n\in N\mid n \ge 3\}$$, это означает, что любое непустое подмножество этого множества имеет наименьший элемент.
Начало индукции n=3 обеспечено определением ассоциативной операции.
Допустим, что утверждение верно для всех k, $$3 \le k<n$$. Рассмотрим произвольную расстановку скобок на n сомножителях a1,a2,...,an, соответствующую применениям бинарной операции * (каждый раз к двум элементам). Наша цель - доказать, что результат применения операции * для произвольной расстановки скобок совпадает с результатом применения для регулярной слева расстановки скобок (... ((a1*a2)*a3)*...)*an. При этом для n=2 имеем a1*a2, а для n=1 имеем a1.
В каждой расстановке скобок есть последнее применение операции * (например: $$(a * b)\circledast c$$ ; $$(a_1*a_2)\circledast (a_3*a_4)$$ ; $$((a_1*a_2)*a_3) \circledast (a_4*a_5)$$, здесь $$\circledast$$ обозначает последнее применение операции * в каждой из приведенных расстановок). Таким образом, последнее применение операции * происходит к произведению k сомножителей a1,a2,...,ak с некоторой расстановкой скобок и к произведению (n-k) сомножителей ak+1,...,an с некоторой расстановкой скобок, при этом $$1 \le k<n$$, $$1 \le n-k<n$$. Результат произведения операции * в левом и правом блоке не зависит от расстановки скобок (возможно, k=1 или k=2 ; возможно, n-k=1 или n-k=2 ; если $$3 \le k<n$$, то в силу индуктивного предположения; если $$3 \le n-k<n$$, то также в силу индуктивного предположения). Выберем в левом произведении регулярную слева расстановку скобок, а в правом произведении - регулярную справа расстановку скобок. Тогда имеем, применяя последовательно ассоциативность для трех сомножителей, [(... ((a1*a2)*a3)... ak-1)*ak]*[ak+1*(ak+2*(... (an-1*an)... ))]=[((... ((a1*a2)*a3)... ak-1)*ak)*ak+1]*[ak+2*(... (an-1*an)... )]=...= ((a1*a2)*a3)... an-1)*an
(в наших обозначениях, если k=1, то [a1]=a1 ; аналогично, если n-k=1, то [an]=an ).
Итак, результат применения операции * в соответствии с исходной (произвольной) расстановкой скобок совпал с результатом применения при регулярной слева расстановке скобок. Таким образом, результат применения ассоциативной операции не зависит от расстановки скобок.
Пусть U, V - непустые множества, $$f: U\to V$$ - (однозначное) отображение из множества U в множество V, т. е. каждому элементу $$u\in U$$ сопоставляется элемент $$f(u)\in V$$.
Замечание 1.4.1.
f к элементу $$u\in U$$ через f(u), т. е. f пишем слева от u. Возможно (а иногда и удобнее) было бы использовать обозначение uf.f=f', если для любого $$u\in U$$ имеем f(u)=f'(u).Set, в которой объекты - множества, морфизмы - отображения множеств, является одной из основных категорий в математике.Рассмотрим образ отображения $$f: U\to V$$$$\text{Im} f = \{v\in V\mid v=f(u),\ u\in U\}.$$
Можно рассмотреть также полезное отношение эквивалентности $$\tau_f$$ на множестве U, определяемое отображением $$f: U\to V$$,$$u_1\mathrel{\tau_f} u_2 \iff f(u_1)=f(u_2).$$
Определение 1.5.1.Отображение $$f: U\to V$$ называется:
U при отображении f переходят в разные элементы в V (т. е. $$u_1,u_2\in U,\ u_1\ne u_2 \Rightarrow f(u_1)\ne f(u_2)$$ )V является образом некоторого элемента из U (т. е. $$\forall v\in V\ \exists u\in U,\ v=f(u)$$, другими словами, $$\text{Im} f=V$$ )f инъективно и сюръективно (т. е. $$\forall v\in V\ \exists u\in U,\ v=f(u)$$ )Замечание 1.5.2.
f отображает множество U на множество V ".Задачи 1.5.3.
|U|=m, |V|=n. Доказать, что $$|\{f: U\to V\}|=n^m$$.|U|=m, L(U) - совокупность всех подмножеств множества U (включая пустое подмножество). Доказать, что |L(U)|=2m.Указание.
Для подмножества $$T\subseteq U$$ рассмотреть его характеристическую функцию $$C_T: U\to \{0,1\},\quad C_T(u)=\begin{cases} 1, u\in T,\\ 0, u\notin T. \end{cases} $$
Следствие
$$1+C_n^1+...+C_n^n=2^n$$.
|U|=m, |V|=n.Пример 1.5.4.
f: N -> N, f(n)=n+1, является инъективным, но не является сюръективным.f: N -> N, f(1)=1 и f(n)=n-1 для n>1, является сюръективным, но не является инъективным.1U(u)=u для всех $$u\in U$$, очевидно, является биекцией.Лемма 1.5.5. Пусть U - конечное множество, $$f: U\to U$$. Тогда равносильны условия:
f - инъективное отображение;f - сюръективное отображение.Доказательство.
$$1)\Rightarrow 2)$$ Пусть $$|U|=n<\infty$$. Так как $$f$$ - инъективное отображение, то $$|\text{Im} f|=n$$. Поскольку $$\text{Im} f\subseteq U$$, $$|\text{Im} f|=n=|U|$$, то $$\text{Im} f=U$$, т. е. f - сюръективное отображение.
$$2)\Rightarrow 1)$$ Допустим противное, т. е. что $$f$$ не является инъективным отображением. Тогда $$f(u_1)=f(u_2)$$ для некоторых $$u_1,u_2\in U$$, $$u_1\ne u_2$$. Следовательно, |Im f|<n=|U|, поэтому Im f<U, т. е. отображение f не является сюръективным, что приводит к противоречию.
Замечание 1.5.6.
Условие конечности множества U в лемме 1.5.5 существенно, как показывает пример 1.5.4. Более того, это соображение может быть использовано для характеризации конечных множеств в терминах отображений.
Определение 1.6.1.
Для диаграммы отображений$$U\xrightarrow{f} V \xrightarrow{g} W$$ определим произведение (иногда называемое композицией или суперпозицией) $$h=gf$$ отображений $$f$$ и $$g$$ следующим образом:$$h=gf: U\to W,\quad h(u)=g(f(u))$$ для $$u\in U$$.
Замечание 1.6.2.
Не любые два отображения можно перемножить!
Примеры 1.6.3.
U, $$1_V: V\to V$$ - тождественное отображение множества V, $$f: U\to V$$, то f1U=f=1Vf.f(k)=k+1 для $$1 \le k<n$$, f(n)=1, то fn=1U, где U={1,2,...,n}.Теорема 1.6.4 (об ассоциативности произведения отображений).
Для диаграммы отображений $$U\xrightarrow{f} V \xrightarrow{g} W \xrightarrow{h} Z$$ имеем h(gf)=(hg)f.
Доказательство. Ясно, что$$h(gf): U\to Z,\quad (hg)f: U\to Z.$$
Для любого $$u\in U$$ имеем (h(gf))(u)=h((gf)(u))=h(g(f(u))),
((hg)f)(u)=(hg)(f(u))=h(g(f(u))),
таким образом, (h(gf))(u)=((hg)f)(u) для всех $$u\in U$$, следовательно, h(gf)=(hg)f.
Пусть U - множество, $$T(U)=\{f: U\to U\}$$ - совокупность всевозможных отображений с операцией произведения отображений. В силу доказанной теоремы 1.6.4 эта операция ассоциативна. Нейтральным элементом относительно этой операции является тождественное отображение 1U. Итак, T(U) -
Задача 1.7.1.
T(U) множества U коммутативен тогда и только тогда, когда |U|=1 (т. е. множество U состоит из одного элемента).
Указание
Если $$a\in U$$, то рассмотрим отображение $$f_a: U\to U$$, fa(u)=a для всех $$u\in U$$. Если $$a\ne b$$, то $$f_af_b=f_a\ne f_b=f_bf_a$$.
Теорема 1.8.1.
Пусть $$f: U\to V$$ - отображение непустых множеств. Тогда:
f - инъективное отображение тогда и только тогда, когда существует отображение $$g: V\to U$$ такое, что gf=1U (т. е. существует левый обратный элемент для отображения f ),f - сюръективное отображение тогда и только тогда, когда существует отображение $$g: V\to U$$ такое, что fg=1V (т. е. существует правый обратный элемент для отображения f ),f - биективное отображение тогда и только тогда, когда существует отображение $$g: V\to U$$ такое, что gf=1U и fg=1V (т. е. существует левый и правый обратные для отображения f ).Доказательство.
1а) Пусть $$f: U\to V$$ - инъективное отображение. Построим отображение $$g: V\to U$$ следующим образом. Если $$v\in \text{Im} f\subseteq V$$ и v=f(u), $$u\in U$$, то этот элемент u определен единственным образом (в силу инъективности отображения f ). В этом случае положим g(v)=u.
Для всех элементов $$v\in V\setminus \text{Im} f$$ положим $$g(v)=u_0\in U$$, где u0 - некоторый фиксированный элемент в U. Тогда для всякого элемента $$u\in U$$ имеем (gf)(u)=g(f(u))=u=1U(u),
т. е. gf=1U.
1б) Если существует отображение $$g: V\to U$$ такое, что gf=1U, и f(u1)=f(u2) для $$u_1,u_2\in U$$, то u1=1U(u1)=(gf)(u1)=g(f(u1))=g(f(u2))=(gf)(u2)=1U(u2)=u2.
Итак, f - инъективное отображение.
2а) Пусть $$f: U\to V$$ - сюръективное отображение. Для каждого элемента $$v\in V$$ множество $$\{u\in U\mid f(u)=v\}$$ не является пустым. Выберем в нем один элемент uv (для интересующихся аксиоматикой теории множеств: это можно сделать в силу аксиомы выбора). Определим отображение $$g: V\to U$$, полагая g(v)=uv. Тогда (fg)(v)=f(g(v))=f(uv)=v=1V(v).
Таким образом, fg=1V.
2б) Если fg=1V для некоторого отображения $$g: V\to U$$, то для всякого $$v\in V$$ имеем v=1V(v)=(fg)(v)=f(g(v)),
т. е. v=f(u) для u=g(v), следовательно, $$f: U\to V$$ - сюръективное отображение.
3а) Если $$f: U\to V$$ - биекция, то для всякого элемента $$v\in V$$ существует, и единственный, элемент $$u\in U$$ такой, что v=f(u). В этом случае положим g(v)=u. Получим отображение $$g: V\to U$$, для которого: (gf)(u)=g(f(u))=u
для всякого $$u\in U$$, т. е. gf=1U ; (fg)(v)=f(g(v))=f(g(f(u)))=f(u)=v
для всякого $$v\in V$$, т. е. fg=1V.
Замечание 1.8.2. Можно было воспользоваться уже доказанными утверждениями 1а), 2а): из инъективности отображения $$f: U\to V$$ следует существование отображения $$g: V\to U$$, для которого gf=1U ; из сюръективности отображения $$f: U\to V$$ следует существование отображения $$g': V\to U$$, для которого fg'=1V ; но тогда g'=1Ug'=(gf)g'=g(fg')=g1V=g; таким образом, gf=1U, fg=1V.
3б) Если существует отображение $$g: V\to U$$, для которого gf=1U и fg=1V, то в силу 1б), f - f - сюръекция, т. е. f - биекция.
Замечание 1.8.3. Отображение g, для которого gf=1U, fg =1V, как мы показали, определено однозначно. Оно будет обозначаться $$g=f^{-1}$$.
Лемма 1.8.4. Пусть $$U\xrightarrow{f} V \xrightarrow{g} W$$.
f, g - gf - f, g - сюръекции, то gf - сюръекция.f, g - биекции, то gf - биекция.f - биекция, то отображение $$g=f^{-1}$$ - биекция.Доказательство.
gf - w=g(v) для некоторого $$v\in V$$ ; далее, v=f(u) для некоторого $$u\in U$$ ; поэтому w=g(f(u))=(gf)(u), т. е. отображение gf является сюръекцией.gf=1U, fg=1V, то $$f=g^{-1}$$, и поэтому $$g=f^{-1}$$ является биекцией.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.