Extras din curs
Fie ρ ≤ A2 o relaţie oarecare.
În cele ce urmează vom incerca să determinăm cea mai mică (in sensul incluziunii
de mulţimi) relaţie de echivalenţă pe A care conţine ρ , adică relaţia de echivalenţă
generată de ρ . Dacă o vom nota, pentru moment, prin < ρ > , este clar că
< ρ > = I{τ ⊆ A2 |τ echivalenta, ρ ⊆τ }.
Această definiţie nu este foarte utilă din punct de vedere practic, ea este însă
folositoare atunci când este vorba de minimalitatea ei. Putem insă să o construim efectiv:
1.10 Definiţie. Relaţia = = ∪ ( )∪ ( )∪ ...
ρ Uρ ρ ρ o ρ ρ o ρ o ρ
n N
t n se numeşte închiderea
tranzitivă a relaţiei ρ .
Să observăm că ρ t este o relaţie tranzitivă şi, în plus, este inclusă in orice relaţie
tranzitivă ce conţine ρ .
Fie A ρ~ = ρ ∪ ρ −1 ∪ Δ . Această relaţie este, evident, reflexivă şi simetrică, şi este
cea mai mică (in sensul incluziunii) relaţie cu aceste proprietăţi ce include ρ .
Din acest moment este clar că avem:
1.1 Propoziţie. Relaţia de echivalenţă generată de ρ este t ρ ~ (inchiderea tranzitivă a lui
ρ ~
). În plus, b a b a t = ⇔ ρ ~ sau există şirul de elemente din A a c c c b n , = , ,....., = 1 2 astfel
incât ~ , ( ) 1, 1
1 = − + c c i n i i ρ (sau, echivalent, ( ) 1 1, 1, + ∀ = − i i i n c ρ c sau i i c ρ c +1 ).■
1.11 Definiţie. Fie A o mulţime, α ⊆ A× A o relaţie de echivalenţă peste A. O
submulţime B a lui A se numeste α - saturată dacă U[ ]
b B
B b
= α .
1.2 Propoziţie. În ipotezele precedente, B este α - saturată dacă şi numai dacă pentru
orice b B [b] ⊆ B α , .
Demonstraţie. "⇒:" este evidentă.
":" Deoarece [ ]α b b rezultă că U[ ]
b B
B b
α . Din ipoteză,
(∀)b B [b] ⊆ B α , , deci [b] B
b B
U
α , deci avem egalitatea cerută.■
2. Semigrupuri şi Monoizi
În general, mulţimilor intâlnite in matematică li se asociază şi o structură
algebrică, în sensul că suntem in măsură să adunăm sau să înmulţim elementele lor.
Dacă S este o mulţime nevidă, o operaţie binară pe S este o funcţie ϕ : S × S → S ,
valoarea lui ϕ intr-o pereche (x, y) din S2 fiind, în fond, valoarea obţinută prin aplicarea
operaţiei perechii (x, y); ϕ(x, y) se notează, pentru o scriere mai uşoară, prin x × y , x ⋅ y ,
x + y , ...
2.1 Definiţie.
Preview document
Conținut arhivă zip
- Limbaje Formale.pdf