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

30                                     çÌÁ×Á I. íÎÏÖÅÓÔ×Á É ÍÏÝÎÏÓÔÉ

      ÒÁÓÓÕÖÄÅÎÉÊ. âÅÚÏÐÁÓÎÙÅ (ÐÏ ËÒÁÊÎÅÊ ÍÅÒÅ ÐÏËÁ ÎÅ ÐÒÉ×ÅÄÛÉÅ Ë ÐÒÏ-
      ÔÉ×ÏÒÅÞÉÀ) ÐÒÁ×ÉÌÁ ÏÂÒÁÝÅÎÉÑ ÓÏ ÍÎÏÖÅÓÔ×ÁÍÉ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÙ ×
      ÁËÓÉÏÍÁÔÉÞÅÓËÏÊ ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ× (ÆÏÒÍÁÌØÎÁÑ ÔÅÏÒÉÑ ZF, ÎÁÚ×ÁÎÎÁÑ
      × ÞÅÓÔØ ãÅÒÍÅÌÏ É æÒÅÎËÅÌÑ). äÏÂÁ×É× Ë ÜÔÏÊ ÔÅÏÒÉÉ ÁËÓÉÏÍÕ ×ÙÂÏÒÁ,
      ÐÏÌÕÞÁÅÍ ÔÅÏÒÉÀ, ÎÁÚÙ×ÁÅÍÕÀ ZFC (Óhoice ÐÏ-ÁÎÇÌÉÊÓËÉ ¡ ×ÙÂÏÒ).
      åÓÔØ É ÄÒÕÇÉÅ, ÍÅÎÅÅ ÐÏÐÕÌÑÒÎÙÅ ÔÅÏÒÉÉ.
   ïÄÎÁËÏ ÆÏÒÍÁÌØÎÏÅ ÐÏÓÔÒÏÅÎÉÅ ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ× ×ÙÈÏÄÉÔ ÚÁ ÒÁÍËÉ ÎÁ-
ÛÅÇÏ ËÕÒÓÁ. ðÏÜÔÏÍÕ ÍÙ ÏÇÒÁÎÉÞÉÍÓÑ ÎÅÆÏÒÍÁÌØÎÙÍ ÏÐÉÓÁÎÉÅÍ ÏÇÒÁÎÉÞÅ-
ÎÉÊ, ÎÁËÌÁÄÙ×ÁÅÍÙÈ ×Ï ÉÚÂÅÖÁÎÉÅ ÐÒÏÔÉ×ÏÒÅÞÉÊ: ÎÅÌØÚÑ ÐÒÏÓÔÏ ÔÁË ÒÁÓ-
ÓÍÏÔÒÅÔØ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÍÎÏÖÅÓÔ× ÉÌÉ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÍÎÏÖÅÓÔ×, ÎÅ Ñ×ÌÑ-
ÀÝÉÈÓÑ Ó×ÏÉÍÉ ÜÌÅÍÅÎÔÁÍÉ, ÐÏÓËÏÌØËÕ ËÌÁÓÓ ÐÏÔÅÎÃÉÁÌØÎÙÈ ÐÒÅÔÅÎÄÅÎÔÏ×
ÓÌÉÛËÏÍ ÎÅÏÂÏÚÒÉÍ. íÎÏÖÅÓÔ×Á ÍÏÖÎÏ ÓÔÒÏÉÔØ ÌÉÛØ ÐÏÓÔÅÐÅÎÎÏ. îÁÐÒÉ-
ÍÅÒ, ÍÏÖÎÏ ÏÂÒÁÚÏ×ÁÔØ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÐÏÄÍÎÏÖÅÓÔ× ÄÁÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á
(ÁËÓÉÏÍÁ ÓÔÅÐÅÎÉ). íÏÖÎÏ ÒÁÓÓÍÏÔÒÅÔØ ÐÏÄÍÎÏÖÅÓÔ×Ï ÄÁÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á,
ÏÂÒÁÚÏ×ÁÎÎÏÅ ÜÌÅÍÅÎÔÁÍÉ Ó ËÁËÉÍ-ÔÏ Ó×ÏÊÓÔ×ÏÍ (ÁËÓÉÏÍÁ ×ÙÄÅÌÅÎÉÑ). íÏÖ-
ÎÏ ÒÁÓÓÍÏÔÒÅÔØ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÜÌÅÍÅÎÔÏ×, ×ÈÏÄÑÝÉÈ ÈÏÔÑ ÂÙ × ÏÄÉÎ ÉÚ
ÜÌÅÍÅÎÔÏ× ÄÁÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á (ÁËÓÉÏÍÁ ÓÕÍÍÙ). åÓÔØ É ÄÒÕÇÉÅ ÁËÓÉÏÍÙ.
   éÚÌÁÇÁÑ Ó×ÅÄÅÎÉÑ ÉÚ ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ×, ÍÙ ÂÕÄÅÍ ÓÔÁÒÁÔØÓÑ ÄÅÒÖÁÔØÓÑ
ÐÏÄÁÌØÛÅ ÏÔ ÏÐÁÓÎÏÊ ÞÅÒÔÙ, É ÕËÁÚÙ×ÁÔØ ÎÁ ÏÐÁÓÎÏÓÔØ × ÔÅÈ ÍÅÓÔÁÈ, ËÏÇÄÁ
×ÏÚÎÉËÎÅÔ ÉÓËÕÛÅÎÉÅ Ë ÜÔÏÊ ÞÅÒÔÅ ÐÒÉÂÌÉÚÉÔØÓÑ. ðÏËÁ ÞÔÏ ÔÁËÏÅ ÍÅÓÔÏ ÂÙÌÏ
ÏÄÎÏ: ÐÏÐÙÔËÁ ÏÐÒÅÄÅÌÉÔØ ÍÏÝÎÏÓÔØ ÍÎÏÖÅÓÔ×Á ËÁË ËÌÁÓÓ (ÍÎÏÖÅÓÔ×Ï) ×ÓÅÈ
ÒÁ×ÎÏÍÏÝÎÙÈ ÅÍÕ ÍÎÏÖÅÓÔ×.


     §7. æÕÎËÃÉÉ
   äÏ ÓÉÈ ÐÏÒ ÍÙ ÓÔÁÒÁÌÉÓØ ÏÇÒÁÎÉÞÉ×ÁÔØÓÑ ÍÉÎÉÍÕÍÏÍ ÆÏÒÍÁÌØÎÏÓÔÅÊ
É ÇÏ×ÏÒÉÌÉ Ï ÆÕÎËÃÉÑÈ, ÉÈ ÁÒÇÕÍÅÎÔÁÈ, ÚÎÁÞÅÎÉÑÈ, ËÏÍÐÏÚÉÃÉÉ É Ô. Ð. ÂÅÚ
ÐÏÐÙÔÏË ÄÁÔØ ÏÐÒÅÄÅÌÅÎÉÑ ÜÔÉÈ ÐÏÎÑÔÉÊ. óÅÊÞÁÓ ÍÙ ÄÁÄÉÍ ÆÏÒÍÁÌØÎÙÅ
ÏÐÒÅÄÅÌÅÎÉÑ.
   ðÕÓÔØ A É B ¡ Ä×Á ÍÎÏÖÅÓÔ×Á. òÁÓÓÍÏÔÒÉÍ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÕÐÏÒÑÄÏÞÅÎ-
ÎÙÈ ÐÁÒ ha, bi, ÇÄÅ a ∈ A É b ∈ B. üÔÏ ÍÎÏÖÅÓÔ×Ï ÎÁÚÙ×ÁÅÔÓÑ ÄÅËÁÒÔÏ×ÙÍ
ÐÒÏÉÚ×ÅÄÅÎÉÅÍ ÍÎÏÖÅÓÔ× A É B É ÏÂÏÚÎÁÞÁÅÔÓÑ A × B. (ë ×ÏÐÒÏÓÕ Ï ÔÏÍ,
ÞÔÏ ÔÁËÏÅ ÕÐÏÒÑÄÏÞÅÎÎÁÑ ÐÁÒÁ, ÍÙ Åݾ ×ÅÒξÍÓÑ ÎÁ Ó. 34.)
   ìÀÂÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï R ÍÎÏÖÅÓÔ×Á A×B ÎÁÚÙ×ÁÅÔÓÑ ÏÔÎÏÛÅÎÉÅÍ ÍÅÖÄÕ
ÍÎÏÖÅÓÔ×ÁÍÉ A É B. åÓÌÉ A = B, ÇÏ×ÏÒÑÔ Ï ÂÉÎÁÒÎÏÍ ÏÔÎÏÛÅÎÉÉ ÎÁ ÍÎÏ-
ÖÅÓÔ×Å A. îÁÐÒÉÍÅÒ, ÎÁ ÍÎÏÖÅÓÔ×Å ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ ÍÏÖÎÏ ÒÁÓÓÍÏÔÒÅÔØ
ÂÉÎÁÒÎÏÅ ÏÔÎÏÛÅÎÉÅ ÂÙÔØ ÄÅÌÉÔÅÌÅÍ, ÏÂÙÞÎÏ ÏÂÏÚÎÁÞÁÅÍÏÅ ÓÉÍ×ÏÌÏÍ |. ôÏ-
ÇÄÁ ÍÏÖÎÏ × ÐÒÉÎÃÉÐÅ ÂÙÌÏ ÂÙ ÎÁÐÉÓÁÔØ h2, 6i ∈ | É h2, 7i ∈/ |. ïÂÙÞÎÏ,
ÏÄÎÁËÏ, ÚÎÁË ÏÔÎÏÛÅÎÉÑ ÐÉÛÕÔ ÍÅÖÄÕ ÏÂßÅËÔÁÍÉ (ÎÁÐÒÉÍÅÒ, 2|6).