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

§4. ÷ÐÏÌÎÅ ÕÐÏÒÑÄÏÞÅÎÎÙÅ ÍÎÏÖÅÓÔ×Á                                                                     55

ÜÔÏÔ ÏÂÏÒ×¾ÔÓÑ. åÓÌÉ ÂÅÓËÏÎÅÞÎÏ, ÐÏÓÍÏÔÒÉÍ, ÉÓÞÅÒÐÁÌÉ ÌÉ ÍÙ ×ÓÅ ÜÌÅÍÅÎ-
ÔÙ ÍÎÏÖÅÓÔ×Á A. åÓÌÉ ÎÅÔ, ×ÏÚØÍ¾Í ÍÉÎÉÍÁÌØÎÙÊ ÜÌÅÍÅÎÔ ÉÚ ÏÓÔÁ×ÛÉÈÓÑ.
ïÂÏÚÎÁÞÉÍ ÅÇÏ ω. óÌÅÄÕÀÝÉÊ ÚÁ ÎÉÍ ÜÌÅÍÅÎÔ (ÅÓÌÉ ÏÎ ÅÓÔØ) ÏÂÏÚÎÁÞÉÍ ω +
+1, ÚÁÔÅÍ ω +2 É Ô. Ä. åÓÌÉ É ÎÁ ÜÔÏÍ ÍÎÏÖÅÓÔ×Ï ÎÅ ÉÓÞÅÒÐÁÅÔÓÑ, ÔÏ ×ÏÚØ;Í
ÎÁÉÍÅÎØÛÉÊ ÜÌÅÍÅÎÔ ÉÚ ÏÓÔÁ×ÛÉÈÓÑ, ÎÁÚÏ×¾Í ÅÇÏ ω · 2, É ÐÏ×ÔÏÒÉÍ ×ÓÀ ÐÒÏ-
ÃÅÄÕÒÕ. úÁÔÅÍ ÂÕÄÕÔ ω ·3, ω ·4 É Ô. Ä. åÓÌÉ É ÎÁ ÜÔÏÍ ÍÎÏÖÅÓÔ×Ï ÎÅ ËÏÎÞÉÔÓÑ,
ÍÉÎÉÍÁÌØÎÙÊ ÉÚ ÏÓÔÁ×ÛÉÈÓÑ ÜÌÅÍÅÎÔÏ× ÎÁÚÏ×¾Í ω 2 . úÁÔÅÍ ÐÏÊÄÕÔ ω 2 + 1,
ω 2 + 2, . . . , ω 2 + ω, . . . , ω 2 + ω · 2, . . . , ω 2 · 2, . . . , ω 2 · 3, . . . , ω 3 , . . . (ÍÙ ÎÅ
ÐÏÑÓÎÑÅÍ ÓÅÊÞÁÓ ÐÏÄÒÏÂÎÏ ÏÂÏÚÎÁÞÅÎÉÑ).
    þÔÏ, ÓÏÂÓÔ×ÅÎÎÏ ÇÏ×ÏÒÑ, ÄÏËÁÚÙ×ÁÅÔ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ? ðÏÐÙÔÁÅÍÓÑ ×Ù-
ÄÅÌÉÔØ ÎÅËÏÔÏÒÙÅ ÕÔ×ÅÒÖÄÅÎÉÑ. ðÒÉ ÜÔÏÍ ÐÏÌÅÚÎÏ ÔÁËÏÅ ÏÐÒÅÄÅÌÅÎÉÅ: ÅÓÌÉ
ÌÉÎÅÊÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÍÎÏÖÅÓÔ×Ï A ÒÁÚÂÉÔÏ ÎÁ Ä×Å (ÎÅÐÅÒÅÓÅËÁÀÝÉÅÓÑ)
ÞÁÓÔÉ B É C, ÐÒÉÞ¾Í ÌÀÂÏÊ ÜÌÅÍÅÎÔ B ÍÅÎØÛÅ ÌÀÂÏÇÏ ÜÌÅÍÅÎÔÁ C, ÔÏ
B ÎÁÚÙ×ÁÀÔ ÎÁÞÁÌØÎÙÍ ÏÔÒÅÚËÏÍ ÍÎÏÖÅÓÔ×Á A. äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÐÏÄ-
ÍÎÏÖÅÓÔ×Ï B ÌÉÎÅÊÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á A Ñ×ÌÑÅÔÓÑ ÎÁÞÁÌØÎÙÍ
ÏÔÒÅÚËÏÍ, ÅÓÌÉ ÌÀÂÏÊ ÜÌÅÍÅÎÔ B ÍÅÎØÛÅ ÌÀÂÏÇÏ ÜÌÅÍÅÎÔÁ A \ B. åݾ ÏÄÎÁ
ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÁ: B ⊂ A Ñ×ÌÑÅÔÓÑ ÎÁÞÁÌØÎÙÍ ÏÔÒÅÚËÏÍ, ÅÓÌÉ ÉÚ a, b ∈ A,
b ∈ B É a 6 b ÓÌÅÄÕÅÔ a ∈ B. úÁÍÅÔÉÍ, ÞÔÏ ÎÁÞÁÌØÎÙÊ ÏÔÒÅÚÏË ÍÏÖÅÔ ÂÙÔØ
ÐÕÓÔÙÍ ÉÌÉ ÓÏ×ÐÁÄÁÔØ ÓÏ ×ÓÅÍ ÍÎÏÖÅÓÔ×ÏÍ.
    ïÔÍÅÔÉÍ ÓÒÁÚÕ ÖÅ ÎÅÓËÏÌØËÏ ÐÒÏÓÔÙÈ Ó×ÏÊÓÔ× ÎÁÞÁÌØÎÙÈ ÏÔÒÅÚËÏ×:

     • îÁÞÁÌØÎÙÊ ÏÔÒÅÚÏË ×ÐÏÌÎÅ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á (ËÁË, ×ÐÒÏÞÅÍ,
       É ÌÀÂÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï) Ñ×ÌÑÅÔÓÑ ×ÐÏÌÎÅ ÕÐÏÒÑÄÏÞÅÎÎÙÍ ÍÎÏÖÅÓÔ×ÏÍ.
     • îÁÞÁÌØÎÙÊ ÏÔÒÅÚÏË ÎÁÞÁÌØÎÏÇÏ ÏÔÒÅÚËÁ ÅÓÔØ ÎÁÞÁÌØÎÙÊ ÏÔÒÅÚÏË ÉÓ-
       ÈÏÄÎÏÇÏ ÍÎÏÖÅÓÔ×Á.
     • ïÂßÅÄÉÎÅÎÉÅ ÌÀÂÏÇÏ ÓÅÍÅÊÓÔ×Á ÎÁÞÁÌØÎÙÈ ÏÔÒÅÚËÏ× (× ÏÄÎÏÍ É ÔÏÍ
       ÖÅ ÕÐÏÒÑÄÏÞÅÎÎÏÍ ÍÎÏÖÅÓÔ×Å) ÅÓÔØ ÎÁÞÁÌØÎÙÊ ÏÔÒÅÚÏË ÔÏÇÏ ÖÅ ÍÎÏ-
       ÖÅÓÔ×Á.
     • åÓÌÉ x ¡ ÐÒÏÉÚ×ÏÌØÎÙÊ ÜÌÅÍÅÎÔ ×ÐÏÌÎÅ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á A,
       ÔÏ ÍÎÏÖÅÓÔ×Á [0, x) (×ÓÅ ÜÌÅÍÅÎÔÙ ÍÎÏÖÅÓÔ×Á A, ÍÅÎØÛÉÅ x) É [0, x]
       (ÜÌÅÍÅÎÔÙ ÍÎÏÖÅÓÔ×Á A, ÍÅÎØÛÉÅ ÉÌÉ ÒÁ×ÎÙÅ x) Ñ×ÌÑÀÔÓÑ ÎÁÞÁÌØÎÙ-
       ÍÉ ÏÔÒÅÚËÁÍÉ.
     • ÷ÓÑËÉÊ ÎÁÞÁÌØÎÙÊ ÏÔÒÅÚÏË I ×ÐÏÌÎÅ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á A, ÎÅ
       ÓÏ×ÐÁÄÁÀÝÉÊ ÓÏ ×ÓÅÍ ÍÎÏÖÅÓÔ×ÏÍ, ÉÍÅÅÔ ×ÉÄ [0, x) ÄÌÑ ÎÅËÏÔÏÒÏÇÏ x ∈
       ∈ A. (÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÓÌÉ I 6= A, ×ÏÚØÍ¾Í ÎÁÉÍÅÎØÛÉÊ ÜÌÅÍÅÎÔ x ×
       ÍÎÏÖÅÓÔ×Å A \ I. ôÏÇÄÁ ×ÓÅ ÍÅÎØÛÉÅ ÜÌÅÍÅÎÔÙ ÐÒÉÎÁÄÌÅÖÁÔ I, ÓÁÍ x
       ÎÅ ÐÒÉÎÁÄÌÅÖÉÔ I É ×ÓŠ‚ÏÌØÛÉÅ x ÜÌÅÍÅÎÔÙ ÎÅ ÐÒÉÎÁÄÌÅÖÁÔ I, ÉÎÁÞÅ
       ÐÏÌÕÞÉÌÏÓØ ÂÙ ÐÒÏÔÉ×ÏÒÅÞÉÅ Ó ÏÐÒÅÄÅÌÅÎÉÅÍ ÎÁÞÁÌØÎÏÇÏ ÏÔÒÅÚËÁ.)
     • ìÀÂÙÅ Ä×Á ÎÁÞÁÌØÎÙÈ ÏÔÒÅÚËÁ ×ÐÏÌÎÅ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á
       ÓÒÁ×ÎÉÍÙ ÐÏ ×ËÌÀÞÅÎÉÀ, Ô. Å. ÏÄÉÎ ÅÓÔØ ÐÏÄÍÎÏÖÅÓÔ×Ï ÄÒÕÇÏÇÏ. (óÌÅ-