Математическая логика и теория алгоритмов. Самохин А.В. - 51 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Составители: 

Рубрика: 

§3. æÕÎÄÉÒÏ×ÁÎÎÙÅ ÍÎÏÖÅÓÔ×Á 51
(×) ÄÌÑ ÍÎÏÖÅÓÔ×Á X ×ÅÒÅÎ ÐÒÉÎÃÉÐ ÉÎÄÕËÃÉÉ × ÓÌÅÄÕÀÝÅÊ ÆÏÒÍÅ: ÅÓÌÉ
(ÐÒÉ ËÁÖÄÏÍ x ∈ X) ÉÚ ÉÓÔÉÎÎÏÓÔÉ A(y) ÄÌÑ ×ÓÅÈ y < x ÓÌÅÄÕÅÔ ÉÓÔÉÎ-
ÎÏÓÔØ A(x), ÔÏ Ó×ÏÊÓÔ×Ï A(x) ×ÅÒÎÏ ÐÒÉ ×ÓÅÈ x. æÏÒÍÁÌØÎÏ ÜÔÏ ÚÁÐÉÓÙ-
×ÁÀÔ ÔÁË:
∀x (∀y ((y < x) ⇒ A(y)) ⇒ A(x)) ⇒ ∀x A(x).
äÏËÁÚÁÔÅÌØÓÔ×Ï. óÐÅÒ×Á ÄÏËÁÖÅÍ ÜË×É×ÁÌÅÎÔÎÏÓÔØ ÐÅÒ×ÙÈ Ä×ÕÈ Ó×ÏÊÓÔ×.
åÓÌÉ x
0
> x
1
> x
2
> . . . ¡ ÂÅÓËÏÎÅÞÎÁÑ ÕÂÙ×ÁÀÝÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ,
ÔÏ, ÏÞÅ×ÉÄÎÏ, ÍÎÏÖÅÓÔ×Ï Å¾ ÚÎÁÞÅÎÉÊ ÎÅ ÉÍÅÅÔ ÍÉÎÉÍÁÌØÎÏÇÏ ÜÌÅÍÅÎÔÁ (ÄÌÑ
ËÁÖÄÏÇÏ ÜÌÅÍÅÎÔÁ ÓÌÅÄÕÀÝÉÊ Åݾ ÍÅÎØÛÅ). ðÏÜÔÏÍÕ ÉÚ (Á) ÓÌÅÄÕÅÔ (Â). îÁ-
ÐÒÏÔÉ×, ÅÓÌÉ B ¡ ÎÅÐÕÓÔÏÅ ÍÎÏÖÅÓÔ×Ï, ÎÅ ÉÍÅÀÝÅÅ ÍÉÎÉÍÁÌØÎÏÇÏ ÜÌÅÍÅÎ-
ÔÁ, ÔÏ ÂÅÓËÏÎÅÞÎÕÀ ÕÂÙ×ÁÀÝÕÀ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÔÁË.
÷ÏÚØÍ¾Í ÐÒÏÉÚ×ÏÌØÎÙÊ ÜÌÅÍÅÎÔ b
0
∈ B. ðÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÏÎ ÎÅ Ñ×ÌÑÅÔÓÑ
ÍÉÎÉÍÁÌØÎÙÍ, ÔÁË ÞÔÏ ÍÏÖÎÏ ÎÁÊÔÉ b
1
∈ B, ÄÌÑ ËÏÔÏÒÏÇÏ b
0
> b
1
. ðÏ ÔÅÍ
ÖÅ ÐÒÉÞÉÎÁÍ ÍÏÖÎÏ ÎÁÊÔÉ b
2
∈ B, ÄÌÑ ËÏÔÏÒÏÇÏ b
1
> b
2
É Ô. Ä. ðÏÌÕÞÁÅÔÓÑ
ÂÅÓËÏÎÅÞÎÁÑ ÕÂÙ×ÁÀÝÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ.
ôÅÐÅÒØ ×Ù×ÅÄÅÍ ÐÒÉÎÃÉÐ ÉÎÄÕËÃÉÉ ÉÚ ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ÍÉÎÉÍÁÌØÎÏÇÏ ÜÌÅ-
ÍÅÎÔÁ × ÌÀÂÏÍ ÐÏÄÍÎÏÖÅÓÔ×Å. ðÕÓÔØ A(x) ¡ ÐÒÏÉÚ×ÏÌØÎÏÅ Ó×ÏÊÓÔ×Ï ÜÌÅ-
ÍÅÎÔÏ× ÍÎÏÖÅÓÔ×Á X, ×ÅÒÎÏÅ ÎÅ ÄÌÑ ×ÓÅÈ ÜÌÅÍÅÎÔÏ× x. òÁÓÓÍÏÔÒÉÍ ÎÅÐÕÓÔÏÅ
ÍÎÏÖÅÓÔ×Ï B ÔÅÈ ÜÌÅÍÅÎÔÏ×, ÄÌÑ ËÏÔÏÒÙÈ Ó×ÏÊÓÔ×Ï A ÎÅ×ÅÒÎÏ. ðÕÓÔØ x ¡
ÍÉÎÉÍÁÌØÎÙÊ ÜÌÅÍÅÎÔ ÍÎÏÖÅÓÔ×Á B. ðÏ ÕÓÌÏ×ÉÀ ÍÅÎØÛÉÈ ÜÌÅÍÅÎÔÏ× × ÍÎÏ-
ÖÅÓÔ×Å B ÎÅÔ, ÐÏÜÔÏÍÕ ÄÌÑ ×ÓÅÈ y < x Ó×ÏÊÓÔ×Ï A(y) ×ÙÐÏÌÎÅÎÏ. îÏ ÔÏÇÄÁ
ÐÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÄÏÌÖÎÏ ÂÙÔØ ×ÙÐÏÌÎÅÎÏ É A(x) ¡ ÐÒÏÔÉ×ÏÒÅÞÉÅ.
ïÓÔÁÌÏÓØ ÄÏËÁÚÁÔØ ÓÕÝÅÓÔ×Ï×ÁÎÉÅ ÍÉÎÉÍÁÌØÎÏÇÏ ÜÌÅÍÅÎÔÁ × ÌÀÂÏÍ ÎÅ-
ÐÕÓÔÏÍ ÐÏÄÍÎÏÖÅÓÔ×Å, ÉÓÈÏÄÑ ÉÚ ÐÒÉÎÃÉÐÁ ÉÎÄÕËÃÉÉ. ðÕÓÔØ B ¡ ÐÏÄÍÎÏ-
ÖÅÓÔ×Ï ÂÅÚ ÍÉÎÉÍÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×. äÏËÁÖÅÍ ÐÏ ÉÎÄÕËÃÉÉ, ÞÔÏ B ÐÕÓÔÏ;
ÄÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, × ËÁÞÅÓÔ×Å A(x) ×ÏÚØÍ¾Í Ó×ÏÊÓÔ×Ï x /∈ B. ÷ ÓÁÍÏÍ ÄÅÌÅ,
ÅÓÌÉ A(y) ×ÅÒÎÏ ÄÌÑ ×ÓÅÈ y < x, ÔÏ ÎÉËÁËÏÊ ÜÌÅÍÅÎÔ, ÍÅÎØÛÉÊ x, ÎÅ ÌÅÖÉÔ
× B. åÓÌÉ ÂÙ x ÌÅÖÁÌ × B, ÔÏ ÏÎ ÂÙÌ ÂÙ ÔÁÍ ÍÉÎÉÍÁÌØÎÙÍ, Á ÔÁËÉÈ ÎÅÔ.
íÎÏÖÅÓÔ×Á, ÏÂÌÁÄÁÀÝÉÅ Ó×ÏÊÓÔ×ÁÍÉ (Á) (×), ÎÁÚÙ×ÁÀÔÓÑ ÆÕÎÄÉÒÏ×ÁÎ-
ÎÙÍÉ. ëÁËÉÅ ÅÓÔØ ÐÒÉÍÅÒÙ ÆÕÎÄÉÒÏ×ÁÎÎÙÈ ÍÎÏÖÅÓÔ×? ðÒÅÖÄÅ ×ÓÅÇÏ, ÎÁÛ
ÉÓÈÏÄÎÙÊ ÐÒÉÍÅÒ ¡ ÍÎÏÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ.
äÒÕÇÏÊ ÐÒÉÍÅÒ ¡ ÍÎÏÖÅÓÔ×Ï N × N ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ (ÍÅÎØÛÅ
ÔÁ ÐÁÒÁ, Õ ËÏÔÏÒÏÊ ×ÔÏÒÏÊ ÞÌÅÎ ÍÅÎØÛÅ; × ÓÌÕÞÁÅ ÒÁ×ÅÎÓÔ×Á ÓÒÁ×ÎÉ×ÁÅÍ
ÐÅÒ×ÙÅ). ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÒÏ×ÅÒÉÍ ÕÓÌÏ×ÉÅ (Â). îÁÍ ÂÕÄÅÔ ÕÄÏÂÎÏ ÓÆÏÒÍÕÌÉ-
ÒÏ×ÁÔØ ÅÇÏ ÔÁË: ×ÓÑËÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ u
0
> u
1
> u
2
> . . . ÜÌÅÍÅÎÔÏ×
ÍÎÏÖÅÓÔ×Á ÒÁÎÏ ÉÌÉ ÐÏÚÄÎÏ ÓÔÁÂÉÌÉÚÉÒÕÅÔÓÑ (×ÓÅ ÞÌÅÎÙ, ÎÁÞÉÎÁÑ Ó ÎÅËÏÔÏ-
ÒÏÇÏ, ÒÁ×ÎÙ); ÏÞÅ×ÉÄÎÏ, ÞÔÏ ÜÔÏ ÜË×É×ÁÌÅÎÔÎÁÑ ÆÏÒÍÕÌÉÒÏ×ËÁ.
ðÕÓÔØ ÄÁÎÁ ÐÒÏÉÚ×ÏÌØÎÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÐÁÒ
hx
0
, y
0
i > hx
1
, y
1
i > hx
2
, y
2
i > . . .
§3. æÕÎÄÉÒÏ×ÁÎÎÙÅ ÍÎÏÖÅÓÔ×Á                                          51

   (×) ÄÌÑ ÍÎÏÖÅÓÔ×Á X ×ÅÒÅÎ ÐÒÉÎÃÉÐ ÉÎÄÕËÃÉÉ × ÓÌÅÄÕÀÝÅÊ ÆÏÒÍÅ: ÅÓÌÉ
(ÐÒÉ ËÁÖÄÏÍ x ∈ X) ÉÚ ÉÓÔÉÎÎÏÓÔÉ A(y) ÄÌÑ ×ÓÅÈ y < x ÓÌÅÄÕÅÔ ÉÓÔÉÎ-
ÎÏÓÔØ A(x), ÔÏ Ó×ÏÊÓÔ×Ï A(x) ×ÅÒÎÏ ÐÒÉ ×ÓÅÈ x. æÏÒÍÁÌØÎÏ ÜÔÏ ÚÁÐÉÓÙ-
×ÁÀÔ ÔÁË:
               ∀x (∀y ((y < x) ⇒ A(y)) ⇒ A(x)) ⇒ ∀x A(x).
   äÏËÁÚÁÔÅÌØÓÔ×Ï. óÐÅÒ×Á ÄÏËÁÖÅÍ ÜË×É×ÁÌÅÎÔÎÏÓÔØ ÐÅÒ×ÙÈ Ä×ÕÈ Ó×ÏÊÓÔ×.
åÓÌÉ x0 > x1 > x2 > . . . ¡ ÂÅÓËÏÎÅÞÎÁÑ ÕÂÙ×ÁÀÝÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ,
ÔÏ, ÏÞÅ×ÉÄÎÏ, ÍÎÏÖÅÓÔ×Ï Å¾ ÚÎÁÞÅÎÉÊ ÎÅ ÉÍÅÅÔ ÍÉÎÉÍÁÌØÎÏÇÏ ÜÌÅÍÅÎÔÁ (ÄÌÑ
ËÁÖÄÏÇÏ ÜÌÅÍÅÎÔÁ ÓÌÅÄÕÀÝÉÊ Åݾ ÍÅÎØÛÅ). ðÏÜÔÏÍÕ ÉÚ (Á) ÓÌÅÄÕÅÔ (Â). îÁ-
ÐÒÏÔÉ×, ÅÓÌÉ B ¡ ÎÅÐÕÓÔÏÅ ÍÎÏÖÅÓÔ×Ï, ÎÅ ÉÍÅÀÝÅÅ ÍÉÎÉÍÁÌØÎÏÇÏ ÜÌÅÍÅÎ-
ÔÁ, ÔÏ ÂÅÓËÏÎÅÞÎÕÀ ÕÂÙ×ÁÀÝÕÀ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÔÁË.
÷ÏÚØÍ¾Í ÐÒÏÉÚ×ÏÌØÎÙÊ ÜÌÅÍÅÎÔ b0 ∈ B. ðÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÏÎ ÎÅ Ñ×ÌÑÅÔÓÑ
ÍÉÎÉÍÁÌØÎÙÍ, ÔÁË ÞÔÏ ÍÏÖÎÏ ÎÁÊÔÉ b1 ∈ B, ÄÌÑ ËÏÔÏÒÏÇÏ b0 > b1. ðÏ ÔÅÍ
ÖÅ ÐÒÉÞÉÎÁÍ ÍÏÖÎÏ ÎÁÊÔÉ b2 ∈ B, ÄÌÑ ËÏÔÏÒÏÇÏ b1 > b2 É Ô. Ä. ðÏÌÕÞÁÅÔÓÑ
ÂÅÓËÏÎÅÞÎÁÑ ÕÂÙ×ÁÀÝÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ.
   ôÅÐÅÒØ ×Ù×ÅÄÅÍ ÐÒÉÎÃÉÐ ÉÎÄÕËÃÉÉ ÉÚ ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ÍÉÎÉÍÁÌØÎÏÇÏ ÜÌÅ-
ÍÅÎÔÁ × ÌÀÂÏÍ ÐÏÄÍÎÏÖÅÓÔ×Å. ðÕÓÔØ A(x) ¡ ÐÒÏÉÚ×ÏÌØÎÏÅ Ó×ÏÊÓÔ×Ï ÜÌÅ-
ÍÅÎÔÏ× ÍÎÏÖÅÓÔ×Á X, ×ÅÒÎÏÅ ÎÅ ÄÌÑ ×ÓÅÈ ÜÌÅÍÅÎÔÏ× x. òÁÓÓÍÏÔÒÉÍ ÎÅÐÕÓÔÏÅ
ÍÎÏÖÅÓÔ×Ï B ÔÅÈ ÜÌÅÍÅÎÔÏ×, ÄÌÑ ËÏÔÏÒÙÈ Ó×ÏÊÓÔ×Ï A ÎÅ×ÅÒÎÏ. ðÕÓÔØ x ¡
ÍÉÎÉÍÁÌØÎÙÊ ÜÌÅÍÅÎÔ ÍÎÏÖÅÓÔ×Á B. ðÏ ÕÓÌÏ×ÉÀ ÍÅÎØÛÉÈ ÜÌÅÍÅÎÔÏ× × ÍÎÏ-
ÖÅÓÔ×Å B ÎÅÔ, ÐÏÜÔÏÍÕ ÄÌÑ ×ÓÅÈ y < x Ó×ÏÊÓÔ×Ï A(y) ×ÙÐÏÌÎÅÎÏ. îÏ ÔÏÇÄÁ
ÐÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÄÏÌÖÎÏ ÂÙÔØ ×ÙÐÏÌÎÅÎÏ É A(x) ¡ ÐÒÏÔÉ×ÏÒÅÞÉÅ.
   ïÓÔÁÌÏÓØ ÄÏËÁÚÁÔØ ÓÕÝÅÓÔ×Ï×ÁÎÉÅ ÍÉÎÉÍÁÌØÎÏÇÏ ÜÌÅÍÅÎÔÁ × ÌÀÂÏÍ ÎÅ-
ÐÕÓÔÏÍ ÐÏÄÍÎÏÖÅÓÔ×Å, ÉÓÈÏÄÑ ÉÚ ÐÒÉÎÃÉÐÁ ÉÎÄÕËÃÉÉ. ðÕÓÔØ B ¡ ÐÏÄÍÎÏ-
ÖÅÓÔ×Ï ÂÅÚ ÍÉÎÉÍÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×. äÏËÁÖÅÍ ÐÏ ÉÎÄÕËÃÉÉ, ÞÔÏ B ÐÕÓÔÏ;
ÄÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, × ËÁÞÅÓÔ×Å A(x) ×ÏÚØÍ¾Í Ó×ÏÊÓÔ×Ï x ∈ / B. ÷ ÓÁÍÏÍ ÄÅÌÅ,
ÅÓÌÉ A(y) ×ÅÒÎÏ ÄÌÑ ×ÓÅÈ y < x, ÔÏ ÎÉËÁËÏÊ ÜÌÅÍÅÎÔ, ÍÅÎØÛÉÊ x, ÎÅ ÌÅÖÉÔ
× B. åÓÌÉ ÂÙ x ÌÅÖÁÌ × B, ÔÏ ÏÎ ÂÙÌ ÂÙ ÔÁÍ ÍÉÎÉÍÁÌØÎÙÍ, Á ÔÁËÉÈ ÎÅÔ.
   íÎÏÖÅÓÔ×Á, ÏÂÌÁÄÁÀÝÉÅ Ó×ÏÊÓÔ×ÁÍÉ (Á) (×), ÎÁÚÙ×ÁÀÔÓÑ ÆÕÎÄÉÒÏ×ÁÎ-
ÎÙÍÉ. ëÁËÉÅ ÅÓÔØ ÐÒÉÍÅÒÙ ÆÕÎÄÉÒÏ×ÁÎÎÙÈ ÍÎÏÖÅÓÔ×? ðÒÅÖÄÅ ×ÓÅÇÏ, ÎÁÛ
ÉÓÈÏÄÎÙÊ ÐÒÉÍÅÒ ¡ ÍÎÏÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ.
   äÒÕÇÏÊ ÐÒÉÍÅÒ ¡ ÍÎÏÖÅÓÔ×Ï N × N ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ (ÍÅÎØÛÅ
ÔÁ ÐÁÒÁ, Õ ËÏÔÏÒÏÊ ×ÔÏÒÏÊ ÞÌÅÎ ÍÅÎØÛÅ; × ÓÌÕÞÁÅ ÒÁ×ÅÎÓÔ×Á ÓÒÁ×ÎÉ×ÁÅÍ
ÐÅÒ×ÙÅ). ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÒÏ×ÅÒÉÍ ÕÓÌÏ×ÉÅ (Â). îÁÍ ÂÕÄÅÔ ÕÄÏÂÎÏ ÓÆÏÒÍÕÌÉ-
ÒÏ×ÁÔØ ÅÇÏ ÔÁË: ×ÓÑËÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ u0 > u1 > u2 > . . . ÜÌÅÍÅÎÔÏ×
ÍÎÏÖÅÓÔ×Á ÒÁÎÏ ÉÌÉ ÐÏÚÄÎÏ ÓÔÁÂÉÌÉÚÉÒÕÅÔÓÑ (×ÓÅ ÞÌÅÎÙ, ÎÁÞÉÎÁÑ Ó ÎÅËÏÔÏ-
ÒÏÇÏ, ÒÁ×ÎÙ); ÏÞÅ×ÉÄÎÏ, ÞÔÏ ÜÔÏ ÜË×É×ÁÌÅÎÔÎÁÑ ÆÏÒÍÕÌÉÒÏ×ËÁ.
   ðÕÓÔØ ÄÁÎÁ ÐÒÏÉÚ×ÏÌØÎÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÐÁÒ
                    hx0 , y0i > hx1 , y1i > hx2, y2i > . . .

Страницы