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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§8. ïÐÅÒÁÃÉÉ ÎÁÄ ÍÏÝÎÏÓÔÑÍÉ 39
ôÅÏÒÅÍÁ 10. åÓÌÉ ÍÎÏÖÅÓÔ×Ï A
1
×A
2
×···×A
n
ÒÁÚÂÉÔÏ ÎÁ ÎÅÐÅÒÅÓÅËÁ-
ÀÝÉÅÓÑ ÞÁÓÔÉ B
1
, . . . , B
n
, ÔÏ ÎÁÊľÔÓÑ ÔÁËÏÅ i, ÐÒÉ ËÏÔÏÒÏÍ ÍÏÝÎÏÓÔØ B
i
ÎÅ ÍÅÎØÛÅ ÍÏÝÎÏÓÔÉ A
i
.
äÏËÁÚÁÔÅÌØÓÔ×Ï. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÒÁÓÓÍÏÔÒÉÍ ÐÒÏÅËÃÉÀ ÍÎÏÖÅÓÔ×Á B
i
⊂
⊂ A
1
×. . .×A
n
ÎÁ A
i
. åÓÌÉ ÈÏÔÑ ÂÙ ÐÒÉ ÏÄÎÏÍ i ÏÎÁ ÐÏËÒÙ×ÁÅÔ A
i
ÐÏÌÎÏÓÔØÀ,
ÔÏ ×Ó¾ ÄÏËÁÚÁÎÏ. åÓÌÉ ÎÅÔ, ×ÙÂÅÒÅÍ ÄÌÑ ËÁÖÄÏÇÏ i ÎÅÐÏËÒÙÔÕÀ ÔÏÞËÕ x
i
.
îÁÂÏÒ hx
1
, . . . , x
n
i ÎÅ ×ÈÏÄÉÔ ÎÉ × ÏÄÎÏ ÉÚ ÍÎÏÖÅÓÔ× B
i
, ÞÔÏ ÐÒÏÔÉ×ÏÒÅÞÉÔ
ÐÒÅÄÐÏÌÏÖÅÎÉÀ.
úÁÍÅÔÉÍ, ÞÔÏ × ÆÏÒÍÕÌÉÒÏ×ËÅ ÜÔÏÇÏ ÕÔ×ÅÒÖÄÅÎÉÑ (ËÏÔÏÒÏÅ ÉÎÏÇÄÁ ÎÁ-
ÚÙ×ÁÀÔ ÔÅÏÒÅÍÏÊ ë¾ÎÉÇÁ) ÇÏ×ÏÒÉÔÓÑ Ï ÄÅËÁÒÔÏ×ÏÍ ÐÒÏÉÚ×ÅÄÅÎÉÉ ËÏÎÅÞÎÏÇÏ
ÞÉÓÌÁ ÍÎÏÖÅÓÔ×, ËÏÔÏÒÏÅ ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ ÉÎÄÕËÔÉ×ÎÏ (ÓËÁÖÅÍ, A×B×C
ÂÕÄÅÔ ÓÏÓÔÏÑÔØ ÉÚ ÔÒÏÅË ha, b, ci, ËÏÔÏÒÙÅ ÓÕÔØ ÐÁÒÙ hha, bi, ci). äÅËÁÒÔÏ×Ï
ÐÒÏÉÚ×ÅÄÅÎÉÅ ÓÞ¾ÔÎÏÇÏ ÞÉÓÌÁ ÍÎÏÖÅÓÔ× ÕÖÅ ÔÁË ÎÅ ÏÐÒÅÄÅÌÉÛØ. ÷ÙÈÏÄ ÔÁ-
ËÏÊ: A
0
× A
1
× A
2
× . . . (ÓÞ¾ÔÎÏÅ ÞÉÓÌÏ ÓÏÍÎÏÖÉÔÅÌÅÊ) ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ
ËÁË ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ a
0
, a
1
, a
2
, . . . , Õ ËÏÔÏÒÙÈ a
i
∈ A
i
,
ÔÏ ÅÓÔØ ËÁË ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÆÕÎËÃÉÊ a, ÏÐÒÅÄÅ̾ÎÎÙÈ ÎÁ N ÓÏ ÚÎÁÞÅÎÉÑÍÉ
× ÏÂßÅÄÉÎÅÎÉÉ ×ÓÅÈ A
i
, ÐÒÉÞ¾Í a(i) ∈ A
i
ÐÒÉ ×ÓÅÈ i. ðÏÓÌÅ ÔÁËÏÇÏ ÏÐÒÅÄÅ-
ÌÅÎÉÑ ÔÅÏÒÅÍÁ 10 ÌÅÇËÏ ÐÅÒÅÎÏÓÉÔÓÑ É ÎÁ ÓÞ¾ÔÎÙÅ (Á ÔÁËÖÅ É ÎÁ ÌÀÂÙÅ)
ÐÒÏÉÚ×ÅÄÅÎÉÑ.
ðÅÒÅÈÏÄÑ Ë ÏÔÒÉÃÁÎÉÑÍ, ÔÅÏÒÅÍÕ ë¾ÎÉÇÁ ÍÏÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÔÁË:
ÅÓÌÉ ÐÒÉ ×ÓÅÈ i = 0, 1, 2 . . . ÄÌÑ ÍÏÝÎÏÓÔÅÊ a
i
É b
i
×ÙÐÏÌÎÅÎÏ ÎÅÒÁ×ÅÎÓÔ×Ï b
i
<
< a
i
, ÔÏ
b
0
+ b
1
+ b
2
+ . . . < a
0
× a
1
× a
2
× . . .
õÞÉÔÙ×ÁÑ, ÞÔÏ c × c × . . . (ÓÞ¾ÔÎÏÅ ÐÒÏÉÚ×ÅÄÅÎÉÅ) ÒÁ×ÎÏ c
ℵ
0
, ÔÏ ÅÓÔØ c,
ÍÏÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÔÁËÏÅ ÓÌÅÄÓÔ×ÉÅ ÔÅÏÒÅÍÙ ë¾ÎÉÇÁ: ÅÓÌÉ ËÏÎÔÉÎÕÕÍ
ÒÁÚÂÉÔ ÎÁ ÓÞ¾ÔÎÏÅ ÞÉÓÌÏ ÐÏÄÍÎÏÖÅÓÔ×, ÔÏ ÏÄÎÏ ÉÚ ÎÉÈ ÉÍÅÅÔ ÍÏÝÎÏÓÔØ ËÏÎ-
ÔÉÎÕÕÍÁ.
úÁÄÁÞÁ 67. äÏËÁÖÉÔÅ ÐÏÄÒÏÂÎÏ ÜÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ.
úÁÄÁÞÁ 68. ðÕÓÔØ a
0
, a
1
, a
2
, . . . ¡ ÍÏÝÎÏÓÔÉ, ÐÒÉÞ¾Í a
i
> 2 ÄÌÑ ×ÓÅÈ i.
ðÏËÁÖÉÔÅ, ÞÔÏ
a
0
+ a
1
+ a
2
+ . . . 6 a
0
× a
1
× a
2
× . . .
úÁÄÁÞÁ 69. ðÕÓÔØ m
0
< m
1
< m
2
< . . . ¡ ×ÏÚÒÁÓÔÁÀÝÁÑ ÐÏÓÌÅÄÏ-
×ÁÔÅÌØÎÏÓÔØ ÍÏÝÎÏÓÔÅÊ. äÏËÁÖÉÔÅ, ÞÔÏ ÓÕÍÍÁ m
0
+ m
1
+ m
2
+ . . . ÎÅ
ÐÒÅÄÓÔÁ×ÉÍÁ × ×ÉÄÅ a
ℵ
0
ÎÉ ÄÌÑ ËÁËÏÊ ÍÏÝÎÏÓÔÉ a.
§8. ïÐÅÒÁÃÉÉ ÎÁÄ ÍÏÝÎÏÓÔÑÍÉ                                                  39

   ôÅÏÒÅÍÁ 10. åÓÌÉ ÍÎÏÖÅÓÔ×Ï A1 ×A2 ×· · ·×An ÒÁÚÂÉÔÏ ÎÁ ÎÅÐÅÒÅÓÅËÁ-
ÀÝÉÅÓÑ ÞÁÓÔÉ B1 , . . . , Bn, ÔÏ ÎÁÊľÔÓÑ ÔÁËÏÅ i, ÐÒÉ ËÏÔÏÒÏÍ ÍÏÝÎÏÓÔØ Bi
ÎÅ ÍÅÎØÛÅ ÍÏÝÎÏÓÔÉ Ai .
   äÏËÁÚÁÔÅÌØÓÔ×Ï. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÒÁÓÓÍÏÔÒÉÍ ÐÒÏÅËÃÉÀ ÍÎÏÖÅÓÔ×Á Bi ⊂
⊂ A1 ×. . .×An ÎÁ Ai. åÓÌÉ ÈÏÔÑ ÂÙ ÐÒÉ ÏÄÎÏÍ i ÏÎÁ ÐÏËÒÙ×ÁÅÔ Ai ÐÏÌÎÏÓÔØÀ,
ÔÏ ×Ó¾ ÄÏËÁÚÁÎÏ. åÓÌÉ ÎÅÔ, ×ÙÂÅÒÅÍ ÄÌÑ ËÁÖÄÏÇÏ i ÎÅÐÏËÒÙÔÕÀ ÔÏÞËÕ x i.
îÁÂÏÒ hx1, . . . , xni ÎÅ ×ÈÏÄÉÔ ÎÉ × ÏÄÎÏ ÉÚ ÍÎÏÖÅÓÔ× Bi , ÞÔÏ ÐÒÏÔÉ×ÏÒÅÞÉÔ
ÐÒÅÄÐÏÌÏÖÅÎÉÀ.
   úÁÍÅÔÉÍ, ÞÔÏ × ÆÏÒÍÕÌÉÒÏ×ËÅ ÜÔÏÇÏ ÕÔ×ÅÒÖÄÅÎÉÑ (ËÏÔÏÒÏÅ ÉÎÏÇÄÁ ÎÁ-
ÚÙ×ÁÀÔ ÔÅÏÒÅÍÏÊ ë¾ÎÉÇÁ) ÇÏ×ÏÒÉÔÓÑ Ï ÄÅËÁÒÔÏ×ÏÍ ÐÒÏÉÚ×ÅÄÅÎÉÉ ËÏÎÅÞÎÏÇÏ
ÞÉÓÌÁ ÍÎÏÖÅÓÔ×, ËÏÔÏÒÏÅ ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ ÉÎÄÕËÔÉ×ÎÏ (ÓËÁÖÅÍ, A×B ×C
ÂÕÄÅÔ ÓÏÓÔÏÑÔØ ÉÚ ÔÒÏÅË ha, b, ci, ËÏÔÏÒÙÅ ÓÕÔØ ÐÁÒÙ hha, bi, ci). äÅËÁÒÔÏ×Ï
ÐÒÏÉÚ×ÅÄÅÎÉÅ ÓÞ¾ÔÎÏÇÏ ÞÉÓÌÁ ÍÎÏÖÅÓÔ× ÕÖÅ ÔÁË ÎÅ ÏÐÒÅÄÅÌÉÛØ. ÷ÙÈÏÄ ÔÁ-
ËÏÊ: A0 × A1 × A2 × . . . (ÓÞ¾ÔÎÏÅ ÞÉÓÌÏ ÓÏÍÎÏÖÉÔÅÌÅÊ) ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ
ËÁË ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ a0 , a1 , a2 , . . . , Õ ËÏÔÏÒÙÈ ai ∈ Ai,
ÔÏ ÅÓÔØ ËÁË ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÆÕÎËÃÉÊ a, ÏÐÒÅÄÅ̾ÎÎÙÈ ÎÁ N ÓÏ ÚÎÁÞÅÎÉÑÍÉ
× ÏÂßÅÄÉÎÅÎÉÉ ×ÓÅÈ Ai, ÐÒÉÞ¾Í a(i) ∈ Ai ÐÒÉ ×ÓÅÈ i. ðÏÓÌÅ ÔÁËÏÇÏ ÏÐÒÅÄÅ-
ÌÅÎÉÑ ÔÅÏÒÅÍÁ 10 ÌÅÇËÏ ÐÅÒÅÎÏÓÉÔÓÑ É ÎÁ ÓÞ¾ÔÎÙÅ (Á ÔÁËÖÅ É ÎÁ ÌÀÂÙÅ)
ÐÒÏÉÚ×ÅÄÅÎÉÑ.
   ðÅÒÅÈÏÄÑ Ë ÏÔÒÉÃÁÎÉÑÍ, ÔÅÏÒÅÍÕ ë¾ÎÉÇÁ ÍÏÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÔÁË:
ÅÓÌÉ ÐÒÉ ×ÓÅÈ i = 0, 1, 2 . . . ÄÌÑ ÍÏÝÎÏÓÔÅÊ ai É bi ×ÙÐÏÌÎÅÎÏ ÎÅÒÁ×ÅÎÓÔ×Ï bi <
< ai , ÔÏ
                     b 0 + b 1 + b 2 + . . . < a 0 × a1 × a2 × . . .
   õÞÉÔÙ×ÁÑ, ÞÔÏ c × c × . . . (ÓÞ¾ÔÎÏÅ ÐÒÏÉÚ×ÅÄÅÎÉÅ) ÒÁ×ÎÏ cℵ0 , ÔÏ ÅÓÔØ c,
ÍÏÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÔÁËÏÅ ÓÌÅÄÓÔ×ÉÅ ÔÅÏÒÅÍÙ ë¾ÎÉÇÁ: ÅÓÌÉ ËÏÎÔÉÎÕÕÍ
ÒÁÚÂÉÔ ÎÁ ÓÞ¾ÔÎÏÅ ÞÉÓÌÏ ÐÏÄÍÎÏÖÅÓÔ×, ÔÏ ÏÄÎÏ ÉÚ ÎÉÈ ÉÍÅÅÔ ÍÏÝÎÏÓÔØ ËÏÎ-
ÔÉÎÕÕÍÁ.
  úÁÄÁÞÁ 67. äÏËÁÖÉÔÅ ÐÏÄÒÏÂÎÏ ÜÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ.
  úÁÄÁÞÁ 68. ðÕÓÔØ a0 , a1 , a2, . . . ¡ ÍÏÝÎÏÓÔÉ, ÐÒÉÞ¾Í ai > 2 ÄÌÑ ×ÓÅÈ i.
ðÏËÁÖÉÔÅ, ÞÔÏ
                    a0 + a 1 + a 2 + . . . 6 a 0 × a1 × a2 × . . .
  úÁÄÁÞÁ 69. ðÕÓÔØ m0 < m1 < m2 < . . . ¡ ×ÏÚÒÁÓÔÁÀÝÁÑ ÐÏÓÌÅÄÏ-
×ÁÔÅÌØÎÏÓÔØ ÍÏÝÎÏÓÔÅÊ. äÏËÁÖÉÔÅ, ÞÔÏ ÓÕÍÍÁ m0 + m1 + m2 + . . . ÎÅ
ÐÒÅÄÓÔÁ×ÉÍÁ × ×ÉÄÅ aℵ0 ÎÉ ÄÌÑ ËÁËÏÊ ÍÏÝÎÏÓÔÉ a.

Страницы