curs2 handout 4on1

7/25/2019 Curs2 Handout 4on1

1/5

Buna ordonare si inductie

Principiul bunei ordonari

Orice submultime nevida a lui N are un cel mai mic element.

Principiul inductieiFieS Nastfel ncat:

(i) 0 S si

(ii) pentru oricen N, daca n S, atunci n + 1 S.

Atunci S= N.

Observatie

Principul bunei ordonari si principiul inductiei sunt echivalente.

1

Principiul inductiei (forma tare)


FieS Nastfel ncat:

(i) 0 S si

(ii) pentru oricen N, daca {0, 1, . . . , n} S, atunci n + 1 S.

Atunci S= N.

Dem.: Aplicam Principiul inductiei pentru

S = {n N | {0, . . . , n} S}.

Obtinem S = N. Rezulta ca, pentru oricen N, {0, . . . , n} S,deci n S. Prin urmare,S= N.

2

Principiul inductiei

FieP: N {0, 1}un predicat (o proprietate). P(n) = 1 nseamnaca P(n) este adevarat.

Principiul inductiei

Pasul initial. Verificam caP(0) = 1.

Ipoteza de inductie. Presupunem caP(n) = 1, unde n N.

Pasul de inductie. Demonstram ca P(n+ 1) = 1.

Concluzie: P(n) = 1 pentru oricen N.


Pasul initial. Verificam caP(0) = 1.

Ipoteza de inductie. Presupunem caP(k) = 1 pentru orice

k n, unden N. Pasul de inductie. Demonstram ca P(n+ 1) = 1.

Concluzie: P(n) = 1 pentru oricen N. 3

Principiul diagonalizarii

Principiul diagonalizarii

FieRo relatie binara pe o multimeA si D A definita astfel:

D= {x A | (x, x) / R}.

Pentru oricea A, definim

Ra= {x A | (a, x) R}.

Atunci Deste diferit de fiecareRa.

Dem.: Presupunem ca exista a A astfel ncat D= Ra. Suntposibile doua cazuri:

a D. Rezulta ca (a, a) / R, deci a / Ra = D. Contradictie. a / D. Rezulta ca (a, a) R, deci a Ra = D. Contradictie.

Prin urmare,D=Ra pentru oricea A.4


2/5

Argumentul diagonal al lui Cantor

Teorema CantorNu exista o bijectie ntre N si mult imea 2N a partilor lui N, deci Nsi 2N nu sunt echipotente.

Dem.: Presupunem ca exista o bijectief : N 2N. Prin urmare,2N poate fi enumerata ca 2N = {S0,S1, . . . ,Sn, . . . , }, unde

Si =f(i) pentru oricei N. Consideram relatia binaraR NNdefinita astfel:

R= {(i,j) | j f(i)} = {(i,j) | j Si}

si aplicam Principiul diagonalizarii. Astfel,

D = {n N | (n, n) / R} = {n N | n / Sn},

Ri = {j N | (i,j) R} = {j N | j Si} =Si, i N.

DeoareceD N si f este bijectie, existak N a.. D= Sk =Rk.Pe de alta parte, conform Principiului diagonalizarii,D=Ri

pentru oricei N. Am obtinut o contradictie.5

Multimi numarabile

Definitie

O multimeA estenumarabil adaca este echipotenta cu N .O multime finita sau numarabil a se numeste cel mult numarabila.

Corolar

2N nu este multime numarabila.

Propozitie

(i) Orice submultime infinita a lui N este numarabila.

(ii) Reuniunea unei familii cel mult numarabile de multiminumarabile este multime numarabila.

(iii) Z si Q sunt numarabile.

(iv) Produsul cartezian al unei familii cel mult numarabile demultimi numarabile este multime numarabila.

Dem.: Exercitiu. 6

Relatii binare

FieA o multime nevida si R A A o relatie binara peA.Notatie: ScriemxRy n loc de (x, y) R si (xRy) n loc de(x, y) R.

Definitie R estereflexivadaca xRx pentru oricex A.

R esteireflexivadaca(xRx) pentru oricex A.

R este simetrica daca pentru orice x, y A,

xRy implica yRx.

R este antisimetrica daca pentru orice x, y A,

xRy si yRx implica x=y.

R estetranzitivadaca pentru oricex, y, z A,

xRy si yRz implica xRz. R estetotala daca pentru orice x, y A,

xRy sauyRx. 7

Relatii de echivalenta

Definitie

FieA o multime nevida si R A A o relatie binara peA. R senumesterelatie de echivalentadaca este reflexiva, simetrica si

tranzitiva.Exemple

Fien N. Definim relatia (mod n) Z Z astfel:

(mod n) = {(x, y) Z | n divide (x y)}.

Relatia (mod n) se numeste congruenta modulo n. Folosimnotatiax y(mod n) pentru (x, y) (mod n).

Fief :A Bo functie. Definim relatia ker f A Aastfel:

ker f = {(a1, a2) A A | f(a1) = f(a2)}.

ker f se numeste si nucleul lui f.

Notatii: Vom nota relatiile de echivalenta cu. Scriemx ydaca (x, y) si x ydaca (x, y) /.

8


3/5


FieA o multime nevida si A A o relatie de echivalenta.

Definitie

Pentru oricex A, clasa de echivalenta[x] a lui x este definitaastfel: [x] = {y A | x y}.

Propozitie A=

xA[x].

[x] = [y] ddaca x y.

[x] [y] = ddacax y ddaca [x] = [y].

Dem.: Exercitiu.

Definitie

Multimea tuturor claselor de echivalenta distincte ale elementelorlui A se numest multimea cata lui A prin si se noteazaA/.

Aplicatia : A A/, (x) = [x] se numeste functia cat.9


FieA o multime nevida si A A o relatie de echivalenta.

Definitie

Unsistem de reprezentantipentru este o submultimeX Acaresatisface: pentru oricea A exista un unicx X a.. a x.

PropozitieFieX un sistem de reprezentanti pentru. AtunciA =

xX[x] si

A/= {[x] | x X}.

Dem.: Exercitiu.

Exemplu

Consideram congruenta modulo 2, (mod 2):[0] = {2n | n Z} = 2Z, [1] = {2n+ 1 | n Z} = 2Z + 1;[2n] = [0] si [2n+ 1] = [1] pentru oricen Z; multimea cat esteZ2= {[0], [1]}. Sisteme de reprezentanti: X = {0, 1}, X = {2, 5},X = {999, 20}.

10

Partitii

FieA o multime nevida.

Definitie

Opartitiea luiA este o familie (Ai)iI de submultimi nevide ale luiA care verifica proprietatile:

A=

iIAi si A i Aj= pentru oricei=j.

Partitia (Ai)iI se numeste finitadaca Ieste finita.

Propozitie

Exista o bijectie ntre mult imea relatiilor de echivalenta peA simultimea partitiilor luiA:

(Ai)iI partitie a lui A relatia de echivalenta peA definitaprin: x y exista i I a.. x, y Ai.

relatie de echivalenta pe A partitia ([x])xX, undeX A este un sistem de reprezentanti pentru.

Dem.: Exercitiu. 11

Relatii de ordine

Definitie

FieA o multime nevida. O relatie binara R pe A este relatie de ordine partialadaca este reflexiva, antisimetrica si tranzitiva.

ordine strictadaca este ireflexiva si tranzitiva.

ordine totaladaca este antisimetrica, tranzitiva si totala.

Notatii: Vom nota relatiile de ordine partiala si totala cu , iarrelatiile de ordine stricta cu


4/5

Multimi partial ordonate

Fie (A, ) o multime partial ordonata.

Proprietatii Orice relatie de ordine totala este reflexiva. Prin urmare, orice

multime total ordonata este multime partial ordonata.

Relatia< definita prinx


5/5

Multimi bine/inductiv ordonate

Fie (A, ) o multime partial ordonata.

Definitie

Spunem ca (A, ) este multimebine ordonatadaca oricesubmultime nevida a lui A are minim. In acest caz, se numesterelatie debuna ordonarepe A.

Exemple

(N,

curs2 handout 4on1

Documents