Равномощность множеств. Примеры. Счётные множества и множества мощности континуум.

Рассмотрим два множества A и B.

Отображение ƒ из A в B (обозначается ƒ: A→B) — это правило, которое каждому элементу множества A ставит в соответствие элемент множества B, причём ровно один. (При этом не запрещается двум элементам множества A ставить в соответствие один и тот же элемент множества B, рис. 1, а.)

Отображение ƒ называется взаимно однозначным, если каждый элемент множества B поставлен в соответствие ровно одному элементу множества A (рис. 1, б).

Множества A и B называются равномощными, если существует взаимно однозначное отображение ƒ:A→B. Понимать это можно так: множества равномощны, если в них одинаковое количество элементов.

Например, множества {0, 1, 2} и {лошадь, корова, телевизор} равномощны, а множества {0, 1, 2} и {лошадь, корова} неравномощны (телевизор был по делу...).

Определение Множества, эквивалентные по числу элементов множеству N={1, 2, 3, 4, …} называются счетными множествами.

Примеры счетных множеств:

{2, 4, 6, 8, …}; ;{1, 4, 9, 16, 25, …}; {1, 8, 27, 64, 125, …}

Свойства счетных множеств изложим, пользуясь терминологией математики, т.е. громко именуя их теоремами.

Теорема 1. Для того, чтобы множество А было счетным, необходимо и достаточно, чтобы его можно было представить в виде А={a1, a2, a3,…}

Бинарные отношения на множестве. Примеры. Частные виды. Особенности графов и матриц.*)

Определение. Про соответствие f между множествами A и B в случае, когда эти множества равны (A=B), можно говорить, что это бинарное отношение на множестве A. Таким образом бинарное отношение это частный случай соответствия. Поэтому для бинарных отношений справедливо все, что верно для соответствий.

Примеры. 1) A=N Пусть afb, если a b. Например, 1f1, но 1 2, 13f1, но 13 7.

2) A – тоже, но afb, если натуральное a кратно простому b. Это другой пример, так как здесь на втором месте не может быть 1, т.к. оно не простое (простое – N, у которого ровно 2 делителя; составное – N, у которого больше двух делителей).

3) A={1, 2, 3, …, 9} Пусть afb, если a≤b. Например, 0≤ любого b, любое a≤9, но 3 2.

Определения. 1. f называется рефлексивным отношением, если всегда afa, т.е. любой элемент a находится в отношение f сам с собой. На графе такого отношения каждая точка снабжена петлей.

Примеры. 1) Быть кратным на N (но не на N₀). 2) Быть родственниками. 3) Быть не выше (но не «быть выше»).

2. В последнем случае, когда всегда a не f a, говорят что f антирефлексивно. В этом случае на графе нет ни одной петли.

3. f называется симметричным отношением, если из afb всегда следует bfa. На графе все стрелки вот такие:↔.

4. Если же для различных a и b из afb всегда следует b не f a, то такое f называют антисимметричным.

Примеры. 1) быть знакомыми, 2) быть одного возраста, 3) учиться в одном классе, 4) иметь одних и тех же родителей и т.д., 5) быть мамой своего ребенка, 6) быть длиннее на множестве отрезков.

5. f называется транзитивным отношением, если из afb,bfc всегда следует afc. На графе все цепочки должны быть замкнуты.

6. Если же f одновременно рефлексивно, симметрично и транзитивно, то оно называется отношением эквивалентности.

Примеры. 1) Учиться в одном классе. 2) Родиться в одном и том же году или в одном и том же месте. 3) Начинаться с одинаковой буквы, но не иметь «хотя бы одну» одинаковую букву (мама f мыла, мыла f рыльце, но мама не f рыльце).