1: Бінарні операції

Найосновнішим визначенням у цьому курсі є наступне:

Визначення 1.1: Двійкова операція

Двійкова операція$*$ на множині$S$ - це функція$S \times S$ from to$S$. Якщо$(a,b) \in S \times S$ тоді ми пишемо,$a * b$ щоб вказати зображення елемента$(a,b)$ під функцією$*$.

Наступна лема більш детально пояснює, що саме означає це визначення.

Лема 1.1 Двійкова операція$*$ на$S$ множині є правилом для об'єднання двох елементів$S$ для отримання третього елемента$S$. Це правило має задовольняти наступним умовам:

(а)

$a \in S \mbox{ and } b \in S \Longrightarrow a*b \in S$.

[S закрито під$*$.]

(б)

Для всіх$a,b,c,d$ в$S$
$a=c \mbox{ and } b=d \Longrightarrow a*b=c*d.$

[Заміна допустима.]

(c)

Для всіх$a,b,c, d$ в$S$
$a=b \Longrightarrow a*c=b*c$.

(г)

Для всіх$a,b,c, d$ в$S$
$c=d\Longrightarrow a*c=a*d$.

Proof Нагадаємо, що функція$f$ від множини$A$ до множини$B$ - це правило, яке присвоює кожному елементу$x \in A$ елемент, зазвичай позначається$f(x)$, у множині$B$. Більш того, це правило повинно задовольняти $$\begin{align} \label{eqn1.1} x=y \Longrightarrow f(x) = f(y) \end{align}$$ умові З іншого боку, декартовий твір$S \times S$ складається з безлічі всіх впорядкованих пар$(a,b)$ де$a, b \in S$. Рівність впорядкованих пар визначається правилом $$\begin{align} \label{eqn1.2} a = c \mbox{ and } b = d \Longleftrightarrow (a,b) = (c,d). \end{align}$$ Тепер в цьому випадку ми припускаємо, що$*$ це функція від множини$S \times S$ до$S$ множини і замість запису$*(a,b)$ пишемо$a*b$. Тепер, якщо$a, b \in S$ тоді$(a,b)\in S \times S$. Так правило$*$ присвоює$(a,b)$ елементу$a*b \in S$. Це встановлює (а). Тепер імплікація ([eqn1.1]) стає $$\begin{align} \label{eqn1.3} (a,b) = (c,d) \Longrightarrow a*b = c*d. \end{align}$$ від ([eqn1.2]) і ([eqn1.3]) ми отримуємо $$\begin{align} \label{eqn1.4} a = c \mbox{ and } b = d \Longrightarrow a*b = c*d. \end{align}$$ Це встановлює (b).

Щоб довести (c) ми припускаємо, що$a=b$. За рефлексивністю рівності ми маємо для всього$c \in S$ цього$c = c$. Таким чином, ми маємо$a=b$$c=c$ і з частини (б) випливає$a*c=b*c$, що, за бажанням. Доказ (d) аналогічний. $\blacksquare$

Зауваження

У частині (а) порядок$a$ і$b$ має важливе значення. Ми не припускаємо, що$a*b$ це те саме, що$b*a$. Хоча іноді це може бути правдою$a*b = b*a$, що це не є частиною визначення бінарної операції.

Заява (b) говорить$b=d$, що якщо$a=c$ і, ми можемо замінити$a$ і$c$$d$ для$b$ у виразі$a*b$ і отримуємо вираз $c*d$який дорівнює$a*b$. Можна не думати, що таке природне твердження необхідно. Щоб побачити необхідність цього, див. Проблема 1.7 нижче.

Частина (c) вищезгаданої леми говорить про те, що ми можемо помножити обидві сторони рівняння праворуч на один і той же елемент. Частина (d) говорить, що ми можемо помножити обидві сторони рівняння зліва на один і той же елемент.

Двійкові операції зазвичай позначаються символами, такими як $$\nonumber +, \cdot, * , \times, \circ, \star, \bullet, \diamond, \boxdot, \boxtimes, \otimes, \oplus, \odot, \vee, \wedge, \cup, \cap, \cdots$$ Так само, як часто використовується$f$ для загальної функції, ми використовуємо для$*$ позначення загальної бінарної операції. Більш того, якщо$* : S\times S\to S$ задана бінарна операція на множині$S$, ми пишемо$a * b$ замість$*(a,b)$. Це називається інфіксним позначенням. На практиці ми скорочуємо ще більше; так само, як ми використовуємо$ab$ замість$a \cdot b$ або$a \times b$ в середній школі алгебру, ми часто будемо використовувати$ab$ замість$a*b$ загальної бінарної операції.

Позначення. Позначимо натуральні числа, цілі числа, раціональні числа, а дійсні числа символами$\mathbb{N}$$\mathbb{Z}$,$\mathbb{Q}$, і$\mathbb{R}$, відповідно.

Нагадаємо, що $$\begin{aligned} \mathbb{N} &=& \{ 1,2,3, \dots \} \\ \mathbb{Z} &=& \{ \dots, -3, -2, -1, 0, 1, 2, 3, \dots \} \\ \mathbb{Q} &=& \{ \frac n m: n,m \in \mathbb{Z}\mbox{ and } m \ne 0 \}\end{aligned}$$ На даний момент ми припускаємо, що студенти мають базові знання про всі ці системи числення. Пізніше в ході ми наведемо список аксіом, з яких можна вивести всі властивості цих систем числення. Див Додаток C для деяких основних властивостей$\mathbb{N}$ і$\mathbb{Z}$ які нам знадобляться час від часу.

Тепер ми перерахуємо деякі приклади бінарних операцій. Деякі повинні бути вам дуже знайомі. Деякі можуть бути для вас новими.

Приклад 1.1 Звичайне додавання на$\mathbb{N}$$\mathbb{Z}$,$\mathbb{Q}$ і$\mathbb{R}$.

Приклад 1.2 Звичайне множення на$\mathbb{N}$$\mathbb{Z}$,$\mathbb{Q}$ і$\mathbb{R}$.

Приклад 1.3 Звичайне віднімання на$\mathbb{Z}$,$\mathbb{Q}$ і$\mathbb{R}$. Зауважте, що віднімання не є двійковою операцією,$\mathbb{N}$ оскільки, наприклад,$1 - 2 \notin \mathbb{N}$.

Приклад 1.4 Звичайне поділ на$\mathbb{Q}- \{ 0 \}$ і$\mathbb{R}- \{ 0 \}$. Зверніть увагу, що ділення не є двійковою операцією на$\mathbb{N}$ і$\mathbb{Z}$ так як, наприклад,$\frac 1 2 \notin \mathbb{N}$ і$\frac 1 2 \notin \mathbb{Z}$. Також зауважте, що ми повинні видалити 0 з$\mathbb{Q}$ і$\mathbb{R}$ оскільки ділення на 0 не визначено.

Приклад 1.5 Для кожного цілого числа$n \ge 2$ визначте множину $$\nonumber \mathbb{Z}_n = \{ 0, 1, 2, \dots, n-1 \}.$$ For all$a, b \in \mathbb{Z}_n$ let

$a + b =$залишок, коли звичайна сума$a$ і$b$ ділиться на$n$, і

$a \cdot b =$залишок при звичайному добутку$a$ і$b$ ділиться на$n$.

Двійкові операції, визначені в прикладі 1.5, зазвичай називаються додавання по модулю$n$ і множення по модулю$n$. Ціле число$n$$\mathbb{Z}_n$ in називається модулем. Множина модуля - moduli.

У прикладі 1.5 було б точніше використовувати щось на зразок$a +_n b$ і$a \cdot_n b$ для додавання і множення в$\mathbb{Z}_n$, але в інтересах збереження позначення простим ми опускаємо індекс$n$. Звичайно, це означає, що в будь-якій ситуації ми повинні бути дуже чіткими щодо цінності$n$. Відзначимо також, що це дійсно нескінченний клас прикладів:$\mathbb{Z}_2 = \{0,1\}$$\mathbb{Z}_3 = \{0,1,2\}$$\mathbb{Z}_4 = \{0,1,2,3\}$,, і т.д. тільки щоб було зрозуміло, наведемо кілька прикладів додавання і множення:

В$\mathbb{Z}_4$:

$2 + 3 =1$,$2 + 2 = 0$,$0 + 3 = 3$,$2\cdot3= 2$,$2\cdot2=0$ і$1\cdot3=3$.

В$\mathbb{Z}_5$:

$2 + 3 =0$,$2 + 2 = 4$,$0 + 3 = 3$,$2\cdot3=1$,$2\cdot2=4$ і$1\cdot3=3$\

Приклад 1.6 Для кожного цілого числа$n \ge 1$ ми дозволяємо$[n] = \{1,2, \cdots, n \}$.
Перестановка на$[n]$ - це функція від$[n]$ до$[n]$ якої є як один до одного, так і на. Ми визначаємо$S_n$, щоб бути множиною всіх перестановок на$[n]$. Якщо$\sigma$ і$\tau$ є елементами,$S_n$ ми визначаємо їх продукт,$\sigma \tau$ щоб бути складом$\sigma$ і$\tau$, тобто, $$\nonumber \sigma \tau (i) = \sigma(\tau(i)) \quad \mbox{for all }\in \mbox{ n}.$$ Див Додаток B, якщо будь-який з термінів, що використовуються в цей приклад незнайомий.

Знову ж таки, у нас є нескінченна кількість прикладів:$S_1$$S_2$$S_3$$S_4$,,, і т.д. ми обговорюємо цей приклад, а також інші приклади докладніше пізніше. Для початку наведемо ще кілька прикладів:

Приклад 1.7 Давайте$K$ позначимо будь-яку з таких дій:$\mathbb{Z},\mathbb{Q}, \mathbb{R}, \mathbb{Z}_n$. $M_2(K)$Дозволяти множина всіх$2 \times 2$ матриць $$\nonumber \left [ \begin{array} {c c} a & b \\ c & d \end{array} \right]$$ , де$a,b,c,d$ є будь-які елементи$K$. Додавання і множення матриць визначаються наступними правилами:

$$\left [ \nonumber \begin{array} {c c} a & b \\ c & d \end{array} \right] + \left [ \begin{array} {c c} a' & b' \\ c' & d' \end{array} \right] = \left [ \begin{array} {c c} a + a' & b+b' \\ c+c' & d+d' \end{array} \right]$$

$$\nonumber \left [ \begin{array} {c c} a & b \\ c & d \end{array} \right] \cdot \left [ \begin{array} {c c} a' & b' \\ c' & d' \end{array} \right] = \left [ \begin{array} {c c} aa' +bc' & ab'+bd' \\ ca'+dc'& cb'+dd' \end{array} \right]$$

для всіх$a,b,c,d,a',b',c',d' \in K$.

Приклад 1.8 Звичайне додавання векторів в$\mathbb{R}^n$,$n \in \mathbb{N}$. Точніше

$$\nonumber \mathbb{R}^n = \{ (x_1, x_2, \dots, x_n) \ | \ x_i \in \mathbb{R}\mbox{ for all $i$} \}.$$

Додавання визначається правилом: $$\nonumber (x_1, x_2, \dots, x_n) + (y_1, y_2, \dots, y_n) = (x_1 + y_1, x_2 +y_2, \dots, x_n+y_n).$$ де$x_i+y_i$ позначається звичайне складання дійсних чисел$x_i$ і$y_i$.

Приклад 1.9 Додавання по модулю 2 для двійкових послідовностей довжини$n$,$n \in \mathbb{N}$. (Цей приклад важливий для інформатики.) У цьому випадку набір $$\nonumber \mathbb{Z}_2^n = \{ (x_1, x_2, \dots, x_n) \ | \ x_i \in \mathbb{Z}_2 \mbox{ for all $i$} \}.$$ Recall that$\mathbb{Z}_2 = \{0,1\}$. Додавання визначається правилом: $$(x_1, x_2, \dots, x_n) + (y_1, y_2, \dots, y_n) = (x_1 + y_1, x_2 +y_2, \dots, x_n+y_n).$$ де$x_i+y_i$ позначається додавання по модулю 2 (також зване виключним або)$x_i$ і$y_i$. Точніше$0+0=0$$0+1=1$,$1+0=1$ і$1+1=0$.

Приклад 1.10 Перехресний$\mathbf{u} \times \mathbf{v}$ добуток векторів$\mathbf{u}$ і$\mathbf{v}$ в$\mathbb{R}^3$. Нагадаємо, що якщо $$\begin{aligned} \mathbf{u} &=&(u_1,u_2,u_3) \\ \mathbf{v}&=&(v_1,v_2,v_3)\end{aligned}$$ то$\mathbf{u} \times \mathbf{v}$ визначається за формулою, $$\nonumber \mathbf{u} \times \mathbf{v} = \left( \left | \begin{array} {cc} u_2&u_3\\v_2&v_3 \end{array} \right |, -\left | \begin{array} {cc} u_1&u_3\\v_1&v_3 \end{array} \right |, \left | \begin{array} {cc} u_1&u_2\\v_1&v_2 \end{array} \right | \right),$$ де $$\nonumber \left | \begin{array} {cc} a&b\\c&d \end{array} \right | = ad-bc.$$

Приклад 1.11 Операції set$\cup$ і$\cap$ є бінарними операціями над$\mathcal{P}(X)$ множиною всіх підмножин$X$. Нагадаємо, що$\mathcal{P}(X)$ множина називається силовим набором$X$; і, якщо$A$ і$B$ є множинами, то$A \cup B$ називається об'єднанням$A$ і$B$ і$A \cap B$ називається перетином$A$ і$B$.

Визначення 1.2:

Припустимо, що$*$ це двійкова операція на множині$S$.

1. Ми говоримо,$*$ що асоціативно, якщо

   $$x*(y*z) = (x*y)*z \quad \mbox{for all x,y,z }\in\mbox{ S}.$$

2. Ми говоримо, що елемент$e$ в$S$ - це ідентичність щодо$*$ якщо

   $$x*e = x \mbox{ and } e*x = x \quad \mbox{for all $x$ in $S$}.$$

3. $e \in S$Дозволяти бути ідентичністю по відношенню до$*$. Враховуючи,$x \in S$ ми говоримо, що елемент$y \in S$ є зворотним,$x$ якщо обидва $$x*y=e \mbox{ and } y*x=e.$$
4. Ми говоримо, що$*$ є комутативним, якщо $$x*y=y*x \quad \mbox{ for all $x,y \in S.$}$$
5. Ми говоримо, що елемент$a$ ідемпотентний щодо$*$ якщо$S$ $$a*a=a.$$
6. Ми говоримо, що елемент$z$ дорівнює нулю щодо$*$ if$S$ $$z*x=z \mbox{ and } x*z=z \quad \mbox{for all $x \in S$}.$$

Проблема 1.1 Припустимо, що$*$ це двійкова операція на множині$S$. Доведіть наступні твердження.

(i) Якщо$e$ і$e'$ є ідентичностями стосовно$*$$S$ далі$e = e'$. [Підказка: Що таке$e*e'$?]

(ii) Якщо$z$ і$z'$ є нулями по відношенню до$*$ on$S$ then$z = z'$. [Підказка: Що таке$z*z'$?]

Завдання 1.2 Пройдіть всі наведені вище приклади бінарних операцій і визначте, які не є асоціативними. Показати неасоціативність, надавши три конкретні елементи$a,b,c$ такі, що$a*(b*c) \ne (a*b)*c$.

Завдання 1.3 Пройдіть всі наведені вище приклади бінарних операцій і визначте, які не є комутативними. Показати некомутативність, надавши два конкретних елементи$a,b$ такі, що$a*b \ne b*a$.

Зауваження

Набір може мати кілька бінарних операцій над ним. Для прикладу розглянемо безліч$\mathbb{R}$ дійсних чисел. Пишемо$(\mathbb{R}, \cdot)$$(\mathbb{R}, +)$, і$(\mathbb{R}, -)$ вказуємо множину$\mathbb{R}$ з двійковими операціями множення, додавання і віднімання відповідно. Аналогічно, ми використовуємо це позначення для інших множин, таких як$M_2(\mathbb{R})$ множина,$2 \times 2$ матриць над дійсними числами$\mathbb{R}$. Використовуємо$(M_2(\mathbb{R}), \cdot)$ і$(M_2(\mathbb{R}), + )$ для позначення множення матриці і додавання матриць відповідно на$M_2(\mathbb{R})$.

Завдання 1.4 Визначте, який із прикладів$(\mathbb{R}, \cdot)$$(\mathbb{R}, +)$$(M_2(\mathbb{R}), \cdot)$, та$(\mathcal{P}(X), \cup)$ мають тотожності. Якщо є ідентичність, визначте елементи, які не мають зворотних.

Задача 1.5 Визначте, який з прикладів$(\mathbb{R}, \cdot)$$(\mathbb{R}, +)$$(M_2(\mathbb{R}), \cdot)$,, і$(\mathcal{P}(X), \cup)$ мають нулі. Якщо є нуль, визначте, чи є ненульові елементи, твір яких дорівнює нулю.

Завдання 1.6 Визначте$(\mathbb{R}, \cdot)$, який із прикладів$(\mathbb{R}, +)$$(M_2(\mathbb{R}), \cdot)$,, і$(\mathcal{P}(X), \cup)$ мають ідемпотенти. Постарайтеся знайти всі ідемпотенти в кожному конкретному випадку.

Завдання 1.7 Тут ми наведемо приклад правила, яке, здається, визначає бінарну операцію, але не робить, оскільки підміна неприпустима. $a,b,c,d$Дозволяти бути цілими числами з$b \ne 0$ і$d \ne 0$. Потім $$\frac a b \in \mathbb{Q} \ \mbox{ and } \ \frac c d \in \mathbb{Q}.$$ визначте$*$$\mathbb{Q}$ по: $$\frac a b * \frac c d = \frac {a+c}{b^2+d^2}.$$ Показати, що $$\frac a b * \frac c d \in \mathbb{Q},$$ так$\mathbb{Q}$ закрито під$*$. Покажіть на конкретному прикладі, що це правило не допускає заміни.