Курсовая работа: Комбінаторика

Припустимо, що К (а ) ∩ К (b) ≠ Ш. Тоді у них є спільний елемент с , тобто

с є К (а ) і с є К (b )

Але елементи одного класу, відповідно до (1) знаходяться у відношенні р між собою, значить

арс і bрс

Із симетричності відношення р із bрс слідує срb , а із транзитивності відношення р випливає:

якщо арс і срb , то арb .

А це протирічить умові, що а b.

Значить, припущення не вірне і

К (а ) ∩ К (b) = Ш.

Покажемо, що виконується і умова 3).

Із формули (1) видно, що будь-який а є А належить класові К (а ), тобто

а є К (а ). Отже, щоб одержати множину А треба об’єднати усі ці класи

К (а ) = А

^{а є А}

Ми довели, що відношення р розбиває множину А на класи еквівалентності.

Тепер покажемо, що: 1) два елементи одного класу еквівалентні між собою, а 2) два елементи різних класів не еквівалентні. Доведемо перше.

Нехай b і с будь-які два елементи одного класу К (а ). Доведемо, що bрс . Раз b є К (а ), то по формулі (1) – арb , а з того, що с є К (а ) слідує, що арс . За симетричністю відношення р – з а р b слідує b р а . За транзитивністю відношення р маємо bра і арс , то bрс.

Доведемо друге. Нехай маємо два різні класи К (b ) ≠ К (с ). Покажемо, що b с . Доведемо від супротивного. Припустимо, що bрс . Нехай d – довільний елемент множини К (с ), тоді cpd .

За симетричністю р маємо із bрс слідує срb.

За транзитивністю із bрс і срd слідує bpd.

Значить d є К (b ).

Ми довели, що якщо d є К (с ), то d є К (b ) для вільного d.

Отже, К (с ) К (b ).

Аналогічно доводимо, що К (b ) К (с ).

Отже, К (b ) = К (с ).

А це протирічить умові. Значить, наше припущення не вірне і b с .

§ 2. 5. Відношення порядку. Упорядкована множина.

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

Інтуїтивне представлення про порядок об’єктів переважно пов’язано з їх взаємним розміщенням в просторі (вище – нижче, ближче – дальше, правіше – лівіше); в часі (раніше – пізніше); з порівнянням їх розмірів (більше – менше, легше – тяжче).

Ці відношення і подібні їм відносяться до важливого класу відношень, що називають відношеннями порядку.

Відношенням строгого порядку називається будь-яке відношення, яке є антирефлексивним, антисиметричним і транзитивним.

Отже, відношення р буде відношенням строгого порядку, якщо:

1. х х для будь-якого х є А, тобто (х, х) Р для будь-якої пари

2. (х, х) є А І.

3. якщо хру , то у х для будь - якого х, у є А, тобто якщо (х, у) є Р, то