ZACHODNIOPOMORSKI UNIWERSYTET TECHNOLOGICZNY
W SZCZECINIE

2012

MATEMATYKA DYSKRETNA

Wykład 5: Moc zbioru

Prowadzący Wykłady: dr inż. Larisa Dobryakova

2

Zbiory równoliczne

Dwa zbiory

X

i

Y są równoliczne, gdy istnieje wzajemnie jednoznaczne

odwzorowanie (bijekcja)

1 1

:

na

f X

Y





,

przekształcające zbiór

X

na

Y .

Równoliczność zbiorów zapisujemy

~

X Y

.

3

Zbiory skończone i nieskończone (1)

Przez

n

oznaczamy moc zbioru





0,1,2,3,...,

1

n

n







, gdzie

n

 

.

Każdy zbiór

X

równoliczny

n



dla pewnego

n

, nazywamy skończonym,

n

zaś

nazywamy w tym przypadku liczbą elementów zbioru

X

.

Zbiór, który nie jest ani skończony ani pusty, nazywamy zbiorem nieskończonym.

UWAGA. Dwa zbiory skończone są równoliczne wtedy i tylko wtedy, gdy mają tyle
samo elementów.

Dla zbioru pustego



zachodzi

 0

n

.

4

Zbiory skończone i nieskończone (2)

Przykład

Podać funkcję ustalającą równoliczność zbioru



i zbioru





\ 0,1,2,...,99



.

5

Zbiory skończone i nieskończone (3)

Dla dowolnych zbiorów

, ,

X Y Z

zachodzi:



~

X

X

.



~

~

X Y

Y X



.





 

 



~

~

~

X Y

Y Z

X Z





.

Przykład

Czy zbiory





:0

10

X

x N

x









i











  





2

:

20

jestliczbą parzystą

Y

x x

x

x

są równoliczne?

6

Zbiór przeliczalny

Każdy zbiór

X

, który jest równoliczny ze zbiorem liczb naturalnych





0,1,2,3,...





,

czyli

~

X

, nazywamy zbiorem przeliczalnym.

Zbiory skończone lub przeliczalne nazywa się co najwyżej przeliczalnymi.

UWAGA. Zbiór jest co najwyżej przeliczalny, jeżeli wszystkie jego elementy można
ustawić w ciąg, w którym każdy element występuje tylko raz.

Oznacza to, że elementy zbioru co najwyżej przeliczalnego można ustawić w ciąg
skończony lub nieskończony, w którym żaden element nie powtarza się, czyli
ponumerować.

Przykład

Dowieść, że zbiór liczb całkowitych jest przeliczalny.

Do zbiorów przeliczalnych należą także zbiory liczb parzystych, liczb nieparzystych,
zbiór liczb wymiernych.

7

Zbiór nieprzeliczalny. Liczby kardynalne

Zbiór nieskończony

X

, który nie jest równoliczny ze zbiorem liczb naturalnych

nazywamy nieprzeliczalnym.

Zbiorem nieprzeliczalnym jest zbiór liczb rzeczywistych



.

Moce zbiorów nazywamy też liczbami kardynalnymi.

Liczby kardynalne zbiorów skończonych nazywamy skończonymi, zbiorów
nieskończonych – nieskończonymi.

Moc zbioru liczb naturalnych przyjęto oznaczać pierwszą literą alfabetu hebrajskiego

0



(alef zero), a moc zbioru liczb rzeczywistych literą gotycką C (continuum).

8

Porównywanie mocy zbiorów (1)

Mówimy, że moc zbioru

X

jest nie większa od mocy zbioru

Y , co zapisujemy:

X

Y



,

jeśli

X

jest równoliczny z pewnym podzbiorem

Y .

Wynika stąd, że jeśli zbiór

X

jest podzbiorem zbioru

Y , to moc zbioru

X

jest nie

większa, niż moc zbioru

Y

:

X Y

X

Y

 



.

Jeśli

X

Y



i

X

Y



, to mówimy, że zbiór

X

ma moc mniejszą, niż zbiór

Y .

Przykład

0

0





 



C

C

, więc

0



 C

, bo







.

9

Porównywanie mocy zbiorów (2)

Dla dowolnych dwóch zbiorów

X

i

Y zachodzi dokładnie jeden z warunków:

,

,

X

Y X

Y X

Y







.

Cantor udowodnił, że

0



jest najmniejszą nieskończoną liczbą kardynalną. Ponadto

pokazał, że dla każdej liczby kardynalnej istnieje liczba bezpośrednio od niej
większa.

Twierdzenie Cantora. Dla dowolnego zbioru

X

, zbiór potęgowy tego zbioru

2

X

(czyli zbiór jego wszystkich podzbiorów) ma moc większą od mocy zbioru
wyjściowego:

2

X

X



.

Wynika stąd, że dla każdej liczby kardynalnej istnieje liczba większa od niej, zatem
nie istnieje największa liczba kardynalna.

10

Porównywanie mocy zbiorów (3)

Twierdzenie Cantora-Bernsteina. Jeśli moc zbioru

X

jest nie większa od mocy

zbioru

Y i moc zbioru Y jest nie większa od mocy zbioru

X

, to moce tych zbiorów są

równe:





X

Y

Y

X

X

Y











.

Wniosek. Istnieje nieskończenie wiele liczb kardynalnych większych od

0



:

2

0

2

2

...

















11

Działania na liczbach kardynalnych (1)

Opierając się na pojęciu równoliczności zbiorów można zdefiniować działania na
liczbach kardynalnych: dodawanie, mnożenie, potęgowanie. Pozwala to zbudować
arytmetykę liczb kardynalnych.

Niech

X

i

Y będą zbiorami rozłącznymi, oraz

X

a



i

Y

b



.

Sumą

a b

 liczb kardynalnych

,

a b

nazywamy liczbę kardynalną będącą mocą

zbioru

X Y



:

a b

X Y

 



.

Własności dodawania liczb kardynalnych:



a b b a

   – przemienność;





 



a

b c

a b

c











– łączność;





 



a b

a c

b c

 







– monotoniczność;











0

0

max ,

a

b

a b

a b







 







.

12

Działania na liczbach kardynalnych (2)

Określenie iloczynu i potęgi liczb kardynalnych nie wymaga założenia, by zbiory

X

i

Y były rozłączne.

Iloczyn

a b

 liczb kardynalnych

,

a b

określamy jako moc iloczynu kartezjańskiego

X Y



zbiorów

X

i

Y

:

a b

X Y

 



.

Własności mnożenia liczb kardynalnych:



a b b a

   – przemienność;





 



a b c

a b c











– łączność;











   

a b c

a b a c

– rozdzielność mnożenia względem dodawania;



razy

...

n

n

n a a a a

a

       







 ;







0

0

max ,

a

b

a b

a b







 

  

.

13

Działania na liczbach kardynalnych (3)

Przez liczbę

b

a

rozumiemy moc zbioru wszystkich funkcji ze zbioru

Y w zbiór

X

:

b

Y

a

X



.

Własności potęgowania liczb kardynalnych:



b c

b

c

a

a a







.







c

c

c

a b

a b







.



 

c

b

b c

a

a





.

Można zauważyć, że w przypadku liczb kardynalnych skończonych własności działań
na liczbach kardynalnych są takie same jak własności „zwykłych” działań
arytmetycznych na liczbach naturalnych.

Własności działań na liczbach kardynalnych nieskończonych różnią się istotnie od
własności „zwykłych” działań arytmetycznych.

Na przykład, jeśli

b

jest nieskończona i

a b

 , to

a b b

  . Jeśli ponadto

0

a

 , to

a b b

  .

14

Wnioski z działań na zbiorach



0

0

0

0

,

n

n

















dla

0

n

 .



0

0

0

0

0

0

,

 

  











.



0

0

,





 

 

C

C

C

C

.





C

C

C C C

C

+ = ,

=

.



0

2



 C

.

Przykład 1

Dowieść, że zbiory

X

i

Y

są równoliczne:

 

1,2

X



,

 

5,3

Y



.

Przykład 2

Jaką moc mają następujące zbiory:





:4

A

x

x



 

,









  







:

ln

B

y

z

y

z

,

,

,

A B A B A B







.