Множини Множиною називається сукупність предметів або понять, об'єднаних якою-небудь спільною властивістю. Наприклад, говорять про множину літер у абетці, множину осіб, які навчаються у одному класі школи тощо. Предмети, що входять до множини, називаються її елементами. Множини позначають великими літерами, а елементи малими літерами латинської або грецької абеток. Множина записується через перелічення її елементів у фігурних дужках Наприклад, вираз означає множину, яка складається з чисел (елементів) Множини та варто розглядати як однакові, оскільки у другому випадку елемент згаданий двічі при переліченні елементів, що є несуттєвим для визначення самої множини. Таким чином, для повного задання множини достатньо перелічити усі її елементи. Порядок запису елементів також не відіграє суттєвого значення. Наприклад, множина з трьох елементів припускає шість перестановок:

Той факт, що елемент належить до множини записується У протилежному випадку, якщо необхідно, пишуть що означає, що елемент не міститься у

Множина що складається з елемента і сам цей елемент вважаються різними об'єктами. Зокрема, доводиться відрізняти елемент множину яка складається з одного елемента та множину елементом якої є множина тощо.

Разом із множинами, що містять елементи, розглядають пусту множину, яка не містить жодного елемента. Усі пусті множини є рівними і позначаються символом Варто відзначити, що множина містить в якості елемента пусту множину і тому не є пустою.

Якщо кожний елемент множини входить до множини то називається підмножиною a називається надмножиною При цьому пишуть та Зрозуміло, що якщо та то Зрозуміло також, що для будь-яких множин з слідує

Якщо кожний елемент множини міститься у множині але множина містить хоча б один елемент, який не міститься у тобто якщо та то називається власною підмножиною а - власною надмножиною У цьому випадку записують Запис означає, що є підмножиною відмінною від З слідує тощо.

Пуста множина має лише одну частину: множина що складається з одного елемента має дві частини: та множина що складається з двох елементів, має чотири частини: Таким чином, множина, яка складається з певного числа елементів, має частин.

Нехай - декотра властивість, притаманна об'єктам, і нехай формула означає, що об'єкт наділений властивістю Тоді через позначається множина об'єктів, які наділені властивістю Наприклад, нехай дана множина Тоді буде підмножиною елементами якої є числа, більші від 4. Знак порівнювання "" означає "більше" (запис буквально: усі більші від ). Тобто Варто відзначити, що замість перелічення усіх елементів множини може використовуватися змінна, яка представляє усі елементи множини. У нашому випадку представляє усі елементи множини Зазвичай множину задають без перелічення усіх її елементів, користуючись змінною як збірним символом для елементів даної множини. При цьому обов'язково вказують, що елемент належить множині, наприклад, або тощо. Замість вертикальної риски у записі можуть використовуватися дві крапки, тобто

Порядковий номер елемента множини записується знизу праворуч біля знака елемента, Для позначення конкретних значень, які пробігає використовують горизонтальну риску над найменшим та найбільшим елементами множини (зрозуміло, що ). Наприклад, множина з 20 людей вишикувалася у шеренгу по росту. Елемент буде вдповідати найменшій людині у шерензі, а елемент - найбільшій. При цьому пишуть а у дужках вказують значення порядкових номерів, які пробігає В нашому випадку, формально, Таким чином, запис означає множину чисельністю 20 елементів . Чисельність множини також називається її потужністю або кардинальним числом і позначається В нашому прикладі із шеренгою

Інколи для запису множини використовують позначення де вказує значення номера кінцевого елемента,

Відношення на множинах Множина із визначеними на ній відношеннями називається реляційною системою і позначається . Множина відношень складається із підмножин,

Декартовим добутком множин та символічно називається сукупність усіх пар виду де Наприклад, якщо то Далі,

Будь-яке відношення , задане на фіксованій парі довільних множин та є підмножиною множини тобто

Нехай дана множина а - бінарне відношення на множині позначуване Це відношення називається відношенням порядку, якщо справджуються наступні твердження:

транзитивність: якщо та то асиметричність: якщо то неможливо

Множина із відношенням порядку називається впорядкованою множиною.

Множина називається лінійно впорядкованою, якщо для будь-якої пари елементів множини виконується одне з двох співвідношень або Лінійно впорядкована множина називається також ланцюгом.

Нехай - лінійно впорядкована множина, а - її підмножина. Елемент називається мінімальним, якщо для будь-якого Наприклад, мінімальним елементом множини є число

Лінійно впорядкована множина називається цілком впорядкованою, якщо будь-яка її підмножина містить мінімальний елемент. Відношення порядку на такій множині називається відношенням повного порядку. Прикладом лінійно впорядкованої множини із відношенням повного (суворого) порядку є множина натуральних чисел, що використовуються при лічбі предметів. Відношення порівняння на множині натуральних чисел, визначає порядок слідування чисел: Символ позначає нескінченість. Множина натуральних чисел є нескінченною, оскільки для даного натурального числа завжди знайдеться число більше від (тобто або ).

Початковим елементом цілком впорядкованої множини називається її мінімальний елемент. Наприклад, початковим елементом множини натуральних чисел є число Відрізком лінійно впорядкованої множини називається така підмножина що для будь-яких її елементів та будь-якого які задовільняють умові маємо Початковим відрізком цілком впорядкованої множини назвивається відрізок, що містить мінімальний елемент цієї множини. Початковим елементом відрізку є його мінімальний елемент.

Нехай на множині задане відношення яке називається відношенням часткового порядку, для якого виконуються наступні аксіоми: для будь-якого (рефлексивність); якщо та то (транзитивність); якщо та то (асиметричність).

Зокрема, відношення "бути підмножиною" на множині усіх підмножин множини є відношенням часткового порядку. Зрозуміло, що - відношення часткового порядку, де

Якщо - відношення, визначене на парі множин та то зворотним відношенням (символічно ) називається відношення (визначене на парі множин ), яке складається з тих пар для яких Наприклад, якщо відношення порядку (відношення порівняння або "менше"), то

і тому ("більше"). Символ означає "рівносильно". Зрозуміло, що

Знак дорівнює означає відношення рівності, яке базується на наступних властивостях: (рефлексивність, тобто кожний елемент рівний сам собі); якщо то (симетричність); якщо та то (транзитивність).

Наприклад, відношення рівності є підмножиною декартового добутку множин Воно визначає сукупність усіх "діагональних" пар

Верхня та нижня границі. Нехай - частково впорядкована множина елементів Якщо та то називається мажорантою елементів та У цому випадку пишуть Наприклад, для множини мажорантою буде елемент Зрозуміло, що якщо такий елемент існує, то він лише один. Аналогічним чином визначається міноранта для та вона позначається У нашому прикладі

Елемент називається максимальним, якщо кожний елемент або не порівнюваний із або Іншими словами, елемент називається максимальним, якщо не існує такого що Для підмножини та ми пишемо якщо для кожного виконується умова

Нехай - непуста частково впорядкована множина така, що будь-яка її лінійно (цілком) впорякована підмножина (тобто ланцюг) () має у мажоранту. Тоді містить принаймні один максимальний елемент. Це рівносильно твердженню, що будь-яка непуста множина може бути цілком впорядкована.

Еквівалентність. Бінарне відношення на множині називається відношенням еквівалентності, якщо для будь-яких елементів (рефлексивність); якщо то (симетричність); якщо та то (транзитивність).

Відношення еквівалентності співпадає із відношенням рівності Виділениі властивості (рефлексивність, симетричність, транзитивність) можна представити у наступному вигляді: Рефлексивність: Симетричність: Транзитивність:

Ці три умови є рівносильними наступним:

Припустимо, що існує деяка ознака, за якою пара елементів та множини є еквівалентними. При цьому ми вимагаємо від цієї еквівалентності лише щоб вона була наділена властивостями симетрії, транзитивності й рефлексивності. Скажімо, множину учнів Івано-Франківська ми розподілимо по школам. Два довільно обрані учні з цієї множини будуть "еквівалентними", якщо вони навчаються у одній і тій самій школі (хоча у різних класах). Якщо ми розподілимо учнів по класам, то двоє учнів будуть "еквівалентні", якщо вони навчаються у одному і тому самому класі (хоча у різних школах).

Розбиттям непустої множини називається сукупність непустих попарно непересічних підмножин множин множини таких, що об'єднання усіх множин дорівнює множині в цілому. Підмножини називаються класами розбиття, або суміжними класами (класами еквівалентності). Скажімо, в якості можна розглядати множини учнів, розподілених по школам №1, №2, ..., №n, які є підмножинами множини

З кожним розбиттям пов'яжемо бінарне відношення визначене на вважаючи, що за визначенням є справедливим лише тоді, коли та належать одному і тому ж самому шару множини Зрозуміло, що відношення є відношенням еквівалентності Якщо множину зобразити квадратом, а шари - прямокутниками, на які розбивається квадрат, то відношення справедливе тоді, коли точки та належать одному і тому самому прямокутнику (тобто одній і тій самій підмножині множини ).

Таким чином, кожна еквівалентність на множині відповідає деякому розбиттю множини на підмножини. Підмножини множини називаються суміжними класами. Система усіх суміжних класів по є розбиттям множини Оскільки елементи з лише тоді є еквівалентними, коли вони містяться у одному і тому самому суміжному класі. Таким чином, розбиття на суміжні класи по та задана еквівалентність відповідають одне одному. Сукупність усіх суміжних класів множини по еквівалентності позначається через і називається фактор-множиною від по

Відношення еквівалентності є частковим випадком відношення толерантності (його називають також відношенням схожості або наближеною рівністю), яке має наступні властивості: рефлексивність, ; симетричність,

Відношення толерантності не є транзитивним в загальному випадку. Воно часто використовується для опису схожості між реальними об'єктами, для опису відношень знайомства чи союзу між людьми. Справді, Тарас може бути знайомий із Лесею, а Леся - із Андрієм, однак це не значить, що Тарас знайомий із Андрієм.

Нехай на множині задана толерантність, тобто підмножина Підмножина називається ядром даної толерантності якщо усі її елементи попарно зв'язані між собою. Найпростіші ядра складаються з одного елемента, оскільки через рефлексивність толерантності кожний такий елемент поставлений у відповідність самому собі, Ядро називається максимальним, якщо воно не міститься у жодному іншому ядрі однієї і тієї ж підмножини .

Ядра для толерантності - те саме, що й класи для еквівалентності. Однак, на відміну від класів, вони перетинаються між собою й не утворюють розбиття. Наприклад, якщо відношення еквівалентності розбиває суспільство на окремі непересічні підмножини (на основі відповідного фактора - раси, діаспори тощо), то у випадку відношення схожості (толерантності) відмінності між людьми зовсім не є обов'язковими.

-арні відношення. Декартовим добутком (або прямий добуток) системи множин називається сукупність послідовностей де Будь-яка підмножина множини називається відношенням, визначеним на системі Декартовий добуток де називається -ним степенем множини і позначається Відношення визначене на системі називається -арним відношенням на множині

Для декартового добутку справедливе наступне твердження: