Конечное множество

Множество ${\displaystyle M}$ называется конечным, если оно либо пусто, либо найдётся натуральное${\displaystyle \ n}$ такое, что ${\displaystyle M}$ может быть взаимно однозначно отражено на подмножество ${\displaystyle N_{n}\subset \mathbb {N} :N_{n}=\{x|x\in \mathbb {N} ,x\leqslant n\}}$, то есть может быть занумеровано не более чем${\displaystyle \ n}$ числами. 

В противном случае множество называется бесконечным^[2].

• Каждое непустое подмножество конечного множества конечно.
• Множество всех подмножеств конечного множества конечно.
• Каждое множество, содержащее бесконечное подмножество, бесконечно.
• Множество всех подмножеств бесконечного множества бесконечно^[3].

Если два множества состоят из одного и того же конечного числа элементов, то между элементами этих множеств возможно установить такое соответствие, при котором каждому элементу одного множества соответствует один и только один элемент другого множества, и обратно; если же число элементов первого множества меньше, чем второго, то можно установить взаимно однозначное соответствие между первым множеством и частью второго.

Понятие взаимно однозначного соответствия не предполагает, что множества, между элементами которых устанавливается это соответствие, непременно конечны^[1].

Два множества называются количественно эквивалентными, если между ними возможно установить взаимно однозначное соответствие.

Количественно эквивалентные множества обычно называют просто эквивалентными множествами.

Два конечных множества эквивалентны тогда и только тогда, когда они состоят из одного и того же конечного числа элементов.

Два множества эквивалентных одному и тому же третьему множеству, эквивалентны между собою^[4].

Используя понятие эквивалентности, определяют счётное множество как множество, эквивалентное множеству всех натуральных чисел^[4].

• Всякое множество, эквивалентное счётному множеству, само есть счётное множество.
• Всякие два счётных множества эквивалентны.

Отображением множества ${\displaystyle A}$ во множество ${\displaystyle B}$ (функцией на ${\displaystyle A}$ со значениями в ${\displaystyle B}$) называется правило, по которому каждому элементу множества ${\displaystyle A}$ сопоставляется один или несколько элементов множества ${\displaystyle B}$. 

Для обозначения отображения ${\displaystyle \varphi }$ множества ${\displaystyle A}$ в множество ${\displaystyle B}$ используют запись ${\displaystyle \varphi :A\rightarrow B}$. Если ${\displaystyle x\in A}$, то множество всех элементов из ${\displaystyle B}$, сопоставляемых при отображении ${\displaystyle \varphi }$ элементу ${\displaystyle x}$, обозначается через ${\displaystyle \varphi (x)}$ и называется образом элемента ${\displaystyle x}$.

Если при отображении ${\displaystyle \varphi :A\rightarrow B}$ каждому элементу из ${\displaystyle A}$ сопоставляется в точности один элемент из ${\displaystyle B}$, то отображение (функция) ${\displaystyle \varphi }$ называется однозначным. Отображение, не являющееся однозначным, называется многозначным.

Однозначное отображение ${\displaystyle \varphi :A\rightarrow B}$ называется

• сюръективным (сюръекцией), если ${\displaystyle \varphi (A)=B}$ (отображение «на»);
• инъективным (инъекцией), если образы различных элементов различны (отображение «в»).
• биективным (биекцией) или взаимно однозначным, если оно сюръективно и инъективно^[4].

Два множества ${\displaystyle A}$ и ${\displaystyle B}$ называются равномощными (обозначение: ${\displaystyle A\sim B}$ ), если существует биекция ${\displaystyle \varphi :A\sim B}$. Отношение равномощности, рассматриваемое на любой заданной совокупности множеств, рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности^[4].