Қажеттілігін дәлелдеу: жиынының кластарға бөлінуі берілсін. Бұл бөлінудің эквиваленттік қатынас екенін дәлелдейміз:
жиынында қатынасын аламыз: « элементі элементі жататын класқа жатады». Бұл қатынас рефлексивті: әрбір элемент өз класында өзімен- өзі жатады.
– симметриялы: кез-келген элементі кез-келген элементімен бір класта жатса, онда элементі де -пен бір класта жатады.
- транзитивті: кез-келген үшін, егер элементі - пен бір класта жатса, элементі -пен бір класта жатса, онда элементі -пен бір класта жатады;
Сонымен – «бір класта жату» қатынасы жиынында эквивалентті қатынас.
Жеткіліктілігінің дәлелдеуі:симметриялы, рефлексивті, транзитивті қасиеттерге ие әрбір эквиваленттік қатынастың жиынын өзара қиылыспайтын кластарға бөлетінін дәлелдейміз.
Ол үшін жиынының әрбір элементіне жиынын сәйкес қоямыз. жиыны, элементімен қатынаста болатын барлық элементтердің жиыны, элементінің бейнесі деп аталады.
- рефлексивті болғанда үшін , бұл әрбір элемент өзінің сәйкес жиынында жатады деген сөз, яғни . Енді егер болса, онда екенін дәлелдеу керек:
Шындығында, бұл жағдайда . Егер , онда , ендеше , , транзитивтілік бойынша → . Яғни жиынының әр элементі – да жатып тұр, керісінше болғандықтан болады. орындалатындықтан, симметриялы қасиет бойынша , сондықтан . Яғни -ның кез – келген элементі – да жатады: → .
Егер жиындарының ортақ бір элементі болса, болады. Ендеше олар – мен де тең болады. Бұдан .
Кез – келген R(в) R(в) екі жиыны бір – бірімен тең болады (егер в R(а) болса), не қиылыспайды (егер в R(а) болады ). Сөйтіп біз бір-бірімен қиылыспайтын ішкі жиындарға Х жиынын бөлдік.
