Ответ

• Если каждому элементу $x \in A$ соответствует не один, а несколько образов $y \in B$, то говорят, что задано соответствие из множества $A$ в множество $B$: $\rho \subseteq A\times B$.

• Область определения соответствия $\rho \subseteq A \times B\colon$

  $$D_\rho = \lbrace x\colon (x, y) \in \rho,\, y \in B \rbrace$$

• Область значений соответствия $\rho \subseteq A \times B\colon$

  $$R_\rho = \lbrace y\colon (x, y) \in \rho,\, x \in A \rbrace$$

• Сечение соответствия $\rho \subseteq A \times B$ по элементу $x \in A\colon$

  $$\rho (x) = \lbrace y\colon (x, y) \in \rho,\, y \in B \rbrace$$

• Сечение соответствия $\rho \subseteq A \times B$ по множеству $C \subseteq D_\rho\colon$

  $$\rho (C) = \lbrace y\colon (x, y) \in \rho,\, x \in C,\, y \in B \rbrace$$

• Соответствие $\rho \subseteq A \times B$ называется функциональным по первой компоненте, если для каждого $y \in R_\rho$ существует единственный элемент $x \in D_\rho$ такой, что $(x, y) \in \rho$.

• Соответствие $\rho \subseteq A \times B$ называется функциональным по второй компоненте, если для каждого $x \in D_\rho$ сечение $\rho (x)$ содержит единственный элемент $y \in B$.

• Соответствие $\rho \subseteq A \times B$, которое всюду определено и функционально по второй компоненте, называется отображением множества $A$ в множество $B$ ($f\colon A \to B$).

• Соответствие $\rho \subseteq A \times B$, которое и только лишь функционально по второй компоненте, но не является всюду определённым, называется частичным отображением множества множества $A$ в множество $B$.

Ответ

• Бинарное отношение на некотором множестве называется
  • порядком, если оно рефлексивное, антисимметричное и транзитивное
  • предпорядком, если оно рефлексивное и транзитивное
• Элемент $a \in A$ упорядоченного множества $\mathbf{A} = (A, \leqslant)$ называется

  • наименьшим элементом данного множества, если $(\forall x \in A)\, (a \leqslant x)$

  • наибольшим элементом данного множества, если $(\forall x \in A)\, (a \geqslant x)$

  • минимальным элементом данного множества, если $(\forall x \in A)\, (a \leqslant x \vee a \updownarrow x)$

  • максимальным элементом данного множества, если $(\forall x \in A)\, (a \geqslant x \vee a \updownarrow x)$

    $\updownarrow$ — несравнимость

• Точной верхней гранью $(\sup B)$ подмножества $B \subseteq A$ называют наименьший элемент множества всех верхних граней.
• Точной нижней гранью $(\inf B)$ подмножества $B \subseteq A$ называют наибольший элемент множества всех нижних граней.
• Пусть дана некоторая последовательность $a_1, a_2, \ldots, a_n, \ldots$ элементов какого-то упорядоченного множества. Тогда её точной верхней (нижней) гранью считается точная верхняя (нижняя) грань области значений этой последовательности как функции натуральной переменной.
  Обозначение: $\sup a_n\, (\inf a_n)$

Ответ

Бинарное отношение на некотором множестве называют ... если оно (рефлексивно/иррефлексивно/симметрично/антисимметрично/транзитивно):

Обязательно написать нужно, что обозначают Р, И, С, А, Т

Ответ

• Бинарное отношение на некотором множестве называют эквивалентностью, если оно рефлексивно, симметрично и транзитивно.
• Класс эквивалентности элемента $x$ по отношению эквивалентности $\rho\colon$

  $$[x]_\rho \leftrightharpoons \lbrace y\colon y \operatorname{\rho} x \rbrace$$

• Множество классов эквивалентности $\lbrace [x]_\rho\colon x \in A \rbrace$ называется фактор-множеством множества $A$ по отношению эквивалентности $\rho \subseteq A^2$ и обозначается $A / \rho$.

Ответ

Запись $x \operatorname{\rho} y$ используется вместо записи $(x, y) \in \rho$.

Отношение $\rho \subseteq A^2$ называется

• рефлексивным, если $(\forall x \in A)\, (x \operatorname{\rho} x)$, то есть $\operatorname{id}_A \subseteq \rho$ (диагональ полностью содержится в отношении)
• иррефлексивным, если $(\forall x \in A)\, \big((x, x) \notin \rho\big)$, то есть $\operatorname{id}_A \cap \rho = \varnothing$ (диагональ полностью исключается из отношения)
• симметричным, если $(\forall x, y \in A)\, (x \operatorname{\rho} y \Rightarrow y \operatorname{\rho} x)$, то есть $\rho^{-1} = \rho$
• антисимметричным, если $(\forall x, y \in A)\, (x \operatorname{\rho} y \operatorname{\&} y \operatorname{\rho} x \Rightarrow x = y)$, то есть $\rho^{-1} \cap \rho \subseteq \operatorname{id}_A$, в частности, $\rho^{-1} \cap \rho \subseteq \varnothing$
• транзитивным, если $(\forall x, y, z \in A)\, (x \operatorname{\rho} y \operatorname{\&} y \operatorname{\rho} z \Rightarrow x \operatorname{\rho} z)$

Ответ (без доказательства)

Упорядоченное множество $\mathbf{A} = (A, \leqslant)$ называется индуктивным упорядоченным, если

1. оно имеет наименьший элемент,
2. любая неубывающая последовательность его элементов имеет точную верхнюю грань.

Ответ (без доказательства)

• Композиция соответствий $\rho \subseteq A \times B$ и $\sigma \subseteq C \times D\colon$

  $$\rho \circ \sigma \leftrightharpoons \Set{(x, y)\colon (\exists z)\, (x, z) \in \rho \operatorname{\&}\, (z, y) \in \sigma} \subseteq A \times D$$

• Если $\rho \subseteq A \times B$, то соответствие

  $$\rho^{-1} \leftrightharpoons \set{(y, x)\colon (x, y) \in \rho} \subseteq B \times A$$

  называется обратным к $\rho$.

Свойства:

1. $\rho \circ (\sigma \circ \tau) = (\rho \circ \sigma) \circ \tau$
2. $\rho \circ (\sigma \cup \tau) = (\rho \circ \sigma) \cup (\rho \circ \tau)$
   $(\sigma \cup \tau) \circ \rho = (\sigma \circ \rho) \cup (\tau \circ \rho )$
3. $(\rho \circ \sigma)^{-1} = \sigma^{-1} \circ \rho^{-1}$
4. Для бинарных отношений $\rho \subseteq A^2\colon \rho \circ \operatorname{id}_A = \operatorname{id}_A \circ \rho = \rho$

Ответ (без доказательства)

Ответ

• n-арной операцией на множестве $A$ называется любое отображение вида $\omega\colon A^n \to A$; n-арная операция $\omega$ любому кортежу $(a_1, \ldots, a_n) \in A^n$ однозначно сопоставляет элемент $\in A$.
• Алгебраическая структура есть упорядоченная пара $\mathbf{A} = (A, \Omega)$, где $A$ — непустое множество, называемое носителем, а $\Omega$ — некоторое множество операций на носителе, называемое сигнатурой.

Вместо термина «алгебраическая структура» обычно говорят просто «алгебра».

• Рассмотрим бинарную операцию $(n = 2)$ на множестве $A$, обозначив её $*$. Эту операцию называют:

  • ассоциативной, если $(x * y) * z = x * (y * z)$

  • коммутативной, если $x * y = y * x$

  • идемпотентной, если $x * x = x$

    $\forall x, y, z \in A$

• Пусть $\mathbf{G} = (G, *)$ — некий группоид.
  • Элемент $\varepsilon \in G$ называется нулём по операции $*$, если для любого $a \in G$ имеет место $a * \varepsilon = \varepsilon * a = 0$.
  • Элемент $\varepsilon \in G$ называется нейтральным элементом по операции $*$, если для любого $a \in G$ имеет место $a * \varepsilon = \varepsilon * a = a$.

Ответ

Пусть $\mathbf{G} = (G, *)$ — некий группоид.

• Группоидом называют произвольную алгебру, сигнатура которой состоит из одной бинарной операции (например, $(G, *)$, $(\R, +)$, $(V, \times)$ и т.д.).
• Группоид $G$ называют полугруппой, если его операция ассоциативна, то есть имеет место тождество

  $$a * (b * c) = (a * b) * c\quad (\forall a, b, c \in G)$$

• Полугруппа с нейтральным элементом называется моноидом.

• Элемент $a'$ называется обратным к элементу $a$, если выполняется равенство

  $$a \cdot a' = a' \cdot a = \varepsilon$$

  Тогда сам элемент $a$ называется обратимым.
• Моноид, все элементы которого обратимы, называется группой.

Ответ

Полукольцом называется алгебра с двумя бинарными и двумя нульарными операциями $(S, +, \cdot, 0, 1)$, свойства которых устанавливают следующие основные тождества (аксиомы):

1. Сложение полукольца ассоциативно
   $a + (b + c) = (a + b) + c$
2. Сложение полукольца коммутативно
   $a + b = b + a$
3. Нуль есть нейтральный элемент по сложению
   $a + 0 = a$
4. Умножение полукольца ассоциативно
   $a \cdot (b \cdot c) = (a \cdot b) \cdot c$
5. Единица есть нейтральный элемент по умножению
   $a \cdot 1 = 1 \cdot a = a$
6. Умножение дистрибутивно относительно сложения слева и справа
   $a(b + c) = ab + ac$
   $(b + c)a = ba + ca$
7. Аннулирующее свойство нуля
   $a \cdot 0 = 0 \cdot a = 0$

• Полукольцо называется идемпотентным, если операция сложения идемпотентна, то есть $a + a = a$ для любого $a$.
• На носителе произвольного идемпотентного полукольца можно определить такое отношение:

  $$a \leqslant b \leftrightharpoons a + b = b$$

  Отношение $\leqslant$ есть отношение порядка (рефлексивное, антисимметричное и транзитивное), которое называется естественным порядком полукольца.

Ответ

• Полукольцо $(S, +, \cdot, 0, 1)$ называется замкнутым, если:
  • Оно идемпотентно
  • Любая последовательность имеет точную верхнюю грань по естественному порядку
  • Операция умножения непрерывна, то есть для любого элемента $a$ и любой последовательности $\set{b_n}_{n \geqslant 0}$ выполняются равенства:

    $$a \sup b_n = \sup (ab_n),\quad (\sup b_n) a = \sup (b_n a)$$

• Точная верхняя грань последовательности степеней элемента $a$ называется итерацией и обозначается $a^*$, то есть:

  $$a^* = \sum_{n = 0}^\infty x^n,\quad где\ x^0 = 1,\ x^n = x^{n-1} x,\ n = 1, 2, \ldots$$

  Пример:
  $\textbf{B} = (\set{0, 1}, +, *, 0, 1)$ — идемпотентное полукольцо. $\sup B = 1$, если хотя бы один её член равен 1, иначе равен 0. Итерация любого элемента полукольца $B$ равна 1.
  • Для $1^*$ это очевидно.
  • Для $0^*$ имеем

    $$0^* = 0^0 + 0^1 + \ldots + 0^k + \ldots = 1 + 0 + \ldots + 0 + \ldots = 1$$

Ответ

Кольцо — это алгебра типа $(2, 2, 0, 0)$, то есть алгебра с двумя бинарными и двумя нульарными операциями

$$\mathbf{R} = (R, +, \cdot, 0, 1)$$

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

1. Сложение кольца ассоциативно
   $a + (b + c) = (a + b) + c$
2. Сложение кольца коммутативно
   $a + b = b + a$
3. Нуль есть нейтральный элемент по сложению
   $a + 0 = a$
4. Каждый элемент кольца имеет обратный по сложению, называемый противоположным к $a$ и обозначаемым $-a$
   $(\forall a)\, (\exists a')\, (a + a' = 0)$
5. Умножение кольца ассоциативно
   $a \cdot (b \cdot c) = (a \cdot b) \cdot c$
6. Единица есть нейтральный элемент по умножению
   $a \cdot 1 = 1 \cdot a = a$
7. Умножение дистрибутивно относительно сложения слева и справа
   $a(b + c) = ab + ac$
   $(b + c)a = ba + ca$

• Кольцо, все ненулевые элементы которого обратимы по умножению, называется телом.
• Тело, умножение которого коммутативно, называется полем.