2024-09-16

Operatorer

Identitet (för *)

e \in A sådant att e * a = a * e = a \forall a \in A

Invers

Antag e är en identitet för * på A . För a \in A, om det finns b \in A så att b * a = a * b = e, kallas b en invers till a .

Övning. Om $a$ har invers $b$ , är $a$ alltid invers till $b$ ?

Kommunativitet

* är kommunativ om a * b = b * a \forall a, b \in A

Associativitet

* är associativ om \forall a, b, c \in A, a * (b * c) = (a * b) * c

Sats 3.30

Låt $*$ vara en binär operator på en icke-tom mängd $A$ . Det finns som mest en identitet för $*$ på $A$ . Om $a \in A$ och $*$ är associativ har $a$ högst en invers m.a.p. $*$

Bevis

$e_{1} = e_{1} * e_{2} = e_{2} * e_{1} = e_{2}$

$e_{1} = e_{2}$ , det kan bara finnas en identitet, V.S.B.

Antag att $a$ har två inverser, $b, c (m.a.p. *)$ . Vill visa $b = c$

b = b * e = b * (a * c) = (b * a) * c = e * c = c

Relationer

Vad är en relation?

Tidigare exempel på relationer:

Logiska relationer: $⟹$ , $⟺$
Mängder: $\subseteq$ , $=$

$A, B$ är två icke-tomma mängder. En relation från $A$ till $B$ är en delmängd $R \subseteq A \times B = {(a, b) : a \in A, b \in B}$ , Om $A = B$ säger vi att $R$ är en relation på $A$ .

För $a \in A, b \in B$ , tolka $(a, b) \in R$ som att " $a$ är relaterat till $b$ " enligt den regel som beskriver $R$ .

Notation

$(a, b) \in R$ skrivs $a R b$

Exvivalensrelationer & Partiell ordning

Egenskaper

3.36, 3.39, 3.48

Reflexiv om $\forall a \in A : a R a$
Symmetrisk om $a R b ⟹ b R a \forall a, b \in A$
Antisymmetrisk om $(a R b \land b R a) ⟹ a = b \forall a, b \in A$
Transitiv om $(a R b \land b R c) ⟹ a R c \forall a, b, c \in A$
Partiell ordning om $R$ är reflexiv, antisymmetrisk och transitiv
Ekvivalensrelation om $R$ reflexiv, symmetrisk och transitiv

OBS

En relation $R$ kan vara både symmetrisk och antisymmetrisk, en av de eller ingetdera.

Notera

Relationen definierad på $R \times R$ av $=$ har egenskaperna 1-4.

$\leq$ ger upphov till en partiell ordning på $R$ .

$R : två räta linjer är parallella$
$R$ är en ekvivalensrelation

$A = {alla städer i Europa}$
$x R y ⟺ x$ ligger i samma land som $y$
$R$ är en ekvivalensrelation

Ekvivalensklass

För en ekvivalensrelation $R$ på $A$ , för $a \in A$ definierar vi: $$[a]={b\in A:aRb}$$
$[a]$ kallas för " $a$ 's ekvivalensklass" (notera $a \in [a]$ , eftersom $R$ reflexiv)

I exemplet utegör länderna i Europa ekvivalensklasserna.

$a \in [a]$
$a R b ⟹ [a] = [b]$
$a$ ej relaterad till $b ⟹ [a] \cap [b] = \emptyset$ (betyder att ekvivalensklasserna för $R$ ger en uppdelning av $A$ i disjunkta delmängder. En partition av $A$ ).