16-tema. Predikatlar esabınıń qarama-qarsılıqsızlıǵı, tolıqlıǵı

16-tema. Predikatlar esabınıń qarama-qarsılıqsızlıǵı, tolıqlıǵı 

 

Hár qanday aksiomatikalıq teoriyada bazıbir formula hám onıń biykarlaması keltirilip shıǵarılıwshı bolsa, onda bunday teoriya 

qarama-qarsılıqlı, keri jaǵdayda qarama-qarsılıqsız teoriya ekenligi málim. 

Teorema-1. Predikatlar esabı qarama-qarsılıqsız. 

Bul teoremanıń dálilleniwi aytımlar esabı ushın dálillengen teoremanıń dálilleniwi menen birdey. 

Aytımlar esabındaǵı aksiomalar sisteması ushın tar hám keń maǵanadaǵı tolıqlılıq problemalarınan ekinshi tiykarǵı problema 

bolıp, onı tómendegi predikatlar esabı ushın keltiremiz. 

1-anıqlama.  Predikatlar  algebrasınıń  hár  bir  birdeyine  ras  formulası  predikatlar  esabında  keltirilip  shıǵarılıwshı  bolsa,  onda 

predikatlar esabınıń aksiomalar sisteması keń maǵanada tolıq delinedi. 

2-anıqlama. (I). Eger 

S

├ 

A

  hám 

S

├ 

A

 bolǵan hesh qanday 

A

 tastıyıqlawı bar bolmasa, onda tastıyıqlawlar kópligi qarama-

qarsılıqsız delinedi. 

(II). 

S

 kópligine kiriwshi tastıyıqlaw ras bolatuǵın model bar bolsa, onda 

S

  tastıyıqlawlardıń orınlanıwshı kópligi delinedi. 

(III). Hár bir 

A

 tastıyıqlaw ushın 

S

├ 

A

  yamasa 

S

├ 

A

 orınlı bolsa, onda 

S

  ( deduktiv ) tolıq kóplik delinedi. 

Bunda,  qálegen  kvantorsız  yamasa  erikli  ózgeriwshilerge  iye  bolmaǵan  formula  jabıq  formula  yaki  tastıyıqlaw  hám  de 

S

  - 

tastıyıqlawlardıń bazıbir kópligi bolıp tabıladı. 

Lemma-1.  Eger 



















n

S

S

S

1

0

  shártin  qanaatlandırıwshı

)

,

2

,

1

,

0

(









i

S

i

    tastıyıqlawlar  kópligi  qarama-qarsılıqsız  bolsa, 

onda tastıyıqlawlardıń 

t

t

S

S

0



 

 kópligi qarama-qarsılıqsız boladı. 

Dálilleniwi.

 

Meyli, hár bir 

i

S

 qarama-qarsılıqsız bolǵanda 

S

  qarama-qarsılıqlı bolsın. Onda sonday bir 

A

  tastıyıqlawı tabılıp, 

S

├ 

A

  hám 

S

├ 

A

  boladı.  Bunnan  konyuksiyanı 

)

(

  kiritiw  qádesine  muwapıq 

S

├ 

A

A



    bolatuǵınlıǵı  kelip  shıǵadı. 

A

A 

 

formulanıń dálilleniwinde 

S

 kópliginiń shekli sandaǵı formulaları qollanıladı. 

S

S 



. 

S 

-formulalarınıń shekli kópligi hám

S 

├

A

A 

    bolsın.  Onda  qandayda  bir 

k

S

  ushın 

k

S

S 



  boladı  hám  bunnan 

k

S

├

A

A 

  ekenligi  kelip  shıǵadı.  Payda  bolǵan  qatnas 

tastıyıqlawlardıń 

k

S

 kópligi qarama-qarsılıqlı dálillendi. 

Lemma-2. Tastıyıqlawlardıń 

S

 kópligi qarama-qarsılıqsız bolıwı ushın onıń hár bir shekli úles kópligi qarama-qarsılıqsız bolıwı 

zárúr hám jeterli. 

Dálilleniwi. Zárúrli shártiniń orınlanıwı (yaǵnıy 

S

 qarama-qarsılıqsız bolatuǵını ) anıq. Jetkilikli shártin qarama-qarsı dep oylap 

dálilleymiz:  

S

 kópliginiń hár bir shekli úles kópligi qarama-qarsılıqsız bolǵan jaǵdayda 

S 

 kópligi qarama-qarsılıqlı bolsın. Onda 

S

 te sonday bir 

A

 formula tabılıp, 

S

├

A

A 

  bolıp,  

A

A 

 dıń dálilleniwi de shekli 

S 

 kópliginiń formulaları da qatnasadı. 

S

S 



 

hám 

S 

├ 

A

A 

    bolǵanlıǵı  ushın 

S 

  kóplik  qarama-qarsılıqlı  kóplik  ekenliginen,  biziń  oylaǵanımızdıń  nadurıs  ekenligi  kelip 

shıǵadı. 

Teorema (Lendenbaum). Eger 

S

 tastıyıqlawlardıń qarama-qarsılıqsız kópligi, onda 

S

 ti óz ishine alǵan tastıyıqlawlardıń 

T

  tolıq 

sisteması bar boladı. 

Dálilleniwi. Teoremanı kerekli 

T

 kópligin dúziw jolı menen dálilleymiz. Daslep qaralıp atırǵan alfavit sanaqlı ( alfavittiń quwatı 

-  kópliktiń  quwatı sıpatında  )  ekenligi,  onıń quramına  kirgen signatura, basqa  formulalar  kópligi hám  de onıń quramına kirgen 

barlıq tastıyıqlawlar kópligi sanaqlı boladı. Sonıń menen birge signaturadaǵı hár bir ańlatpa formula bolıwı, formulalardıń bolsa, 

tastıyıqlaw bolatuǵının anıqlay alamız. 

Bul bizge hár bir tastıyıqlawdı qandayda bir usıl járdeminde natural sanlar menen nomerlew imkaniyatın beredi. Tastıyıqlawlardı 

sonday nomerlew múmkin, onda tastıyıqlawlardıń ózi berilgende onıń natural nomerin tabıw hám de nomerge qarap tastıyıqlawdıń 

ózin tiklew múmkin. Sanaqlı kóplik elementlerin (tastıyıqlawlar kópligin) bunday nomerlew Gyodel nomerasiyası delinedi. 

,...

,...,

,

1

0

n

A

A

A

  sonday  nomeraciyalardıń  biri  bolsın.  kerekli 

T

  kópligin  2-lemmada  keltirilgen  “  keńeyip  baratuǵın  ” 

tastıyıqlawlardıń  kóplikleriniń  birikpesi  sıpatında  dúzemiz.  Hár  bir 

i

S

  kóplik 

i

  qádemde  dúzilip,  onıń  qarama-qarsılıq-sızlıǵı 

induksiya metodı járdeminde dálillenedi.   

 

 

Nolinshi qádemde  

0

S

 kópligin tómendegishe dúzeyik:  



















.

'

,

 

 

 

у

 

 

ege

,

0

0

daуda

jag

ri

ke

A

S

bolsa

A

S

amasa

A

S

r

у

S

S

 

 

Egerde 

0

S

S 

  bolsa,  onda 

0

S

  diń  tábiyiy  túrde  qarama-qarsılıqsız  (

S

  kópligi  shártiniń  qarama-qarsılıqsız  bolǵanı  ushın). 





A

S

S





0

 bolsın. Shártke kóre 

S

├

0

A

  hám 

S

├

0

A

.  

0

S

 dı qarama- qarsılıqlı kóplik dep alsaq, onda qandayda bir 

B

 formula 

ushın 

S

, 

0

A

├

B

B 

 boladı. Basqasha aytqanda 

S

├

0

A



B

B 

 boladı. 

S

├

)

(

)

(

A

B

B

A







 - ( kontrapoziciya ) 

S

├

),

(

)

(

0

0

A

B

B

B

B

A











 

S

├

0

A

B

B





, 

S

, 

B

B 

├

0

A

,  

├

B

B 



B

B 

,  

S

├

B

B 

, (├

B

B 

 bolǵanı ushın ), 

S

, 

B

B 

├

0

A

 

qatnaslardan 

,

,

Г А С Г

А

Г С







 qádesine tiykarlanıp 

S

├

0

A

kelip shıǵadı. Bul joqarıdaǵı shártke qarama-qarsı. Demek ,  

0

S

 qarama-

qarsılıqsız kóplik eken. 

n

S

n

,

- qádemnen hám qarama-qarsılıqsızlıǵı dálillengen kóplik bolsın. Onda 

)

1

( 

n

 qádemge tómendegi 

kóplikti dúzemiz:  





1

1

1

1

, ege  

  у

 

 

 

,

'

.

n

n

n

n

n

n

n

n

S

у

r S

A

amasa S

A

bolsa

S

S

A

keri jag daуda

















 





 

1



n

S

diń qarama-qarsılıqsızlıǵı 

0

S

 diń qarama-qarsılıqızlıǵın kórsetkendey dálillenedi. 

Endi 

T

 sıpatında dúzilgen 

)

,

2

,

1

,

0

(









i

S

i

 kóplikleriniń birikpesin alamız. 

i

i

S

T





. 1- lemmaǵa tiykarlanıp 

T

 tastıyıqlawlarınıń 

qarama-qarsılıqsız kóplik ekenligi kelip shıǵadı.  

T

 nıń tolıq ekenligin kórseteyik. 

C

 bazıbir kóplikten alınǵan qálegen tastıyıqlaw 

bolsın. Onda sonday bir 

n

 natural nomeri tabılıp,

n

A

C

 boladı. 

n

S

 kópliginiń dúzilisi boyınsha 

n

S

├

n

A

  yamasa 

n

S

├

n

A

 boladı. 

n

S

T



 bolǵanı ushın 

T

├

n

A

  yamasa 

T

├

n

A

 boladı. Yaǵnıy 

T

 tastıyıqlawlarınıń tolıq kóplik ekenligi kelip shıǵadı. Teorema tolıq 

dálillendi. 

Teorema (K. Gyodel , tolıqlıq teoreması ). Qálegen 

A

 tastıyıqlaw predikatlar esabında keltirilip shıǵarılıwshı (dálilleniwshi ) 

bolıwı ushın onıń birdeyine ras bolıwı zárúrli hám jeterli, yaǵnıy ├



A

 

A

.  

Dálilleniwi. Zárúrli shárti 1- teoremanıń mazmunınan kelip shıǵadı. 

Jetkilikligi.  Egerde  tastıyıqlawlardıń 

S

  kópligi  orınlanıwshı  bolmasa,  onda 

S

  qarama-qarsılıqlı  kóplik  boladı.  Meyli, 

A

 

birdeyine ras formula ( tastıyıqlaw ) bolsın. Onda onıń biykarlaması bir 

B

 tastıyıqlaw bolıwı ushın 

 

A

 ├

B

B 

 

boladı. Kontrapoziciya qádesine tiykarlanıp 

  

 

B

B 

├

A

 

├ 

B

B 

 h’ám de ├

A



A

 lardan ├

A

 ekenligi kelip shıǵadı. Teorema dálillendi. 

 

 

Sorawlar hám shınıǵıwlar 

 

1.  K.Gyodel teoremasınıń zárúrli shártin dálilleń. 

2. 

S

 kópligi orınlanıwshı bolıwı ushın hár bir shekli úles kópligi orınlanıwshı bolıwı jetkilikli me? 

3.  Tómendegi formulalar PE keltirilip shıǵarılıwshı formula bola ma? 

1). 

).

(

)

(

x

U

x

x

U

x







 

2). 

).

(

)

(

x

U

x

x

U

x







 

3). 

).

,

(

у

у)

,

U(

у

x

U

x

x

у

x











 

4). 

).

,

(

у

у)

,

U(

у

x

U

x

x

у

x











 

5). 

)).

(

)

(

(

))

(

)

(

(

x

B

x

U

x

x

B

x

x

U

x











