20. Равномощные множества

---

ВПЕРЁД ⇒

Кардинальное число

⇐ НАЗАД

Связь композиции прямой и обратной взаимно однозначных функций с отношением тождества

---

Равномощные множества

Если существует взаимно однозначное соответствие между множествами $X$ и $Y$, то множества $X$ и $Y$ называются равномощными ($X\simeq Y$).

Для упрощения дальнейшего рассмотрения равномощных множеств воспользуемся понятиями рефлексивности, симметричности и транзитивности. Строго говоря, данные понятия используются для описания характера некоторого бинарного отношения $R$ на множестве $M$. Напомним, что означают эти понятия.

Рефлексивность бинарного отношения $R$ на множестве $M$:

$xRx$, где $x\in M$

Симметричность бинарного отношения $R$ на множестве $M$:

Из $xRy$ (где $x\in M$ и $y\in M$) следует $yRx$ (где $y\in M$ и $x\in M$)

Транзитивность бинарного отношения $R$ на множестве $M$:

Из $xRy$ (где $x\in M$ и $y\in M$) и $yRz$ (где $y\in M$ и $z\in M$) следует $xRz$ (где $x\in M$ и $z\in M$)

Рассмотрим бинарное отношение равномощности "$\simeq$" на множестве из двух элементов $M=\{X,Y\}$ (то есть элементы $X$ и $Y$ являются равномощными множествами):

$⟨k,l⟩\in \simeq$, где $k\in M$, $l\in M$ и $M=\{X,Y\}$

Рефлексивность отношения равномощности (рефлексивность равномощных множеств)

Любое множество $X$ равномощно самому себе ($X\simeq X$).

Доказательство:

Мы знаем, что любое множество $X$ находится в отношении тождества с самим собой. Также мы знаем, что отношение тождества - это взаимно однозначная функция (то есть взаимно однозначное соответствие между множествами $X$ и $Z$ такими, что $X=Z$). Получаем, что множество $X$ находится во взаимно однозначном соответствии с самим собой. Из этого следует, что множество $X$ равномощно самому себе. Всё сказанное применимо к любому элементу рассматриваемого множества $M=\{X,Y\}$. Это означает, что выполняется условие рефлексивности бинарного отношения "$\simeq$" на множестве $M$:

$⟨k,k⟩\in \simeq$, где $k\in M$, и $M=\{X,Y\}$

Симметричность отношения равномощности (симметричность равномощных множеств)

Из равномощности множеств $X$ и $Y$ ($X\simeq Y$) следует равномощность множеств $Y$ и $X$ ($Y\simeq X$).

Доказательство:

Если $X$ и $Y$ - равномощные множества ($X\simeq Y$), то между ними есть взаимно однозначное соответствие, то есть существует некоторая взаимно однозначная функция $f$, отображающая $X$ на $Y$. Поскольку $f$ - взаимно однозначная функция, то из этого следует, что обратное к ней отношение тоже является взаимно однозначной функцией, отображающей $Y$ на $X$. Существование взаимно однозначного соответствия между $Y$ и $X$ означает равномощность $Y$ и $X$ ($Y\simeq X$). Таким образом выполняется условие симметричности бинарного отношения "$\simeq$" на множестве $M$:

$⟨k,l⟩\in \simeq$ и $⟨l,k⟩\in \simeq$, где $k\in M$, $l\in M$ и $M=\{X,Y\}$

Транзитивность отношения равномощности (транзитивность равномощных множеств)

Из равномощности множеств $X$ и $Y$ ($X\simeq Y$) и равномощности множеств $Y$ и $Z$ ($Y\simeq Z$) следует равномощность множеств $X$ и $Z$ ($X\simeq Z$).

Доказательство:

Пусть на этот раз $M$ - множество, состоящее из трёх равномощных множеств ($M=\{X,Y,Z\}$). Равномощность множеств $X$ и $Y$, а также $Y$ и $Z$ означает наличие взаимно однозначных функций $f$ и $g$ таких, что $f$ отображает $X$ на $Y$, а $g$ отображает $Y$ на $Z$. Тогда, отображение $X$ на $Z$ представляет собой композицию $g\circ f$ взаимно однозначных функций $g$ и $f$, которая тоже является взаимно однозначной функцией. Таким образом, между $X$ и $Z$ существует взаимно однозначное соответствие, откуда следует равномощность множеств $X$ и $Z$. Таким образом выполняется условие транзитивности бинарного отношения "$\simeq$" на множестве $M$:

Из $⟨k,l⟩\in \simeq$ и $⟨l,n⟩\in \simeq$ следует $⟨k,n⟩\in \simeq$, где $k\in M$, $l\in M$, $n\in M$ и $M=\{X,Y,Z\}$

Наличие у отношения равномощности "$\simeq$" свойств рефлексивности, симметричности и транзитивности означает, что отношение равномощности является отношением эквивалентности. Другими словами, равномощные множества являются аналогами друг друга в том смысле, что любые два равномощных множества обладают одинаковым количеством элементов, причём элементы из этих двух множеств можно поставить во взаимно однозначное соответствие друг другу.

---

ВПЕРЁД ⇒

Кардинальное число

⇐ НАЗАД

Связь композиции прямой и обратной взаимно однозначных функций с отношением тождества

---

Источники

• Э. Мендельсон “Введение в математическую логику”. Глава 0 “Введение” (стр. 7-18).

Категория

Математическая-логика Математическая-логика

Теги

• Логика Логика
• Множество Множество
• Функция Функция
• Композиция-функций Композиция-функций
• Взаимно-однозначное-соответствие Взаимно-однозначное-соответствие
• Равномощные-множества Равномощные-множества
• Симметричность Симметричность
• Рефлексивность Рефлексивность
• Транзитивность Транзитивность
• Мощность Мощность