Relatii binare

Relatii binare

Relatia binarã pe o multime

Definitia III.1. Fie M o multime nevidã. Se numeste relatia binarã R pe M o parte a produsului cartezian MxM. Dacã x M este relatia R cu y M, atunci scriem xRy sau (x,y) R. Deci o relatie binarã se referã la perechile de elemente din M.

Proprietãti ale relatiilor binare pe o mul# 23423i89x 5;ime:

1. Relatia binarã R pe multimea M se numeste reflexivã dacã " a M avem pe aRa.

2. Relatia binarã R pe multimea M se numeste simetricã dacã " a,b M avem aRb implicã bRa.

3. Relatia binarã R pe multimea M se numeste antisimetricã dacã " a,b M, aRb si bRa implicã a=b.

4. Relatia binarã R pe multimea M se numeste tranzitivã dacã " a,b,c M, aRb implicã bRc implicã aRc.

Definitia III.2. Se numeste greficul relatiei R definitã pe M multimea G = .

Definitia III.3. O relatie binarã R definitã pe o multime nevidã M se numeste relatie de echivalentã dacã ea este reflexicã, tranzitivã si simetricã.

Exemplu: Fie N multimea numerelor naturale si numãrul 3 fixat. Pe N stabilim urmãtoarea relatie R: a si b din N sunt în relatie cu R, dacã a si b împãrtite la 3 dau acelasi rest. Scriem a b (mod 3); de pildã 4 1 (mod 3). Aceasta este o relatie de echivalentã.

Definitia III.4. Fie M o multime. R o relatie de echivalentã pe M si a un element fixat din M. Se numeste clasã de echivalentã corespunzãtoare elementului a multimea C_a = . Douã clase de echivalentã C_a si C_b sau coincid (când aRb) sau sunt disjuncte.

Definitia III.5. Fie M o multime si R o relatie de echivalentã pe M. Se numeste multimea cât a lui M în raport cu relatia R si se noteazã M/R multimea claselor de echivalentã.

Definitia III.6. Fie M o multime nevidã. Se numeste relatie de ordin pe M o relatie binarã care este reflexivã, tranzitivã si antisimetricã.

Se noteazã: "<" sau " "

De exemplu: relatia cunoscutã de ordine naturalã " " pe N, Z, Q si R este o relatie de ordine.

Definitia III.7. Fie M o multime nevidã si " " o relatie de ordin pe M. Aceastã relatie de ordin se numeste relatie de ordine totalã dacã oricare douã elemente ale lui M sunt comparabile adicã "a,b M avem sau a<b sau b<a. Multimea înzestratã cu o relatie de ordine totalã se numeste multime total ordonatã.

Definitia III.8. Fie M o multime nevidã. O relatie de ordine pe M se numeste relatie de bunã ordonare dacã orice parte nevidã a lui M are un cel mai mic element. Multimea M, cu aceastã relatie de bunã ordonare, se zice bine ordonatã.

O relatie de bunã ordonare pe M este o relatie de ordie totalã pe M.