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

                                               x 4. oTNOENIQ \KWIWALENTNOSTI I RAZBIENIQ NA KLASSY

  4.3. kLASSY \KWIWALENTNOSTI.
oPREDELENIE 1. pUSTX A NEKOTOROE MNOVESTWO A %               | OTNOENIE \KWIWALENTNOSTI NA
MNOVESTWE A. dLQ KAVDOGO \LEMENTA a 2 A OPREDELIM PODMNOVESTWO a MNOVESTWA A SLEDU-
                          |                            ,


@]IM OBRAZOM:
                                  a = fx j x 2 A I (a
 x) 2 %g:
   pODMNOVESTWO a NAZOWEM KLASSOM \KWIWALENTNOSTI MNOVESTWA A PO %, OPREDELQEMOE \LE-
MENTOM a. |LEMENT a NAZOWEM PREDSTAWITELEM \TOGO KLASSA.
   iNOGDA a BUDEM OBOZNA^ATX a% , ^TOBY QWNO UKAZYWATX, ^TO a QWLQETSQ KLASSOM PO %.
pRIMER 1. pUSTX A = f1
 2
 3g, % = f(1
 1)
 (2
 2)
 (3
 3)
 (1
3)
 (3
 1)g. tOGDA 1 = 3 = f1
 3g,
2 = f2g.
tEOREMA 1. pUSTX A | NEKOTOROE MNOVESTWO, % | \KWIWALENTNOSTX NA A, A PREDMETY a,
b | \LEMENTY MNOVESTWA A.
  1.   dLQ L@BOGO a 2 A, a 2 a. tAKIM OBRAZOM PREDSTAWITELX KLASSA a EMU PRINADLEVIT.
  2.   eSLI b 2 a, TO b = a. |TO OZNA^AET, W ^ASTNOSTI, ^TO KAVDYJ \LEMENT KLASSA a QWLQ-
       ETSQ EGO PREDSTAWITELEM.
  3.   a = b () (a
 b) 2 %.
  4.   dWA PROIZWOLXNYH KLASSA a I b LIBO NE PERESEKA@TSQ LIBO SOWPADA@T.
dOKAZATELXSTWO. 1. tAK KAK % REFLEKSIWNO, TO DLQ PROIZWOLXNOGO \LEMENTA a 2 A, (a
 a) 2 % I,
PO\TOMU, IZ OPREDELENIQ KLASSA a SLEDUET, ^TO a 2 a.
   2. pUSTX b 2 a. eSLI x 2 b, TO, PO OPREDELENI@ b, (b
 x) 2 %. s DRUGOJ STORONY, TAK KAK b 2 a,
TO (a
 b) 2 %. iZ TRANZITIWNOSTI % SLEDUET, ^TO (a
 x) 2 % I, SLEDOWATELXNO, x 2 a. tAKIM OBRAZOM,
b  a.
    eSLI y 2 a, TO (a
 y) 2 %. tAK KAK (a
 b) 2 %, TO IZ SIMMETRI^NOSTI % SLEDUET, ^TO (b
 a) 2 %.
tOGDA (b
 y) 2 %, TO ESTX y 2 b. tAKIM OBRAZOM, a  b. iTAK, a = b.
    3. iZ P. 1 TEOREMY SLEDUET, ^TO b 2 b. iZ a = b I b 2 b, SLEDUET, ^TO (a
 b) 2 %, PO OPREDELENI@
KLASSA a.
    pUSTX (a
 b) 2 %. tOGDA, ESLI x 2 a, TO (a
 x) 2 %. iZ SIMMETRI^NOSTI % SLEDUET, ^TO (b
 a) 2 %.
zNA^IT (b
 x) 2 % I, SLEDOWATELXNO, x 2 b, TO ESTX a  b. aNALOGI^NO DOKAZYWAETSQ, ^TO b  a.
    4. pUSTX a \ b 6= ? I x 2 a \ b. tOGDA x 2 a I x 2 b, SLEDOWATELXNO, PO OPREDELENI@ KLASSOW a
I b, (a
 x) 2 % I (b
 x) 2 %. tOGDA (a
 b) 2 % I PO P. 3 \TOJ TEOREMY a = b.
    zAMETIM, ^TO IZ P. 1 TOLXKO ^TO DOKAZANNOJ TEOREMY SLEDUET, ^TO KAVDYJ KLASS \KWIWALENT-
NOSTI NEPUST.

  4.4. fAKTORMNOVESTWO.
oPREDELENIE 1. pUSTX A NEKOTOROE MNOVESTWO A %
                         |                    ,    | \KWIWALENTNOSTX NA A. mNOVES-
TWO WSEWOZMOVNYH KLASSOW \KWIWALENTNOSTI MNOVESTWA A PO OTNOENI@ % NAZYWAETSQ FAK-
TORMNOVESTWOM MNOVESTWA A PO OTNOENI@ % I OBOZNA^AETSQ A % (NE PUTATX S A n %).
                                                           


tEOREMA 1. pUSTX A MNOVESTWO A % %1 I %2 \KWIWALENTNOSTI NA A tOGDA
                         |             ,   ,           |                         .      :


  1.     A% QWLQETSQ RAZBIENIEM MNOVESTWA A
  2.   eSLI \KWIWALENTNOSTI
                          %1 I %2 NA MNOVESTWE A RAZLI^NY, TO RAZLI^NY I FAKTORMNO-
       VESTWA A %1 I A %2 .

                                                  29