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

UptoLike

ВУЗ: 

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

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

Рубрика: 

170 çÌÁ×Á X. ôÅÏÒÅÍÁ Ï ÎÅÐÏÄ×ÉÖÎÏÊ ÔÏÞËÅ
≡-ÐÒÏÄÏÌÖÅÎÉÅ. üÔÏ ÄÅÌÁÅÔÓÑ ÔÁË. ÷ÙÒÁÖÅÎÉÅ [[x](x)](y) ×ÙÞÉÓÌÉÍÏ
ÚÁ×ÉÓÉÔ ÏÔ Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×. íÙ ×ÓÐÏÍÉÎÁÅÍ, ÞÔÏ U ÅÓÔØ ÇÌÁ×ÎÁÑ ÕÎÉ×ÅÒ-
ÓÁÌØÎÁÑ ÆÕÎËÃÉÑ, É ÎÁÈÏÄÉÍ ÔÁËÕÀ ÐÒÏÇÒÁÍÍÕ g, ÞÔÏ [[g](x)](y) = [[x](x)](y)
ÐÒÉ ×ÓÅÈ x É y. ðÒÉ ÜÔÏÍ [g](x) ÏÐÒÅÄÅÌÅÎÏ ÄÌÑ ×ÓÅÈ x. ðÕÓÔØ ÍÙ ÈÏÔÉÍ
ÎÁÊÔÉ ÎÅÐÏÄ×ÉÖÎÕÀ ÔÏÞËÕ ÐÒÏÇÒÁÍÍÙ h. íÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ ËÏÍÐÏ-
ÚÉÃÉÀ [h]([g](x)). üÔÏ ×ÙÒÁÖÅÎÉÅ ×ÙÞÉÓÌÉÍÏ ÚÁ×ÉÓÉÔ ÏÔ x, É ÐÏÔÏÍÕ
ÓÕÝÅÓÔ×ÕÅÔ ÐÒÏÇÒÁÍÍÁ t, ÄÌÑ ËÏÔÏÒÏÊ [t](x) = [h]([g](x)) ÐÒÉ ×ÓÅÈ x. üÔÁ
ÐÒÏÇÒÁÍÍÁ ÐÒÉÍÅÎÉÍÁ ËÏ ×ÓÅÍ x, ÐÏÓËÏÌØËÕ ÔÁËÏ×Ù h É g. ôÅÐÅÒØ ÎÅÐÏÄ×ÉÖ-
ÎÏÊ ÔÏÞËÏÊ ÂÕÄÅÔ [g](t). þÔÏÂÙ ÕÂÅÄÉÔØÓÑ × ÜÔÏÍ, ÍÙ ÄÏÌÖÎÙ ÐÒÏ×ÅÒÉÔØ,
ÞÔÏ [[g](t)](x) = [[h]([g](t))](x) ÄÌÑ ×ÓÅÈ x. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÏ Ó×ÏÊÓÔ×Õ g
ÉÍÅÅÍ [[g](t)](x) = [[t](t)](x). ÷ÓÐÏÍÉÎÁÑ ÏÐÒÅÄÅÌÅÎÉÅ t, ÜÔÏ ×ÙÒÁÖÅÎÉÅ
ÍÏÖÎÏ ÐÅÒÅÐÉÓÁÔØ ËÁË [[h]([g](t))](x) ¡ ÞÔÏ ËÁË ÒÁÚ É ÔÒÅÂÏ×ÁÌÏÓØ.
§2. ðÒÏÇÒÁÍÍÁ, ÐÅÞÁÔÁÀÝÁÑ Ó×ÏÊ ÔÅËÓÔ
ëÌÁÓÓÉÞÅÓËÉÍ ÐÒÉÍÅÒÏÍ ÐÒÉÍÅÎÅÎÉÑ ÔÅÏÒÅÍÙ Ï ÎÅÐÏÄ×ÉÖÎÏÊ ÔÏÞËÅ Ñ×ÌÑ-
ÅÔÓÑ ÔÁËÏŠž ÓÌÅÄÓÔ×ÉÅ: ÓÕÝÅÓÔ×ÕÅÔ ÐÒÏÇÒÁÍÍÁ, ÐÅÞÁÔÁÀÝÁÑ (ÎÁ ÌÀÂÏÍ
×ÈÏÄÅ) Ó×ÏÊ ÓÏÂÓÔ×ÅÎÎÙÊ ÔÅËÓÔ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÓÌÉ ÂÙ ÔÁËÏÊ ÐÒÏÇÒÁÍÍÙ ÎÅ
ÂÙÌÏ, ÔÏ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÅ
p 7→ (ÐÒÏÇÒÁÍÍÁ, ËÏÔÏÒÁÑ ÎÁ ÌÀÂÏÍ ×ÈÏÄÅ ÐÅÞÁÔÁÅÔ p)
ÎÅ ÉÍÅÌÏ ÂÙ ÎÅÐÏÄ×ÉÖÎÏÊ ÔÏÞËÉ.
æÏÒÍÁÌØÎÏ ÇÏ×ÏÒÑ, ÜÔÏ ÓÌÅÄÓÔ×ÉÅ ÍÏÖÎÏ ×ÙÒÁÚÉÔØ ÔÁË:
ôÅÏÒÅÍÁ 67. ðÕÓÔØ U(n, x) ¡ ÇÌÁ×ÎÁÑ ×ÙÞÉÓÌÉÍÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ
ÆÕÎËÃÉÑ ÄÌÑ ËÌÁÓÓÁ ×ÓÅÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ. ôÏÇÄÁ
ÓÕÝÅÓÔ×ÕÅÔ ÔÁËÏÅ ÞÉÓÌÏ p, ÞÔÏ U(p, x) = p ÄÌÑ ÌÀÂÏÇÏ x.
÷ ÐÒÏÇÒÁÍÍÉÓÔÓËÉÈ ÔÅÒÍÉÎÁÈ: ÐÕÓÔØ U(p, x) ¡ ÒÅÚÕÌØÔÁÔ ÐÒÉÍÅÎÅÎÉÑ
C-ÐÒÏÇÒÁÍÍÙ p Ë ÓÔÁÎÄÁÒÔÎÏÍÕ ×ÈÏÄÕ x. (õÔÏÞÎÅÎÉÑ: (1) ÍÙ ÏÔÏÖÄÅÓÔ×ÌÑÅÍ
ÞÉÓÌÁ É ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ÂÁÊÔÏ×; (2) ÅÓÌÉ ÐÒÏÇÒÁÍÍÁ ÎÅ ÚÁ×ÅÒÛÁÅÔ ÒÁ-
ÂÏÔÙ, ÍÙ ÓÞÉÔÁÅÍ, ÞÔÏ ÒÅÚÕÌØÔÁÔ ÎÅ ÏÐÒÅÄÅ̾Î, ÄÁÖÅ ÅÓÌÉ ÎÁ ÓÔÁÎÄÁÒÔÎÙÊ
×ÙÈÏÄ ÞÔÏ-ÔÏ ÐÏÓÌÁÎÏ.) ñÓÎÏ, ÞÔÏ ÆÕÎËÃÉÑ U ÂÕÄÅÔ ÇÌÁ×ÎÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÊ
ÆÕÎËÃÉÅÊ. ðÏÜÔÏÍÕ Ë ÎÅÊ ÍÏÖÎÏ ÐÒÉÍÅÎÉÔØ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÎÏÅ ÔÏÌØËÏ ÞÔÏ
ÕÔ×ÅÒÖÄÅÎÉÅ; ÐÏÌÕÞÉÍ ÐÒÏÇÒÁÍÍÕ p, ËÏÔÏÒÁÑ ÐÒÉ ÌÀÂÏÍ ×ÈÏÄÅ ÎÁ ×ÙÈÏÄÅ
ÄÁ¾Ô p.
ñÓÎÏ, ÞÔÏ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ ÐÒÉÍÅÎÉÍÏ ÄÌÑ ÌÀÂÏÇÏ ÑÚÙËÁ ÐÒÏÇÒÁÍÍÉÒÏ-
×ÁÎÉÑ; ÔÏ, ÞÔÏ ÍÙ ÕÐÏÍÑÎÕÌÉ ÑÚÙË C, ÒÏÌÉ ÎÅ ÉÇÒÁÅÔ.
úÁÄÁÞÁ 194. äÏËÁÖÉÔÅ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ C-ÐÒÏÇÒÁÍÍÁ, ËÏÔÏÒÁÑ ÐÅ-
ÞÁÔÁÅÔ Ó×ÏÊ ÔÅËÓÔ ÚÁÄÏÍ ÎÁÐÅÒ¾Ä.
170                               çÌÁ×Á X. ôÅÏÒÅÍÁ Ï ÎÅÐÏÄ×ÉÖÎÏÊ ÔÏÞËÅ

≡-ÐÒÏÄÏÌÖÅÎÉÅ. üÔÏ ÄÅÌÁÅÔÓÑ ÔÁË. ÷ÙÒÁÖÅÎÉÅ [[x](x)](y) ×ÙÞÉÓÌÉÍÏ
ÚÁ×ÉÓÉÔ ÏÔ Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×. íÙ ×ÓÐÏÍÉÎÁÅÍ, ÞÔÏ U ÅÓÔØ ÇÌÁ×ÎÁÑ ÕÎÉ×ÅÒ-
ÓÁÌØÎÁÑ ÆÕÎËÃÉÑ, É ÎÁÈÏÄÉÍ ÔÁËÕÀ ÐÒÏÇÒÁÍÍÕ g, ÞÔÏ [[g](x)](y) = [[x](x)](y)
ÐÒÉ ×ÓÅÈ x É y. ðÒÉ ÜÔÏÍ [g](x) ÏÐÒÅÄÅÌÅÎÏ ÄÌÑ ×ÓÅÈ x. ðÕÓÔØ ÍÙ ÈÏÔÉÍ
ÎÁÊÔÉ ÎÅÐÏÄ×ÉÖÎÕÀ ÔÏÞËÕ ÐÒÏÇÒÁÍÍÙ h. íÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ ËÏÍÐÏ-
ÚÉÃÉÀ [h]([g](x)). üÔÏ ×ÙÒÁÖÅÎÉÅ ×ÙÞÉÓÌÉÍÏ ÚÁ×ÉÓÉÔ ÏÔ x, É ÐÏÔÏÍÕ
ÓÕÝÅÓÔ×ÕÅÔ ÐÒÏÇÒÁÍÍÁ t, ÄÌÑ ËÏÔÏÒÏÊ [t](x) = [h]([g](x)) ÐÒÉ ×ÓÅÈ x. üÔÁ
ÐÒÏÇÒÁÍÍÁ ÐÒÉÍÅÎÉÍÁ ËÏ ×ÓÅÍ x, ÐÏÓËÏÌØËÕ ÔÁËÏ×Ù h É g. ôÅÐÅÒØ ÎÅÐÏÄ×ÉÖ-
ÎÏÊ ÔÏÞËÏÊ ÂÕÄÅÔ [g](t). þÔÏÂÙ ÕÂÅÄÉÔØÓÑ × ÜÔÏÍ, ÍÙ ÄÏÌÖÎÙ ÐÒÏ×ÅÒÉÔØ,
ÞÔÏ [[g](t)](x) = [[h]([g](t))](x) ÄÌÑ ×ÓÅÈ x. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÏ Ó×ÏÊÓÔ×Õ g
ÉÍÅÅÍ [[g](t)](x) = [[t](t)](x). ÷ÓÐÏÍÉÎÁÑ ÏÐÒÅÄÅÌÅÎÉÅ t, ÜÔÏ ×ÙÒÁÖÅÎÉÅ
ÍÏÖÎÏ ÐÅÒÅÐÉÓÁÔØ ËÁË [[h]([g](t))](x) ¡ ÞÔÏ ËÁË ÒÁÚ É ÔÒÅÂÏ×ÁÌÏÓØ.

  §2. ðÒÏÇÒÁÍÍÁ, ÐÅÞÁÔÁÀÝÁÑ Ó×ÏÊ ÔÅËÓÔ
   ëÌÁÓÓÉÞÅÓËÉÍ ÐÒÉÍÅÒÏÍ ÐÒÉÍÅÎÅÎÉÑ ÔÅÏÒÅÍÙ Ï ÎÅÐÏÄ×ÉÖÎÏÊ ÔÏÞËÅ Ñ×ÌÑ-
ÅÔÓÑ ÔÁËÏŠž ÓÌÅÄÓÔ×ÉÅ: ÓÕÝÅÓÔ×ÕÅÔ ÐÒÏÇÒÁÍÍÁ, ÐÅÞÁÔÁÀÝÁÑ (ÎÁ ÌÀÂÏÍ
×ÈÏÄÅ) Ó×ÏÊ ÓÏÂÓÔ×ÅÎÎÙÊ ÔÅËÓÔ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÓÌÉ ÂÙ ÔÁËÏÊ ÐÒÏÇÒÁÍÍÙ ÎÅ
ÂÙÌÏ, ÔÏ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÅ
          p 7→ (ÐÒÏÇÒÁÍÍÁ, ËÏÔÏÒÁÑ ÎÁ ÌÀÂÏÍ ×ÈÏÄÅ ÐÅÞÁÔÁÅÔ p)
ÎÅ ÉÍÅÌÏ ÂÙ ÎÅÐÏÄ×ÉÖÎÏÊ ÔÏÞËÉ.
   æÏÒÍÁÌØÎÏ ÇÏ×ÏÒÑ, ÜÔÏ ÓÌÅÄÓÔ×ÉÅ ÍÏÖÎÏ ×ÙÒÁÚÉÔØ ÔÁË:
  ôÅÏÒÅÍÁ 67. ðÕÓÔØ U(n, x) ¡ ÇÌÁ×ÎÁÑ ×ÙÞÉÓÌÉÍÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ
ÆÕÎËÃÉÑ ÄÌÑ ËÌÁÓÓÁ ×ÓÅÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ. ôÏÇÄÁ
ÓÕÝÅÓÔ×ÕÅÔ ÔÁËÏÅ ÞÉÓÌÏ p, ÞÔÏ U(p, x) = p ÄÌÑ ÌÀÂÏÇÏ x.
  ÷ ÐÒÏÇÒÁÍÍÉÓÔÓËÉÈ ÔÅÒÍÉÎÁÈ: ÐÕÓÔØ U(p, x) ¡ ÒÅÚÕÌØÔÁÔ ÐÒÉÍÅÎÅÎÉÑ
C-ÐÒÏÇÒÁÍÍÙ p Ë ÓÔÁÎÄÁÒÔÎÏÍÕ ×ÈÏÄÕ x. (õÔÏÞÎÅÎÉÑ: (1) ÍÙ ÏÔÏÖÄÅÓÔ×ÌÑÅÍ
ÞÉÓÌÁ É ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ÂÁÊÔÏ×; (2) ÅÓÌÉ ÐÒÏÇÒÁÍÍÁ ÎÅ ÚÁ×ÅÒÛÁÅÔ ÒÁ-
ÂÏÔÙ, ÍÙ ÓÞÉÔÁÅÍ, ÞÔÏ ÒÅÚÕÌØÔÁÔ ÎÅ ÏÐÒÅÄÅ̾Î, ÄÁÖÅ ÅÓÌÉ ÎÁ ÓÔÁÎÄÁÒÔÎÙÊ
×ÙÈÏÄ ÞÔÏ-ÔÏ ÐÏÓÌÁÎÏ.) ñÓÎÏ, ÞÔÏ ÆÕÎËÃÉÑ U ÂÕÄÅÔ ÇÌÁ×ÎÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÊ
ÆÕÎËÃÉÅÊ. ðÏÜÔÏÍÕ Ë ÎÅÊ ÍÏÖÎÏ ÐÒÉÍÅÎÉÔØ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÎÏÅ ÔÏÌØËÏ ÞÔÏ
ÕÔ×ÅÒÖÄÅÎÉÅ; ÐÏÌÕÞÉÍ ÐÒÏÇÒÁÍÍÕ p, ËÏÔÏÒÁÑ ÐÒÉ ÌÀÂÏÍ ×ÈÏÄÅ ÎÁ ×ÙÈÏÄÅ
ÄÁ¾Ô p.
  ñÓÎÏ, ÞÔÏ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ ÐÒÉÍÅÎÉÍÏ ÄÌÑ ÌÀÂÏÇÏ ÑÚÙËÁ ÐÒÏÇÒÁÍÍÉÒÏ-
×ÁÎÉÑ; ÔÏ, ÞÔÏ ÍÙ ÕÐÏÍÑÎÕÌÉ ÑÚÙË C, ÒÏÌÉ ÎÅ ÉÇÒÁÅÔ.
  úÁÄÁÞÁ 194. äÏËÁÖÉÔÅ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ C-ÐÒÏÇÒÁÍÍÁ, ËÏÔÏÒÁÑ ÐÅ-
ÞÁÔÁÅÔ Ó×ÏÊ ÔÅËÓÔ ÚÁÄÏÍ ÎÁÐÅÒ¾Ä.

Страницы