Дискретная математика. Кулабухов С.Ю. - 35 стр.

                                                                                 x 5. oTNOENIE PORQDKA

   2. pUSTX hA
 i | KONE^NAQ CEPX I B  A, B 6= ?.
   eSLI jB j = 1, TO b 2 B QWLQETSQ NAIMENXIM DLQ PODMNOVESTWA B.
   eSLI jB j > 1, TO PUSTX a
 b 2 B, a 6= b. tAK KAK A LINEJNO UPORQDO^ENO, TO a < b ILI b < a,
ZNA^IT fa
 bg  B IMEET NAIMENXIJ \LEMENT. dALEE, WYBIRAEM PROIZWOLXNYJ c 2 B n fa
 bg I
SRAWNIWAEM EGO S NAIMENXIM \LEMENTOM MNOVESTWA fa
 bg (\TO WOZMOVNO, TAK KAK A | CEPX).
tAKIM OBRAZOM, POLU^AEM NAIMENXIJ \LEMENT MNOVESTWA fa
 b
 cg. |TOT PROCESS ZAKON^ITSQ NA-
HOVDENIEM NAIMENXEGO \LEMENTA PODMNOVESTWA B, TAK KAK A I, SLEDOWATELXNO, B QWLQ@TSQ
KONE^NYMI MNOVESTWAMI. w SILU PROIZWOLXNOSTI WYBORA B ZAKL@^AEM, ^TO A WPOLNE UPORQDO-
^ENO.
   zAMETIM, ^TO TREBOWANIE KONE^NOSTI LINEJNO UPORQDO^ENNOGO MNOVESTWA WO WTOROM PUNKTE
TOLXKO ^TO DOKAZANNOJ TEOREMY QWLQETSQ SU]ESTWENNYM.
pRIMER 2. pUSTX A = fa1
 a2
 a3
 : : :g fbg. wWEDEM NA A BINARNOE OTNOENIE  SLEDU@]IM
OBRAZOM: ai  aj , ESLI ^ISLO j NE PREWOSHODIT i b < ai DLQ L@BOGO i. o^EWIDNO, ^TO A LINEJNO
UPORQDO^ENO. oDNAKO, A NE QWLQETSQ WPOLNE UPORQDO^ENNYM, TAK KAK PODMNOVESTWO fa1
 a2
 a3
 : : :g
NE IMEET NAIMENXEGO \LEMENTA.
  5.4. rEETKI.
oPREDELENIE 1. pUSTX hA
 i       UPORQDO^ENNOE MNOVESTWO. B  A, a 2 A.
                                    |


  1.   a NAZYWAETSQ NIVNEJ GRANICEJ (WERHNEJ GRANICEJ) MNOVESTWA B , ESLI a MENXE (BOLXE)
       L@BOGO \LEMENTA IZ B , OTLI^NOGO OT a.
  2.   a NAZYWAETSQ TO^NOJ NIVNEJ GRANICEJ (TO^NOJ WERHNEJ GRANICEJ) MNOVESTWA B , ESLI a
       ESTX NIVNQQ GRANICA (WERHNQQ GRANICA) I a BOLXE (MENXE) L@BOJ DRUGOJ NIVNEJ (WERH-
       NEJ) GRANICY MNOVESTWA B .
  3.   A NAZYWAETSQ REETKOJ, ESLI L@BAQ PARA \LEMENTOW IZ A IMEET TO^NU@ WERHN@@ GRA-
       NICU I TO^NU@ NIVN@@ GRANICU.
pRIMER 1.
  1. pUSTX A = f1
 2
 3
 4
 5g.
      (a) hA
 EA i NE QWLQETSQ REETKOJ.
      (b) pUSTX % = EA f(1
 3)
 (2
 3)
 (1
 4)
 (2
 4)
 (3
5)
 (4
 5)
 (1
5)
 (2
5)g, TOGDA hA
 %i NE QWLQ-
            ETSQ REETKOJ.
  2. A = f1
 2
 3g. h2A 
 i | REETKA.
  3. hN
 ... i | REETKA.
tEOREMA 1. wSQKOE LINEJNO UPORQDO^ENNOE MNOVESTWO QWLQETSQ REETKOJ.
   dOKAZATELXSTWO PROWEDITE SAMOSTOQTELXNO.
sLEDSTWIE 1. wSQKOE WPOLNE UPORQDO^ENNOE MNOVESTWO QWLQETSQ REETKOJ.
   sLEDUET IZ TEOREMY 5.3.1 I PREDYDU]EJ TEOREMY.
tEOREMA 2. wSQKAQ KONE^NAQ REETKA IMEET NAIMENXIJ I NAIBOLXIJ \LEMENT.
   dOKAZATELXSTWO PROWEDITE SAMOSTOQTELXNO.
   5.5. nOWYE TERMINY. aNTISIMMETRI^NOSTX. ~ASTI^NO UPORQDO^ENNOE MNOVESTWO. mI-
NIMALXNYE (MAKSIMALXNYE) I NAIMENXIE (NAIBOLXIE) \LEMENTY. pOKRYTIE. gRAFY UPORQDO-
^ENNYH MNOVESTW. lINEJNO UPORQDO^ENNYE I WPOLNE UPORQDO^ENNYE MNOVESTWA. nIVNQQ (WERH-
NQQ) GRANICA. tO^NAQ NIVNQQ (WERHNQQ) GRANICA. rEETKA.
                                                    35