ÿþP o d s t a w y m a t e m a t y k i d l a i n f o r m a t y k ó w
J a n u s z J . S z u s t e r
W s t p d o t e o r i i m n o g o [c i
L i t e r a t u r a
[ 1 ] Z o f i a A d a m o w i c z , P a w e B Z b i e r s k i , L o g i k a m a t e m a t y c z n a , P W N W - w a 1 9 9 1 ,
[ 2 ] W o j c i e c h G u z i c k i , P i o t r Z a k r z e w s k i , W y k Ba d y z e w s t p u d o m a t e m a t y k i w p r o w a d z e n i e
d o t e o r i i m n o g o [c i , W y d a w n i c t w o N a u k o w e P W N W - w a 2 0 0 5
[ 3 ] W o j c i e c h G u z i c k i , P i o t r Z a k r z e w s k i , W s t p d o m a t e m a t y k i z b i ó r z a d a D, W y d a w n i c t w o
N a u k o w e P W N W - w a 2 0 0 5
[ 4 ] K a z i m i e r z K u r a t o w s k i , A n d r z e j M o s t o w s k i , T e o r i a m n o g o [c i , M o n o g r a f i e M a t e m a t y c z n e
t . X X V I I , W - w a 1 9 7 8 ,
[ 5 ] I g o r A . Aa w r o w , Aa r i s a L . M a k s i m o w a , Z a d a n i a z t e o r i i m n o g o [c i , l o g i k i m a t e m a t y c z n e j i
t e o r i i a l g o r y t m ó w , P W N W - w a 2 0 0 4 ,
[ 6 ] J a n u s z O n y s z k i e w i c z , W i k t o r M a r e k , E l e m e n t y l o g i k i i t e o r i i m n o g o [c i , P W N W - w a 2 0 0 4 .
[ 7 ] H e l e n a R a s i o w a , W s t p d o m a t e m a t y k i w s p ó Bc z e s n e j , P W N W - w a 2 0 0 3 ,
[ 8 ] J e r z y T i u r y n , W s t p d o t e o r i i m n o g o [c i i l o g i k i , W r o c Ba w 2 0 0 0 ,
[ 9 ] A g n i e s z k a W o j c i e c h o w s k a , E l e m e n t y l o g i k i i t e o r i i m n o g o [c i , P W N W - w a 1 9 7 9 .
1 . Z A R Y S H I S T O R I I T E O R I I M N O G O ZC I 2
1 . Z a r y s h i s t o r i i t e o r i i m n o g o [c i
E w o l u c j a m y [l i m a t e m a t y c z n e j p r z e b i e g a w s p o s ó b n i e p r z e r w a n y o d c o n a j m n i e j 5 0 0 0 l a t .
W i o d Ba o n a o d , j a k b y [m y t o d z i [ p o w i e d z i e l i , a p l i k a c j i a r y t m e t y c z n y c h p o p r z e z r o z w ó j g e o m e -
t r i i i a l g e b r y o r a z p r ó b y f o r m a l i z a c j i i d e i m a t e m a t y c z n y c h z w y k o r z y s t a n i e m d o r o b k u f i l o z o f ó w
z w a n e g o o d c z a s ó w A r y s t o t e l e s a l o g i k . W r a z z e w z r o s t e m p o z i o m u k o m p l i k a c j i a n a l i z o w a n y c h
o b i e k t ó w m a t e m a t y c y p o t r z e b o w a l i c o r a z t o n o w y c h n a r z d z i p o z w a l a j c y c h n a j e d n o z n a c z n y
o p i s z a r ó w n o n o w o u z y s k i w a n y c h w y n i k ó w j a k i t y c h , k t ó r e b y By z n a n e s t o s u n k o w o d a w n o , a l e
j z y k i c h o p i s u b y B m a Bo p r e z y z y j n y . T a k i e p o j c i a j a k z b i ó r i z a w i e r a n i e b y By w p r z e s z Bo [c i r o -
z u m i a n e i n t u i c y j n i e , m i d z y i n n y m i z u w a g i n a g e o m e t r y c z n e o d n i e s i e n i a , i n i e b u d z i By s p o r ó w
i n t e r p r e t a c j e t y c h p o j . K Bo p o t y z a c z By s i p o j a w i a w m o m e n c i e , g d y o b i e k t e m r o z w a |a D
b y By p o j c i e r ó w n o l i c z n o [c i z b i o r ó w , c z y t e | p o j a w i e n i a s i w k o n t e k [c i e z b i o r u p o j c i a l i c z -
b y c z y w i e l k o [c i . J e d n y m z t a k i c h p r o b l e m ó w b y B p r o b l e m n i e o g r a n i c z o n e j p o d z i e l n o [c i c z y
r o z c i g l i w o [c i b a d a n y j u | p r z e z p i t a g o r e j c z y k ó w . T e n p r o b l e m p r o w a d z i B c z s t o d o k Bo p o t ó w
n a t u r y f i l o z o f i c z n e j i d o t y k a B o n z a r ó w n o e l e a t ó w j a k B o l z a n a i C a n t o r a .
P o r a z p i e r w s z y z z a g a d n i e m r ó w n o l i c z n o [c i l u b b a r d z i e j p r e c y z y j n i e u o g ó l n i o n e j r ó w n o l i c z -
n o [c i p o j a w i a s i w p r a c a c h G a l i l e u s z a , k t ó r y w y k a z u j e w z a j e m n i e j e d n o z n a c z n o d p o w i e d n i o [
m i d z y l i c z b a m i n a t u r a l n y m i i i c h d r u g i m i p o t g a m i .
D z i [ w y d a j e s i c o n a j m n i e j n i e z r o z u m i a Be , j a k p r z e z c a Be w i e k i m o g By b y u t r z y m y w a n e
i k u l t y w o w a n e p o g l d y m a t e m a t y c z n e , o k t ó r y c h d z i [ w i e m y , |e b y By n i e p r e c y z y j n e l u b c a B-
k o w i c i e b Bd n e . W y t Bu m a c z e n i e t e g o z j a w i s k a w y d a j e s i j e d n a k b y d o [ n i e s k o m p l i k o w a n e .
M i a n o w i c i e , n i e i s t n i e Bo w e w n t r z n e z a p o t r z e b o w a n i e m a t e m a t y k i n a p r e c y z j e w t y m w z g l -
d z i e . R o z w ó j a n a l i z y m a t e m a t y c z n e j j a k i d o k o n a B s i w X I X w i e k u z a s p r a w w i e l u ó w c z e s n y c h
m a t e m a t y k ó w w [r ó d k t ó r y c h n a l e |y w y m i e n i C a u c h y e g o , W e i e r s t r a s s a , B o l z a n o , R i e m a n n a ,
P o i n c a r é g o , M i t t a g - L e f f e r a , C a n t o r a , D e d e k i n d a , B e r n s t e i n a i P e a n o . T a l i s t a n i e j e s t o c z y w i [c i e
k o m p l e t n a , a l e w y m i e n i o n e n a z w i s k a w s k a z u j n a r a n g d o s t r z e |o n e g o p r o b l e m u .
B e z w t p i e n i a z a o j c a t e o r i i m n o g o [c i w j e j d z i s i e j s z y m r o z u m i e n i u n a l e |y u z n a m a t e m a -
t y k a n i e m i e c k e g o G e o r g a F e r d y n a n d a L u d w i g a C a n t o r a ( 1 8 4 5 - 1 9 1 8 ) . W y c h o d z c o d a n a l i z y
p r a c R i e m a n n a d o s z e d B p r o b l e m ó w z w i z a n y c h z p r z e l i c z a l n o [c i o r a z k o n s t r u o w a n i e m l i c z b
r z e c z y w i s t y c h . W l a t a c h 1 8 7 8 - 1 8 8 4 C a n t o r o g Bo s i B c y k l s z e [c i u r o z p a w p o [w i c o n y c h p r o b l e -
m o m r ó w n o l i c z n o [c i , t e o r i i z b i o r ó w c a Bk o w i c i e u p o r z d k o w a n y c h , w Ba s n o [c i o m t o p o l o g i c z n y m
R i R n , a t a k |e p r o b l e m o m m i a r y . W p r o w a d z e n i e w 1 8 8 2 r o k u p r z e z C a n t o r a p o j c i a z b i o r u
d o b r z e u p o r z d k o w a n e g o d a j e p o d s t a w d o b a d a n i a l i c z b k a r d y n a l n y c h o r a z p o z w a l a s f o r m u -
Bo w a h i p o t e z c o n t i n u u m . O p ó r m a t e m a t y k ó w w o b e c w y n i k ó w C a n t o r a b y B d o [ j e d n o l i t y i
t w a r d y . J e d y n i e C a r l W e i e r s t r a s s b y B n a s t a w i o n y d o j e g o w y n i k ó w |y c z l i w i e . O p ó r t e n p o w o d o -
w a n y b y B r e w o l u c y j n y m c h a r a k t e r e m t y c h w y n i k ó w , b u r z y By o n e b o w i e m p o n a d d w u t y s i c z n
t r a d y c j m a t e m a t y c z n . P o w y n i k a c h C a n t o r a p r z y s z Ba k o l e j n a u z u p e Bn i e j c e j e r e z u l t a t y B e r n -
s t e i n a i Z e r m e l o . P r a w d z i w y m s o j u s z n i k i e m C a n t o r a w p r a c a c h n a d t e o r i m n o g o [c i b y B J u l i u s
W i l h e l m R i c h a r d D e d e k i n d ( 1 8 3 1 - 1 9 1 6 ) . N i e k t ó r e s p o [r ó d w y n i k ó w u z y s k a n y c h p r z e z C a n t o -
r a i j e g o k o n t u n u a t o r ó w b y By o d k r y t e p r z e z D e d e k i n d a j e d n a k n i e z o s t a By o n e o p u b l i k o w a n e .
C o w i c e j w i e l e w y n i k ó w t e g o o s t a t n i e g o p o k a z a Bo j a k w p e Bn i n a l e |y s t o s o w a t e o r i e a k s j o -
m a t y c z n e . M i a n o w i c i e , D e d e k i n d r o z w a |a j c o g ó l n e p r z y p a d k i z b i o r ó w , a n i e t y l k o z b i o r ó w
L I T E R A T U R A 3
c a Bk o w i c i e u p o r z d k o w a n y c h , d o c h o d z i d o z b i o r ó w k r a t o w y c h i g r u n t o w n i e a n a l i z u j e i c h w Ba -
s n o [c i . C h o c i a | w o d r ó |n i e n i u o d w y n i k ó w C a n t o r a , r e z u l t a t y u z y s k a n e p r z e z D e d e k i n d a n i e
z n a l a z By n a t y c h m i a s t o w e g o z a s t o s o w a n i a , t o o k a z a By s i o n e n i e z w y k l e w a |n i e j u | w n i e o d l e g Be j
p r z y s z Bo [c i .
W y n i k i p r a c C a n t o r a p o z w o l i By n a f o r m a l i z a c j m a t e m a t y k i , a j e d n o c z e [n i e d a By p o c z t e k
u p o w s z e c h n i a n i u s i m e t o d a k s j o m a t y c z n y c h . J e d n a k p o z a t y m o s i g n i c i e m d a By o n e p o c z t e k
k r y z y s o w i p o d s t a w m a t e m a t y k i . P o j a w i By s i o t o p a r a d o k s y t e o r i i m n o g o [c i . W i k s z o [ z n i c h
b y Ba b l i zn i a c z o p o d o b n a , p o d w z g l d e m n a t u r y , d o t y c h z j a k i m i z e t k n i t o s i w c z e [n i e j p r z y
o d k r y c i u g e o m e t r i i n i e e u k l i d e s o w y c h . S k o n s t a t o w a t o m o |n a s f o r m u Bo w a n i e m z a c z e r p n i t y m z
E l e m e n t ó w h i s t o r i i m a t e m a t y k i N i c o l a s a B o u r b a k i , |e p r ó |n e s p r ó b y z b u d o w a n i a j a k i e j k o l w i e k
t e o r i i m a t e m a t y c z n e j z a p o m o c o d w o By w a n i a s i ( j a w n e g o l u b n i e ) d o i n t u i c j i . S z Bo z a t e m
o t o , b y d l a t e o r i i m n o g o [c i s t w o r z y p o d s t a w a k s j o m a t y c z n a n a l o g i c z n d o u k Ba d u a k s j o -
m a t ó w g e o m e t r i i e l e m e n t a r n e j , b e z d o c i e k a n i a c o n a z y w a m y z b i o r e m , w s e n s i e n a t u r y o b i e k t u ,
j a k r ó w n i e | n i e j e s t d e f i n i o w a n e p r z y n a l e |e n i e d o z b i o r u , a j e d y n i e w y r a zn i e f o r m u Bo w a n e s
w a r u n k i c h a r a k t e r y z u j c e p r z y n a l e |n o [ d o u s t a l o n e g o z b i o r u . P i e r w s z y m , k t ó r y z b u d o w a B t a -
k a k s j o m a t y z a c j b y B Z e r m e l o i s t a Bo s i t o w 1 9 0 8 r o k u . P r ó b a t a u z u p e Bn i o n a p r z e z w y n k i
S k o l e m a i F r a e n k l a p o z w o l i Ba n a k o n s t r u k c j a k s j o m a t y k i t e o r i i m n o g o [c i , j e d n a k c e n j a k
n a l e |a Bo z a t o z a p Ba c i , b y Ba k o m i e c z n o [ w p r o w a d z e n i a t a k |e r e g u B l o g i k i .
L i t e r a t u r a
[ 1 ] N . B o u r b a k i E l e m e n t y h i s t o r i i m a t e m a t y k i , P W N W a r s z a w a 1 9 8 0 ,
[ 2 ] A . P . J u s z k i e w i c z H i s t o r i a m a t e m a t y k i ( o d c z a s ó w n a j d a w n i e j s z y c h d o p o c z t k u c z a s ó w
n o w o |y t n i c h ) , T o m 1 - 3 , P W N W a r s z a w a 1 9 7 5 ,
[ 3 ] K . K u r a t o w s k i , A . M o s t o w s k i T e o r i a m n o g o [c i , M o n o g r a f i e M a t e m a t y c z n e X X V I I , W a r -
s z a w a 1 9 7 8 ,
[ 4 ] R . M u r a w s k i F i l o z o f i a m a t e m a t y k i z a r y s d z i e j ó w , W y d a w n i c t w o N a u k o w e P W N 1 9 9 5
L I T E R A T U R A 4
1 . 1 . W a |n e o s o b y i d a t y w r o z w o j u t e o r i i m n o g o [c i
J u l i u s W i l h e l m R i c h a r d D E D E K I N D ( "1 8 3 1 B r a u n s c h w e i g w N i e m c z e c h 1 9 1 6 B r a u n -
s c h w e i g w N i e m c z e c h ) , n o w o c z e s n a t e o r i a l i c z b a l g e b r a i c z n y c h , p r a k r o j e D e d e k i n d a .
P a u l D a v i d G u s t a v D U B O I S - R E Y M O N D ( "1 8 3 1 B e r l i n 1 8 8 9 F r e i b u r g w N i e m c z e c h ) ,
b a d a B s z e r e g i l i c z b o w e , a p r z y t y m w n i ó s B w i e l e d o t e o r i i z b i o r ó w .
G e o r g F e r d y n a n d L u d w i g C A N T O R ( "1 8 4 5 S t P e t e r s b u r g w R o s j i 1 9 1 8 H a l l e w N i e m -
c z e c h ) , t w ó r c a t e o r i i m n o g o [c i , k t ó r a w p By n Ba n a r o z w ó j c a Be j m a t e m a t y k i , a w s z c z e g ó l n o [-
c i n a p o d s t a w y w s p ó Bc z e s n e j a n a l i z y m a t e m a t y c z n e j , k o n s t r u k c j a C a n t o r a l i c z b r z e c z y w i -
s t y c h .
M a g n u s G ö s t a M I T T A G - L E F F L E R ( "1 8 4 6 S z t o k h o l m 1 9 2 7 S z t o k h o l m ) , t w ó r c a s k a n -
d y n a w s k i e j s z k o By m a t e m a t y c z n e j , p r z y c z y n i B s i d o u p o r z d k o w a n i a t e o r i i m n o g o [c i .
E r n s t F r i e d r i c h F e r d i n a n d Z E R M E L O ( "1 8 7 1 B e r l i n 1 9 5 3 F r e i b u r g w N i e m c z e c h ) , b a d a B
p o d s t a w y m a t e m a t y k i , a u t o r f u n d a m e n t a l n y c h p r a c z t e o r i i m n o g o [c i w s z c z e g ó l n o [c i
a k s j o m a t y k i t e o r i i m n o g o [c i .
´
J u l i u s H e n r i P O I N C A R E ( "1 8 5 4 N a n c y w e F r a n c j i 1 9 1 2 P a r y |) , z a j m o w a B s i w i e l o m a
d y s c y p l i n a m i m a t e m a t y c z n y m i , a t a k |e f i z y k i f i l o z o f i . J e g o p r a c e d o t y c z c e p o d s t a w
m a t e m a t y k i s t a n o w i By i s t o t n y w k Ba d w r o z w ó j t e o r i i m n o g o [c i .
A d o l f A b r a h a m H a l e v i F R A E N K E L ( "1 8 9 1 M o n a c h i u m 1 9 6 5 J e r o z o l i m a ) , w s p ó l n i e z
F r a e n k l e m i C a n t o r e m w s p ó Bt w o r z y B w s p ó Bc z e s n t e o r i m n o g o [c i .
F r i e d r i e c h L u d w i g G o t t l o b F R E G E ( "1 8 4 8 W i s m a r w M e c k l e n b u r g i i - S c h w e r i n i e w N i e m -
c z e c h 1 9 2 5 B a d K l e i n e n w N i e m c z e c h ) , p i e r w s z e u j c i e r a c h u n k u z d a D j a k o s f o r m a l i z o -
w a n e j t e o r i i a k s j o m a t y c z n e j .
G i u s e p p e P E A N O ( "1 8 5 8 C u n e o n a S a r d y n i i 1 9 3 2 T u r y n w e W Bo s z e c h ) , a t y t m e t y k a
j a k o t e o r i a a k s j o m a t y c z n a s f o r m a l i z o w a n a ( A r y t m e t y k a P e a n o ) .
D a v i d H I L B E R T ( "1 8 6 2 K r ó l e w i e c w P r u s a c h W s c h o d n i c h 1 9 4 3 G e t y n g a w N i e m -
c z e c h ) , j e g o b a d a n i a n a d p o d s t a w a m i g e o m e t r i i ( 1 8 9 8 - 1 9 0 2 ) z a p o c z t k o w a By n o w o c z e s n ,
a k s j o m a t y c z n b u d o w t e o r i i m a t e m a t y c z n y c h ( 2 3 p r o b l e m y H i l b e r t a , t e o r i a s p e k t r a l n a
o p e r a t o r ó w l i n i o w y c h p o d s t a w o w y a p a r a t m e c h a n i k i k w a n t o w e j ) .
B e r t r a n d A r t h u r W i l l i a m R U S S E L ( "1 8 7 2 R a v e n s c r o f t w W a l i i 1 9 7 0 P e n r h y n d e n -
d r a e t h w W a l i i ) , w 1 9 0 2 r a n a l i z u j c z a p r o p o n o w a n y p r z e z F r e g e g o s y s t e m l o g i c z n y c h
p o d s t a w m a t e m a t y k i z a u w a |y B w n i m s p r z e c z n o [ p o l e g a j c n a t z w . p a r a d o k s i e k l a s
( a n t y n o m i a R u s s e l l a ) , w 1 9 0 3 o g Bo s i B P r i n c i p l e s o f M a t h e m a t i c s , w k t ó r y c h s t a r a B s i
s p r o w a d z i t e o r i m n o g o [c i , a n a w e t c a B m a t e m a t y k d o l o g i k i , w 1 9 0 8 r s t w o r z y B z a -
s a d y t z w . t e o r i i t y p ó w l o g i c z n y c h . W l a t a c h 1 9 1 0 - 1 9 1 3 B . A . W . R u s s e l l w r a z z A l f r e d e m
N o r t h W h i t e h e a d e m ( " 1 8 6 1 R a m s g a t e h r a b s t w o K e n t w A n g l i i 1 8 4 7 C a m b r i d g e w
M a s s a c h u s e t t s U S A ) n a p i s a l i i o p u b l i k o w a l i P r i n c i p i a M a t h e m a t i c a ( t . I I I I ) , w k t ó r e j
L I T E R A T U R A 5
i d e p r z e w o d n i b y Bo p o s z u k i w a n i e p o d s t a w m a t e m a t y k i w z a s a d a c h l o g i c z n y c h , r e z u l -
t a t e m z a [ p r z e d s t a w i e n i e m a t e m a t y k i w p o s t a c i s y s t e m u s f o r m a l i z o w a n e g o o r a z n a d a n i e
w s p ó Bc z e s n e g o k s z t a Bt u l o g i c e m a t e m a t y c z n e j .
J o h n ( J a n o s ) v o n N E U M A N N ( "1 9 0 3 B u d a p e s z t 1 9 5 7 W a s z y n g t o n ) , m a t e m a t y k , c h e -
m i k , f i z y k , i n f o r m a t y k w s p ó Bt w ó r c a b r o n i a t o m o w e j . J e g o b a d a n i a z t e o r i i m n o g o [c i p r z y -
c z y n i By s i d o w y k o r z y s t a n i a u z y s k a n y c h p r z e z n i e g o w y n i k ó w w z a s t o s o w a n i a c h p r a k -
t y c z n y c h o r a z d o u s z l a c h e t n i e n i a w i e l u w y n i k ó w .
H e n r i L e o n L E B E S G U E ( "1 8 7 5 B e a v a i s w e F r a n c j i 1 9 4 1 P a r y |) , t w ó r c a o g ó l n e j t e o r i i
m i a r y i c a Bk i . W t r a k c i e b a d a D n a d t y m i t e o r i a m i u z y s k a B w a |n e d l a t e o r i i m n o g o [c i
w y n i k i .
W a c Ba w S I E R P I CS K I ( "1 8 8 2 W a r s z a w a 1 9 6 9 W a r s z a w a ) , b a d a B t e o r i l i c z b , t o p o l o g i
i t e o r i m n o g o [c i . W 1 9 1 2 r o k u n a p i s a B f u n d a m e n t a l n k s i |k d o t y c z c t e j o s t a t n i e j
d y s c y p l i n y , w k t ó r e j z a m i e [c i B r ó w n i e | w i e l e w Ba s n y c h w y n i k ó w .
K u r t G Ö D E L ( "1 9 0 6 B r ü n n w A u s t r o w g r z e c h o b e c n i e B r n o w C z e c h a c h 1 9 7 8 P r i n -
c e t o n w s t a n i e N o w y J o r k w U S A ) , n i e p e Bn o [ t e o r i i a k s j o m a t y c z n y c h s f o r m a l i z o w a n y c h
z a w i e r a j c y c h a r y t m e t y k . T w i e r d z e n i e o n i e s p r z e c z n o [c i h i p o t e z y c o n t i n u u m z a k s j o m a -
t y k t e o r i i m n o g o [c i .
K a z i m i e r z K U R A T O W S K I ( "1 8 9 6 W a r s z a w a 1 9 8 0 W a r s z a w a ) , j e d e n z t w ó r c ó w L w o w -
s k i e j S z k o By M a t e m a t y c z n e j , b a d a c z t e o r i i m n o g o [c i , t o p o l o g i i , t e o r i i g r a f ó w , a n a l i z y m a t e -
m a t y c z n e j i p o d s t a w m a t e m a t y k i . J e g o w y n i k i b a d a D z p o d s t a w m a t e m a t y k i p r z y c z y n i By
s i d o u p o r z d k o w a n i a t e j d y s c y p l i n y ( l e m a t K u r a t o w s k i e g o - Z o r n a ) .
S t a n i s Ba w M a r c i n U L A M ( "1 9 0 9 L w ó w 1 9 8 4 S a n t a F e w U S A ) , t w ó r c a m e t o d y M o n t e
C a r l o , w s z e c h s t r o n n y m a t e m a t y k o z d o l n o [c i a c h p r z e n o s z e n i a w y n i k ó w m a t e m a t y c z n y c h
d o i n n y c h n a u k . J e g o p r a c e z t e o r i i p r o c e s ó w s t o c h a s t y c z n y c h , r ó w n a D r ó |n i c z k o w y c h
c z s t k o w y c h , a n a l i z y f u n k c j o n a l n e j o r a z i c h z a s t o s o w a n i a w f i z y c e p r z y c z y n i By s i d o b a -
d a D p r o b l e m ó w t e o r i i m n o g o [c i . N i e k t ó r e z j e g o w y n i k ó w p r a c p o z o s t a j u t a j n i o n e p o d z i [
d z i e D, z e w z g l d u n a i c h w y k o r z y s t a n i e p r z y k o n s t r u k c j i b o m b y a t o m o w e j i w o d o r o w e j .
B e z s p o r n i e S t a n i s Ba w U l a m j e s t u w a |a n y z a t w ó r c k o n c e p c j i b o m b y w o d o r o w e j , b y B o n
t a k |e s t a By m k o n s u l t a n t e m w t r a k c i e j e j b u d o w y .
P a u l J o s e p h C O H E N ( "1 9 3 4 L o n g B r a n c h , N e w J e r s e y ) , n i e z a l e |n o [ h i p o t e z y c o n t i n u u m
( 1 9 6 3 ) , m e d a l F i e l d s a w 1 9 6 6 .
2 . W P R O W A D Z E N I E 6
2 . W p r o w a d z e n i e
W a r t o d o d a , |e t a k j a k l o g i k a m a t e m a t y c z n a k o r z y s t a z p o j t e o r i i m n o g o [c i , t a k t e o r i a
m n o g o [c i w y k o r z y s t u j e w i e l e p o j l o g i k i . W t e j c z [c i w y k Ba d u n i e b d z i e m y f o r m a l i z o w a p o -
j l o g i k i m a t e m a t y c z n e j , b d z i e t o p r z e d m i o t e m d r u g i e j c z [c i . J e d n a k z u w a g i n a u |y t e c z n o [
p o d s t a w o w y c h f a k t ó w l o g i c z n y c h p r z e d s t a w i m y j e w z n a c z n y m u p r o s z c z e n i u . D o d a n a l e |y , |e
p o s Bu |y m y s i l o g i k z n a n z n a u k i w s z k o l e [r e d n i e j . J e s t t o w p e w n y m s e n s i e k l a s y c z n e p o -
d e j [c i e d o t e j d y s c y p l i n y , o d m i e n n e o d p o d e j [c i a k t ó r e z a p r e z e n t o w a n e w c z [c i p o [w i c o n e j
l o g i c e . T e n l o g i c z n y d u a l i z m j e s t j e d n a k k o n i e c z n y z e w z g l d u n a g r a d a c j t r u d n o [c i .
N i e c h Z o z n a c z a z b i ó r w s z y s t k i c h z d a D o r z e k a j c y c h o d n o s z c y c h s i d o m a t e m a t y k i . N i e c h
p o n a d t o 0 b d z i e s y m b o l e m f a Bs z u , n a t o m i a s t 1 s y m b o l e m p r a w d y . F u n k c j w : Z ’!{ 0 , 1 }
n a z y w a m y w a r t o [c i o w a n i e m . P r z y j m i j m y u m o w , |e e l e m e n t y z b i o r u Z b d z i e m y o z n a c z a
m a By m i l i t e r a m i a l f a b e t u :
p , q , r , s , p 1 , q 1 , r 1 , s 1 , p 2 , q 2 , r 2 , s 2 , . . . ,
k t ó r y c h m o |e b y n a w e t n i e s k o Dc z e n i e w i e l e . L i t e r y o z n a c z a b d o b i e k t y z w a n e z m i e n n y m i
z d a n i o w y m i .
N a r z d z i e m z a c z e r p n i t y m z j z y k a p o t o c z n e g o s s p ó j n i k i , z w a n e w l o g i c e r ó w n i e | f u n k t o -
r a m i z d a n i o t w ó r c z y m i . P o z w a l a j o n e b u d o w a z e z d a D p r o s t y c h z d a n i a z Bo |o n e . I t a k , z a m i a s t
p i s a n i e u |y j e m y s y m b o l u <" ( s y m b o l i z y j e o n z d e f o r m o w a n l i t e r N , o d n e g o , c o o z n a c z a
p r z e c z ) , z a m i a s t p i s a j e [l i . . . , t o z a p i s z e m y ’!, s y m b o l ”! b d z i e z a s t p o w a B z w r o t w t e d y i
t y l k o w t e d y ( l u b k r ó t k o w t t ) , s y m b o l '" o z n a c z a b d z i e i , z a [ s y m b o l (" b d z i e z a s t p o w a B
s p ó j n i k l u b .
O p r ó c z s p ó j n i k ó w ( f u n k t o r ó w z d a n i o t w ó r c z y c h ) p o s Bu g i w a s i b d z i e m y n a w i a s a m i : o t w i e -
r a j c y m ( o r a z z a m y k a j c y m ) . W o p a r c i u o n a w i a s y , f u n k t o r y z d a n i o t w ó r c z e i z m i e n n e
z d a n i o w e t w o r z y b d z i e m y f o r m u By r a c h u n k u z d a D. K a |d a z t a k i c h f o r m u B s t a j e s i z d a n i e m ,
g d y w m i e j s c e z m i e n n y c h z d a n i o w y c h w s t a w i m y z d a n i a o c z y w i [c i e w m i e j s c e u s t a l o n e j l i t e r y
w s t a w i a m y t o s a m o z d a n i e .
N a w i a s y , w y m i e n i o n e j a k o e l e m e n t s k Ba d o w y f o r m u B z d a n i o w y c h u Ba t w i a j , a n i e k i e d y w r c z
u m o |l i w i a j , o d c z y t a n i e t a k i e j f o r m u By g d y w z b i o r z e f u n k t o r ó w n i e z o s t a Ba w p r o w a d z o n a
h i e r a r c h i a m o c y w i z a n i a .
W [r ó d w s z y s t k i c h f o r m u B r a c h u n k u z d a D s z c z e g ó l n i e w a |n r o l p e Bn i f o r m u By p r a w d z i w e
b e z w z g l d u n a w a r t o [ l o g i c z n w y s t p u j c y c h w n i c h z m i e n n y c h z d a n i o w y c h . F o r m u By t a k i e
n a z y w a m y t a u t o l o g i a m i i w z a p i s i e d l a p o d k r e [l e n i a t e g o f a k t u p o p r z e d z a m y s y m b o l e m . R o l a
t a u t o l o g i i p o l e g a n a t y m , |e z a i c h p o m o c m o |e m y d o k o n y w a o p e r a c j i l o g i c z n y c h n i e z a l e |n i e
o d t r e [c i z d a D, k t ó r e l o g i c z n i e p r z e k s z t a Bc a m y .
O s o b n y m z a g a d n i e n i e m j e s t s p r a w d z e n i e c z y d a n a f o r m u Ba j e s t t a u t o l o g i . P r z e d s t a w i m y
p o c h o d z c o d E r n s t a S c h r ö d e r a m e t o d z e r o j e d y n k o w , l u b i n a c z e j m e t o d t a b l i c o w . P o l e g a
o n a n a r o z p a t r z e n i u w s z y s t k i c h u k Ba d ó w w a r t o [c i l o g i c z n y c h z m i e n n y c h z d a n i o w y c h w y s t p u -
j c y c h w d a n y m w y r a |e n i u . M e t o d a t a n a z y w a n a j e s t n i e k i e d y m e t o d m a t r y c o w , z e w z g l d u
n a p o s Bu g i w a n i e s i w n i e j t a b e l k a m i m a t r y c o w y m i , p r z e d s t a w i a j c y m i w j a k i s p o s ó b w a r t o [
l o g i c z n a z d a n i a z Bo |o n e g o u t w o r z o n e g o p r z y p o m o c y d a n e g o f u n k t o r a , l u b f u n k t o r ó w , j e s t w y -
2 . W P R O W A D Z E N I E 7
z n a c z o n a p r z e z w a r t o [c i l o g i c z n e z d a D s k Ba d o w y c h . P o z o s t a j c p r z y d o t y c h c z a s o w y c h u m o w a c h
m o |e m y z d e f i n i o w a p o s z c z e g ó l n e f u n k t o r y . T y m r a z e m d e f i n i c j a m a p o s t a n a s t p u j c e j t a b e l i :
w ( p ) w ( q ) w ( <" p ) w ( p '" q ) w ( p (" q ) w ( p ’! q ) w ( p ”! q )
0 0 1 0 0 1 1
0 1 1 0 1 1 0
1 0 0 0 1 0 0
1 1 0 1 1 1 1
M e t o d z e r o j e d y n k o w z i l u s t r u j e m y n a s t p u j c y m p r z y k Ba d e m .
P r z y k Ba d . S p r a w d z i m y c z y f o r m u Ba w { ( p ’! q ) ’! [ ( q ’! r ) ’! ( p ’! r ) ] } j e s t t a u t o l o g i
( t w i e r d z e n i e m ) r a c h u n k u z d a D.
w [ ( q ’! r ) ’! w { ( p ’! q ) ’!
w ( p ) w ( q ) w ( r ) w ( p ’! q ) w ( q ’! r ) w ( p ’! r )
’! ( p ’! r ) ] ’! [ ( q ’! r ) ’! ( p ’! r ) ] }
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 1 0 1 0 1 1 1
0 1 1 1 1 1 1 1
1 0 0 0 1 0 0 1
1 0 1 0 1 1 1 1
1 1 0 1 0 0 1 1
1 1 1 1 1 1 1 1
T a b e l a t a p o k a z u j e w j a k i s p o s ó b n a l e |y p o s t p o w a d l a s p r a w d z e n i a c z y r o z p a t r y w a n a f o r -
m u Ba j e s t t a u t o l o g i . P o n i e w a | o s t a t n i a k o l u m n a s k Ba d a s i z s a m y c h j e d y n e k , t o o z n a c z a t o , |e
d l a w s z y s t k i c h m o |l i w y c h u k Ba d ó w w a r t o [c i l o g i c z n y c h z d a D s k Ba d o w y c h , z b u d o w a n y c h z g o d n i e
z f o r m u B, o t r z y m u j e m y z d a n i e p r a w d z i w e . Z a t e m b a d a n a p r z e z n a s f o r m u Ba j e s t t a u t o l o g i .
P r z e d s t a w i m y t e r a z k i l k a w a |n i e j s z y c h t a u t o l o g i i , k t ó r y c h s p r a w d z e n i e p o z o s t a w i a m y d o
s a m o d z i e l n e g o w y k o n a n i a p r z y u |y c i u o b u p r z e d s t a w i o n y c h m e t o d .
p o s t a p r a w a n a z w a p r a w a
w ( p (" q ) = w ( q (" p ) p r z e m i e n n o [c i a l t e r n a t y w y
w ( p '" q ) = w ( q '" p ) p r z e m i e n n o [c i k o n i u n k c j i
w ( p (" ( q (" r ) ) = w ( ( p (" q ) (" r ) Bc z n o [c i a l t e r n a t y w y
w ( p '" ( q '" r ) ) = w ( p '" q ) '" r ) Bc z n o [c i k o n i u n k c j i
w ( p '" ( q (" r ) ) = w ( ( p '" q ) (" ( p '" r ) ) r o z d z i e l n o [c i k o n i u n k c j i w z g l d e m a l t e r n a t y w y
w ( p (" ( q '" r ) ) = w ( ( p (" q ) '" ( p (" r ) ) r o z d z i e l n o [c i a l t e r n a t y w y w z g l d e m k o n i u n k c j i
w ( p ("<"p ) = 1 w y Bc z o n e g o [r o d k a
w ( p Ð!Ò! p ) = 1 t o |s a m o [c i
w ( <" ( p '"<"p ) ) = 1 s p r z e c z n o [c i
w ( p Ô!<" ( <" p ) ) = 1 p o d w ó j n e g o p r z e c z e n i a
w ( [ ( p Ò! q ) '" ( q Ò! r ) ] Ò! ( p Ò! r ) ) = 1 s y l o g i z m u
w ( ( <" p Ò! p ) Ò! p ) = 1 s p r o w a d z a n i a d o n i e d o r z e c z n o [c i
w ( p Ò! q ) = w ( <" q Ò!<" p ) k o n t r a p o z y c j i
w ( p '" ( p Ò! q ) Ò! q ) = 1 r e g u Ba o d r y w a n i a
Z a j m i e m y s i t e r a z b a r d z o w a |n y m i z p r a k t y c z n e g o p u n k t u w i d z e n i a t a u t o l o g i a m i z w a n y m i
3 . Z B I O R Y I O P E R A C J E N A Z B I O R A C H 8
p r a w a m i d e M o r g a n a . P o z w a l a j o n e p r z e c z y f u n k t o r o m d w u c z Bo n o w y m i s c z s t o w y k o r z y -
s t y w a n e w d o w o d a c h n i e w p r o s t .
p o s t a p r a w a n a z w a p r a w a
w ( <" ( p '" q ) ) = w ( <" p ("<"q ) p r a w o d e M o r g a n a d l a k o n i u n k c j i
w ( <" ( p (" q ) ) = w ( <" p '"<"q ) p r a w o d e M o r g a n a d l a a l t e r n a t y w y
B e z p o [r e d n i k o n s e k w e n c j p r a w d e M o r g a n a d l a z d a D s n a s t p u j c e t a u t o l o g i e :
w ( <" ( p ’! q ) ) = w ( p '"<"q )
w ( <" ( p ”! q ) ) = w ( [ ( p '"<"q ) (" ( q '"<"p ) ] )
W m a t e m a t y c e s p o t y k a m y s i c z s t o z p o j c i a m i w a r u n k u k o n i e c z n e g o i w a r u n k u w y s t a r -
c z a j c e g o . P o j c i a t e w i | s i z f u n k t o r a m i i m p l i k a c j i i r ó w n o w a |n o [c i . R o z w a |m y i m p l i k a c j
p ’! q , ( ”)
w k t ó r e j z d a n i e p n a z y w a m y p o p r z e d n i k i e m , a z d a n i e q n a s t p n i k i e m i m p l i k a c j i ( ”) . M ó w i m y
w t e d y |e z d a n i e q j e s t w a r u n k i e m k o n i e c z n y m d l a p , n a t o m i a s t p j e s t w a r u n k i e m d o s t a t e c z n y m
d l a q .
D l a i m p l i k a c j i ( ”) i m p l i k a c j
p ! q , ( l u b i n a c z e j q ’! p ) ( ")
n a z y w a m y o d w r o t n .
J e [l i p r a w d z i w e s i m p l i k a c j a p r o s t a i i m p l i k a c j a o d w r o t n a , t o z d a n i e p ”! q n a z y w a m y
w a r u n k i e m k o n i e c z n y m i w y s t a r c z a j c y m .
3 . Z b i o r y i o p e r a c j e n a z b i o r a c h
W t e o r i i m n o g o [c i , p o d o b n i e j a k w k a |d e j d y s c y p l i n i e m a t e m a t y c z n e j , k o r z y s t a m y z p o -
j p r z y j m o w a n y c h b e z d e f i n i c j i t a k z w a n y c h p o j p i e r w o t n y c h . Z a l i c z a m y d o n i c h : p o j c i e
z b i o r u i p o j c i e p r z y n a l e |n o [c i d o z b i o r u l u b i n a c z e j b y c i e e l e m e n t e m z b i o r u . Z a m i a s t m ó w i ,
|e a j e s t e l e m e n t e m z b i o r u A p i s z e m y a " A , j e [l i n a t o m i a s t a n i e j e s t e l e m e n t e m z b i o r u A
p i s z e m y a " A . J e [l i z a j m u j e m y s i u s t a l o n t e o r i m a t e m a t y c z n ( w n a s z y m p r z y p a d k u t e o r i
m n o g o [c i ) , t o p o z a p o j c i a m i p i e r w o t n y m i p r z y j m u j e s i b e z d o w o d u p e w n l i c z b w Ba s n o [c i
( t w i e r d z e D) o d n o s z c y c h s i d o o b i e k t ó w t e o r i i ( w n a s z y m p r z y p a d k u z b i o r ó w ) z w a n y c h a k -
s j o m a t a m i i w o p a r c i u o t a k i z e s t a w n a r z d z i f o r m u Bo w a n e s d a l s z e w Ba s n o [c i o b i e k t ó w t e j
t e o r i i . I s t n i e n i e t a k i e j k o l e k c j i p o j p i e r w o t n y c h i a k s j o m a t ó w w p r z y p a d k u u s t a l o n e j t e o r i i
p o z w a l a n a z w a j t e o r i a k s j o m a t y c z n . J a k j u | m ó w i l i [m y w c z [c i p o [w i c o n e j h i s t o r i i t e o r i i
m n o g o [c i d y s c y p l i n a t a m a a k s j o m a t y k z w a n a k s j o m a t y k Z e r m e l o - F r a e n k l a .
R o z p a t r z m y d w a d o w o l n e z b i o r y A i B . M ó w i m y , |e A j e t r ó w n y B w t e d y i t y l k o w t e d y ,
g d y z b i o r y t e m a j i d e n t y c z n e e l e m e n t y . Z w y k l e f a k t t e n w y r a |a m y p i s z c :
A = B w t e d y i t y l k o w t e d y , g d y d l a k a |d e g o a z a c h o d z i : a " A w t t a " B .
Z a l e |n o [ t n a z y w a m y z a s a d e k s t e n s j o n a l n o [c i .
3 . Z B I O R Y I O P E R A C J E N A Z B I O R A C H 9
M ó w i m y , |e A j e s t p o d z b i o r e m B l u b r ó w n o w a |n i e A j e s t z a w a r t y w B w t e d y i t y l k o w t e d y ,
g d y k a |d y e l e m e n t z b i o t u A j e s t e l e m e n t e m z b i o r u B . P i s z e m y w t e d y A †" B . N i e k i e d y o z b i o r z e
B m ó w i m y , |e j e s t n a d z b i o r e m z b i o r u A . J e [l i A †" B i A = B , t o A n a z y w a m y p o d z b i o r e m
w Ba [c i w y m z b i o r u B i p i s z e m y w t e d y A B . Z b i ó r n i e z a w i e r a j c y |a d n e g o e l e m e n t u n a z y w a m y
z b i o r e m p u s t y m i o z n a c z a m y s y m b o l e m ". N a m o c y z a s a d y e k s t e n s j o n a l n o [c i i s t n i e j e d o k Ba d n i e
j e d e n z b i ó r p u s t y .
Z b i ó r b d z i e m y u w a |a z a o k r e [l o n y j e [l i z o s t a Bo p o d a n e k r y t e r i u m p o z w a l a j c e r o z s t r z y g -
n c z y d a n y e l e m e n t n a l e |y , c z y t e | n i e n a l e |y d o r o z p a t r y w a n e g o z b i o r u .
W z a l e |n o [c i o d s p o s o b u o k r e [l e n i a i r o d z a j u z b i o r u o z n a c z a m y g o s y m b o l e m { a 1 , . . . , a n } ,
g d y z b i ó r j e s t s k o Dc z o n y i s k Ba d a s i z n e l e m e n t ó w , a l b o { x | w ( x ) } , g d z i e w ( x ) j e s t w a r u n k i e m
c h a r a k t e r y z u j c y m d a n y z b i ó r . Z a m i a s t A )"{ x | w ( x ) } b d z i e m y p i s a { x " A | w ( x ) } . J e |e l i A
j e s t z b i o r e m , k t ó r e g o e l e m e n t a m i s z b i o r y , t o A n a z y w a b d z i e m y r o d z i n z b i o r ó w .
J e [l i A i B s d o w o l n y m i z b i o r a m i , t o p r z e z s u m t y c h z b i o r ó w r o z u m i e m y z b i ó r A *"
B , k t ó r e g o e l e m e n t a m i s t e i t y l k o t e e l e m e n t y , k t ó r e n a l e | d o z b i o r u A l u b d o z b i o r u B .
N a t o m i a s t i l o c z y n e m ( p r z e c i c i e m ) z b i o r ó w n a z y w a m y z b i ó r A )" B , k t ó r e g o e l e m e n t a m i s t e
i t y l k o t e e l e m e n t y , k t ó r e s r ó w n o c z e [n i e e l e m e n t a m i z b i o r u A i z b i o r u B . R ó |n i c z b i o r u A
i B n a z y w a m y z b i ó r A \ B , z Bo |o n y z t y c h i t y l k o t y c h e l e m e n t ó w , k t ó r e n a l e | d o A i n i e
n a l e | d o B . D l a z b i o r u A s y m b o l e m P ( A ) l u b t e | 2 A o z n a c z a b d z i e m y z b i ó r z Bo |o n y z e
w s z y s t k i c h p o d z b i o r ó w t e g o z b i o r u i n a z y w a g o b d z i e m y z b i o r e m p o t g o w y m z b i o r u A . J e |e l i
w o d n i e s i e n i u d o u s t a l o n e g o z b i o r u A r o z w a |a n i a o g r a n i c z y m y t y l k o d o j e g o p o d z b i o r ó w ( t j .
e l e m e n t ó w P ( A ) ) , t o z b i ó r A n a z y w a b d z i e m y w t e d y p r z e s t r z e n i .
D z i a Ba n i a s u m y i i l o c z y n u d w ó c h z b i o r ó w m o |n a r o z s z e r z y n a w i k s z l i c z b z b i o r ó w , t o
z n a c z y n a r o d z i n y z b i o r ó w . D l a r o d z i n y z b i o r ó w A j e j s u m o z n a c z a m y p r z e z A i m a m y
w t e d y :
x " A w t t , g d y i s t n i e j e A "A , |e x " A .
P o d o b n i e d e f i n i u j e m y i l o c z y n r o d z i n y z b i o r ó w A . M a m y m i a n o w i c i e :
x " A w t t , d l a k a |d e g o A "A , |e x " A .
R o z p a t r z m y t e r a z s y t u a c j , k i e d y e l e m e n t x n i e n a l e |y o d p o w i e d n i o d o s u m y z b i o r ó w , i l o -
c z y n u z b i o r ó w o r a z r ó |n i c y z b i o r ó w . A z a t e m , j e [l i x " A *" B , t o z g o d n i e z d e f i n i c j s u m y
z b i o r ó w x " A i x " B . Z k o l e i j e [l i x " A )" B , t o x " A l u b x " B . N a t o m i a s t f a k t , |e
x " A \ B o z n a c z a n a m o c y d e f i n i c j i , |e x " A l u b x " B .
Z a t e m s y m b o l i c z n i e m o |e m y w y r a z i t e u w a g i p i s z c :
x " A *" B a" x " A '" x " B ,
x " A )" B a" x " A (" x " B ,
x " A \ B a" x " A (" x " B .
P r z e z f o r m u B r a c h u n k u z b i o r ó w r o z u m i e m y w y r a |e n i e u t w o r z o n e z s y m b o l i z b i o r ó w , s y m b o l i
o p e r a c j i n a z b i o r a c h i n a w i a s ó w . P o d o b n i e j a k w p r z y p a d k u f o r m u B r a c h u n k u z d a D t a u t o l o g i a m i
n a z y w a b d z i e m y t e s p o [r ó d f o r m u B r a c h u n k u z d a D, k t ó r e s p r a w d z i w e n i e z a l e |n i e o d d o b o r u
w y s t p u j c y c h w n i c h z b i o r ó w .
3 . Z B I O R Y I O P E R A C J E N A Z B I O R A C H 1 0
( 1 ) P r a w a p r z e m i e n n o [c i . J e [l i A i B s d o w o l n y m i z b i o r a m i t o
A *" B = B *" A ,
A )" B = B )" A .
D o w ó d . W y k a |e m y n a w s t p i e p r a w d z i w o [ p r z e m i e n n o [c i d l a s u m y . P r z y p u [m y , |e
x " B *" A . N a m o c y d e f i n i c j i w i e m y , |e x " A *" B Ð!Ò! x " A (" x " B . Z d r u g i e j s t r o n y n a
m o c y p r a w a p r z e m i e n n o [c i a l t e r n a t y w y :
p (" q a" q (" p ,
m a m y , |e x " A *" B Ð!Ò! x " A *" B Ð!Ò! x " A (" x " B Ð!Ò! x " A *" B Ð!Ò! x " B (" x "
A Ð!Ò! x " B *" A .
D o w ó d d r u g i e g o z p r a w p r z e b i e g a p o d o b n i e .
( 2 ) P r a w a Bc z n o [c i . J e [l i A , B , C s d o w o l n y m i z b i o r a m i , t o p r a w d z i w e s r ó w n o [c i :
A *" ( B *" C ) = ( A *" B ) *" C ,
A )" ( B )" C ) = ( A )" B ) )" C .
D l a d o w o d u t y c h p r a w w y s t a r c z y w y k o r z y s t a o d p o w i e d n i o p r a w o p r z e m i e n n o [c i d l a a l t e r -
n a t y w y i d l a k o n i u n k c j i .
( 3 ) P r a w a r o z d z i e l n o [c i . J e [l i A , B , C s d o w o l n y m i z b i o r a m i , t o p r a w d z i w e s r ó w n o [c i :
A )" ( B *" C ) = ( A )" B ) *" ( B )" C ) ,
A *" ( B )" C ) = ( A *" B ) )" ( A *" C ) .
W t y m p r z y p a d k u r ó w n i e | w y s t a r c z y w y k o r z y s t a p r a w a r a c h u n k u z d a D t j . p r a w a r o z d z i e l -
n o [c i k o n i u n k c j i w z g l d e m a l t e r n a t y w y i a l t e r n a t y w y w z g l d e m k o n i u n k c j i .
( 4 ) P r a w a t a u t o l o g i i . J e [l i A j e s t d o w o l n y m z b i o r e m , t o p r a w d z i w e s r ó w n o [c i :
A *" A = A ,
A )" A = A .
Aa t w o u d o w o d n i p r a w a r a c h u n k u z d a D:
p (" p a" p o r a z p '" p a" p ,
t o b e z o [r e d n i o z t y c h p r a w w y n i k a j p r a w a t a u t o l o g i i .
( 5 ) P r a w a d e M o r g a n a . J e [l i A , B , C s d o w o l n y m i z b i o r a m i , t o p r a w d z i w e s r ó w n o [c i :
A \ ( B )" C ) = ( A \ B ) *" ( A \ C ) ,
A \ ( B *" C ) = ( A \ B ) )" ( A \ C ) .
4 . I L O C Z Y N K A R T E Z J A CS K I Z B I O R Ó W I R E L A C J E 1 1
P r a w a d e M o r g a n a d l a z b i o r ó w s k o n s e k w e n c j p r a w d e M o r g a n a d l a z d a D.
B a r d z i e j z n a n a p o s t a p r a w d e M o r g a n a d o t y c z y d o p e Bn i e n i a z b i o r u . J e [l i X j e s t p r z e s t r z e -
n i z a [ A " P ( X ) i B " P ( X ) , t o p r z e z d o p e Bn i e n i e z b i o r u A d o p r z e s t r z e n i X r o z u m i e m y
z b i ó r A = X \ A p o d o b n i e B = X \ B . P r z y t a k i c h o z n a c z e n i a c h p r a w a d e M o r g a n a m o |e m y
z a p i s a w p o s t a c i
( A *" B ) = A )" B , ( A )" B ) = A *" B .
4 . I l o c z y n k a r t e z j a Ds k i z b i o r ó w i r e l a c j e
N i e c h A i B b d d o w o l n y m i z b i o r a m i i n i e c h x " A o r a z y " B . W y n i k a s t d , |e { x } ‚"A
o r a z { x , y } ‚"A *" B , a z a t e m
{ { x } , { x , y } } ‚" P ( P ( A *" B ) ) .
P r z y j m u j e m y u m o w n o t a c y j n , |e s y m b o l
x , y = { { x } , { x , y } }
o z n a c z a b d z i e p a r u p o r z d k o w a n o p o p r z e d n i k u x i n a s t p n i k u y . Z b i ó r
{ x , y | x " A '" y " B }
n a z y w a m y i l o c z y n i e m k a r t e z j a Ds k i m ( p r o d u k t e m k a r t e z j a Ds k i m ) z b i o r ó w A i B o r a z o z n a c z a m y
s y m b o l e m A × B .
N i e c h x , y o r a z z , t b d e l e m e n t a m i z b i o r u A × B . P a m i t a m y , |e x , y = { { x } , { x , y } }
o r a z z , t = { { z } , { z , t } } . S k o r o p a r y t e s z b i o r a m i t o z b a d a j m y k i e d y s o n e r ó w n e . P r z y -
p u [m y , |e s r ó w n e i z a s t o s u j m y d o n i c h d e f i n i c j r ó w n o [c i z b i o r ó w . W y n i k a s t d , |e
{ z } "{ x , y } o r a z { z , t } " x , y ,
a w k o n s e k w e n c j i , |e
( 1 ) { z } = { x } l u b { z } = { x , y } ( 2 )
o r a z
( 3 ) { z , t } = { x } l u b { z , t } = { x , y } ( 4 )
R ó w n o [ ( 1 ) m a m i e j s c e j e d y n i e w t e d y , g d y x = z = y . W t a k i m p r z y p a d k u r ó w n o [c i ( 3 )
o r a z ( 4 ) s r ó w n o w a |n e i m a m y z = t = x . M a m y w i c , |e z = t = x . P r o w a d z i t o d o w n i o s k u ,
|e x = y = z = t . J e [l i r o z p a t r z y m y p r z y p a d e k ( 3 ) , t o r ó w n o [ o k a z u j e s i t a k |e s p e Bn i o n a .
Z a j m i j m y s i t e r a z p r z y p a d k i e m ( 4 ) . W t e d y z = x o r a z : b d z z = y , b d z t = y . G d y z = y ,
t o z a c h o d z i r ó w n o [ ( 2 ) i o t r z y m u j e m y r o z p a t r y w a n y j u | p r z y p a d e k . G d y n a t o m i a s t t = y , t o
m a m y x = z i y = t . J e [l i r o z p a t r z y m y t e r a z i m p l i k a c j o d w r o t n d o d o w i e d z i o n e j t z n . j e [l i
p r z y p u [c i m y , |e x = z i y = t , t o t e z a j e s t o c z y w i s t a , n a m o c y d e f i n i c j i r ó w n o [c i z b i o r ó w .
O t r z y m a l i [m y z a t e m n a s t p u j c e t w i e r d z e n i e .
4 . I L O C Z Y N K A R T E Z J A CS K I Z B I O R Ó W I R E L A C J E 1 2
T w i e r d z e n i e . W a r u n k i e m k o n i e c z n y m i w y s t a r c z a j c y m n a t o , b y p a r y x , y i z , t b y By
r ó w n e j e s t , b y z a c h o d z i By r ó w n o [c i : x = z o r a z y = t .
P o j c i e i l o c z y n u k a r t e z j a Ds k i e g o m a Ba t w i n t e r p r e t a c j g e o m e t r y c z n . J e [l i A i B s d o w o l -
n i e u s t a l o n y m i z b i o r a m i , t o e l e m e n t y z b i o r u A × B n a z y w a m y n i e k i e d y p u n k t a m i , z a [ z b i o r y
A i B o s i a m i w s p ó Br z d n y c h . J e [l i t = x , y j e s t p u n k t e m w A × B , t o x n a z y w a m y o d c i t ,
z a [ y r z d n p u n k t u t . T a i n t u i c j a w y w o d z i s i z g e o m e t r i i p Ba s z c z y z n y , g d z i e z b i ó r p u n k -
t ó w p Ba s z c z y z n y m o |e b y u t o |s a m i a n y z i l o c z y n e m × , p r z y c z y m o z n a c z a z b i ó r l i c z b
r z e c z y w i s t y c h .
K o r z y s t a j c b e z p o [r e d n i o z d e f i n i c j i p r o d u k t u k a r t e z j a Ds k i e g o m o |e m y w y p r o w a d z i w i e l e
p r a w w i |c y c h t o d z i a Ba n i e z d z i a Ba n i a m i t e o r i i z b i o r ó w .
P r z y k Ba d . W y k a |e m y t o |s a m o [: ( A )" B ) × C = ( A × C ) )" ( B × C ) .
N i e c h ( x , y ) " ( A )" B ) × C . W t e d y
( x , y ) " ( A )" B ) × C Ð!Ò! ( x " A )" B ) '" ( y " C ) Ð!Ò! ( x " A '" x " B ) '" y " C Ð!Ò!
Ð!Ò! x " A '" ( y " C '" x " B ) Ð!Ò! ( x " A '" y " C ) '" ( x " B '" y " C ) Ð!Ò!
Ð!Ò! ( x , y ) " A × C '" ( x , y ) " B × C Ð!Ò! ( x , y ) " ( A × C ) )" ( B × C ) .
P o s Bu g u j c s i p o d o b n t e c h n i k d o w o d o w m o |e m y w y k a z a p r a w d z i w o [ f o r m u B, o k t ó r y c h
m ó w i n a s t p u j c e t w i e r d z e n i e .
T w i e r d z e n i e . J e [l i A 1 , A 2 o r a z B s d o w o l n y m i z b i o r a m i , t o
( A 1 *" A 2 ) × B = A 1 × B *" A 2 × B ,
( A 1 \ A 2 ) × B = A 1 × B \ A 2 × B ,
B × ( A 1 *" A 2 ) = B × A 1 *" B × A 2 ,
B × ( A 1 \ A 2 ) = B × A 1 \ B *" B × A 2 ,
D o w o l n y p o d z b i ó r i l o c z y n u k a r t e z j a Ds k i e g o z b i o r u A × B , t z n . d o w o l n y z b i ó r p a r u p o r z d -
k o w a n y c h o p o p r z e d n i k a c h z A i n a s t p n i k a c h z B n a z y w a m y r e l a c j ( d w u c z Bo n o w ) . J e [l i
p o d z b i ó r t a k i o z n a c z y m y p r z e z t o z a m i a s t p i s a a , b " p i s z e m y c z e s t o a b i m ó w i m y , |e
a j e s t w r e l a c j i z b .
D z i e d z i n r e l a c j i ( d z i e d z i n l e w o s t r o n n ) n a z y w a m y z b i ó r D z a w a r t y w A i z Bo |o n y z
p o p r z e d n i k ó w p a r n a l e |c y c h d o r e l a c j i . P r z e c i w d z i e d z i n ( d z i e d z i n p r a w o s t r o n n ) r e l a c j i n a -
z y w a m y p o d z b i ó r R z b i o r u B z Bo |o n y z n a s t p n i k ó w p a r n a l e |c y c h d o r e l a c j i . F o r m a l i z u j c
t e d e f i n i c j e m o |e m y z a p i s a :
D = { a " A | i s t n i e j e b " B , |e a b } o r a z R = { b " B | i s t n i e j e a " A , |e a b }
P r z e z p o l e r e l a j i r o z u m i e m y z b i ó r b d c y s u m d z i e d z i n y i p r z e c i w d z i e d z i n y ( o b u d z i e d z i n )
r e l a c j i .
N i e c h ‚" A × B . P r z e z w y k r e s r e l a c j i r o z u m i e m y z b i ó r
G r ( ) = { a , b "A × B | a b } .
4 . I L O C Z Y N K A R T E Z J A CS K I Z B I O R Ó W I R E L A C J E 1 3
T a k w i c w y k r e s r e l a c j i i r e l a c j a s p e Bn i a j t s a m d e f i n i c j , z a t e m j e s t t o t e n s a m o b i e k t .
R e l a c j a ‚" A × B w y z n a c z a n o w r e l a c j - 1 ‚" B × A w n a s t p u j c y s p o s ó b :
d e f
( b , a ) " - 1 Ð!Ò! ( a , b ) " .
R e l a c j - 1 n a z y w a m y r e l a c j o d w r o t n d o r e l a c j i .
W t a k i m p r z y p a d k u m a m y , |e D - 1 = R o r a z R - 1 = D .
N i e c h ‚" A × B o r a z µ ‚" B × C , b d t a k i e , |e D ‚"R µ . R e l a c j · ‚" A × C t a k , |e
x , z "· Ð!Ò! i s t n i e j e y " B , |e x y '" y z .
n a z y w a m y z Bo |e n i e m ( s u p e r p o z y c j ) r e l a c j i o r a z µ i o z n a c z a m y p i s z c · = µ æ% .
P r z y k Ba d . W e zm y p o d u w a g r e l a c j e :
‚"{ a , b , c } × { ±, ³} i µ ‚"{ ±, ², ³} × { - 2 , 0 , 1 , 5 , 8 }
g d z i e = a , ± , b , ± , c , ³ } o r a z µ = { ±, - 2 , ±, 0 , ², 1 , ³, 5 , ´, 8 } . Z Bo |e n i e m
t y c h r e l a c j i j e s t r e l a c j a · ‚"{ a , b , c } × { - 2 , 0 , 1 , 5 , 8 } t a k a , |e
· = µ æ% = { a , - 2 , a , 0 , b , - 2 , b , 0 , c , 5 } .
P r z y k Ba d . D a n a j e s t r e l a c j a Ç †"{ 0 , 1 , 2 , 3 , . . . , 9 } × { 0 , 1 , 2 , 3 , . . . , 9 } z d e f i n i o w a n a w a r u n -
k i e m :
a Çb Ô! 3 a = b (" 3 a + 1 = b .
W y z n a c z y m y r e l a c j Ç- 1 . Z a n i m p r z e j d z i e m y d o w y z n a c z e n i a r e l a c j i Ç- 1 n a w s t p i e w y p i s z m y
p r e c y z y j n i e p a r y n a l e |c e d o r e l a c j i Ç. M a m y :
Ç = { 0 , 0 , 0 , 1 , 1 , 3 , 1 , 4 , 2 , 6 , 2 , 7 , 3 , 9 } .
B e z p o [r e d n i o z d e f i n i c j i r e l a c j i o d w r o t n e j d o s t a j e m y , |e
Ç- 1 = { 0 , 0 , 1 , 0 , 3 , 1 , 4 , 1 , 6 , 2 , 7 , 2 , 9 , 3 } .
T w i e r d z e n i e . J e [l i †" A × B , µ †" B × C i ½ †" C × D , t o :
½ æ% ( µ æ% ) = ( ½ æ% µ ) æ% ;
( µ æ% ) - 1 = µ - 1 æ% - 1 .
D o w ó d . W y k a |e m y p r a w d z i w o [ ( i ) . P r z y p u [m y , |e x , z "A × D . M a j m i e j s c e n a s t p u j c e
f a k t y :
x , z " æ% ( µ æ% ½) w t t , g d y i s t n i e j t " C , |e x , t "µ æ% ½ o r a z t , z " w t t , g d y
i s t n i e j t " C i y " B , |e x , y " o r a z y , t "µ o r a z t , z "½ w t t , g d y
i s t n i e j e y " B , |e a , b o r a z y , z "½ æ% µ w t t , g d y x , t "( ½ æ% µ ) æ% .
R o z p a t r z m y t e r a z p r z y p a d e k ( i i ) . N i e c h t , x "C × A . W t e d y :
4 . I L O C Z Y N K A R T E Z J A CS K I Z B I O R Ó W I R E L A C J E 1 4
t , x "( µ æ% ) - 1 w t t , g d y x , t "µ æ% w t t , g d y
i s t n i e j e y " B , |e x , y " o r a z y , t "µ w t t , g d y
i s t n i e j e y " B , |e y , x " - 1 o r a z t , y "µ - 1 w t t , g d y t , x " - 1 æ% µ - 1
P r z e d s t a w i m y t e r a z k i l k a p r z y k Ba d ó w r e l a c j i .
P r z y k Ba d .
N i e c h A = B = A b d z i e z b i o r e m w s z y s t k i c h l u d z i |y j c y c h n a Z i e m i ( w d o w o l n y m o k r e s i e
j e j i s t n i e n i a ) . R e l a c j b y c i a p r z o d k i e m r o z u m i e m y w t e d y j a k o z b i ó r p a r a , b t a k i c h ,
|e o s o b a a j e s t p r z o d k i e m o s o b y b b e z w z g l d u n a c z a s d z i e l c y i c h d a t y u r o d z e n i a .
N i e c h X = Y = . R o z w a |m y n i e r ó w n o [ y > x + 1 . O z n a c z m y p r z e z z b i ó r p a r x , y ,
k t ó r e s p e Bn i a j n a s z n i e r ó w n o [. S t d p i s z e m y :
x , y " Ð!Ò! y > x + 1 .
N i e c h n i e p u s t y z b i ó r X b d z i e p r z e s t r z e n i , z a [ P ( X ) z b i o r e m p o t g o w y m X . Z g o d n i e z
w p r o w a d z o n p o p r z e d n i o d e f i n i c j i n k l u z j i i d e f i n i c j r e l a c j i w i e m y , |e m i d z y z b i o r a m i
A " P ( X ) o r a z B " P ( X ) z a c h o d z i i n k l u z j a t y l k o w p e w n y c h p r z y p a d k a c h . Z a t e m
i n k l u z j a j e s t w Ba s n o [c i p a r u p o r z d k o w a n y c h A , B z b i o r ó w e l e m e n t ó w P ( X ) . J e s t
w i c i n k l u z j a ‚" p o d z b i o r e m p r o d u k t u P ( X ) × P ( X ) , a w i c r e l a c j .
D o t y c h c z a s r o z w a |a l i [m y p r z y p a d k i , g d y p r o d u k t k a r t e z j a Ds k i t w o r z o n y b y B z d w ó c h z b i o r ó w ,
a c o z a t y m i d z i e r e l a c j e o d n o s i By s i d o p a r e l e m e n t ó w . W p r z y p a d k u o g ó l n y m r e l a c j a m i
d w u c z Bo n o w y m i w p r o d u k c i e X × Y , g d z i e X i Y s d o w o l n y m i z b i o r a m i , n a z y w a m y p o d z b i o r y
t e g o p r o d u k t u . J e [l i j e s t p o d z b i o r e m p r o d u k t u X × X , t o m i a s t m ó w i , |e j e s t r e l a c j
d w u c z Bo n o w w w p r o d u k c i e X × X , c z s t o m ó w i m y , |e j e s t r e l a c j d w u c z Bo n o w w X . W
z b i o r z e w s z y s t k i c h r e l a c j i d w u c z Bo n o w y c h m o |e m y w y r ó |n i p e w n e i c h k l a s y . P r z e d s t a w i m y j e
w n a s t p u j c e j d e f i n i c j i .
R e l a c j d w u c z Bo n o w ‚" X × X n a z y w a m y :
d e f
z w r o t n Ð!Ò! d l a k a |d e g o x " X j e s t x x ;
d e f
p r z e c i w z w r o t n Ð!Ò! d l a k a |d e g o x " X j e s t <" ( x x ) ;
d e f
s y m e t r y c z n Ð!Ò! d l a k a |d e g o x " X o r a z y " X j e s t x y = Ò! y x ;
d e f
p r z e c i w s y m e t r y c z n Ð!Ò! d l a k a |d e g o x " X o r a z y " X j e s t :
x y = Ò!<" ( y x ) ;
d e f
a n t y s y m e t r y c z n Ð!Ò! d l a k a |d e g o x " X o r a z y " X j e s t :
( x y ) '" ( y x ) = Ò! ( x = y ) ;
d e f
p r z e c h o d n i Ð!Ò! d l a k a |d y c h x " X i y " X i k a |d e g o z " X j e s t :
( x y ) '" ( y z ) Ò! ( x z ) ;
5 . L I C Z B Y N A T U R A L N E 1 5
d e f
s p ó j n Ð!Ò! d l a k a |d e g o x " X i k a |d e g o y " X j e s t :
{ ( x = y ) = Ò! [ ( x y ) (" ( y x ) ] } .
P r z y k Ba d . P o s z c z e g ó l n e r o d z a j e r e l a c j i z i l u s t r u j e m y p r z y k Ba d a m i
R e l a c j a p r z y s t a w a n i a t r ó j k t ó w j e s t r e l a c j z w r o t n w z b i o r z e w s z y s t k i c h t r ó j k t ó w .
R e l a c j a w i k s z o [c i l i c z b w z b i o r z e l i c z b r z e c z y w i s t y c h j e s t p r z e c i w z w r o t n a .
P r z y k Ba d e m r e l a c j i s y m e t r y c z n e j j e s t r e l a c j a p o d z i e l n o [c i w z b i o r z e l i c z b c a Bk o w i t y c h , b o
k a |d a l i c z b a c a Bk o w i t a j e s t p o d z i e l n a p r z e z s a m s i e b i e .
P r z y k Ba d e m r e l a c j i p r z e c i w s y m e t r y c z n e j j e s t r e l a c j a w i k s z o [c i w z b i o r z e l i c z b r z e c z y w i s -
t y c h .
R e l a c j a n i e w i k s z o [c i w z b i o r z e l i c z b r z e c z y w i s t y c h j e s t p r z y k Ba d e m r e l a c j i a n t y s y m e t -
r y c z n e j .
R ó w n o l e g Bo [ p r o s t y c h n a p Ba s z c z y zn i e j e s t r e l a c j p r z e c h o d n i .
N i e c h X b d z i e z b i o r e m l i t e r a l f a b e t u Ba c i Ds k i g o . P r z y j t a u m o w a c o d o k o l e j n o [c i l i t e r w
n i m z a w a r t y c h p o z w a l a u s t a l i r e l a c j h i e r a r c h i w y r a z ó w ( h a s e B) w s k o r o w i d z a c h n a z w
c z y h a s e B. T a k o k r e [l o n a r e l a c j a j e s t r e l a c j s p ó j n . P o d o b n i e r e l a c j a n i e w i k s z o [c i ( )
j e s t r e l a c j s p ó j n .
2
W z b i o r z e p a r l i c z b r z e c z y w i s t y c h m o |e m y o k r e [l i r e l a c j t a k , |e
d e f
x 1 , y 1 x 2 , y 2 Ð!Ò! x 1 x 2 '" y 1 y 2 .
R e l a c j a t a j e s t j a k z a u w a |a m y ; z w r o t n a , a n t y s y m e t r y c z n a i p r z e c h o d n i a . N i e j e s t n a t o -
m i a s t s p ó j n a . J a k s i n i e b a w e m o k a |e , r e l a c j a j e s t w y g o d n y m p r z y k Ba d e m s Bu |c y m
i l u s t r o w a n i u i n n y c h w Ba s n o [c i s z c z e g ó Bo w y c h o d n o s z c y c h s i d o r e l a c j i b i n a r n y c h .
5 . L i c z b y n a t u r a l n e
N i e c h A b d z i e r o d z i n z b i o r ó w . R o d z i n t n a z y w a m y i n d u k t y w n w t t , g d y :
1 . " "A ;
2 . d l a k a |d e g o X "A , z b i ó r X *"{ X } "A .
5 . L I C Z B Y N A T U R A L N E 1 6
O p e r a c j n a s t p n i k a n a z y w a m y o p e r a c j , k t ó r a k a |d e m u z b i o r o w i X p r z y p o r z d k o w u j e z b i ó r
X *"{ X } . N a s t p n i k z b i o r u X o z n a c z a m y p r z e z X . W a k s j o m a t y c e Z e r m e l o - F r a e n k l a i s t n i e n i e
z b i o r ó w i n d u k t y w n y c h g w a r a n t u j e a k s j o m a t n i e s k o Dc z o n o [c i . M ó w i c k r ó t k o w y r a |a o n i s t n i e -
n i e z b i o r ó w n i e s k o Dc z o n y c h .
T w i e r d z e n i e . I s t n i e j e n a j m n i e j s z y z b i ó r i n d u k t y w n y t j . t a k i z b i ó r i n d u k t y w n y A , |e d l a
d o w o l n e g o z b i o r u i n d u k t y w n e g o B j e s t A †"B .
D o w ó d . P r z y p u [m y , |e A j e s t z b i o r e m i n d u k t y w n y m . R o z p a t r z m y r o d z i n z b i o r ó w ” t a k ,
|e
”= { B †" A | B j e s t z b i o r e m i n d u k t y w n y m } .
W y n i k a s t d , |e r ó w n i e | z b i ó r A 0 = ” j e s t z b i o r e m i n d u k t y w n y m . P o z o s t a j e w y k a z a , |e A
j e s t n a j m n i e j s z y m z b i o r e m i n d u k t y w n y m . J e [l i B j e s t z b i o r e m i n d u k t y w n y m , t o B )"A "”. Z
k o l e i z d e f i n i c j i i l o c z y n u z b i o r ó w w y n i k a , |e
A 0 †"B )"A .
Z d r u g i e j s t r o n y s k o r o B )" A †" B , t o A 0 †" B . Z t e g o , |e o s t a t n i a i n k l u z j a z a c h o d z i d l a
w s z y s t k i c h e l e m e n t ó w r o d z i n y ”, t o A 0 j e s t n a j m n i e j s z y m z b i o r e m i n d u k t y w n y m , w s e n s i e
r e l a c j i z a w i e r a n i a .
P r z e z z b i ó r l i c z b n a t u r a l n y c h r o z u m i e m y n a j m n i e j s z y z b i ó r i n d u k t y w n y i o z n a c z a m y g o
p r z e z . Z d e f i n i c j i z b i o r u i n d u k t y w n e g o ( w a r u n e k 1 . ) , z a w i e r a o n z b i ó r p u s t y ", k t ó r y r e p r e -
z e n t u j e l i c z b 0 . Z d r u g i e j s t r o n y ( w a r u n e k 2 . ) , z a w i e r a n a s t p n i k 0 ( o z n a c z a n y s y m b o l e m
1 ) , a t a k |e n a s t p n i k n a s t p n i k a 0 ( o z n a c z a n y s y m b o l e m 2 ) , i t d .
T w i e r d z e n i e . ( Z a s a d a i n d u k c j i ) J e [l i M ‚" j e s t z b i o r e m l i c z b n a t u r a l n y c h s p e Bn i a j c y m
w a r u n k i :
0 "M ,
d l a d o w o l n i e w y b r a n e j l i c z b y n t a k i e j , |e n "M , z a c h o d z i n "M ,
t o M z a w i e r a w s z y s t k i e l i c z b y n a t u r a l n e t j . M = .
D o w ó d . T e z a t w i e r d z e n i a j e s t k o n s e k w e n c j b y c i a p r z e z n a j m n i e j s z y m z b i o r e m i n d u k t y w -
n y m .
M a By m i l i t e r a m i a l f a b e t u b d z i e m y o z n a c z a e l e m e n t y z b i o r u .
T w i e r d z e n i e . D l a d o w o l n y c h m " o r a z n " :
1 . j e [l i m " n , t o m †" n ;
2 . n " n ;
3 . j e [l i m = n , t o m = n ;
4 . j e [l i m †" n o r a z m = n , t o m " n ;
5 . L I C Z B Y N A T U R A L N E 1 7
5 . z a c h o d z i : m †" n l u b n †" m ;
6 . z a c h o d z i d o k Ba d n i e j e d n a z m o |l i w o [c i : m " n , m = n , n " m .
D o w ó d . D o w ó d p o p r o w a d z i m y p r z e z i n d u k c j .
A d 1 . N i e c h M = { n " | d l a k a |d e g o m " n j e s t m †" n } . C h c e m y w y k a z a i n d u k t y w n o [
z b i o r u M . M a m y : 0 " M . P r z y p u [m y , |e n " M . P o t o b y w y k a z a , |e n " M o b i e r z m y
d o w o l n e m " n . P o n i e w a | n = n *"{ n } , t o m a m y m o |l i w e d w a p r z y p a d k i . J e [l i m " n , t o z
z a Bo |e n i a i n d u k c y j n e g o m a m y m †" n , a w i c m †" n . J e |e l i z a [ m = n , t o m †" n . W y n i k a
s t d , |e w k a |d y m z t y c h p r z y p a d k ó w m †" n , c o w k o n s e k w e n c j i d o w o d z i , |e n "M .
A d 2 . R o z p a t r z m y z b i ó r M = { n " | n " n } . W t a k i m p r z y p a d k u 0 "M . P r z y p u [m y , |e
n "M i z a Bó |m y , |e
n " n *"{ n } .
W t e d y a l b o n " n a l b o n = n . J e [l i n " n , t o k o r z y s t a j c z w a r u n k u 1 . m a m y n *"{ n } †"n ,
c o o z n a c z a , |e n " n c o p r z e c z y z a Bo |e n i u i n d u k c y j n e m u . J e [l i z a [ n = n , t o o t r z y m u j e m y
s p r z e c z n o [ z z a Bo |e n i e m i n d u k c y j n y m . Z a t e m p r z y p u s z c z e n i e , |e n " n *"{ n } j e s t b Bd n e .
D o w o d z i t o , |e n "M .
A d 3 . T e r a z z a Bó |m y , |e m *"{ m } = n *"{ n } . W y n i k a s t d , |e m m u s i n a l e |e d o z b i o r u p o
p r a w e j s t r o n i e z n a k u r ó w n o [c i . J e [l i m " n , t o n a m o c y ( i ) m a m y , |e m †" n . G d y z a [ m = n ,
t o t a k |e m †" n . Z s y m e t r i i z a Bo |e D w y n i k a r ó w n i e | n †" m , c o p r o w a d z i d o r ó w n o [c i m = n .
A d 4 . N i e c h t e r a z M = { n " | d l a k a |d e g o m †" n , j e [l i m = n , t o m " n } . N a p e w n o
0 "M b o z b i ó r p u s t y n i e z a w i e r a p o d z b i o r ó w w Ba [c i w y c h . P r z y p u [m y , |e n "M i n i e c h
m †" n . ( ")
Z a Bó |m y , |e m j e s t p o d z b i o r e m w Ba [c i w y m z b i o r u n . P o k a |e m y , |e m " n . J e [l i n " m , t o n a
p o d s t a w i e 1 . j e s t n †" m , z a t e m n †" m i z z a Bo |e n i a : m †" n , o t r z y m u j e m y r ó w n o [ n = m
a w i c s p r z e c z n o [. M a m y z a t e m n " m . Z z a Bo |e n i a ( ") o t r z y m u j e m y
m †" n .
J e [l m = n , t o m " n . N i e c h z a t e m m = n . P o n i e w a | m j e s t p o d z b i o r e m w Ba [c i w y m n , t o z
z a Bo |e n i a i n d u k c y j n e g o o t r z y m u j e m y , |e m " n , c o d a j e m " n . T o z a [ o z n a c z a k o n i e c d o w o d u
p o d p u n k t u 4 . t w i e r d z e n i a .
A d . 5 . T e r a z r o z p a t r z m y z b i ó r M = { n " | d l a k a |d e g o m " , j e [l i n †" m , t o m †" n } .
D l a w y k a z a n i a i n d u k t y w n o [c i z b i o r u M z a u w a |m y , |e 0 " M o r a z z a Bó |m y , |e n " M .
O b i e r z m y d o w o l n y m t a k i , |e
n †" m ( e&)
Z z a Bo |e n i a i n d u k c y j n e g o m a m y , |e m †" n l u b t e | n †" m . G d y m †" n , t o m †" n c o k o Dc z y
p r o c e s d o w o d o w y . P r z y p u [m y z a t e m , |e n m . N a p o d s t a w i e 4 . m a m y , |e n " m . W y n i k a
s t d , |e n †" m , c o p r z e c z y ( e&) . D o w o d z i t o , |e z a Bo |o n y p r z y p a d e k n i e m o |e z a j [. S t d
n "M .
6 . F U N K C J E 1 8
A d . 6 . T e n p o d p u n k t j e s t k o n s e k w e n c j w c z e [n i e j s z y c h p o d p u n k t ó w . J e d e n z w a r u n k ó w w y n i k a
z 4 . i 5 . , p o d c z a s g d y n i e m o |l i w o [ z a j [c i a d w ó c h s p o [r ó d w y m i e n i o n y c h p r z y p a d k ó w w y n i k a z
2 . o r a z 1 .
W z b i o r z e l i c z b n a t u r a l n y c h r e l a c j a z a w i e r a n i a †" o z n a c z a n a j e s t s y m b o l e m , p o d c z a s , g d y
r e l a c j a p r z y n a l e |n o [c i " o z n a c z a n a j e s t s y m b o l e m <