Introducere ın Logica matematicasi

teoria formala a dreptei

Constantin Milici

1

Cuprins

1 Sistemul formal al calculului propozitional 41.1 Formulele calcului propositional . . . . . . . . . . . . . . 41.2 Sistemul deductiv al calcului propozitional . . . . . . . . 41.3 Necontradictia si completitudinea calcului propozitional 131.4 Independenta sistemului calcului propozitional . . . . . 15

2 Calculul restrans al predicatelor. 182.1 Limbajul calcului restrans al predicatelor. . . . . . . . . 182.2 Axiomele calcului restrans al predicatelor. . . . . . . . . 192.3 Deductia ın calculul restrans al predicatelor . . . . . . . 232.4 Regula C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5 Necontradictia si completitudinea calcului restrans al

predicatelor . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.6 Independenta calculului restrans al predicatelor . . . . 332.7 Calculul restrans al predicatelor cu egalitate . . . . . . 34

3 Teoria formala a dreptei 363.1 Axiomele abstracte. . . . . . . . . . . . . . . . . . . . . . 363.2 Axiomele de incidenta si ordine. . . . . . . . . . . . . . . 363.3 Axioma lui Pash. . . . . . . . . . . . . . . . . . . . . . . . . 363.4 Deductia formala a dreptei. . . . . . . . . . . . . . . . . . 373.5 Topologia dreptei . . . . . . . . . . . . . . . . . . . . . . . . 473.6 Axiomele de congruenta si continuitate . . . . . . . . . . 603.7 Dreapta formala ın geometria hiberbolica . . . . . . . . 62

2

Introducere

Aceasta carte a fost scrisa sub influenta cartilor lui Mendelson [1] si Rosser[4].Autorul a ıntalnit diverse dificultati ın formalizarea unor rezultate clasice.Capitolul 1 si 2 este sub influenta unui exercitiu din cartea lui Mendelson.Modelul de interpretare este boolean, sirurile de interpretare sunt con-

struite cu valorile 0 si 1.Calculul predicatelor este ca ın cartea lui Rosser (restrans), nu are functori

si predicate atomice.Topologia dreptei (capitolul 3), deasemeni este ımprumutata din Rosser.Cartea este destinata studentilor care fac cursuri de logica sau fundamente

de geometrie cat si cercetatorilor ın logica formala.

Autorul

3

1 Sistemul formal al calculului propozitional

1.1 Formulele calcului propositional

Definitia (1.1). Multimea de simboluri Ω:Ω= {X1, X2, . . . , Xn,¬,→} se numeste alfabetul calcululuipropozitional si se noteaza Ω= Ω(X1, X2 . . . , Xn).Simbolurile X1, X2, . . . , Xn se numesc variabile propozitionale. Sim-

bolurile ¬, → se numesc operatiile calcului propozitional (”¬” se numestenegatia si se citeste ”non” iar ”→” se numeste implicatia si se citeste”implica”).Definitia (1.2). Un sir finit A=ρ1ρ2 . . . ρm (m ≥ 1) de simboluri din

Ω, se numeste asmblaj.Numarul m se numeste lungimea asamblajului si se noteaza cu δ(A).

Definitia (1.3). Un sir finit (*) A1, A2, . . . , Ar r ≥ 1 de asamblaje(ın Ω) se zice sir formativ¸ ın notatie poloneza daca oricare ar fi indicele i(1 ≤ i ≤ r) este ındeplinita una din conditiile:a) Ai coincide cu una din variabilele X1, X2, . . . , Xn;b) Exista ın sirul (*) un asamblaj Fj cu j ≤ i cu Fi≡¬Fj;c) Exista ın sirul (*) doua asamblaje Fh, Fk cu h, k ≤ i astfel caFi≡→ FhFk;Multimea asamblajelor de forma (¬F) sau (→FG) formeaza multimea

formulelor ın propozitionale ın notatie poloneza notataA(X1, X2, . . . , Xn).

1.2 Sistemul deductiv al calcului propozitional

In cele ce urmeaza vom face urmatorul abuz de notatie: vom nota (A→B)ın loc de →AB.

Definitia (1.4). Axiomele sistemului deductiv L3 al calculuipropozitional

Oricare ar fi formulele A, B, C din A(X1, X2, . . . , Xn) urmatoarele formulese zic axiome ale sistemului deductiv L3.(L1) A →(B →A)(L2) (A →(B →C)) →((A →B) →(A →C))(L3) (¬B →¬A) →(A →B)

4

Remarca Axiomele (L1)-(L3) se mai zic scheme, deoarece fiecare reprezintaın realitate o infinitate de axiome.

Acest sistem este cunoscut ca sistemul L3 sistemul lui J. Lukasiewicz.

Introducem urmatoarele legaturi prin definitie:

A ∧B ≡¬(A →¬B)A∨B ≡¬A →B

A ↔B ≡(A →B) ∧(B →A)Definitia (1.5). Un sir finit de formule propozitionale din L3

F1, F2, . . . , Fm

se zice text demonstrativ (pentru Fm) ın L3 daca oricare ar fi indicele i(1 ≤ i ≤ n), formula Fi satisface una din conditiile:- este o axioma

- este dedusa prin substitutie din o formula precedenta

- exista h, k < i astfel ıncat Fk coincide cu Fh → Fi.Orice formula propozitionala dintr-un text demonstrativ se zice teorema

(ın particular axiomele sunt teoreme).

Remarca. Regula care permite deducerea teoremei Fi din teorema Fhsi Fh → Fi se numeste modus ponens si o vom nota (MP).In cele ce urmeaza vom stabili pe cale matematica o serie de propozitii

care ne vor spune despre o formula sau alta daca este teorema sistemului L3.Asemenea propozitii matematice despre teoremele sistemului L3 se vor numimetateoreme.

Definitia (1.6). (a deductiei simple cu ipoteze auxiliare).

Fie Θ o lista arbitrara (eventual vida) de formule si F o formula oarecare(continuta sau nu ın Θ). Vom zice ca formula F este simplu deductibila dinlista Θ si o notam Θ ` F daca exista un sir de formule

(Θ) : F1, F2, . . . , Fn; (n ≥ 1)cu Fn = F si avand proprietatea ca oricare ar fi indicele i (1 ≤ i ≤ n),

formula Fi satisface una din clauzele:

-Fi este formula din Θ

-Fi este o axioma logica din lista (L1)-(L3)

-Fi se obtine cu regula (MP) din formulele Fh, Fkcu h, k < i.

Sirul (Θ) se numeste deductie simpla a formulei F din (lista) Θ, , iarformulele din Θ se numesc ipoteze auxiliare.

5

Daca Θ este formata din formulele E1, E2, . . . , Ek atunci ın loc de Θ ` Fvom nota E1, E2, . . . , Ek ` F sau simplu Θ`F. In general daca lista Θ esteformata din doua liste Θ1,Θ2 atunci notatiile Θ ` F si Θ1,Θ2 ınseamnaacelasi lucru. Daca Θ este vida atunci notam simplu `F.Remarca. Atunci cand nu este pericol de confuzie vom nota formulele

din Θ cu {F1, F2, . . . , Fk}Metateorema I (MTI).Oricare ar fi formulele A, B, C din L3 si oricare ar fi lista Θ de ipoteze

auxiliare afirmatiile (1), (2), (3) de mai jos sunt adevarate.(1) Daca (Θ `A si Θ `A →B) atunci Θ `B(2)Daca Θ `B atunci Θ ` A→B.Demonstratie.(1) Ipoteze:F1F2.. .Fm≡A; deductia simpla din Θ a formulei A;G1...Gn≡A→B; deductia simpla din Θ a formulei A→B;Deductia: H≡B; (MP): Fm, Gn.(2) Ipoteze:F1F2...Fm≡B; deductia simpla din Θ a formulei B;Deductia:G1≡B→(A→B); ax.logica (L1);G2≡A→B; (MP): Fm,G1;Remarca In cele ce urmeaza daca intr-o axioma sau o metateorema o

formula A se va substitui cu B vom nota A/B.Metateorema II (MTII).Daca A este o formula din L3 atunci `A →A

6

Demonstratie.F1≡(A →((A→A) →A) →((A →(A →A)) →(A →A)); B/A →A, C/A

in (L3);F2≡A →((A →A) →A); B/ A →A in (L1);F3≡((A →(A →A)) →(A →A)); (MP):F2, F1;F4≡A →(A →A); B/A in (L1);F5≡A →A ;(MP): F4, F3;Metateorema deductiei simple (DT). Daca Θ este o lista de formule

si A, B sunt formule din L3 si daca Θ,A `B atunci Θ`A→B.In particular daca A`B atunci `A→B.Demonstratie.Sa presupunem ca B este simplu deductibila din lista Θ,A adica Θ,A`B.Aceasta ınseamna ca exista un sir de formule F1, F2, . . . , Fn (Fn≡B) cu

proprietatea ca fiecare formula Fi, (1 ≤ i ≤ n) satisface una din conditiile:(a) Fi, apartine listei Θ(b) Fi, coincide cu A(c) Fi, este o axioma logica din lista (L1)-(L3)(d) Fi, se obtine din doua formule Fh, Fk, (h, k < i) cu ajutorul regulii

(MP).Vom demonstra prin inductie dupa indicele i, ca fiecare formula A→Fi

(deci si A→B) este simplu deductibila adica Θ`A→Fi oricare ar fi i(1 ≤ i ≤ n).Daca i=1 sa aratam ca Θ`A→Fi. Pentru formula F1, sunt posibileevident cazurile (a), (b), (c).(a) F1, apartine listei ΘH1≡F1;H2≡F1 →(A→F1); ax.(L1);H3≡A →F1; (MP): H1,H2;(b) F1≡A atunci A →A este (MTI),(2) si prin urmare Θ`A →A;(c) F1 este una din axiomele (L1)-(L3);H1≡F1;H2≡F1→(A →F1); ax.(L1);H3≡A →F1 ; (MP): H1,H2;Sa presupunem ca i > 1 si sa admitem ipoteza de inductieΘ`A →F1, Θ`A →F2,. . .,Θ`A →Fi−1Sa demonstram ca ın acest caz Θ`A →Fi.Daca Fi satisface cazurile (a), (b), (c) rationam ca si la cazul i=1. Sa

examinam cazul (d).

7

(d) Sapresupunem ca exista h, k < i ıncat Fk ≡Fh →Fi. In acest cazavem urmatoarea deductie simpla din Θ;F1≡A →Fh; ipoteza de inductie;F2≡A→(Fh→Fi); ipoteza de inductie;F3≡(A→(Fh→Fi))→((A →Fh) →(A→Fi)); ax.(L2)F4≡(A →Fh) →(A →Fi);; (MP): F2,F3;F5≡A →Fi; (MP):F1,F4;Aceasta metateorema este cunoscuta sub numele de metateorema luiHerbrand. Vom nota aceasta metateorema prin (DT).Metateorema III (MTIII).Oricare ar fi formulele A, B, C ale sistemului L3 au loc afirmatiile:(1) silogisme (sil)(a) A →B, B →C `A→C sau `(A →B) →((B →C) →(A→C))(b) B →C, A →B `A→C sau `(B →C) →((A →B) →(A→C))(2) permutarea premizelorA→(B →C) `B →(A →C) sau `(A→(B →C)) →(B →(A →C))(3) `(A →(A →B)) →(A →B)(4) `A →((A →B) →B)(5) `¬A →(A →B)Demonstratie.(1a) A →B, B →C `A→CF1≡A→B; ip.F2≡B→C; ip.F3≡A; ip.F4≡B; (MP):F3,F1;F5≡C;(MP):F4,F2;am obtinut deductia A →B, B →C, A `C si cu (DT) obtinem (a).Analog se obtin celelalte afirmatii.(2) permutarea premizelor`(A→(B →C)) →(B →(A →C))F1≡A→(B →C); ip.F2≡B; ip.F3≡A; ip.F4≡B →C;(MP):F3,F1F5≡C;(MP):F2,F4(3) `(A →(A →B)) →(A →B)F1≡A →(A →B); ip.F2≡A; ip.

8

F3≡A →B; (MP):F2,F1(4) `A →((A →B) →B)F1≡A; ip.F2≡A →B; ip.F3≡B; (MP):F1,F2(5) `¬A →(A →B)F1≡¬A; ip.F2≡A; ip.F3≡¬B →¬A; MTI. (2);F4≡F3 →(A →B); ax.(L3);F5≡A→B; (MP):F3,F4F6≡B; (MP):F2,F5Metateorema IV (MTIV).Oricare ar fi formulele A, B, C ale sistemului L3 au loc afirmatiile:(1) `¬¬A →A(2) `A →¬¬A(3) `(A →B) →(¬B →¬A)(4) `A →(¬B →¬(A →B))(5) `(¬B →¬A) →((B →C) →(A →C))(6) `(¬B →¬B) →((B →C) →(A →C))(7) `(¬B →B) →((¬B →B) →B)(8) `(¬B →B) →B(9) `(A →B) →(( ¬A →B) →B)Demonstratie.(1) `¬¬A →AIn MTIII (sil) (B →C) →((A →B) →(A→C))vom substitui A cu ¬¬A notata A/¬¬A apoi B/¬A →¬¬¬A,C/¬¬A →A - F1F1≡((¬A →¬¬¬A) →(¬A →A)) →→((¬¬A →(¬A →(¬A →¬¬¬A)) →→(¬¬A →(¬¬A →(¬¬→A))In (L3) (¬B →¬A) →(A →B)B/A, A/¬¬A - F2F2≡(¬A →¬¬¬A) →( ¬¬A →A)F3≡((¬¬A →(¬A →(¬A →¬¬¬A)) →→(¬¬A →(¬¬A →(¬¬→A)); (MP):F2,F1In (L3) (¬B →¬A) →(A →B)B/A, A/¬¬A - F4

9

F4≡((¬¬A →(¬A →(¬A →¬¬¬A))In MTIII (2) A/¬A, B/¬¬¬A - F5F5≡(¬¬A →(¬A →(¬A →¬¬¬A)F6≡¬¬A →(¬¬A →(¬¬→A); (MP):F5,F3In MTIII (3) (A →(A →B)) →(A →B)A/¬¬A, B/A - F7F7≡(¬¬A →(¬¬A →A)) →(¬¬A →A)F8≡¬¬A →A(2) `A →¬¬AIn (L3) (¬B →¬A) →(A →B)B/¬¬A - F1F1≡(¬¬¬A →¬A) →(A →¬¬A)In (1) ¬A ¬→A , A/¬A - F2F2≡¬¬¬A →¬AF3≡A →¬¬A;(MP):F2,F1(3) `(A →B) →(¬B →¬A)F1≡A →B; ip.F2≡¬B; ip.F3≡¬A ¬→A; (1) de mai susF4≡¬A ¬→B; (sil):F3,F1F5≡B →¬¬B; (2) de mai sus cu A/BF6≡¬¬A →¬¬B; (sil):F4,F5In (L3) (¬B →¬A) →(A →B)B/¬A, A/¬B - F7F7≡(¬¬A →¬¬B) →(¬B →¬A);F8≡¬B →¬A; (MP):F6,F7F9≡¬A; (MP):F2,F8Avem deductia A →B, ¬B `¬A si cu (DT) obtinem (3)(4) `A →(¬B →¬(A →B))F1≡A →((A →B) →B) ; MTIII (4); In (3) de mai sus A/A →B - F2F2≡((a →B) →B) →(¬B →¬(A →B))F3≡A →(¬B →¬(A →B));(sil):F1,F2(5) `(¬B →¬A) →((B →C) →(A →C))F1≡¬B →¬A; ip.F2≡B →C; ip.F3≡(¬B →¬A) →(A →B);(L3)F4≡A →B; (MP):F1,F3F5≡A →C; (sil):F4,F2

10

(6) `(¬B →¬B) →((B →C) →(A →C))In (B →C) →((A →B) →(A →C))A/¬B →B, B/¬B →¬A, C/(B →C) →(A →C)F1≡((¬B →¬A) →((B →C) →(A →C)) →(((¬B →B) →(¬B →¬A)) →((¬B →B) →((B →C) →(A →C)))F2≡(¬B →¬A) →((B →C) →(A →C)); (5) de mai susF3≡((¬B →B) →(¬B →¬A)) →((¬B →B) →((B →C) →(A →C));

(MP):F2,F1F4≡(¬B →B) →(¬B →¬A)

G1≡¬B →B; ip.G2≡¬B; ip.G3≡¬B →(B →¬A); MTIII (5) A/B, B/¬AG4≡B; (MP):G2,G1G5≡B →¬A; (MP):G2,G3G6≡¬A; (MP):G4,G5

F5≡(¬B →B) →((B →C) →(A →C): (MP):F4,F5(7) `(¬B →B) →((¬B →B) →B)In permutarea premizelor MTIII (2) (A→(B →C)) →(B →(A →C))A/¬B →B, B/B →B, C/ (¬B →B) →B - F1F1≡((¬B →B) →((B →B) →((¬B →B))→→((B →B) →((¬B →B) →((¬B →B) →B)))In (6) de mai sus A/¬B →B, C/B - F2F2≡(¬B →B) →((B →B) →((¬B →B) →B))F3≡(B →B) →((¬B →B)→((¬B →B) →B)); (MP):F2, F1F4≡B →B; MTII A/BF5≡(¬B →B)→((¬B →B) →B)(8) `(¬B →B) →BIn MTIII (3) (A →(A →B)) →(A →B)A/¬B →B - F1F1≡((¬B →B) →((¬B →B) →B)) →→((¬B →B) →B)F2≡(¬B →B) →((¬B →B)→B); (7) de mai susF3≡(¬B →B) →B; (MP):F2, F1(9) `(A →B) →(( ¬A →B) →B)F1≡A →B; ip.F2≡¬A →B; ip.F3≡(A →B) →(¬B →¬A); (3) de mai susF4≡¬B →¬A; (MP):F1,F3

11

F5≡¬B →B; (sil):F4, F2F6≡(¬B →B) →B; (8) de mai susF7≡B; (MP):F5,F6Metateorema V (MTV).Oricare ar fi formulele A, B, C ale sistemului L3 au loc afirmatiile:(1) A, B `A ∧B (∧- int)(2) A ∧B `A (∧- el)A ∧B `B (∧- el)(3) A, A↔B `B (MPE)(4) A ↔B, B ↔C `A ↔C (sile)Demonstratie.(1) A, B `A ∧BTranscriem A ∧B ≡¬(A →¬B)F1≡A; ip.F2≡B; ip.In MTIII (4) A →((A →B) →B)B/¬B - F3F3≡A →((A →¬B) →¬B)F4≡(A →¬B) →¬B; (MP):F1,F3F5≡F4 →(B →¬(A →¬B)); MTIV (3)F6≡B →¬(A →¬B); (MP):F4,F5F7≡¬(A →¬B); (MP):F2,F6(2) A ∧B `B (∧- el) ; pentru A analog;F1≡A ∧B; ip.F2≡¬(A →¬B); transcriere F1F3≡¬B →(A →¬B); ax.(L1)F4≡F3 →(¬(A →¬B) →¬¬B); MTIV (3)F5≡¬(A →¬B) →¬¬B; (MP):F3,F4F6≡¬¬B; (MP):F2,F6F7≡¬¬B →B; MTIV (1) A/BF8≡B; (MP):F6,F7(3) A, A↔B `B (MPE)F1≡A; ip.F2≡A↔B; ip.F3≡(A →B) ∧(B →A); transcriere F2F4≡A →B; (∧) - el F3F5≡B; (MP):F1,F4

12

1.3 Necontradictia si completitudinea calcului propozitional

Fie multimea B = {0,1} dotata cu operatiile :Negatia: 0 = 1, 1 = 0x ∨ y ≡ x+ y = sup{x, y}x ∧ y ≡ x ∗ y = inf{x, y}Multimea B cu aceste operatii formeaza o algebra Boole.Definitia (1.7) Multimea aplicatiilor f : Bn → B, se numeste multimea

functilor boolene de n variabile.Definitia (1.8) Pentru variabilele x1, x2, . . . xn ∈ B avem:(¬f)(x1, x2, . . . , xn) = f(x1, x2, . . . , xn)(f →g)(x1, x2, . . . , xn) = f(x1, x2, . . . , xn) + g(x1, x2, . . . , xn)Vom construi modelarea booleana a formulelor din L3, prin inductie:- F ≡Xi atunci fF = xi- F ≡¬G atunci fF = fG- F ≡G →H atunci fF = fG + fHDefinitia (1.9) O formula din L3, se spune tautologie daca fF = 1

pentru orice valori ale variabilelor xi din B.Remarca. Tautologiile fundamentale sunt L1, L2, L3Metateorema VI (MTVI).Daca F, F →G sunt tautologii atunci G este tautologie.Demonstratie.Daca F, F→G sunt tautologii atunci fF = 1, fF→G = 1 Deoarece fF→G =

fF + fG = 1. obtinem 0 + fG = 1, deci fG = 1Definitia (1.10)

F σ =

{F, σ = 1¬F, σ = 0

Metateorema VII (MTVII).Fie F = F (X1, X2, . . . , Xk) atunci

X1σ, X2

σ, . . . , Xkσ ` F σ

Demonstratie.Prin inductie pentru n=1 F = X1 si avemX1 ` X1 ¬X1 ` ¬X1 caz trivial. Presupunem ca teorema are loc pentru

lungimi ale lui F mai mici ca n. Daca:Cazul 1) F≡¬G atunci

13

1a) Presupunem Gσ = G atunci F σ = ¬F

X1σ, X2

σ, . . . , Xkσ ` G

dar cum `G→¬¬G MTIII (2) cu (MP) avem

X1σ, X2

σ, . . . , Xkσ ` ¬¬G

deciX1σ, X2

σ, . . . , Xkσ ` ¬F = F σ

1b) Presupunem Gσ = ¬G atunci F σ = ¬G

X1σ, X2

σ, . . . , Xkσ ` Gσ = F = F σ

Cazul 2) F≡G →H cu ipotezele inductei avem

X1σ, X2

σ, . . . , Xkσ ` Gσ

X1σ, X2

σ, . . . , Xkσ ` Hσ

2a) Gσ = ¬G, atunci σ = 0 pentru G rezulta atunci ca σ, pentru Feste 1 (caci 0 →0 = 1 si 0 →1 = 1) deci F σ = F

X1σ, X2

σ, . . . , Xkσ ` ¬G

dar MTIII (5) `¬G →(G →H) si cu (MP) avem

X1σ, X2

σ, . . . , Xkσ ` G→ H = F σ

2b) Hσ = H, atunci evident F σ = F (avem 0 →1 = 1 si 1 →1 = 1)

X1σ, X2

σ, . . . , Xkσ ` H

cu ax. L1 avem H →(G →H) deci cu (MP) avem

X1σ, X2

σ, . . . , Xkσ ` G→ H = F = F σ

2c) Presupunem Gσ = G, si Hσ = ¬H, deci σ pentru G are valoare 1iar pentru H are valoare 0 in conseciinta pentru F are valoare 0 (1 →0 =0)prin urmare F σ = ¬F

X1σ, X2

σ, . . . , Xkσ ` G

X1σ, X2

σ, . . . , Xkσ ` ¬H

14

dar avemMTIV (4) `G →(¬H →¬(G →H)) si cu (MP) de doua ori obtinem

X1σ, X2

σ, . . . , Xkσ ` ¬(G→ H) = ¬F = F σ

Metateorema de completitudineDaca formula F din L3, este tautologie atunci ea este teorema a lui L3.Demonstratie.Fie F o tautologie atunci cu metateorema precedenta avem

X1σ, X2

σ, . . . , Xkσ ` F = F σ

Deci avemX1σ, X2

σ, . . . , Xk ` F

X1σ, X2

σ, . . . ,¬Xk ` F

cu (DT) obtinemX1σ, X2

σ, . . . , Xk−1σ ` Xk → F

X1σ, X2

σ, . . . , Xk−1σ ` ¬Xk → F

Dar avem MTIV (9) `(Xk → F )→ ((¬Xk → F )→ F ))cu (MT) de doua ori avem

X1σ, X2

σ, . . . , Xk−1σ ` F

Repetand procedeul dupa k pasi obtinem `F.Metateorema de necontradictie.Sistemul L3 este necontradictoriu.Demonstratie.Daa L3 ar fi contradictoriu atunci avem in L3 `F si `¬F atunci cu

MTIII (5) `¬F →(F →X)cu (MP) de doua ori obtinem ca `X adica o litera X este teorema ceace

este absurd.

1.4 Independenta sistemului calcului propozitional

Definitia 1.12 O submultime Δ de axiome a unei teorii axiomatice senumeste independenta daca fiecare formula din Δ nu poate fi dedusa curegulile de deductie din axiomele care nu intra in Δ.

15

Metateorema VIII (MTVIII).

Fiecare din axiomele (L1) - (L3) sunt independente.

Demonstratie.

1) Independenta lui (L1) A →(B →A)Definim f(¬A) = ¬f(A) si f(A→ B) = fA → fB dat prin tabelele:Consideram urmatoarele tabele:fA ¬fA0 11 12 0

→ 0 1 20 0 2 21 2 2 02 0 0 0

Daca o formula A primeste valoarea 0 atunci ea se spune separata.

De exemplu (MP) pastreaza proprietatea de separatie

fA = 0, fA→B = 0, dar

fA→B = fA → fB = 0 deci fB = 0Axiomele (L2) si (L3) sunt separate dar (L1) nu.

Fie fA = 1, c si fB = 2 atunci 1 →(2 →1) = 1 →0 = 22) Independenta lui (L2)

Definim f(¬A) = ¬f(A) sif(A→ B) = fA → fB dat prin tabelele:Consideram urmatoarele tabele:fA ¬fA0 11 02 1

→ 0 1 20 0 2 11 0 2 02 0 0 0

(MP) este separata fA = 0, si fA→B = 0 rezulta analog ca la 1) ca fB = 0,se verifica usor ca (L2) nu are loc daca fA = 0, fB = 0, fC = 1, deoarece

fL2 = (0 →(0 →1)) →( (0 →0) →(0 →1)) == (0 →2) →(0 →2) == 1 →1 = 23) Independenta lui (L3)

Definim f(¬A) = f(A) = fA,f(A →B) = f(A) →f(B) =fA → fBcu tabelele:fA ¬fA0 01 1

→ 0 10 1 11 0 1

(L1) si (L2) devin tautologii ın timp ce (L3) devine

16

fL3 = f(B→A)→(A→B) == (fB → fA)→ (fA → fB)

Cu fB = 0, si fA = 1, fL3 = (0 →1) →(1 →0) = 1 →0 = 0

17

2 Calculul restrans al predicatelor.

2.1 Limbajul calcului restrans al predicatelor.

Definitia (2.1).Ansamblul semnelor din lista (a)-(c) se numestealfabetul (formal) al calcului restrans al predicatelor.(a) Simboluri de variabile X1, X2, . . . , Xn, . . . sau notate uneoriX, Y,... etc.(b) Simbolurile operatorilor si cuantificatorilor logici¬,→,∃, ∀.(c) Simbolurile ortograficeSimbolurile parantezelor ”(”, ”)”Remarca 1. Simbolurile ”

∨” (sau), ”

∧” (si), ”↔” (echivalenta) sunt

simboluri derivate si se introduc cu definitia din Cap.2.1Remarca 2. Vom nota limbajul calcului restrans sl predicatelor cu L.Definitia (2.2). Orice secventa finita de semne liniare (distincte sau nu)

ale alfabetului L se numeste asamblaj.Un asamblaj se poate reduce ın particular la un singur simbol liniar.Definitia (2.3). Un sir finit de asamblajeF1, F2, . . . , Fn; (n ≥ 1)se numeste sir formativ (sau constructie formativa ın formule, daca

pentru fiecare indice i (1 ≤ i ≤ n), asamblajul Fi, satisface una din conditiile:(1) este variabila(2) exista un indice j < i, ıncat

Fi ≡ ¬(Fj)

(3) exista doi indici h, k < i, ıncat

Fi ≡ (Fh)→ (Fk)

(4) Exista un indice j < i, si o variabila X continuta ın Fj, astfel caFi ≡ ∃X(Fj), sau Fi ≡ ∀X(Fj)

Orice asamblaj F pentru care exista o construtie formativa cu Fn = F ,se numeste formula.Definitia (2.4). Ansamblul tuturor formulelor lui L, se numeste lim-

bajul (formal) al calcului restrans al predicatelor de prim ordin.Formula lui L

18

Fie E un asamblaj oarecare din L. Asamblajul E este o formula a lui L,daca si numai daca:(i) E este o variabila Xi(ii) exista o formula unic determinata ıncıt

E ≡ ¬(F )

(iii) exista doua formule F, G unic determinate ıncat

E ≡ (F )→ (G)

(iv) exista o formula F iar printre variabilele continute ın F exista o variabilaX unic determinata ınat

E ≡ ∃X(F )

sauE ≡ ∀X(F )

2.2 Axiomele calcului restrans al predicatelor.

Definitia (2.5).(a) Se numesc axiome logice toate formulele care se pot obtine din

urmatoarele formule generale, numite scheme.(L1) A →(B →A)(L2) (A →(B →C)) →((A →B) →(A →C))(L3) (¬B →¬A) →(A →B)(L4) F (Xi)→∃XjF (Xj), Xi, este liber pentru Xjsau uneori F ((Xi|Xj))→∃XjF (Xj)(L5) ∀XjF (Xj)→F (Xi), Xi, este liber pentru Xjsau uneori ∀XjF (Xj)→F ((Xi|Xj)) ın aceste scheme A, B, C, F(X) reprezinta

formule arbitrare.(b) Fie F o formula oarecare din L; zicem ca F este o teorema logica si

notam `F daca exista ın L, un sir finit de formule(δ) F1, F2, . . . , Fn; (n ≥ 1)ıncat Fn≡F si avand proprietatea ca pentru orice indice i (1 ≤ i ≤ n)

formula Fi, satisface cel putin una din conditiile:(D1), Fi, este o axioma logica ;(D2), Fi, este obtinuta prin substitutie din o formula precedenta;(D3), exista doi indici h, k < i, ıncat

19

Fk≡Fh→Fiın acest caz zicem ca Fi, se obtine din formulele Fh, si Fh→Fk, prin regula

modus ponens notata (MP);(D4), exista un indice j < i, ıncat:Fj ≡F(X) si Fi ≡∀XF(X)si spunem ın acest caz ca Fi, este obtinuta din Fj, prin regula intro-

ducerii cuantificarii universale notata (Gen)Sirul (δ) se numeste demonstratie logica(formala) a formulei Fn≡F iar

conditiile (D1)-(D4) se numesc reguli de deductie ale calcului restrans alpredicatelor.Definitia deductiei simple cu ipoteze auxiliare.Fie Θ o lista arbitrara (eventual vida) de formule si F o formula oare-

care (continuta sau nu ın lista Θ). Vom zice ca formula F este simpludeductibila din lista Θ,si notam Θ`F daca exista un sir de formule(θ) : F1, F2, . . . , Fn; (n ≥ 1)cu Fn≡F si avand proprietatea ca oricare ar fi indicelei (1 ≤ i ≤ n), formula Fi, satisface una din conditiile urmatoare:(1) Fi, este formula din lista Θ;(2) Fi, este o axioma logica ;(3) Fi, se obtine cu regula (MP din doua formule Fh, si Fk,

cu h, k < i.sirul (θ), se numeste deductie simpla a formulei F din lista Θ, iar for-

mulele din lista Θ,se numesc ipoteze auxiliare.Remarca 1. Deoare (L1)-(L5) sunt axiomele sistemului L, toate meta-

teoremele si conseciintele sistemului L, raman valabile si ın sistemul L.Metateorema IX (MTIX).Daca F este o formula care nu contine variabila X din L, si G(X) este o

formula din L, atunci au loc afirmatiile:(1) `F→∀XF(2) `∃XF→F(3) `∃X[G(X)↔G(X)](4) `[F

∧∀XG(X)]↔∀X[F

∧G(X)]

(5) `[F∧∃XG(X)]↔∃X[F

∧G(X)]

(6) `∀X[F→G(X)]→[F→∀XG(X)]ın particular avem regula introducerii cuantificari universalenotata (→ ∀)

F → G(X) ` F → ∀XG(X); (→ ∀)

20

(7) `∀X[G(X)→F]→[∃XG(X)→F]ın particular avem regula introducerii cuantificari existentialenotata (∃ →)

G(X)→ F ` ∃XG(X)→ F ; (∃ →)

Demonstratie.(1)F1≡F→F; tautologie;F2≡F→∀XF; (→∀):F1,X;(2)F1≡F→F; tautologieF2≡∃XF→F;(∃→):F1;(3)F1≡G(X)↔G(X);tautologie;F2≡F1→∃XF1; ax.(L4);F3≡∃XF1; (MP): F1,F2; (4)F1≡∀XG(X)→G(X); ax.(L5);F2≡F1→[ (F

∧∀XG(X))→(F

∧G(X))];

tautologia (A→B)→((C∧A)→(C

∧B));

F3≡[F∧∀XG(X)]→[F

∧G(X)]; (MP): F1,F2;

F4≡[F∧∀XG(X)]→∀X[F

∧G(X)];(→∀):F3,X;

F5≡∀X[F∧G(X)]→[F

∧G(X)]; ax.(L2);

F6≡F∧G(X)→F;tautologie;

F7≡F∧G(X)→G(X); tautologie;

F8≡∀X[F∧G(X)]→F; (sil):F5,F6;

F9≡∀X[F∧G(X)]→G(X); (sil):F5,F7;

F10≡∀X[F∧G(X)]→∀XG(X); (→∀):F9,X;

F11≡F8→[F10→[∀X[F∧G(X)]→[F

∧∀XG(X)]]];

tutologia (A→B)→((A→C)→(A→(B∧C)));

F12≡F10→[∀X[F∧G(X)]→[F

∧∀XG(X)]]; (MP): F8,F11;

F13≡∀X[F∧G(X)]→[F

∧∀XG(X)]; (MP): F10,F12;

F14≡F4→[F13→(F4∧F13)]; tautologie;

F15≡F13→(F4∧F13); (MP): F4,F14;

F16≡F4∧F13; (MP): F13,F15;

F17≡[F∧∀XG(X)]↔∀X[F

∧G(X)]; transcriere F16;

(5)F1≡[F

∧G(X)]→∃[F

∧G(X)]; ax.(L4);

21

F2≡G(X)∧F→F

∧G(X); tautologie;

F3≡G(X)∧F→∃X[F

∧G(X)];(sil)F2,F1;

F4≡F3→[G(X)→[F→∃X[F∧G(X)]];

tautologia (A∧B→C)→(A→(B→C));

F5≡G(X)→[F→∃X[F∧G(X)]; (MP): F3,F4;

F6≡∃XG(X)→[F→∃X[F∧G(X)];(∃→):F5,X;

F7≡F6→[∃XG(X)∧F→∃X[F

∧G(X)]];tautologie;

F8≡∃XG(X)∧F→∃X[F

∧G(X)]; (MP): F6,F7;

F9≡F∧∃XG(X)→∃XG(X)

∧F;tautologie;

F10≡F∧∃XG(X)→∃X[F

∧G(X)]; (sil):F9,F8;

F11≡G(X)→∃XG(X); ax.(L1);F12≡F11→[[F

∧G(X)]→[F

∧∃XG(X)]];tautologie;

F13≡[F∧G(X)]→[F

∧∃XG(X)]; (MP): F11,F12;

F14≡∃X[F∧G(X)]→[F

∧∃XG(X)]; (∃→):F13,X;

F15≡F8→[F14→(F8∧F14)];tautologie ;

F16≡F14→(F8∧F14); (MP): F8,F15;

F17≡F8∧F14; (MP): F14,F16;

F18≡[F∧∃XG(X)]↔∃X[F

∧G(X)]; transcriere F17;

(6)F1≡∀X[F→G(X)]→[∀XF→∀XG(X)]; tautologie;F2≡F1→[∀XF→[[∀X[F→G(X)]→∀XG(X)]];tautologia (A→(B→C))→(B→(A→C));F3≡∀XF→[[∀X[F→G(X)]→∀XG(X)]]; (MP): F1,F2;F4≡F→∀XF; (1);F5≡F→[∀X[F→G(X)]→∀XG(X)]; (sil):F4,F3;F6≡F5→[∀X[F→G(X)]→[F→∀XG(X)]];tautologia (A→(B→C))→(B→(A→C));F7≡∀X[F→G(X)]→[F→∀XG(X)]; (MP): F5,F6;(7)F1≡∀X[G(X)→F]→[∃XG(X)→∃XF]; tautologie;F2≡∃XF→F; (2) de mai sus;F3≡F2→[[∃XG(X)→∃XF]→[∃XG(X)→F]];tautologie;F4≡[∃XG(X)→∃XF]→[∃XG(X)→F]; (MP): F2,F3;F5≡∀X[G(X)→F]→[∃XG(X)→F]; (sil):F1,F4.Metateorema X (MTX). (∀-el)In calculul restrans al predicatelor are loc urmatoarea afirmatie:Daca `∀XF(X) atunci `F(X)Demonstratie.

22

F1≡∀XF(X); ip.aux.;F2≡∀XF(X)→F(X); ax.(L5);F3≡F(X); (MP): F2,F2;

2.3 Deductia ın calculul restrans al predicatelor

Definitia (2.6).Fie Q o formula care apartine unei multimi de formule Γ si fieP1,P2,. . .,Pn o deductie din Γ vom spune ca Pi depinde ın deductie de

Q daca:(i) Pi ≡Q sau(ii) Pi este o conseciinta imediata cu (MP) sau Gen a unor formule prece-

dente din deductie din care una depinde de Q.Exemplu. A, ∀XA →C ` ∀CP1≡A; ip.P2≡∀XA; ip.P3≡∀XA →C; ip.P4≡C; (MP):P2, P3P5≡∀XC; (Gen):P4P1 depinde de A, P2 depinde de A, P3 depinde de ∀XA →C,P4 depinde de A si ∀XA →CMetateorema dedutiei pentru calculul restrans al predicatelor.(DT)1) Daca R nu depinde de Q ın deductia Γ,si Q ` Ratunci Γ ` Q → R;2) Daca suntem ın calculul restrans al predicatelor atunci (cf.[1]) avem:Fie Γ, Q ` R, ın care exista o deductie a lui R din {Γ, Q}, ın care reg-

ula (Gen) utilizata la formule care depind ın deductie de Q nu leaga nici ovariabila libera din Q, atunci Γ ` Q → R.3) Sa consideram cazurile (cu toate restrictiile impuse mai sus) ın pasul

inductiei (demonstratia se face prin inductie).Daca P1, P2, . . . , Pn ` Q→ R si F1, F2,. . , Fs sunt pasii demonstratiei

atunci noi luam Q→ F1, Q→ F2,...,Q→ Fs ca pasi ın demonstratia luiP1, P2,...,Pn ` Q → R, cheia inductiei consta ın a demonstra de fiecare

data Q →Fi;Avem urmatoarele cazuri relative sistemului restrans al predicatelor:(a) Fi≡∃XF(X) →C, X nu apare liber ın C(b) Fi≡C →∀XF(X)(c) Fi≡∀XF(X)

23

Demonstratie.(a)F1≡..Fm≡Q→[F(X)→C]; deductia pana aici cu Q→Fj; (j < i);G1≡F(X)→[Q→C];(perm):Fm;G2≡∃XF(X)→[Q→C]; (∃ →):G1;G3≡Q→[∃XF(X)→C]; (perm):G2;G4≡Q→Fi; transcriere G3;(b)F1≡..Fm≡Q→[C→F(X)];deductia pentru Q→Fj;G1≡Q→∀X[C→F(X)];( (→ ∀)1 );G2≡∀X[C→F(X)]→[C→∀XF(X)];(MT1.5);G3≡Q→[C→∀XF(X)]; (sil):G1,G2;Q→[C→∀XF(X)]; (sil):G1,G2;(c)F1≡..Fm≡Q→F(X); deductia pentru Fj;G1≡Q→∀XF(X);( (→ ∀)1 ):Fm;G2≡Q→Fi;transcriere G1;Exemplu. `∀X∀YA →∀Y∀XAF1≡∀X∀YA; ip.F2≡∀X∀YA →∀YA; L5F3≡∀YA; (MP):F1, F2F4≡∀YA →A; L5F5≡A; (MP):F3,F4F6≡∀XA; (Gen):F5F7≡∀Y∀XA; (Gen):F6Metateorema echivalentei[1](1) Fie Xi 6= Xj formula F (Xi) se spune asemenea cu F (Xj) daca Xj

apare ın loc de Xi atunci `∀XiF (Xi)≡∀XjF (Xj)

24

(2) Daca B este o subformula a lui A, si A’ este rezultatul substitutei ınA formulei B cu C, si fiecare variabila libera a formulei B sau C care suntvariabile legate a formulei A se gasesc ın Y1, Y2, . . . Yn atunci

` [∀Y1 . . . Yn(B ↔ C)]→ (A↔ A′)

(3) (substitutia) Fie A, B, A’, C (din (2)):a) Daca `B↔C atunci `A↔A’b) Daca `B↔C si `A atunci `A’

(4)`∀X∀YF ↔∀Y∀XF(5)`∃X∃YF ↔∃Y∃XF(6)`¬∃XF ↔∀X¬F(7)`¬∀XF ↔∃X¬F(8)`¬∃X ¬F(X) ↔∀XF(X)(9)`¬∀X ¬F(X) ↔∃XF(X)Demonstratie.(1)F1≡∀XiF (Xi)→F (Xj); (L5)F2≡∀XjF1; (Gen):F1;F3≡F2 →( ∀XiF (Xi) →∀XjF (Xj));

G1≡F2; ip.G2≡∀XiF (Xi); ip.G3≡F1;(∀) - el:F2;G4≡F (Xj); (MP):G2,G3;G5≡∀XjF (Xj); (Gen):F3

F4≡∀XiF (Xi) →∀XjF (Xj): (MP):F2, F3analog se demonstreaza reciproca;F5≡∀XjF (Xj) →XiF (Xi);F6≡F4 →[F5 →(F4 ∧F5)] ; tautologieF7≡F5 →(F4 ∧F5); (MP):F4, F6F8≡F4 ∧F5; (M):F5, F7(2) prin inductie asupra lungimii formulei A;Cazul 1. A este formula elementara atunci B nu poate fi subformula.Cazul 2. A↔¬D, atunci A’↔¬D’Cu presupunerea imductiva avem ipotezele:F1≡A↔¬D; ip.F2≡A’↔¬D’; ip.F3≡∀Y1 . . . Yk(B ↔ C)→ (D ↔ D′); ip.

25

F4≡(D ↔D’) →( ¬D ↔¬D’); tautologieF5≡∀Y1 . . . Yk(B ↔C) →(A ↔A’); (sile)F3, F4Cazul 3. A↔D →E, iar A’↔D’ →E’F1≡∀Y1 . . . Yk(B ↔ C)→ (D ↔ D′); ip.F2≡∀Y1 . . . Yk(B ↔ C)→ (E ↔ E ′); ip.cu tautologia ((A ↔B) ∧(C ↔D)) →(A →C)≡(B →D))obtinem F3≡∀Y1 . . . Yk(B ↔C) →(A ↔A’)Cazul 4 A↔∀XD , A’ ↔∀XD’F1≡∀Y1 . . . Yk(B ↔ C)→ (D ↔ D′); ip.F2≡∀Y1 . . . Yk(B ↔ C)→ ∀(D ↔ D′);F3≡∀X(D ↔D’)→(∀XD ↔∀XD’);

G1≡∀X(D ↔D’); ip.G2≡∀XD; ip.G3≡D ↔D’; (∀)-el:F1G4≡D;(∀)- el G2G5≡(D ↔D’) →(D →D’);tautologieG6≡D →D’;(MP)G3, G5G7≡D’; (MP:G4, G6G8≡∀D’; (Gen):G7

F4≡∀Y1 . . . Yk(B ↔ C)→ (∀XD ≡∀XD’);(sile):F1, F4(4)`∀X∀YF ↔∀Y∀XFF1≡∀X∀YF;ip.F2≡∀YF; (∀)::F1F3≡F;(∀)::F2F4≡∀XF; (Gen):F4F5≡∀Y∀XF; (Gen):F4(5)`∃X∃YF ↔∃Y∃XFF1≡∃X∃YF;ip.F2≡F →∃XF; (L4)F3≡∃XF →∃Y∃XF ; (L4)F4≡F →∃Y∃XF; (sil): F3,F4F5≡∃YF →∃Y∃XF; (∃ →):F4F6≡∃X∃YF →∃Y∃XF; (∃ →):F5F7≡∃Y∃XF; (MP):F1, F6(6)`¬∃XF ↔∀X¬FF1≡¬∃XF ;ip.F2≡F →∃XF; (L4)F3≡F2 →(¬∃XF →¬F);tautologia (A→B) →(¬B →¬A)

26

F4≡¬∃XF →¬F; (MP):F2, F3F5≡¬F; (MP):F1, F4F6≡∀X¬F; (Gen):F5

G1≡∀X ¬F; ip.G2≡∀X¬F →¬F;(L5)G3≡G2 →(F →¬∀X ¬F); tautologia (A →¬B) →(B →¬A)G4≡F →¬∀X ¬F; (MP):G2, G3G5≡∃XF →¬∀X ¬F;(∃ →):G4G6≡G5 →(∀X¬F →¬∃XF); tautologia (A →¬B) →(B →¬A)G7≡∀X¬F →¬∃XF; (MP):G5, G6G8≡¬∃XF;(MP):G1, G7

(7)`¬∀XF ↔∃X¬FF1≡¬∀XF;ip.F2≡¬F →∃X¬F; (L4)F3≡F2 →(¬∃X¬F →F);tautologia (¬A →B) →(¬B →A)F4≡¬∃X¬F →F; (MP):F2, F3F5≡¬∃X¬F →∀XF; (→ ∀):F4F6≡F5 →(¬∀XF →∃X¬F); tautologia (¬A →B) →(¬B →A)F7≡¬∀XF →∃X¬F; (MP):F5, F6F8≡∃X¬F; (MP):F1,F7

G1≡∃X ¬F; ip.G2≡∀XF →F;(L5)G3≡G2 →(¬F →¬∀XF); tautologia (A →B) →(¬B →¬A)G4≡¬F →¬∀XF; (MP):G2, G3G5≡∃X ¬F →¬∀XF;(∃ →):G4G6≡¬∀XF; (MP):G1, G5

(8)`¬∃X ¬F(X) ↔∀XF(X)F1≡¬F(X) →∃X ¬F(X); (L4)F2≡F1 →[¬∃X ¬F(X) →F(X)]; tau.(¬A →B) →(¬B →A)F3≡¬∃X ¬F(X) →F(X); (MP):F1, F2F4≡¬∃X ¬F(X) →∀F(X); (→∀)

G1≡∀XF(X) →F(X); (L5)G2≡G1 →[¬F(X) →¬∀XF(X)]; tau.G3≡¬F(X) →¬∀XF(X); (MP):G1, G2G4≡∃X¬F(X) →¬∀XF(X); (∃→)G5≡G4 →[∀XF(X) →¬∃X¬F(X)]; tau.G6≡∀XF(X) →¬∃X¬F(X); (MP):G4, G5

27

(9)`¬∀X ¬F(X) ↔∃XF(X)F1≡∀X¬F(X) ↔¬∃X ¬¬F(X); (8) cu ¬F(X)F2≡∀X¬F(X) ↔¬∃XF(X); tr. F1F3≡F2 ↔[∃XF(X) ↔¬∀X ¬F(X)]; tau.F4≡∃XF(X) ↔¬∀X ¬F(X); ; (MPE):F2, F3

2.4 Regula C

Regula care permite de a trece de la ∃XF(X) la F(b) se numeteregula C (C - prima litera de la choice - alegere)Definitia C - deductei Γ`CF daca si numai daca exista un sirG1, G2, . . . , Gn = F , astfel ca:(I) pentru orice i(i) Gi este axioma sau(ii) Gi este din Γ sau(iii) Gi rezulta cu (MP) sau (Gen) din formule precedente sau(iv) Gi ≡H(b) rezulta cu regula C din ∃XH(X), b o constanta noua.(II) Nu se foloseste la regula (Gen) la variabile care au folosit regula C.(III) F nu contine variabile constante utilizate cu regula C.Metateorema XI (MTXI). Daca Γ `C F atunci Γ ` FDemonstratie.Fie o C - deductie a formulei F din Γsi fie ın ordine formulele la care se

aplica C - deductia∃Y1C1(Y1), . . . , ∃YkCk(Yk)

iar constantele introdusec1, . . . , ck

atunci evidentΓ, C1(c1), . . . , Ck(ck) ` F

atunci ın conditiile de restrictie pentru (Gen) si regula C avem cu teorema(DT)

Γ, C1(c1), . . . , Ck−1(ck−1) ` Ck(ck)→ F

Inlocuind constanta ck, cu o variabila noua nemaiıntalnita ın deductie Z avem

Γ, C1(c1), . . . , Ck−1(ck−1) ` Ck(Z)→ F

cu (Gen) avem

Γ, C1(c1), . . . , Ck−1(ck−1) ` ∀Z(Ck(Z)→ F )

28

Dar din MTIX (7) `∀X[G(X)→F]→[∃XG(X)→F]avem atunci `∀Z(Ck(Z) →F) →(∃ZCk(Z) →F) cu(sil) avem

Γ, C1(c1), . . . , Ck−1(ck−1) ` ∃ZCk(Z)→ F

sau

Γ, C1(c1), . . . , Ck−1(ck−1) ` ∃YkCk(Yk)→ F

Asa cum

Γ, C1(c1), . . . , Ck−1(ck−1) ` ∃YkCk(Yk)

cu (MP) avem

Γ, C1(c1), . . . , Ck−1(ck−1) ` F

Procedeul se continua si dupa k pasi avem ` F.Observatie. Am notat variabilele ck pentru pentru a le distinge de for-

mulele Ck.Exemplu. `∀X(F(X) →G(X)) →(∃XF(X) →∃XG(X))F1≡∀X(F(X) →G(X)); ip.F2≡∃XF(X); ip.F3≡F(b); (reg.C ) :F2F4≡F(b) →G(b); (∀) - el:F1F5≡G(b);(MP):F3,F4

G1≡∀X ¬G(X) →¬G(b); (∀) - L5cu tautologia (A →¬B) →(B →¬A) si (MP)G2≡G(b) →∃XG(X)

F6≡G(b) →∃XG(X);F7≡∃XG(X); (MP):F5, F6F8≡∀X(F(X) →G(X)), ∃XF(X) `∃XG(X)cu (DT) rezulta afirmatia.

2.5 Necontradictia si completitudinea calcului restransal predicatelor

Fie W multimea variabilelor din calculul restrans al predicatelor.

W = {X1, X2, . . . , Xn, . . .}

29

Fie algebra Boole B = {0, 1} si o aplicatie

s :W → B

cu s(Xi) = bi

Σ = {(b1, b2, . . .)|bi ∈ B}

multimea unor astfel de siruri.Definitia (2.7)Inductiv se defineste ce ınseamna ca o formula sa fie ındeplinita sub

aceasta interpretarePrin abuz de notatie fie s = (b1, b2, . . .)Notam (i) F≡Xi o variabila atunci s(Xi) = bi(ii) F≡¬G e ındeplinita pe s daca G nu e ındeplinita pe s.(iii) F≡G →H e ındeplinita pe s daca G nu e ındeplinita pe s sau H e

ındeplinita pe s.(iv) F≡F (X1, X2, . . . , Xn) cu variabilele libere W = {X1, X2, . . . , Xn} cu

(s ◦W )(h) = s(W (h)); 1 ≤ h ≤ n

Formula este ındeplinita pe s daca oricare ar fi sirul t t = (c1, c2, . . .)ci ∈ B, ci = t(Xi) astfel ca

(s ◦W )(h) = (t ◦W )(h)

(v) F≡∀XG(X) ındeplinita pe s daca G e ındeplinita pe s daca ea eındeplinita pe orice sir care nu difera de s nu mai mult de componenta i.Pentru orice formula F definim functia booleana ΦF (s) cu proprietatile:1) Φ¬G(s) = ΦG(s)2) ΦG→H(s) = ΦG(s) + ΦH(s)3) Φ∃XG(s) = sup(t◦W∃XG)=(s◦W∃XG)(ΦG(s))4) Φ∀XG(s) = inf (t◦W∀XG)=(s◦W∀XG)(ΦG(s))cu x + y = sup{x,y}, x*y = inf{x,y} ın algebra Boole.Observatie.1) Functia ΦF (s) , se defineste inductiv dupa lungimea formulei F.Daca F≡Xi atunci ΦF (s) = ΦXi(s) = s(Xi) = bi2) Daca

s ◦WF = t ◦WF =⇒ ΦF (s) = ΦF (t)

30

Daca WF = {X1, X2, . . . Xk} sunt variabilele din F avem

(s ◦WF )(h) = s(W (h))

(t ◦WF )(h) = t(W (h))

rezulta ΦF (s) = ΦF (t)3)Φ(Y |X)F = Φ((Y |X)s), deoarece

(Y |X)(s) = s(X), X 6= Y

(Y |X)(s) = s(Y ), X = Y

(Y |X)W (i) = W (i),W (i) 6= X

(Y |X)W (i) = Y,W (i) = X

rezulta ((Y |X)s) ◦W = s ◦ (Y |X)Wsi avem Φ(Y |X)F (s) = Φ((Y |X)s))Definitia (2.8)O formula F se spune adevarata daca ΦF (s) = 1 pe orice sir s din ΣDefinitia (2.9)O formula F e adevarata ın orice interpretare se numeste identitate

logica sau univeral adevarata notata |= F .Metateorema XII (MTXII).Orice teorema din calculul restrans al predicatelor este identitate logica.

` F =⇒|= F

Demonstratie.Se verifica usor axiomele si regulile de dedutie.Exemplu: ΦL1 = ΦA→(B→A) = ΦA + (ΦB + ΦA) = 1pentru (L5) ∀XF (X)→ F (Y )sau

∀XF (X)→ (Y |X)F (X)

avem ΦL5(s) = Φ∀XF (s) + Φ(Y |X)F (s)avem doa posibilitati :1) ΦF ((Y |X)s) = 1 si atunci ΦL5(s) = 12) ΦF ((Y |X)s) = 01 = ΦF ((Y |X)s) ≤ supt◦W∀XF=s◦W∀XFΦF (t) =

31

= inf t◦W∀XF=s◦W∀XFΦF (t) = ΦL5(s) deci ΦL5(s) = 1 Se verifica usor(MP) si (Gen).Metateorema de completitudine.In calculul restrans al predicatelor orice identitate logica este teorema.

|= F =⇒` F

Demonstratie.Evident vom folosi numai formule ınchise deoarece:Daca Γ `F(X) =⇒ Γ ` ∀XF(X) (Gen)Daca Γ `F(X) =⇒ cu (L4) si (MP) avem Γ ` ∃YF(Y)Prin inductie asupra lungimii formulei F.1) F≡¬G

|= F =⇒ ΦF (s) = 1

Sa presupunem prin absurd ca `¬F, sau `¬¬Gdar `¬¬G →G cu (MP) avem `G dar atunci ΦG(s) = 1, care e absurd

caci Φ¬G = 1 = ΦG(s) = 1 =⇒ ΦG(s) = 02) F≡G →H ΦG→H(s) = 1a) Presupun G falsa, ΦG(s) = 0 atunci ΦG(s) = 1Φ¬G(s) = 1 deci `¬G , dar cu tautologia `¬G →(G →H) cu (MP)avem `G →H = Fb) Daca H e adevarata atunci ΦH(s) = 1, sau `H cu axioma(L1) H →(G →H) cu (MP) avem `F.3) F≡∃XG cu ΦF (s) = 1

ΦF (s) = supt◦WF=s◦WFΦG(t)

deoarece exista t0 cut0 ◦WF = s ◦WF

ΦG(t0) = 1

cu surjectia s(Y) = t0(X) avem

(Y |X)s ◦WF = s ◦WF

(Y |X)s ◦WG = s ◦WG

Φ(Y |X)G(s) = ΦG(Y |X)(s) = ΦG(t0) = 1

32

dar prin ipoteza inductei avem `(Y |X)G din(L4) (Y |X)G →∃XG avem cu (MP) `∃XG = F4) F≡∀XG

1 = infΦG(t)t◦WF=s◦WF ≤ Φ(Y |X)G(s)

deciΦ(Y |X)G(s) = 1

Dar atunci `(Y |X)G si cu Gen `F.Metateorema de necontradictie.Calculul restrans al predicatelor este necontradictoriu.Demonstratie.Construim morfismul de coborare in calculul propozitional:h(X) = X daca X e variabilah(¬F) = ¬h(F)h(F →G) = h(F) →h(G)h(∀F) = h(F)h(∃F) = h(F)h(L1) - h(L5) devin tautologii in calculul propozitional.Daca F , F→G sunt teoreme ın calculul restrans al predicatelor atunci

h(F), h(F →G) devin tautologii si h(B) devine tautologie, deci e teorema.h(F) = h(∀XF) deci daca h(F) este tautologie atunci si h(∀XF) este tau-

tologie.In concluzie daca F este teorema ın calculul restrans al predicatelor h(F)

este tautologie.Daca ın calculul restrans al predicatelor am avea `¬F si `Fatunci cu `¬F →(F →X) cu de doua ori (MP) am obtine `X, unde X e

o variabila oarecare ceace e absurd.

2.6 Independenta calculului restrans al predicatelor

1) Independenta lui (L1) A →(B →A)Definim f(¬A) = ¬f(A) si f(A→ B) = fA → fBDefinim 0 = 1, 1 = 0, 2 = 3, 3 = 2si tabelul

33

→*0 —1 —2 —30 *0 —1 —1 —11 *0 —0 —0 —02 *0 —1 —0 —13 *1 —0 —0 —0h(L4) = h(L5) = F →F(L1) nu e separata caci 2 →(0 →2) = 12) Independenta lui (L2) si (L3) se face ca la calculul propozitional.3) Independenta lui (L4) Consideram multimea B = {0,1} dotata cu

operatiile :Negatia: 0 = 1, 1 = 0

→*0 —10 *1 —11 *0 —1(L4) F (Xi)→∃XjF (Xj), Xi, este liber pentru Xjaplicam morfismulh(L4) = h(F(X)→∃YF(Y))=F(X) →∀YF(Y);h(L5) = L5;si cu

f∃X(X) = sup[fF (X)]

f∀XF (X) = inf [fF (X)]

4) ca la cazul 3) cu morfismulh(L4) = L4h(L5) = ∃YF(Y) →F(X)

2.7 Calculul restrans al predicatelor cu egalitate

La calculul restrans al predicatelor se adauga predicatul ”=” si axiomele:(L6) ∀(X = X)(L7) (X = Y) →(F(X,X) →F(X,Y))X, Y variabile oarecare, F(X,X) o formula oarecare iar F(X,Y) obtinuta

prin F(X,X) prin substitutia (nu obligatorie) a variabilei libere X cu Y atuncicand Y e liber pentru X.Metateorema XIII (MTXIII).1) `X = Y →(Y = X)2) `X = Y →(Y = Z →X = Z) ; (sile)Demonstratie.

34

1) Fie F(X,X) ≡X = X c si F(X,Y) ≡Y = XF1≡X = Y; ip.F2≡X = Y →( X = X →Y = X); (L7)F3≡X = X →Y = X; (MP):F1, F@F4≡X = X ; (L6)F5≡Y = X ;(MP):F4, F32) Fie F(Y,Y) ≡Y = Z si F(Y,X)≡X = ZF1≡Y = X →(Y = Z →X = Z); (L7)F2≡X = Y →(Y = X) ; (1) precedent;F3≡X = Y →(Y = Z →X = Z); (sil):F2, F1Remarca Axioma (L7) poate fi presupusa numai pentru formule ele-

mentare si poate fi demonstrata prin inductie pentru formule ın general.

35

3 Teoria formala a dreptei

Acest capitol este o aplicatie a capitolelor precedente.

3.1 Axiomele abstracte.

1. Avem doua categorii de obiecte:- puncte A,B,C,. . . ,X,..- drepte a,b,c,. . . ,x,..Definitie (3.1).- R(A,x) Punctul A pe dreapta x.- R(A

∧B,a)≡R(A,a)

∧R(B,a)

- R(A,a∧b)≡R(A,a)

∧R(A,b)

- dAB≡R(A∧B,x)

- ABC Predicatul: punctele A, B , C in aceasta ordine pe o dreapta- ΔABC - punctele A, B si C nu sunt pe o dreapta.Segmentul A, B se considera ca [R(X,dAB)

∧AXB].

- dBC ∨.AB≡dBC 6= dAB

∧∃X[R(X,dBC)

∧AXB]

3.2 Axiomele de incidenta si ordine.

Axiomele de incidenta.I1) ∀A∃aR(A,a)I2) ∀a ∃A¬R(A,a)I3) ∀A∀a∀B∀b R(A,a

∧b)→¬R(B,a

∧b)

I4) ∃X∃Y[X 6=Y∧dXY ]

Axiomele de ordine:II1) ∀A∀B∀C∀d[R(A

∧B∧C,d)→(ABC→CBA)]

II2) ∀A∀B∀C[R(C,dAB)∧ABC]

II3) ∀A∀B∀C[R(A∧B∧C,d)→(ABC

∧ACB→B = C)]

3.3 Axioma lui Pash.

Pentru orice triunghi ΔABC

(d ∨.AB)→[(d ∨

.AC)

∨(d ∨

.BC)]

Reguli de deductie.

36

Amintim cateva reguli de dedutie stabilite ın capitolele prece-dente:1. Reguli:1) A, A→B `B;(MP)(modus ponens)2) A, B`A

∧B; (

∧-int);

3) A∧B `A (or B); (

∧-el);

4) A→B, B→C `A→C; (syl);5)∀θF(θ) `F(θ); (∀-el);6)∃θF(θ) `F(θ0); (reg.C ) :;7) F(θ)`∀F(θ); (Gen)8)`F(θ0→∃θF(θ); (→∃);9) If Γ, A`B then Γ`A→B; (DT);

3.4 Deductia formala a dreptei.

:Metatheorem 1 (MT1). R(A

∧B∧C,d)`¬BAC →(¬ACB→ABC)

Demonstratie..F1≡¬BAC; ( ipoteza auxiliara)F2≡¬ACB; ip.aux.F3≡∃X¬R(X,dAC); ax.I2;F4≡¬R(D,dAC); (reg.C ) :F3;F5≡∀X∀Y∃Z[R(Z,dXY )

∧XYZ]; ax.II2;

F6≡∃Z[R(Z,dBD)∧BDZ]; (∀-el):F5;

F7≡R(G,dBD)∧BDG; (reg.C ) :F6;

F8≡(dAD ∨.BG)→[(dAD ∨

.BC)

∨(dAD ∨

.CG)]; ax.Pasch pentru ΔBGC;

F9≡dAD ∨.BG; tau.(tautologie);

G1≡dAD 6= dBG; ev.(evident);G2≡R(D,dAD); ev.G3≡BDG;(

∧-el):F7;

G4≡R(D,dAD)∧ADG; (

∧- int):G2,G3;

G5≡G4→∃X[R(X,dAD)∧BXG]; (→∃);

G6≡∃X[R(X,dAD)∧BXG]; (MP):G4,G5;

G7≡G1∧G6; (

∧-int);

F10≡(dAD ∨.BC)

∨(dAD ∨

.CG); (MP):F9,F8;

F11≡¬(dAD ∨.BC)→(dAD ∨

.CG); tr.(transcriere) F10;

37

F12≡¬(dAD ∨.BC); ev. altfel dAD≡dBC;

F13≡dAD ∨.CG; (MP):F12,F11;

F14≡dAD 6= dCG∧∃X[R(X,dAD)

∧CXG]; tr.F13;

F15≡∃X[R(X,dAD)∧CXG]; (

∧- el):F14;

F16≡R(E,dAD)∧CEG; (reg.C ) :F15;

F17≡(dCD ∨.BG)→[(dCD ∨

.AB)

∨(dCD ∨

.AG)]; ax.Pasch pentru ΔBGR;

F18≡dCD ∨.BG; tau.;

G1≡dCD 6= dBG; ev.;G2≡BDG; (

∧-el):F7;

G3≡G1∧G2; (

∧- int);

G4≡G3→∃X[R(X,dCD)∧BXG]; (→∃);

G5≡∃X[R(X,dCD)∧BXG]; (MP):G3,G4;

G6≡G1∧G5; (

∧-int);

F19≡(dCD ∨.AB)

∨(dCD ∨

.AG); (MP):F18,F17;

F20≡¬(dCD ∨.AB); ev. altfel dCD≡dAB;

F21≡F20→(dCD ∨.AC); tr. F19;

F22≡(dCD ∨.AC); (MP):F20,F21;

F23≡dCD 6= dAC∧∃X[R(X,dCD)

∧AXG]; tr. F22;

F24≡∃X[R(X,dCD)∧AXG]; (

∧-el):F23;

F25≡R(F,dCD)∧AFG; (reg.C ) :F24;

F26≡(dCF ∨.AG)→[(dCF ∨

.AE)

∨(dCF ∨

.GE)]; ax.Pasch pentru ΔAGE;

F27≡dCF ∨.AG; tau.;

G1≡dCF 6= dAG; ev.;G2≡AFG; (

∧-el):F25;

G3≡G1∧G2; (

∧- int);

G4≡G3→∃X[R(X,dCF )∧AXG]; (→∃);

G5≡∃X[R(X,dCF )∧AXG]; (MP):G3,G4;

G6≡G1∧G5; (

∧-int);

F28≡(dCF ∨.AE)

∨(dCF ∨

.GE); (MP):F27,F26;

F29≡¬(dCF ∨.GE); ev. altfel dCF≡dGE;

F30≡F29→(dCF ∨.AE); tran.F28;

F31≡dCF ∨.AE; (MP):F29,F30;

38

F32≡dCF 6= dAE∧∃X[R(X,dCF )

∧AXE]; tran. F31;

F33≡∃X[R(X,dCF )∧AXE]; (

∧-el):F32;

F34≡R(F,dCF )∧ADE; (reg.C ) :F33;

F35≡(dBG ∨.AE)→[(dBG ∨

.AC)

∨(dBG ∨

.EC)]; ax.Pasch pentru ΔAEC;

F36≡dBG ∨.AE; tau.;

G1≡dBG 6= dAE; ev.;

G2≡ADE; (∧-el):F34;

G3≡G1∧G2; (

∧- int);

G4≡G3→∃X[R(X,dBG)∧AXE]; (→∃);

G5≡∃X[R(X,dBG)∧AXE]; (MP):G3,G4;

G6≡G1∧G5; (

∧-int);

F37≡(dBG ∨.AC)

∨(dBG ∨

.EC); (MP):F36,F35;

F38≡¬(dBG ∨.EC); ev. altfel dBG≡dEC;

F39≡F38→(dBG ∨.AC); tran.F37;

F40≡dBG ∨.AC; (MP):F38,F39;

F41≡dBG 6= dAC∧∃X[R(X,dBG)

∧AXC]; tran. F40;

F42≡∃X[R(X,dBG)∧AXC]; (

∧-el);

F43≡dBG∩dAC = B; ev.;

F43≡R(B,dBG)∧ABC; ev.;

F44≡ABC; (∧-el):F43;

noi obtinem ¬BAC, ¬ACB `ABC si cu (DT) obtinem MT1.

Metateorema 2 (MT2). If R(E,dAB∧dCD)

∧R(H,dBC

∧dAD) atunci:

1) `ABE∧CDE →AHD

2) `ABE∧CDE →BHC

Demonstratie.

39

A

B

D CE

H

F1≡ABE∧CDE; ip.aux.;

F2≡(dCB ∨.AE)→[(dCB ∨

.AD)

∨(dCB ∨

.ED)]; ax.Pasch pentru ΔAED;

F3≡dCB ∨.AE; tau.;

G1≡dCB 6= dAE; ev.;

G2≡R(B,dCB); ev.

G3≡ABE;(∧-el):F1;

G4≡G3→∃X[R(X,dCB)∧AXE]; (→∃);

G5≡∃X[R(X,dCB)∧AXE]; (MP):G3,G4;

G6≡G1∧G5; (

∧-int);

F4≡(dCB ∨.AD)

∨(dCB ∨

.ED); (MP):F3,F2;

F5≡¬(dCB ∨.ED)→(dCB ∨

.AD); tr. F4;

F6≡¬(dCB ∨.ED); ev. altfel dCB≡dED;

F7≡dCB ∨.AD; (MP):F5,F4;

F8≡dCB 6= dAD∧∃X[R(X,dCB)

∧AXD]; tr.F7;

F9≡∃X[R(X,dCB)∧AXD] ; (

∧- el):F8;

F10≡R(H,dCB)∧ACD; (reg.C ) :F9;

F11≡ACD; (∧-el):F10; cu (DT) noi avem MT2 1).

MT2 2) is similar.

Metateorema 3 (MT3). If R(A∧B∧C∧D,d) atunci:

1) `ABC∧BCD →ACD

2) `ABC∧BCD →ABD

Demonstratie.

40

AB DC

G

F

H

E

F1≡ABC∧BCD; ip.aux.;

F2≡∀d∃X¬R(X,d); ax.I2;F3≡∃X¬R(X,d); (∀- el):F2;F4≡¬R(E,d); (reg.C ) :F3;F5≡∀X∀Y∃Z[R(Z,dXY )

∧XYZ]; ax.II2;

F6≡∀Y∃Z[R(Z,dCY )∧CYZ]; (∀-el):F5;

F7≡∃Z[R(Z,dCE)∧CEZ]; (∀-el):F6;

F8≡R(F,dCE)∧CEF; (reg.C ) :F7;

F9≡(dBF ∨.AC)→[(dBF ∨

.AE)

∨(dBF ∨

.CE)]; ax.Pasch pentru ΔACE;

F10≡dBF ∨.AC; tau.;

G1≡dBF 6= dAC; ev.;G2≡R(B,dBF ); ev.G3≡ABC;(

∧-el):F1;

G4≡G2∧G3; (

∧-int);

G5≡G4→∃X[R(X,dBF )∧AXC]; (→∃);

G6≡∃X[R(X,dBF )∧AXC]; (MP):G4,G5;

G7≡G1∧G6; (

∧-int);

F11≡(dBF ∨.AE)

∨(dBF ∨

.CE); (MP):F10,F9;

F12≡¬(dBF ∨.CE) ev. altfel dBF≡dCE;

F13≡F12 →(dBF ∨.AE); tr. F11;

F14≡dBF ∨.AE; (MP):F12,F13;

F15≡dBF 6= dAE∧∃X[R(X,dBF )

∧AXE]; tr.F14;

F16≡∃X[R(X,dBF )∧AXE] ; (

∧- el):F15;

F17≡R(G,dBF )∧AGE; (reg.C ) :F16;

F18≡(dAE ∨.CF )→[(dAE ∨

.BF )

∨(dAE ∨

.BC)]; ax.Pasch pentru ΔBCF;

41

F19≡dAE ∨.CF ; tau.;

G1≡dAE 6= dCF ; ev.;G2≡R(E,dAE); ev.G3≡CEF;(

∧-el):F6;

G4≡G2∧G3; (

∧-int);

G5≡G4→∃X[R(X,dAE)∧CXF]; (→∃);

G6≡∃X[R(X,dAE)∧CXF]; (MP):G4,G5;

G7≡G1∧G6; (

∧-int);

F20≡(dAE ∨.BF )

∨(dAE ∨

.BC); (MP):F13,F18;

F21≡¬(dAE ∨.BC) ev. altfel dAE≡dBC;

F22≡F21 →(dAE ∨.BF ); tr. F20;

F23≡dAE ∨.BF ; (MP):F21,F22;

F24≡dAE 6= dBF∧∃X[R(X,dAE)

∧BXF]; tr.F23;

F25≡∃X[R(X,dAE)∧BXF] ; (

∧- el):F24;

F26≡dAE∩dBF = G;ev.F27≡R(G,dAE)

∧BGF; (reg.C ) :F25;

F28≡(dGD ∨.AE)→[(dGD ∨

.AC)

∨(dGD ∨

.CE)]; ax.Pasch pentru ΔACE;

F29≡dGD ∨.AE; tau.;

G1≡dGD 6= dAE; ev.;G2≡R(G,dGD); ev.G3≡AGE;(

∧-el):F1;

G4≡G2∧G3; (

∧-int);

G5≡G4→∃X[R(X,dGD)∧AXE]; (→∃);

G6≡∃X[R(X,dGD)∧AXE]; (MP):G4,G5;

G7≡G1∧G6; (

∧-int);

F30≡(dGD ∨.AC)

∨(dGD ∨

.CE); (MP):F29,F28;

F31≡¬(dGD ∨.AC) ev. altfel dGD≡dAC;

F32≡F31 →(dGD ∨.CE); tr. F30;

F33≡dGD ∨.CE; (MP):F31,F32;

F34≡dGD 6= dCE∧∃X[R(X,dGD)

∧CXE]; tr.F33;

F35≡∃X[R(X,dGD)∧CXE] ; (

∧- el):F34;

F36≡R(H,dGD)∧CGE; (reg.C ) :F35;

F37≡BGF; (∧- el):F27;

42

F38≡BCD; (∧- el):F1;

F39≡BGF∧BCD; (

∧int):F37,F38;

F40≡F39→GHD; cu MT2 ın ΔBCF ;F41≡GHD; (MP):F39,F40;F42≡CHE; (

∧- el):F36;

F43≡(dHE ∨.DG)→[(dHE ∨

.AD)

∨(dHE ∨

.AG)]; ax.Pasch pentru

ΔAGD;

F44≡dHE ∨.DG; tau.;

G1≡dHE 6= dDG; ev.;G2≡R(H,dHE); ev.G3≡GHD →DHG; ax. II1;G4≡DHG; (MP):F41,G3;G5≡G2

∧G4; (

∧-int);

G6≡G5→∃X[R(X,dHE)∧DXG]; (→∃);

G7≡∃X[R(X,dHE)∧DXG]; (MP):G5,G6;

G8≡G1∧G7; (

∧-int);

F45≡(dHE ∨.AD)

∨(dHE ∨

.AC); (MP):F44,F43;

F46≡¬(dHE ∨.AE) ev. altfel dHE≡dAE;

F47≡F46 →(dHE ∨.AD); tr. F45;

F48≡dHE ∨.AD; (MP):F47,F46;

F49≡dHE 6= dAD∧∃X[R(X,dHE)

∧AXD]; tr.F48;

F50≡∃X[R(X,dHE)∧AXD] ; (

∧- el):F49;

F51≡dHE∩dAD = C; ev.F52≡R(C,dHE)

∧ACD; (reg.C ) :F50;

F53≡ACD; (∧- el):F52;

Deoarece ABC∧BCD `ACD cu (DT) noi avem

`ABC∧BCD →ACD ;

Similar MT3 2).

Metateorema 4 (MT4). Daca R(A∧B∧C∧D,d) atunci:

1) `ABC∧ACD →BCD

2) `ABC∧ACD →ABD

Demonstratie.

43

AB DC

G

F

H

F1≡ABC∧ACD; ip.aux.;

F2≡∃X¬R(X,d); ax.I2;F3≡¬R(G,d); (reg.C ) :F2;F4≡∀X∀Y∃Z[R(z,dXY )

∧XYZ]; ax.II2;

F5≡∃Z[R(Z,dBG)∧BGZ]; (∀-el):F4;

F6≡R(F,dBG)∧BGF; (reg.C ) :F5;

F7≡(dCF ∨.AG)→[(dCF ∨

.AB)

∨(dCF ∨

.BG)]; ax.Pasch pentru ΔABG;

F8≡F7→[¬(dCF ∨.AB)

∧¬(dCF ∨

.BG) →¬(dCF ∨

.AG)];

cu tau. (A→B)→(¬B →¬A);

F9≡¬(dCF ∨.AB)

∧¬(dCF ∨

.BG) →¬(dCF ∨

.AG); (MP):F7,F8;

F10≡¬(dCF ∨.AB)

∧¬(dCF ∨

.BG); ev. dreapta nu taie laturile

ΔABG;

F11≡¬(dCF ∨.AG); (MP):F10,F9;

F12≡(dCF ∨.AD)→[(dCF ∨

.AG)

∨(dCF ∨

.GD)]; ax.Pasch pentru ΔADG;

F13≡(dCF ∨.AD) tau.

G1≡dFC 6= dAD; ev.;G2≡R(C,dFC); ev.G3≡ACD;(

∧-el):F1;

G4≡G2∧G3; (

∧-int);

G5≡G4→∃X[R(X,dFC)∧AXD]; (→∃);

G6≡∃X[R(X,dFC)∧AXD]; (MP):G4,G5;

G7≡G1∧G6; (

∧-int);

F14≡(dCF ∨.AG)

∨(dCF ∨

.GD); (MP):F13,F12;

F15≡¬(dCF ∨.AG) →(dCF ∨

.GD); tr.F14;

44

F16≡dCF ∨.GD; (MP):F11,F15;

F17≡(dCF ∨.GD)→[(dCF ∨

.BD)

∨(dCF ∨

.BG)]; ax.Pasch pentru

ΔBDG;

F18≡(dCF ∨.BD)

∨(dCF ∨

.BG); (MP):F16,F17;

F19≡¬(dCF ∨.BG) ev. altfel dCF≡dBG;

F20≡F19→(dCF ∨.BD); tr.F18;

F21≡(dCF ∨.BD); (MP):F19,F20;

F22≡dCF 6= dBD∧∃X[R(X,dCF )

∧BXD]; .tr.F21;

F23≡∃X[R(X,dCF )∧BXD]; (

∧-el ):F22;

F24≡dCF∩dBD = C; ev.F25≡R(C,dCF )

∧BCD; (reg.C ) :F23;

F26≡BCD; (∧- el):F25;

Deci ABC∧ACD `BCD si cu (DT) noi avem `ABC

∧ACD

→BCD`ABC

∧ACD→ABC

∧BCD

`ABC∧BCD→ABD cuMT3 noi avem `ABC

∧ACD→BCD (sil);

Metateorema 5 (MT5).`A 6= B → ∃X(AXB)Demonstratie.

A B

E

C

F

X

F1≡A 6= B; ip.F2≡∀d∃X¬R(X,d); ax.I2)F3≡∃X¬R(X,dAB); (∀): F2F4≡¬R(C,dAB); (reg.C ) :F3

45

F5≡∀X∀Y∃Z[R(Z,dXY ) ∧XYZ]; ax. II2)F6≡∃Z[R(Z,dAC) ∧ACZ]; (∀): F5F7≡R(E,dAC) ∧ACE; (reg.C ) :F6F8≡ACE; ; (∧-el)F7F9≡∃Z[R(Z,dEB) ∧EBZ]; (∀): F5F10≡R(F,dEB) ∧EBF; (reg.C ) :F8F11≡EBF; ; (∧-el)F10

F12≡(dFC ∨.AE)→[(dFC ∨

.AB)

∨(dFC ∨

.BE)]; ax.Pasch pentru ΔAEB;

F13≡(dFC ∨.AE); tau.

G1≡dFC 6= dAE; ev.;G2≡ACE; F8G3≡R(F,dFE); ev.G4≡G2 ∧G3;

∧

G5≡G4→∃X[R(X,dFC)]∧AXE] ;

G6≡∃X[R(X,dFC)]∧AXE]; (MP):G4, G5

G7≡G1 ∧G6;∧

F14≡(dFC ∨.AB)

∨(dFC ∨

.BE); (MP): F13, F12

F15≡¬(dFC ∨.BE) →(dFC ∨

.AB); tr. F14

F16≡¬(dFC ∨.BE; ev. altfel dFC≡dFE

F17≡(dFC ∨.AB); (MP):F16, F15

F18≡dFC 6= dAB ∧∃X[R(X,dAB) ∧AXB]Metateoremele de mai sus ne permite a defini un sir de puncte

prin recurenta ascendent:ABC ca A1, A2, A3ABCD≡ABC ∧ACD ca A1, A2, A3, A4. . .A1A2 . . . An−1An≡A1A2 . . . An−1 ∧ A1An−1An, ca A1, A2, . . . , Ansau cu ultima metateorema un sir descendent. . . , An, . . . , A2, A1

46

3.5 Topologia dreptei

Definitia (3.2). Se numeste vecinatate a unui punct X orice segmentdeschis

U = (A,B) ≡ {X|AXB}

Multimea veciinatatilor lui X o notam H(X).Aceasta definitie satisface axiome lui Hausdorff:H1) ∀X∀U [U ∈ H(X)→ X ∈ U ]H2)∀X∀U∀V[U ∈H(X) ∧V ∈H(X) →∃W[W ∈H(X) ∧W ⊆U ∩V]]H3) ∀X∀Y ∀U [U ∈ H(X) ∧ Y ∈ U → ∃V [V ∈ H(Y )→ V ⊆ U ]]H4) ∀X∀Y [X 6= Y → ∃U∃V [U ∈ H(X) ∧ V ∈ H(Y )→ U

⋂V = ∅]]

Definitia (3.3).U ∈OS ≡∀X[X ∈U →∃V[V ∈H(X) ∧V ⊆ U]]U este deschisU ∈CS ≡U ∈ COS; (U apartine complementarei lui OS);U este ınchisX ∈U’ ≡∀V[X ∈V ∧V ∈OS →∃Y[Y 6=X ∧Y ∈V ∧Y ∈U]]U este derivatU = U ∪U’ ınchidereaMetateorema 6 (MT6).`∀U∀V[U ∧V ∈OS →U ∩V ∈OS]Demonstratie.F1≡U ∈OS ∧V ∈OS; ip.F2≡X ∈U ∩V; ip.F3≡F2 →X ∈U; tau.( tautologie)F4≡F2 →X ∈V; tau.F5≡X ∈U; (MP):F2, F3F6≡X ∈V; (MP):F2, F4F7≡F1 →U ∈OS; tau.F8≡F1 →V ∈OS; tau.F9≡U ∈OS; (MP):F1, F7F10≡V ∈OS; (MP):F1, F8F11≡∀X[X ∈U →∃V[V ∈H(X) ∧V ⊆ U]]; transcriere F9F12≡X ∈U →∃V[V ∈H(X) ∧V ⊆ U]; (∀) - el:F14F13≡∃V[V ∈H(X) ∧V ⊆ U]; (MP):F5, F12F14≡V1 ∈H(X) ∧V1 ⊆ U; regula C:F13F15≡∀X[X ∈V →∃W[W ∈H(X) ∧W ⊆ V]];tr.F10

47

F16≡X ∈V →∃W[W ∈H(X) ∧W ⊆ V]; (∀) - el:F15F17≡∃W[W ∈H(X) ∧W ⊆ V];(MP):F6, F16F18≡W1 ∈H(X) ∧W1 ⊆ V ; regula C :F17F19≡F14 →V1 ∈H(X); tau.F20≡V1 ∈H(X);(MP):F14, F19F21≡F18 →W1 ∈H(X); tau.F22≡W1 ∈H(X); (MP):F18, F21F23≡F20 →(F22 →F20 →F22); tau.F24≡F22 →F20 ∧F22;(MP):F20, F22F25≡F20 ∧F22 ; (MP):F22, F24F26≡V1 ∈ H(X) ∧W1 ∈ H(X); transcriere F25F27≡∀X∀U∀V [U ∈ H(X) ∧ V ∈ H(X)→→ ∃W [W ∈ H(X)→ W ⊆ U

⋂V ]]; ax.(H3)

F28≡V1 ∈H(X) ∧W1 ∈H(X) →→∃W[W ∈H(X) ∧W ⊆ V1

⋂W1]; (∀) - el:F27

F29≡∃W[W ∈H(X) →W ⊆ V1⋂W1]; (MP):F26, F28

F30≡W2 ∈H(X) ∧W2 ⊆ V1⋂W1; regula C :F29

F31≡F14 →V1 ⊆ U ; tau.F32≡V1 ⊆ U ; (MP):F14, F31F33≡F18 →W1 ⊆ V ; tau.F34≡W1 ⊆ V ;(MP):F18, F33F35≡V1

⋂W1 ⊆ U

⋂V ; F32, F34

F36≡F30 →W2 ⊆ V1⋂W1; tau.

F37≡W2 ⊆ V1⋂W1; (MP):F30, F36

F38≡W2 ⊆ U⋂V ;(sil):F37, F35

F39≡F30 →W2 ∈ H(X); tau.F40≡W2 ∈ H(X);(MP):F30, F39F41≡F40 →(F38 →F40 ∧F38); tau.F42≡F38 →F40 ∧F38; (MP):F40, F41F43≡F40 ∧F38; (MP):F38, F42F44≡W2 ∈ H(X) ∧W2 ⊆ U

⋂V ; tr.F43

F45≡F44 →∃W[W ∈H(X) ∧W ⊆ U⋂V ]; (L4)

F46≡∃W[W ∈H(X) ∧W ⊆ U⋂V ]; (MP):F44, F45

Am obtinut deductia simplaU ∧V ∈OS, X ∈U

⋂V `∃W[W ∈H(X) ∧W ⊆ U

⋂V ]; cu (DT) apoi

(Gen) se obtine U ∧V ∈OS `U⋂V ∈ OS

Metateorema 7 (MT7).`∀U[U ⊆OS →

⋃(U) ∈OS]

48

Demonstratie.F1≡U ⊆OS; ip.F2≡X ∈OS; ip.F3≡∃V[X ∈V ∧V ∈U]; tr. F2F4≡X ∈U1 ∧ U1 ∈ U ; (reg.C ):F3F5≡∀V[V ∈U →V ∈OS]; tr.F1F6≡U1 ∈ U → U1 ∈ OS; (∀-el):F5F7≡F4 →U1 ∈ U ; tau.F8≡U1 ∈ U ; (MP):F4, F7F9≡U1 ∈ OS; (MP):F8, F6F10≡∀X[X ∈U1 →∃V[V ∈H(X) ∧V ⊆U1]]; tr. F9F11≡X ∈U1 →∃V[V ∈H(X) ∧V ⊆U1]; (∀-el):F10F12≡F4 →X ∈U1; tau.F13≡X ∈U1; (MP):F4, F12F14≡∃V[V ∈H(X) ∧V ⊆U1]; (MP):F13, F11F15≡V1 ∈H(X) ∧V1 ⊆U1; (reg.C ):F14F16≡∀U∀U1[U1 ∈U →U1 ⊆

⋃(U)];

G1≡U1 ∈U; ip.G2≡X ∈U; ip.G3≡G1 ∧G2 ; (∧-int)G4≡G3 →∃U1[X ∈ U1 ∧ U1 ∈ U ]; (L3)G5≡∃U1[X ∈ U1 ∧ U1 ∈ U ]; (MP):G3, G4G6≡X ∈

⋃(U); tr.G5

F17≡U1 ∈U →U1 ⊆⋃(U); (∀-el)::F16

F18≡U1 ⊆⋃(U);(MP):F8, F17

F19≡F15 →V1 ⊆U1; tau.F20≡V1 ⊆U1;(MP):F15, F19F21≡V1 ⊆

⋃(U); (sil):F20, F18

F22≡F15 →V1 ∈H(X); tau.F23≡V1 ∈H(X); (MP):F15, F22F24≡F23 →(F21 →F23 ∧F21); tau.F25≡F21 →F23 ∧F21; (MP):F23, F24F26≡F23 ∧F21; (MP):F21, F25F27≡V1 ∈H(X) ∧V1 ⊆

⋃(U); tr. F26

F28≡F27 →∃V[V ∈H(X) ∧V ⊆⋃(U)]; (L4)

F29≡∃V[V ∈H(X) ∧V ⊆⋃(U)];(MP): F27, F28

Am obtinut deductia simpla:

49

U ⊆OS, X ∈⋃(U) `∃V[V ∈H(X) ∧V ⊆

⋃(U)]; cu (DT) si (Gen)

obtinem U ⊆OS `⋃(U) ∈OS

In mod similar pot fi demonstrate:Metateorema 8 (MT8).`∀U∀V[U ∈CS ∧V ∈CS →U ∪V ∈CS]Metateorema 9 (MT9).`∀U[U ⊆CS →

⋂(U) ∈CS]

Metateorema 10 (MT10).`∀X∀U[U ∈H(X) →U ∈OS]acest enunt este echivalent cu:Metateorema 11 (MT11).`∀U[U ∈CS →U’ ⊆U]Demonstratie.F1≡U ∈CS; ip.F2≡ CU ∈OS; tr.F1F3≡X ∈U’; ip.F4≡X /∈U;ip.F5≡F4 →X ∈ CU;F6≡X ∈ CU; (MP):F4, F5F7≡∀X[X ∈ CU →∃V[V ∈H(X) ∧V ⊆ CU]]; tr. F2F8≡X ∈ CU →∃V[V ∈H(X) ∧V ⊆ CU]; (∀-el):F7F9≡∃V[V ∈H(X) ∧V ⊆ CU];(MP):F6, F8F10≡V1 ∈H(X) ∧V1 ⊆ CU; (reg.C ):F9F11≡∀X∀U[U ∈H(X) →U ∈OS]; met. precedentaF12≡V1 ∈H(X) →V1 ∈OS; (∀-el):F11F13≡F10 →V1 ∈H(X); tau.F14≡V1 ∈H(X);(MP):F10, F13F15≡V1 ∈OS; (MP):F14, F12F16≡∀X∀U [U ∈ H(X)→ X ∈ U ]; ax. H2)F17≡V1 ∈ H(X)→ X ∈ V1; (∀-el):F16F18≡X ∈V1; (MP):F14, F17F19≡F18 →(F15 →F18 ∧F15); tau.F20≡F15 →F18 ∧F15;(MP):F18, F19F21≡F18 ∧F15;(MP):F15, F20F22≡X ∈V1 ∧V1 ∈OS; tr.F21F23≡∀V[X ∈V ∧V ∈OS →∃Y[Y 6= X ∧Y ∈V ∧Y ∈U]]; tr.F3F24≡X ∈V1 ∧V1 ∈OS →∃Y[Y 6= X ∧Y ∈V1 ∧Y ∈U]; (∀-el):F23F25≡∃Y[Y 6= X ∧Y ∈V1 ∧Y ∈U];(MP):F22, F24

50

F26≡Y1 6= X ∧Y1 ∈V1 ∧Y1 ∈U; (reg.C ):F25F27≡F10 →V1 ⊆ CU;tau.F28≡V1 ⊆ CU;(MP):F10, F27F29≡∀X[X ∈V1 →X ∈ CU]; tr. F28F30≡Y1 ∈V1 →Y1 ∈ CU; (∀-el):F29F31≡F26 →Y1 ∈V1 ;tau.F32≡Y1 ∈V1;(MP):F26, F31F33≡Y1 ∈ CU;(MP):F32, F30F34≡F26 →Y1 ∈U; tau.F35≡Y1 ∈U;(MP):F26, F34F36≡F35 →(F33 →F35 ∧F33); tau.F37≡F33 →F35 ∧F33; (MP):F35, F36F38≡F35 ∧F33; (MP):F33, F37F39≡Y1 ∈U ∧Y1 ∈ CU; tr. F38 care este absurdMetateorema 12 (MT12).X ∈ CU, ∀V[V ∈H(X) →¬(V ⊆ CU)] `X ∈U’Demonstratie.F1≡X ∈ CU; ip.F2≡∀V[V ∈H(X) →¬(V ⊆ CU)]; ip.F3≡X ∈W ∧W ∈OS; ip.F4≡F3 →W ∈OS; tau.F5≡W ∈OS; (MP):F3, F4F6≡∀X[X ∈W →∃V[V ∈H(X) ∧V ⊆W]]; tr. F5F7≡X ∈W →∃V[V ∈H(X) ∧V ⊆W]; (∀-el):F6F8≡F3 →X ∈W; tau.F9≡X ∈W;(MP):F3, F8F10≡∃V[V ∈H(X) ∧V ⊆W];(MP):F9, F7F11≡V1 ∈H(X) ∧V1 ⊆W;(reg.C ):F10F12≡F11 →V1 ⊆W; tau.F13≡V1 ⊆W;(MP):F11, F12F14≡F11 →V1 ∈H(X); tau.F15≡V1 ∈H(X); (MP):F11, F14F16≡V1 ∈H(X) →¬(V1 ⊆ CU);(∀-el):F2F17≡¬(V1 ⊆ CU);(MP):F15, F16F18≡¬(∀Y[Y ∈V1 →Y ∈ CU]); tr. F17F19≡F18 →∃Y[Y ∈V1 ∧Y ∈U]; tau.F20≡∃Y[Y ∈V1 ∧Y ∈U];(MP):F18, F19F21≡Y1 ∈V1 ∧Y1 ∈U; (reg.C ):F20

51

F22≡F21 →Y1 ∈U;tau.F23≡Y1 ∈U;(MP):F21, F22F24≡F1 →(F23 →F1 ∧F23); tau.F25≡F23 →F1 ∧F23; (MP):F1, F24F26≡F1 ∧F23; (MP):F23, F25F27≡X ∈ CU ∧Y1 ∈U; tr. F26F28≡F27 →Y1 6= X; tau.F29≡Y1 6= X;(MP):F27, F28F30≡∀Y[Y ∈V1 →Y ∈W]; tr. F13F31≡Y1 ∈V1 →Y1 ∈W; (∀-el):F30F32≡F21 →Y1 ∈ V1; tau.F33≡Y1 ∈ V1;(MP):F21, F32F34≡Y1 ∈W;(MP):F33, F31F35≡F29 →(F34 →F29 ∧F34); tau.F36≡F34 →F29 ∧F34; (MP):F29, F35F37≡F29 ∧F34; (MP):F34, F36F38≡Y1 6= X ∧ Y1 ∈W; tr. F37F39≡F38 →(F23 →F38 ∧F23); tau.F40≡F23 →F38 ∧F23;(MP):F38, F39F41≡F38 ∧F23;(MP):F23, F40F42≡Y1 6= X ∧ Y1 ∈W ∧Y1 ∈U; tr. F41F43≡F42 →∃Y[Y 6= X ∧Y ∈W ∧Y ∈U]; (L4)F44≡∃Y[Y 6= X ∧Y ∈W ∧Y ∈U]; (MP):F42, F43Am obtinut deductia simpla:X ∈ CU, ∀V[V ∈H(X) →¬(V ⊆ CU)],X ∈W ∧W ∈OS `∃Y[Y 6= X ∧Y ∈W ∧Y ∈U]cu (DT) si (Gen) obtinem afirmatia metateoremei.Metateorema 13 (MT13).`∀U[U’ ⊆U →U ∈CS]Demonstratie.F1≡U’ ⊆U; ip.F2≡U /∈ CS; ip.F3≡¬( CU ∈OS); tr. F2F4≡¬∀X[X ∈ CU →∃V[V ∈H(X) ∧V ⊆ CU]]; tr. F3F5≡F4 →∃X[X ∈ CU ∧∀V[V ∈H(X) →¬(V ⊆ CU)]];

G1≡A ∧B ≡¬(A →¬B); definitie;G2≡X ∈ CU →∃V[V ∈H(X) ∧V ⊆ CU]G3≡X ∈ CU →∃V ¬[V ∈H(X) →¬(V ⊆ CU)]

52

G4≡¬[X ∈ CU ∧¬∃V ¬[V ∈H(X) →¬(V ⊆ CU)]]G5≡¬[X ∈ CU ∧∀V[V ∈H(X) →¬(V ⊆ CU)]]G6≡¬∀XG5→∃X[X ∈ CU ∧∀V[V ∈H(X)→¬(V ⊆ CU)]]

F6≡∃X[X ∈ CU ∧∀V[V ∈H(X) →¬(V ⊆ CU)]]; (M):F4, F5F7≡X1 ∈ CU ∧∀V[V ∈H(X1) →¬(V ⊆ CU)]; (reg.C ):F6F8≡F7 →X1 ∈ CU; tau.F9≡X1 ∈ CU;(MP):F7, F8F10≡F7 →X1∈U’; met. precedentaF11≡X1∈U’; (MP):F7, F10F12≡∀X[X∈U’ →X ∈U]; tr. F1F13≡X1∈U’ →X1 ∈U; (∀-el):F12F14≡X1 ∈U; (MP):F11, F13F15≡F14 →(F9 →F14 ∧F9); tau.F16≡F9 →F14 ∧F9; (MP):F14, F15F17≡F14 ∧F9; (MP):F9, F16F18≡X1 ∈U ∧X1 ∈ CU; care e absurd.Lema.Z∈ CU, ∀V[V ∈H(X) →¬(V ⊆ CU)]`X ∈U’Demonstratie.F1≡X ∈ CU; ip.F2≡∀V[V ∈H(X) →¬(V ⊆ CU)]; ip.F3≡X ∈W ∧W ∈OS ; ip.F4≡X ∈W; (∧-el):F3F5≡∀X[X ∈W →∃V[V ∈H(X) ∧V ⊆W]]; tr.F4F6≡X ∈W →∃V[V ∈H(X) ∧V ⊆W]; (∀-el):F5F7≡X ∈W; (∧-el):F3F8≡∃V[V ∈H(X) ∧V ⊆W]; (MP):F7, F6F9≡V1 ∈H(X) ∧V1 ⊆W; (reg.C ):F8F10≡V1 ∈H(X) →¬(V1 ⊆ CU); (∀-el):F2F11≡V1 ∈H(X); (∧-el):F9F12≡¬(V1 ⊆ CU); (MP):F11, F10F13≡¬∀Y[Y ∈V1 →Y ∈ CU]; tr.F12F14≡¬∀Y ¬[Y ∈V1 ∧¬(Y ∈ CU)]; tr.F13cu A ∈B ≡¬(A →¬B)F15≡∃Y[Y ∈V1 ∧Y ∈U]; tr. F14F16≡Y1 ∈ V1 ∧ Y1 ∈ U ; (reg.C ):F15F17≡Y1 ∈ U ; (∧-el):F16F18≡X ∈ CU ∧Y1 ∈ U (∧-int)F1, F12

53

F19≡F18 →X 6= Y1; tau.F20≡X 6= Y1; (MP):F18, F19F21≡V1 ⊆W; (∧-el):F9F22≡∀Y[Y ∈V1 →Y ∈W]; tr. F21F23≡Y1 ∈V1 →Y1 ∈W; (∀-el):F22F24≡Y1 ∈V1; (∧-el):F16F25≡Y1 ∈W ; (MP):F24, F23F26≡X 6= Y1 ∧Y1 ∈W ∧Y1 ∈U ∧F20, F25, F17F27≡F26 →∃Y[X 6= Y ∧Y∈W ∧Y ∈U]; (L4)F28≡∃Y[X 6= Y ∧Y∈W ∧Y ∈U]; (MP):F26, F27F29≡F3 ∧F28; (∧-int)F30≡∀WF29; (Gen)F31≡X ∈U’; tr.F30Metateorema 14 (MT14).`U’ ⊆U →U ∈CSDemonstratie.F1≡U’ ⊆U; ip.F2≡¬(U ∈CS); ip.F3≡¬( CU ∈OS); tr. F2F4≡¬∀X[X ∈ CU →∃V[V ∈H(X) ∧V ⊆ CU]]; tr. F3F5≡¬∀X ¬[X ∈ CU ∧¬∃V ¬[V ∈H(X) ∧¬(V ⊆ CU)]]; tr. F4F6≡∃X[X ∈ CU ∧¬∀V[V ∈H(X) ∧¬(V ⊆ CU)]]; tr. F5F7≡X1 ∈ CU ∧¬∀V[V ∈H(X1) ∧¬(V ⊆ CU)]; (reg.C ):F6F8≡X1 ∈ CU; (∧-el):F7F9≡¬(X1 ∈U); tr. F8F10≡F7 →X1 ∈U’; lemaF11≡X1 ∈U’; (MP:F7, F10F12≡∀X[X ∈U’ →X ∈U]; tr.F1F13≡X1 ∈U’ →X1 ∈U; (∀-el):F12F14≡X1 ∈U; (MP):F11, F13F15≡X1 ∈UF16≡X1 ∈ CU ∧X1 ∈U ; (∧-int)F8, F15 care este absurd.Corolar 1`∀U[U ∈CS →U’ ⊆U]Corolar 2`∀U[U ∈CS →U = U ]Metateorema 15 (MT15).`∀U∀V[U ⊆V →U’ ⊆V’]Demonstratie.F1≡U ⊆V ; ip.

54

F2≡X ∈U’; ip.F3≡∀W[X ∈W ∧W ∈OS →∃Y[ Y 6= X ∧Y ∈W ∧Y ∈U]; tr. F2F4≡X ∈W1 ∧W1 ∈OS →∃Y[ Y 6= X ∧Y ∈W1 ∧Y ∈U]; (∀-el):F3F5≡X ∈W1 ∧W1 ∈OS; ip.F6≡∃Y[ Y 6= X ∧Y ∈W1 ∧Y ∈U]: (MP):F5, F4F7≡Y1 6= X ∧ Y1 ∈ W1 ∧ Y1 ∈ U ; (reg.C ):F6F8≡∀Y[Y ∈U →Y ∈V]; tr. F1F9≡Y1 ∈ U → Y1 ∈ V ; (∀-el):F8F10≡Y1 6= X ∧ Y1 ∈ W1 ∧ Y1 ∈ U → Y1 6= X ∧ Y1 ∈ W1 ∧ Y1 ∈ VA →B `A ∧C →B∧CF11≡Y1 6= X ∧ Y1 ∈ W1 ∧ Y1 ∈ V ; (MP):F7, F10F12≡F11 →∃Y[X 6= Y ∧ Y ∈ W1 ∧ Y ∈ V ]; (L4)F13≡∃Y[X 6= Y ∧ Y ∈ W1 ∧ Y ∈ V ]; (MP):F11, F12Am obtinut deductia:U ⊆V, X ∈U’, X ∈W1 ∧W1 ∈OS `∃Y[X 6= Y ∧ Y ∈ W1 ∧ Y ∈ V ]U ⊆V, X ∈U’`X ∈W1 ∧W1 ∈OS →→∃Y[X 6= Y ∧ Y ∈ W1 ∧ Y ∈ V ]; (DT)U ⊆V, X ∈U’`∀W[X ∈W1 ∧W1 ∈OS →→∃Y[X 6= Y ∧ Y ∈ W1 ∧ Y ∈ V ]]; (Gen)U ⊆V, X ∈U’`X ∈V’; tr.precedentaU ⊆V `∀X[X ∈U’ →X ∈V’]; (Gen)U⊆V `U’ ⊆V’Corolar `∀U∀V[U ⊆V →U ⊆V ]Metateorema 16 (MT16).`∀U∀V[(U ∪V)’ = U’ ∪V’]Demonstratie.Avem U ⊆U ∪V =⇒ U’ ⊆(U ∪V)’

V ⊆U ∪V =⇒ V’ ⊆(U ∪V)’=⇒ U’ ∪V’ ⊆(U ∪V)’Sa aratam invers (U ∪V)’ ⊆U’ ∪V’F1≡X ∈(U ∪V)’; ip.caz 1. X ∈U’ =⇒ X ∈U’ ∪V’caz 2. X ∈V’ =⇒ X ∈U’ ∪V’F2≡¬(X ∈U’) ∧¬(X ∈V’); ip.F3≡¬(X ∈U’); (∧-el):F2F4≡¬∀V[X ∈V ∧V ∈OS →∃Y[X 6= Y ∧Y ∈V ∧Y ∈U] tr. F3F5≡¬∀V ¬[X ∈V ∧V ∈OS ∧¬∃Y ¬[X 6= Y ∧Y ∈V →¬(Y ∈U)];tr. F4

55

F6≡∃V[X ∈V ∧V ∈OS ∧∀Y[X 6= Y ∧Y ∈V →¬(Y ∈U)] ;tr. F5F7≡X ∈V1 ∧V1 ∈OS ∧∀Y[X 6= Y ∧Y ∈V1 →¬(Y ∈U)]; (reg.C ):F6F8≡X ∈V1 ∧V1 ∈OS; (∧-el):F7F9≡∀Y[X 6= Y ∧Y ∈V1 →¬(Y ∈U)]; (∧-el):F7Analog se obtine: F10, F11F10≡X ∈W1 ∧W1 ∈OS;F11≡∀Y[X 6= Y ∧Y ∈W1 →¬(Y ∈V)]F12≡V1 ∈OS; (∧-el):F8F13≡W1 ∈OS; (∧-el):F10F14≡V1 ∈OS ∧W1 ∈OS;(∧-int)F12, F13F15≡F14 →V1 ∩W1 ∈OS; met. U ∈OS ∧W ∈OS →U ∩V ∈OSF16≡V1 ∩W1 ∈OS; (MP):F14, F15F17≡∀X[X ∈V1 ∩W1 →∃V[V ∈H(X) ∧V ⊆V1 ∩W1]; tr. F16F18≡X ∈V1 ∩W1 →∃V[V ∈H(X) ∧V ⊆V1 ∩W1]; (∧-el):F17F19≡X ∈V1;(∧-el):F8F20≡X ∈W1;(∧-el):F10F21≡X ∈V1 ∧X ∈W1; (∧-int)F19, F20F22≡∃V[V ∈H(X) ∧V ⊆V1 ∩W1]; (MP):F21, F18F23≡V2 ∈ H(X) ∧ V2 ⊆V1 ∩W1; (reg.C ):F22F24≡V2 ∈ H(X); (∧-el):F23F25≡X ∈V2 ; din prop. vec.F26≡V2 ⊆V1 ∩W1; (∧-el):F23F27≡∀X[X ∈V2 →X ∈V1 ∩W1]; tr. F26F28≡X ∈V2 →X ∈V1 ∩W1; (∀-el):F27F29≡X ∈V1 ∩W1;F25, F28F30≡X ∈V1 ∩W1 ∧V1 ∩W1 ∈OS; (∧-int)F29, F16F31≡∀T[X ∈T ∧T ∈Os →∃Y[Y 6= X ∧Y ∈T ∧Y ∈(U ∪V)]]; tr F1F32≡X ∈V2 ∧V2 ∈Os→∃Y[Y 6= X ∧Y ∈V2 ∧Y ∈(U ∪V)]; (∀-el):F31F33≡X ∈H(X) →V2 ∈Os;U ∈H(X) →∀Y[Y ∈U →∃V[V ∈H(Y) ∧V ⊆U]se arata echivalenta cu H3):U ∈H(X) ∧Y ∈U →∃V[V ∈H(Y) →V ⊆U]folosind deductiile: A ∧B →C, A, B `C siA →(B →C), A, B `CF34≡V2 ∈Os; (MP):F24, F33F35≡X ∈V2 ∧V2 ∈Os; (∧-int)F25, F34F36≡∃Y[Y 6= X ∧Y ∈V2 ∧Y ∈(U ∪V)]; (MP):F35, F32F37≡Y1 6= X ∧Y1 ∈V2 ∧Y1 ∈(U ∪V); (reg.C ):F36

56

F38≡Y1 ∈V2; (∧-el):F37F39≡∀X[X ∈V2 →X ∈V1 ∩W1];tr. F26F40≡Y1 ∈V2 →Y1 ∈V1 ∩W1; (∀-el):F39F41≡Y1 ∈V1 ∩W1; (MP):F38, F40F42≡Y1 ∈V1 ∧Y1 ∈ W1; tr. F41F43≡Y1 ∈V1; (∧-el):F42F44≡Y1 6= X; (∧-el):F37F45≡Y1 6= X ∧Y1 ∈V1; (∧-int)F44, F43F46≡Y1 6= X ∧Y1 ∈V1 →¬(Y1 ∈U); (∀-el):F9F47≡¬(Y1 ∈U); (MP):F45, F46F48≡¬(Y1 ∈V); analog cu F47F49≡¬(Y1 ∈U)∧¬(Y1 ∈V); (∧-int)F47, F48F50≡¬(Y1 ∈(U ∪V) tr. F49F51≡Y1 ∈(U ∪V); (∧-el):F37F52≡F50 ∧F51; (∧-int)care este absurdMetateorema 17 (MT17).`X ∈U ↔∀V[X ∈V ∧V ∈OS →∃Y[Y ∈V ∧V ∈U]]Demonstratie.X ∈U = U ∪U’ implica imediat partea dreapta din definitie.Sa demonstram invers.F1≡∀V[X ∈V ∧V ∈OS →∃Y[Y ∈V ∧Y ∈U]]; ip.F2≡¬(X ∈U’); ip.F3≡¬∀V[X ∈V ∧V ∈OS →∃Y[ Y 6= X ∧Y ∈V ∧Y ∈U]]; tr. F2F4≡¬∀V ¬[X ∈V ∧V ∈OS ∧¬∃Y ¬[Y ∈V ∧Y ∈U →Y = X]];tr.F3F5≡∃V[X ∈V ∧V ∈OS ∧∀Y[Y ∈V ∧Y ∈U →Y = X]]; tr. F4F6≡X ∈V1 ∧V1 ∈OS ∧∀Y[Y ∈V1 ∧Y ∈U →Y = X]F7≡X ∈V1 ∧V1 ∈OS; (∧-el):F6F8≡X ∈V1 ∧V1 ∈OS →∃Y[Y ∈V1 ∧Y ∈U]; (∀-el):F1F9≡∃Y[Y ∈V1 ∧Y ∈U]; (MP):F7, F8F10≡Y1 ∈V1 ∧Y1 ∈U; (reg.C ):F9F11≡∀Y[Y ∈V1 ∧Y ∈U →Y = X]; (∧-el):F6F12≡Y1 ∈V1 ∧Y1 ∈U →Y1 = X; (∀-el):F11F13≡Y1 = X; (MP):F10, F12F14≡Y1 = X →[Y1 ∈U↔X ∈U]; tautologie de egalitateF15≡Y1 ∈U↔X ∈U; (MP):F13, F14F16≡Y1 ∈U; (∧-el):F10F17≡X ∈U; (MP:F16, F15F18≡U ⊆U = U ∪U’;

57

F19≡X ∈UCorolar `X ∈U ↔∀X[X ∈V ∧V ∈OS ↔U ∩V 6= ∅]Metateorema 18 (MT18).`∀U[U” ⊆U’]Demonstratie.F1≡X ∈U”; ip.F2≡X ∈V ∧V ∈OS; ip.F3≡∀V[X ∈V ∧V ∈OS →∃Y[Y 6=X ∧Y ∈V ∧Y ∈U’]]; tr. F1F4≡X ∈V ∧V ∈OS →∃Y[Y 6=X ∧Y ∈V ∧Y ∈U’]; (∀-el):F2F5≡∃Y[Y 6=X ∧Y ∈V ∧Y ∈U’]; (MP):F2, F3F6≡Y1 6=X ∧Y1 ∈V ∧Y1 ∈U’; (reg.C ):F5F7≡Y1 6=X; (∧-el):F6F8≡Y1 ∈V; (∧-el):F6F9≡Y1 ∈U’; (∧-el):F6F10≡∀V[Y1 ∈V ∧V ∈OS →∃Y[Y 6= Y1 ∧Y ∈V ∧Y ∈U]]; tr. F9F11≡V ∈OS; (∧-el):F2F12≡Y1 ∈V ∧V ∈OS;

∧F8, F11

F13≡Y1 ∈V ∧V ∈OS →∃Y[Y 6= Y1 ∧Y ∈V ∧Y ∈U]; (∀-el):F10F14≡∃Y[Y 6= Y1 ∧Y ∈V ∧Y ∈U]]; (MP):F12, F13F15≡Y2 6= Y1 ∧Y ∈V ∧Y ∈U]; (reg.C ):F14F16≡∀X[X ∈V →∃W[W ∈H(X) ∧W ⊆V]]; tr. F11F17≡Y1 ∈V →∃W[W ∈H(Y1) ∧W ⊆V]; (∀-el):F16F18≡X ∈V; (∧-el):F2F19≡∃W[W ∈H(Y1) ∧W ⊆V];(MP):F8, F17F20≡W1 ∈H(Y1) ∧W1 ⊆V; (reg.C ):F19F21≡W1 ∈H(Y1); (∧-el):F20F22≡W1 ⊆V; (∧-el):F20F23≡W1 ∈H(Y1) →Y1 ∈W1; def. vecinatatiiF24≡Y1 ∈ W1;(MP):F21, F23F25≡∀X∀Y [X 6= Y → ∃U∃V [U ∈ H(X) ∧ V ∈ H(Y )→→ U

⋂V = ∅]]; ax. H4)

F26≡Y2 6= Y1 → ∃U∃V [U ∈ H(Y2) ∧ V ∈ H(Y1)→ U⋂V = ∅]];

(∀-el):F25F27≡Y2 6= Y1; (∧-el):F15F28≡∃U∃V [U ∈ H(Y2) ∧ V ∈ H(Y1)→ U

⋂V = ∅]]; (MP):F27, F26

F29≡U2 ∈ H(Y2) ∧ V1 ∈ H(Y1)→ U2⋂V1 = ∅; (reg.C ):F29

F30≡U2 ∈ H(Y2); (∧-el):F29F31≡V1 ∈ H(Y1); (∧-el):F29

58

F32≡U2⋂V1 = ∅; (∧-el):F29

F33≡6 (Y2 ∈ V1); din F30 si F32F34≡∀V∀U∀V[U ∈H(X) ∧V ∈H(X) →∃W[W ∈H(X) ∧∧W ⊆U ∩V]]; ax. H2F35≡W1 ∈H(Y1) ∧V1 ∈H(Y1) →∃W[W ∈H(Y1) ∧W ⊆V1 ∧W1]];(∀-el):F34F36≡W1 ∈H(Y1) ∧V1 ∈ H(Y1);

∧F21, F31

F37≡∃W[W ∈H(Y1) ∧W ⊆V1 ∧W1]; (MP):F36, F35F38≡W2 ∈H(Y1) ∧W2 ⊆V1 ∧W1; (reg.C ):F37F39≡W2 ∈ H(Y1); (∧-el):F38F40≡W2 ⊆V1 ∧W1; (∧-el):F38F41≡¬(Y2 ∈ W2); din F33 c si F40F42≡Y1 ∈ W2 ; din F39F43≡∀X∀U[U ∈H(X) →U →OS]; met. (MT10)F44≡W2 ∈ H(Y1) →W2 ∈ OS; (∀-el):F43F45≡W2 ∈ OS;(MP):F39, F44F46≡Y1 ∈W2 ∧W2 ∈OS →∃Y[Y 6= Y1 ∧Y ∈W2 ∧Y ∈U]; (∀-el):F10F47≡Y1 ∈ W2 ∧W2 ∈ OS;

∧F42, F45

F48≡∃Y[Y 6= Y1 ∧Y ∈W2 ∧Y ∈U]; (MP):F47, F46F49≡Y3 6= Y1 ∧ Y3 ∈ W2 ∧ Y3 ∈ U ; (∀-el):F48F50≡Y3 6= Y1; (∧-el):F49F51≡Y3 ∈ W2; (∧-el):F49F52≡Y3 ∈ U ; (∧-el):F49F53≡¬(Y2 ∈ W2) ∧Y3 ∈ W2 →Y2 6= Y3; tau.F41, F51 si egalitateF54≡¬(Y2 ∈ W2) ∧Y3 ∈ W2;

∧F41, F51

F55≡Y2 6= Y3; (MP):F54, F53F56≡Y3 ∈ W2; (∧-el):F49F57≡Y3 ∈ W2 ∧W2 ⊆V1 ∧W1 ∧W1 ⊆V;

∧F56,F40, F22

F58≡F57 →Y3 ∈ V ; din F57F59≡Y3 ∈ V ; (MP):F57, F58F60≡Y2 6= Y3 ∧Y3 ∈ V ∧Y3 ∈ U ;

∧F55, F59, F52

F61≡F60 →∃X[X 6= Y3 ∧Y3 ∈ V ∧Y3 ∈ U ; (→ ∃)F62≡∃X[X 6= Y3 ∧Y3 ∈ V ∧Y3 ∈ U ; (MP):F60, F61Am obtinut deductia simpla:X ∈U”, X ∈V ∧V ∈OS `∃X[X 6= Y3 ∧Y3 ∈ V ∧Y3 ∈ UX ∈U” `X ∈V ∧V ∈OS →∃X[X 6= Y3 ∧Y3 ∈ V ∧Y3 ∈ U ; (DT)cu (Gen) se obtine X ∈U” `X ∈U’Corolar `∀[U” ⊆U’]

59

Metateorema 19 (MT19)1)`∀U[U ’ = U’]2)`∀U[U ∈ CS]3)`∀U∀V[U ⊆V ∧V ∈CS →U ⊆V]

3.6 Axiomele de congruenta si continuitate

Definim AB ≡(A,B) ∪{A,B}Axiomele de congruenta.III1)(axioma de congruenta a segmentelor)∀A∀B ∀A’[R(A ∧B,d) & R(A’,l) ⇒ ∃B’[R(B’,l) & AB ∼=A’B’]dreptele d si l uneori pot coincideIII2)(axioma de clasa)∀A∀B ∀C ∀D ∀E ∀F[AB ∼=CD & CD ∼=EF ⇒ AB ∼=EF]III3)(axioma de compatibilitate)[R(A ∧B ∧C,d) & ABC] & [R(A’ ∧B’ ∧C’,l) & A’B’C’] &(AB ∼=A’B’) & (BC ∼=B’C’) ⇒ (AC ∼=A’C’)Din relatia de congruenta rezulta echivalenta ıntre segmente.a) reflexivitatea: AB ∼=AB;b)simetria: AB ∼=CD ⇒ CD ∼=AB;c)tranzitivitatea: (AB ∼=CD) & (CD ∼=EF) ⇒ (AB ∼=EF)Relatia de echivalenta ımparte segmentele ın clase numite lungimi.Axiomele de continuitate.Axioma lui Arhimede.. Fie pe o dreapta d punctele A, A1, B.Aleg punctele A2, A3, . . . cu ordinea

AA1A2, A1A2A3, . . .astfel ca

AA1 ∼=A1A2 ∼=A2A3 ∼=. . .exista atunci un punct An astfel ca sa avem ABAn.Axioma lui Dedekind. Fie punctele

A1, A2, . . . , An, . . . , Bn, . . . B2, B1situate ın aceata ordine pe dreapta d ıncat

A1B1 ⊇ A2B2 ⊇ . . . ⊇ AnBn ⊇ . . .

Atunci aceste intervale au un punct unic comun A0.Definitie. Fie o dreapta d.

60

O functie f : d → R se spune continua (bicontinua daca f−1) ınpunctul X0 daca si numai daca

∀U ∈ H(f(X0))∃V ∈ H(X0)∀X[X ∈ V → f(X) ∈ U ]

Definitie. AB < CD ≡∃E[CED ∧AB ∼=CE]Teorema lui Cantor - Dedekind. Exista o corepodenta bicon-

tinua ıntre o dreapta d si multimea numerelor reale R astfel caordinii de pe dreapta sa-i corespunda ordinea crescatoare sau de-screscatoare din multimea numerelor reale.Demonstratie.Schitam constructia functiei f(X).1) Fie Z multimea numerelor intregi

Z = {. . . ,−n, . . . ,−1, 0, 1, . . . , n, . . .}

la care facem sa corespunda biunivoc

{. . . , A−n, . . . , A−1, A0, A1, . . . , An, . . .}

2) Fie α un numar real ın intervalul [k,k+1] , k ıntreg.Din analiza matematica se stie ca sirul descendent de intervale

[a, b] ⊇ [a1, b1] ⊇ [a2, b2] ⊇ . . . [an, bn] ⊇ . . .

cu numerele rationale an, bn, a = k, b = k+1 si care satisfac

a ≤ a1 ≤ a2 ≤ . . . ≤ an ≤ . . . bn ≤ . . . b2 ≤ b1 ≤ b

bn − an =1

2n

are intersectie nevida numarul α(axioma lui Cantor) si

α = limn→∞

an = limn→∞

bn

Punem Aa = Ak, Ab = Ak+1 si ımpartim intervalul [a,b] ın doua

I1 = [k, k +1

2] I2 = [k +

1

2, k + 1]

Daca α ∈ I1 ⇒ a1 = a, b1 = k+1

2si repectiv avem punctele Aa1, Ab1.

61

Daca α ∈ I2 ⇒ a1 = k +1

2, b1 = k + 1 si repectiv avem punctele

Aa1, Ab1.

b1 − a1 =1

2

procedeul se continua se ımparte intervalul ın 22, parti si se obtie

I1 = [k, k+1

22], I2 = [k+

1

22, k+

2

22], I3 = [k+

2

22, k+

3

22], I4 = [k+

3

22, k+1]

si se reia rationamentul

a) Daca α ∈ I1 ⇒ a2 = k, b2 = k +1

22,⇒ Aa2, Ab2

b) Daca α ∈ I2 ⇒ a2 = k +1

22, b2 = k +

2

22⇒ Aa2, Ab2

c) Daca α ∈ I3 ⇒ a2 = k +2

22, b2 = k +

3

22⇒ Aa2, Ab2

d) Daca α ∈ I4 ⇒ a2 = k +3

22, b2 = k +

4

22⇒ Aa2, Ab2

ın final obtinem puncul Aα (axioma lui Dedekind).

3.7 Dreapta formala ın geometria hiberbolica

Acest capitol nu face apel la tehnica formala, el este introductiv ıngeometria hiperbolica.Fie un cerc Γ = {O,R}, un cerc de centru O, si raza R. si

multimea cercurilor ortogonale cu Γ.Daca A este un punct ın interiorul cercului Γ , iar A’ simetricul

punctului A fata de cercul Γ (OA ∗ OA2 = 1), atunci aceste punctese afla pe cercul ortogonal.Interiorul cercului Γ se numeste planul lui Lobacevski iar punctele

sale (cu exceptia centrului O) se numesc l - puncte Arcele cercurilorortogonale aflate ın interiorul lui Γ se numesc l - drepte.Urmatoarele axiome Hilbert devin teoreme ın geometria hiper-

bolica.(a se vedea pentru mai multe detalii A.I. Markusevici, Teo-

ria Analiticeskix Functii, pg.112, Gosudarstveno Izdatelstvo, Moskva,1950.)Noi vom formaliza aceste axiome.Daca l este o l - dreapta atunci sunt teoreme:

62

I. Axiomele de incidenta.I1) ∀A∀B∃lR(A ∧B, l)I2) ∀A∀B∃!lR(A ∧B, l) (! - exista unic)I3)∀l∃A∃BR(A ∧B, l)II. Axiomele de ordine.II1) ∀A∀B∀C[R(A ∧B ∧ C, l)→ (ABC → CBA)]II2) ∀A∀B∃C[R(A ∧B ∧ C, l)→ ABC]II3) ∀A∀B∀C[R(A ∧B ∧ C, l)→ (ABC ∨ ACB ∨ CAB)]II4)(ax.lui Pash)Fie trei puncte nesituate pe o dreapta l notate A,B,C∀A∀B∀C[¬R(A∨B∨C, l)∧∃XR(X, l)∧AXB → ∃Y [R(Y, l)→ (BY C∨

AY C)]]In cele ce urmeaza ne propunem sa gasim transformarea con-

forma.

(1) w = L(z) =Az + B

Cz +D(AD − BC 6= 0)

care transforma ccercul Γ : |z| = R, ın cercul |w| = R, punctul A(α)din interiorul cercului Γ ın centrul cercului |w| = R.Cum L(α) = 0⇒ Aα +B = 0, astfel

(2) w =z − αλz +m

(λα +m 6= 0)

cu λ =C

A, m =

B

AFie punctul M ∈ Γ, M(z = Reit = R cos t+ iR sin t)Fie λ = a+ ib, m = c+ di, α = x0 + iy0

|R cos t+ iR sin t− x0 − iy0| = R|(R cos t+R sin t)(a+ ib) + c+ id|

Atunci avem sistemul:

−x0 = R2(ac+ bd); (I)

−y0 = R2(ad− bc); (II)

R2 + x20 + y20 = R

2(a2R2 + b2R2 + c2 + d2); (III)

Ecuatia (I) a sistemului minus ecuatia (II)*i da

63

−x0 + iy0 = R2[ac+ bd− i(ad− bc)]

sau

−α = R2λm⇒ λ = −α

R2m(m 6= 0)

Astfel (2) devine

(3) w = R2mz − α

R2mm− αz; (R2mm− αα 6= 0)

Din ecuatiile sistemului facem combinatia (III)− (I)2 − (II)2

obtinem

−(c2 + d2 − 1)(c2R2 + b2R2 − 1) = 0

sau retranscris(mm− 1)(R2λλ− 1) = 0

inlocuind valoarea lui λ obtinem

(mm− 1)(mm− αα) = 0

Cum mm− αα) 6= 0⇒ mm− 1 = 0astfel (3) devine

(4) w = R2mz − αR2 − αz

;

Deoarece mm = 1⇒

(5) w = L(z) = R2eitz − αR2 − αz

Demonstratia axiomei II2)Punctul A(z = α) se va transforma prin o transformare L ın

originea cercului O iar iar B intr-un alt punct pe un diametru cetrece prin O si problema devine ın geometria euclidiana.Definitie. Fie E o multime de l-puncte si E simetrica sa ın

raport cu axa reala.Vom spune ca mutimea E este congruenta cu multimea F

notata

64

E ≡ F daca exista o transformare conforma de tipul (5) de maisus ıncat

F = L(E) ∨ L(E)

se poate arata ca aceasta este o relatie de echivalenta (vezi mon.citaamai sus).III. Axiomele de congruenta.III1) Daca A si B sunt pe o l - dreapta d a si A’ este pe aceasi

dreapta sau pe d atunci

∀A∀B∀A′[R(A ∧B, d) ∧R(A′, d)→ ∃B′(R(B′, d)→ AB ≡ A′B′)]

III2)AB ≡ A′B′

∨AB ≡ A”B”⇒ A′B′ ≡ A”B”

III3) Daca A, B, C sunt pe o l - dreapta d si A’, B’, C’ pe d atunci

AB ≡ A′B′∨BC ≡ B′C ′ ⇒ AC ≡ A′C ′

Metateorema. Axiomele III1) - III3) sunt teoreme ın geometriahiperbolica.Demonstratie.

III1) Fie punctele A,B,C ∈ d atunci L(A) = 0, L(B) = B1, L(C) =R pe OR iar A′, B′ ∈ l− d = d′ atunci L′(A′) = 0, L′(B′) = B1 iar prinL−1L′ , B’ este un punct care satisface axioma.Sa ara tam ca acest punct este unic.

65

Sa presupunem ca avem un punct B” ∈ d′ ıncatL′(B”) = B2 6= B1 pe axa OR cu |OB1| 6= |OB2|Prin definitie avem doua cazuri

L′(OB1) = OB2∨L′(OB1) = OB2

Cazul 1)Pentru A′(α′) printr-un L’ avem L′(A′) = 0 si

w = R2eitz

R2⇒ |w| = |z|

deci |OB1| = |OB2|Cazul 2)B1 trece ın O si O ın B2

w = L′(z) = R2eitz − B1R2 − B1z

; (α = B1)

B2 = L′(O) = −R2eit

B1

R2

⇒ |OB1| = |OB2| ceace este absurd.III2) se demonstreaza ın baza definitei.Daca A, B, C sunt pe o l - dreapta d si A’, B’, C’ pe d atunci

sa presupunem ipoteza

AB ≡ A′B′∨BC ≡ B′C ′

Presupunem ca avem pe un diametru

L(B) = O,L(A) = A1, L(C) = C1∨AB ≡ A′B′

∨AB = A′B′

dar atunci avemA′B′ ≡ A2B2

dar A1, A2 stau pe aceasi dreapta de aceasi parte a lui O deciA1 = A2 aleg C1 = C2 deci A1C1 ≡ A2C2Cu ajutorul proprietatii de echivalenta alui L (tranzitivitatea)

avem AC ≡ A′C ′

IV. Axiomele de continuitateAxioma lui Arhimede.

66

Fie pe o l - dreapta punctele A,A1, B cu ordinea AA1B alegempe l - dreapta punctele A2, . . . An−1 cu ordinea AA1A2, A1A2A3, . . . si

AA1 ≡ A1A2 ≡ . . . An−2An−1

atunci exista un n astfel ca sa avem ordine ABAn si AA1 ≡ BAnAxioma Cantor - DedkindFie pe o l - dreapta punctele

A,A1, A2, . . . , An, . . . , Bn, . . . B1, B

cuA1B1 ⊇ A2B2 ⊇ . . . ⊇ AnBn ⊇ . . .

atunci aceste au un punct comun C.Demonstratia se reduce cu o L transformare pe o dreapta luata

ca diametru.

67

Bibliografie

[1] E. Mendelson, Introduction to Mathematical Logic, D.Van Nos-trand Company, Inc., 1963

[2] C. Milici, Theorie formelle de droite et plan(I), Proc. the 9 thSyposium of Math.and its applications,Timisoara,pg.201 - 208,2001

[3] C. Milici, Theorie formelle de droite et plan(II), Proc. the 10 thSyposium of Math.and its applications,Timisoara,pg.269 - 274,2003

[4] A. Rosser, Logic for Mathematicians, Mc Graw-Hill Company,1953

[5] G. Samboan, Fundamente de matematica ,EDP, Bucuresti, 1974

68