Relație binară

În matematică, o relație binară pe o mulțime A este o submulțime a produsului cartezian $A\times A$.

Ca notație uzuală, dacă $\rho\subseteq A\times A$ este o relație, în loc să scriem $(a,b)\in\rho$, scriem $a\,\rho\,b$.

Tipuri de relații binare

O relație binară $\rho\subseteq A\times A$ se numește:

• reflexivă, dacă $\forall a\in A\,,\ a\,\rho\,a$
• antireflexivă, dacă $\forall a\in A\,,\ (a,a)\notin\rho$
• simetrică, dacă $\forall a,b\in A\,,\ a\,\rho\,b\ \Rightarrow\ b\,\rho\,a$
• antisimetrică, dacă $\forall a,b\in A$, $a\,\rho\,b$ și $b\,\rho\,a$ implică $a=b$
• tranzitivă, dacă $\forall a,b,c\in A$, $a\, \rho\,b$ și $b\,\rho\,c$ implică $a\,\rho\,c$
• de echivalență, dacă este reflexivă, simetrică și tranzitivă
• de preordine dacă este reflexivă și tranzitivă
• de ordine, dacă este reflexivă, antisimetrică și tranzitivă
• de ordine totală, dacă este relație de ordine și $\forall a,b\in A$, $a\,\rho\,b$ sau $b\,\rho\,a$
• relație de bună ordonare, dacă este relație de ordine totală și, în plus, orice submulțime nevidă a lui A posedă un minim ($B\subseteq A\land B\neq\emptyset\Rightarrow \exists m\in B,\forall x\in B, m\leq x$)
• de ordine strictă, dacă este antireflexivă și tranzitivă

Vezi și

• Produs cartezian
• Închidere tranzitivă
• Graf