Zagadnienia i ich opracowanie na egzamin z
LOG110
"Wstęp do logiki i teorii mnogości"
1.Definicja i przykłady tautologii KRZ.
Def. Tautologią KRZ nazywamy formułę KRZ, która ma wartość logiczną 1 przy każdym wartościowaniu.
Przykłady:
Prawo sprzeczności Źśą p'"Ź pźą
Prawo wyłączonego p("Ź p
środka
Prawo podwójnej negacji p Ô!ŹŹ p
Prawo transpozycji
śą pÒ! qźąÔ!śąŹqÒ! Ź pźą
Prawa idempotentnoÅ›ci p'" pÔ! p
p(" pÔ! p
Prawa przemiennoÅ›ci p'"q Ô! q'" p
p("q Ô! q(" p
śą p Ô! qźąÔ!śąq Ô! pźą
Prawa łączności(podobnie
p'"śąq'"rźąÔ!śą p'"qźą'"r
dla alternatywy oraz
równoważności
Prawa rozdzielnoÅ›ci p'"śąq("rźąÔ!śą p'"qźą("śą p'"rźą
p("śąq'"rźąÔ!śą p("qźą'"śą p("rźą
Prawa de'Morgana Źśą p'"q źąÔ!Ź p("Źq
Źśą p("q źąÔ!Ź p'"Źq
Prawo odrywania p'"śą p Ò! qźąÒ! q
Prawo odrzucania śą pÒ! qźą'"Źq Ò!Ź p
Prawa sylogizmu śą p Ò! qźąÒ![śąqÒ! rźąÒ!śą p Ò! rźą]
śą qÒ! rźąÒ![śą p Ò! rźąÒ!śą p Ò!r źą]
śą p Ò!q źą'"śą qÒ! rźąÒ! śą p Ò! rźą
Prawa osÅ‚abiania p'"qÒ! p
p'"qÒ! q
pÒ! p("q
q Ò! p("q
Prawa definiowania śą pÒ! qźąÔ! Źp("q
śą p Ô!q źąÔ!śą p Ò! qźą'"śąq Ò! pźą
śą p Ô! qźąÔ!śą p'"q źą("śąŹ p'"Źq źą
p'"q Ô!Źśą pÒ!Źqźą
Definicje równoważności formuł i stosunku wynikania w KRZ.
Def. Formuła A jest logicznie równoważna formule B w KRZ, jeśli dla każdego wartościowania w
zachodzi w śą Aźą=wśą Bźą
A1,‹Ä…, An
Def. Mówimy, że formuła A wynika logicznie z formuł w KRZ, jeżeli nie istnieje wartościo-
w śą A1źą=‹Ä…=wśą Anźą=1
wanie w takie, że , natomiast w śą Aźą=0
Wynikanie a tautologie.
A1,‹Ä…, An
Tw. Jeśli A wynika logicznie z A1 ,... , An w KRZ oraz są tautologiami KRZ, to A też
jest tautologiÄ… KRZ.
Semantyczne twierdzenie o podstawianiu dla KRZ.
Lemat (o podstawianiu w KRZ). Dla dowolnych A , B"FOR , p "V oraz wartościowania w :
w śą A[ p/ B]źą=w[ p/w śąBźą]śą Aźą
Tw. Dla wszystkich A , B"FOR , p"V , jeśli A jest tautologią KRZ, to A[ p/ B] też jest tautolo-
giÄ… KRZ.
Aksjomatyczny system KRZ.
Aksjomaty systemu KRZ:
A1 Prawo poprzednika
A Ò!śą BÒ! Aźą
A2 Prawo Frege'go
[ AÒ!śą B Ò!C źą]Ò![śą AÒ! BźąÒ!śą AÒ!C źą]
A3 Odwrotne prawo
śąŹB Ò!ŹAźąÒ!śą AÒ! Bźą
transpozycji
A4 Prawo symplifikacji A'" BÒ! A
A5 j.w. A'" BÒ! B
A6 Prawo mnożenia
śą AÒ! BźąÒ![śą AÒ! Cźą Ò!śą AÒ! B'"C źą]
następników
A7 Prawo addycji A Ò! A("B
A8 j.w. B Ò! A("B
A9 Prawo dodawania
śą AÒ! C źąÒ![śą B Ò!C źąÒ!śą A("B Ò!C źą]
poprzedników
A10
śą AÔ! BźąÒ!śą AÒ! Bźą
A11
śą AÔ! BźąÒ!śą B Ò! Aźą
A12
śą AÒ! BźąÒ![śą B Ò! AźąÒ!śą A Ô! Bźą]
Jedyna reguła dowodowa  modus ponens
A
A Ò! B
B
Def. Dowodem formuÅ‚y A w systemie KRZ ze zbioru zaÅ‚ożeÅ„ X ‚"FOR nazywamy ciÄ…g formuÅ‚
A1,‹Ä…, An Ana"A
, ne"1 , taki że oraz dla każdego i=1, ‹Ä…, n zachodzi(przynajmniej) jeden z wa-
runków:
Ai
a) jest aksjomatem systemu,
Ai" X
b) ,
c) istnieją 0"ą j , k"ąi , takie że
A a"AkÒ! Ai
j
Ai A Ak
tzn. jest wnioskiem z i w oparciu o regułę MP.
j
Mówimy, że formuła A jest kosekwencją zbioru X w systemie KRZ, jeżeli istnieje dowód A w KRZ
ze zbioru X ; piszemy wówczas:
X ó" A
KRZ
CnKRZśą X źą={A"FOR : X ó" A}
Oznaczamy .
KRZ
Formułę A nazywamy tezą systemu KRZ, jeżeli:
"ó" A
KRZ
ó" A
piszemy wtedy
KRZ
Definicje termów i formuł języka elementarnego.
i. Każda zmienna indywiduowa i stała indywiduowa jest termem
n
·Ä…1 ,‹Ä… ,·Ä…n
ii. JeÅ›li sÄ… termami, to F śą·Ä…1 ,‹Ä… , ·Ä…nźą jest termem (dla dowolnych n i k)
k
iii. Nie ma innych termów poza zmiennymi indywiduowymi, stałymi indywiduowymi i takimi, które po-
wstają na mocy reguły (ii)
·Ä…1 ,‹Ä… ,·Ä…n
FormuÅ‚Ä… zdaniowÄ… atomowÄ… jest każde wyrażenie postaci Pn śą·Ä…1 ,‹Ä…, ·Ä…nźą , gdzie sÄ… dowolnymi
k
termami
i. Każda formuła zdaniowa atomowa jest formułą zdaniową rachunku predykatów.
ii. JeÅ›li ËÄ… , ÍÄ… sÄ… formuÅ‚ami zdaniowymi jÄ™zyka rachunku predykatów to ŹśąËąźą , śąËąźą'"śąÍąźą ,
" xi śąËąźą " x śąËąźą
śąËąźą("śąÍąźą , śąËąźąÔ!śąÍąźą , śąËąźąÒ!śąÍąźą , i sÄ… formuÅ‚ami zdaniowymi jÄ™zyka ra-
j
chunku predykatów
iii. Nie ma innych formuł zdaniowych języka rachunku predykatów poza formułami atomowymi i takimi
formułami, które powstają dzięki zastosowaniu reguły (ii)
Definicja podstawiania w języku elementarnym.
¸Ä…"TERL A"FORL
Niech ·Ä… , , x"Var , .
Definiujemy ·Ä…[ x /¸Ä…] A[ x/ ¸Ä…]  wynik podstawienia termu ¸Ä… do, odpowiednio, termu ·Ä… i for-
,
muły A .
¸Ä… x= y
y[ x/¸Ä…]a"
a)
{
y x`" y
c"ConL
b) c [ x /¸Ä…]a"c dla
f śą·Ä…1 , ‹Ä…,·Ä…nźą[ x/¸Ä…]a" f śą·Ä…1[ x/¸Ä…],‹Ä… ,·Ä…n [ x/¸Ä…]źą
c)
Rśą·Ä…1 ,‹Ä…, ·Ä…nźą[ x/¸Ä…]a"Rśą·Ä…1[ x/¸Ä…] ,‹Ä…, ·Ä…n[ x/¸Ä…]źą
d)
e) śąŹAźą[ x/¸Ä…]a"Źśą A[ x/¸Ä…]źą
f) Dla @"{'",(",Ò! ,Ô! }:
śą A @ Bźą[ x/ ¸Ä…]a"śą A[ x/¸Ä…]źą@śą B[ x/¸Ä…]źą
g) Dla Q"{" , "} :
śąQy źą A : x= y
śąśąQyźą Aźą[ x/¸Ä…]a"
{
śąQyźąśą A[ x /¸Ä…]źą : x`" y
·Ä…[ x1/¸Ä…1 ,‹Ä… , xn /¸Ä…n]a"·Ä… [ x1/ y1]‹Ä…[ xn/ yn][ y1/¸Ä…1]‹Ä…[ yn/¸Ä…n] y1 ,‹Ä… , yn
, gdzie są zmiennymi nie występują-
A , ¸Ä…1 ,‹Ä…, ¸Ä…n x1 , ‹Ä… , xn
cymi w oraz wśród
Definicja i przykłady podstawialności.
Term ¸Ä… jest podstawialny za zmiennÄ… x do formuÅ‚y A (Podstawienie [ x/¸Ä…] jest dopuszczalne dla
formuły A ), jeśli żadne wolne wystąpienie zmiennej x w A nie znajduje się w zasięgu kwantyfika-
tora wiążącego którÄ…kolwiek ze zmiennych wystÄ™pujÄ…cych w ¸Ä…
Aksjomatyczny system FOL.
L  ustalony język
Aksjomaty logiczne:
- prawa podstawiania:
(L1) " x AÒ! A[ x/t]
(L1') A[ x/t ]Ò! " x A
dla wszystkich formuł A , termów t i zmiennych x , pod warunkiem, że term t jest podstawialny
za x w A
- prawa dołączania kwantyfikatorów:
(L2) " xśąAÒ! BźąÒ!śą A Ò!" x Bźą - dla wszelkich formuÅ‚ A , B i zmiennej x pod warunkiem, że x
nie jest wolne w A
(L2') " xśą AÒ! BźąÒ!śą" x AÒ! Bźą - dla wszelkich formuÅ‚ A , B i zmiennych x takich, że nie jest wolne
w B
- prawa KRZ:
(L3) wszystkie formuły języka L powstające z tautologii KRZ prezz podstawienie formuł języka L za
zmienne zdaniowe
Reguły dowodzenia:
- reguła odrywania (Modus Ponens = MP)
A Ò! B
A
B
- reguła generalizacji (GEN)
A
" x A
dla wszelkich formuł A , B i zmiennych x
Definicja dowodu, stosunku konsekwencji i tezy dla systemu FOL.
X ‚"FORL
Def. Dowodem formuły A w systemie KRL, ze zbioru założeń nazywamy ciąg formuł
A1 ,‹Ä…, An , ne"1 Aa" An
, taki że oraz dla każdego i=1, ‹Ä…, n zachodzi przynajmniej jeden z warun-
ków:
Ai
a) jest aksjomatem systemu KRL
Ai" X
b)
A a"AkÒ! Ai
c)isteniją ją0 , k"ą1 , takie że
j
Aia"śą" xźą A
d)istnieje j"ąi oraz x"Var , takie że
j
X ó" A
Mówimy, że formuła A jest konsekwencją zbioru X w systemie KRL(symbolicznie ), jeśli
KRL
istnieje dowód formuły A w systemie KRL, ze zbioru X .
CnKRLśą X źą
Symbolem oznaczać będziemy zbiór wszystkich konsekwencji zbioru X w systemie KRL
Prawa rozdzielności kwantyfikatorów (pełne i niepełne).
Prawo rozdzielnoÅ›ci dużego " x[Ëąśą xźą'"Íąśą xźą]Ô! " xËąśąxźą'"" x Íąśą xźą
kwantyfikatora względem koniunkcji
Prawo rozdzielnoÅ›ci maÅ‚ego " x[Ëąśąxźą("Íąśąxźą]Ô!" x Ëąśą xźą("" xÍąśą xźą
kwantyfikatora względem
alternatywy
Prawo rozdzielnoÅ›ci dużego " x Ëąśąxźą("" x Íąśą xźąÒ! " x [Ëąśą xźą("Íąśą xźą]
kwantyfikatora względem
alternatywy
UWAGA: Kwantyfikator duży nie
jest w tym przypadku
rozdzielny!
Prawo rozdzielności małego
" x[Ëąśąxźą'"Íąśąxźą]Ò!" xËąśą xźą'"" xÍąśą x źą
kwantyfikatora względem koniunkcji
UWAGA: Kwantyfikator duży nie
jest w tym przypadku
rozdzielny!
Prawo rozdzielnoÅ›ci dużego " x[Ëąśą xźąÒ!Íąśą xźą]Ò![" xËąśą xźąÒ!" xÍąśą xźą]
kwantyfikatora względem implikacji
Prawo rozdzielnoÅ›ci maÅ‚ego " x [Ëąśą x źąÒ!Íąśą x źą]Ò![" xËąśąxźąÒ!" x Íąśąxźą]
kwantyfikatora względem implikacji
(Brak nazwy) " x [Ëąśą x źąÔ!Íąśą xźą]Śą[" x ËąśąxźąÔ! " x Íąśą xźą]
(Brak nazwy) " x[Ëąśą xźąÔ!Íąśą xźą]Śą[" xËąśą xźą" xÍąśą xźą]
Prawa De Morgana i prawa ekstensjonalności dla kwantyfikatorów.
Prawa De Morgana
Ź" x Ëąśą xźąÔ!" xŹËąśąxźą
Ź" x Ëąśą x źąÔ! " xŹËąśąxźą
Prawa ekstensjonalności dla kwantyfikatorów
" x śąAÔ! BźąÒ![" xśą AźąÔ! " x śą Bźą]
" x śąAÔ! BźąÒ![" x śą AźąÔ!" xśąBźą]
Prawa zamiany zmiennych związanych i prawa wyłączania kwantyfikatorów przed nawias.
Prawa zamiany zmiennych zwiÄ…zanych:
(T8) " x AÔ!" y A[ x/ y]
(T8') " x AÔ!" y A[ x / y]
pod warunkiem, że:
1.'y' nie jest wolne w A.
2.'y' jest podstawialne za 'x' w A
UWAGA: W praktyce za 'y' przyjmiemy zmienną nie występującą w " x A (lub " x A ) tzw. mową
zmiennÄ….
Prawa wyłączenia kwantyfikatorów przed nawias:
(T8) Zakładamy, że 'x' nie jest wolne w B:
" x A'"BÔ! " x śą A'"Bźą
" x A("BÔ! " x śą A("Bźą
" x A'"B Ô!"śą A'"Bźą
" x A("B Ô!" xśą A("Bźą
Twierdzenie o dedukcji dla systemu FOL.
X ‚"FORL , A , B"FORL
Niech .
X ó" A Śą B X , Aó" B
a) Jeżeli , to ,
KRL KRL
X , Aó" B , X ó" A Śą B
b) Jeśli dodatkowo A jest zdaniem, to jeżeli to
KRL KRL
Twierdzenie o równoważności dla systemu FOL.
Tw.
Niech formuła C[A/B] powstaje z formuły C przez zastąpienie pewnej liczby wystąpień podformuły A formułą
B. Wtedy:
A Ô! B ó" C Ô! C [ A/ B]
KRL
Aksjomat ekstensjonalności i jego zastosowanie w dowodach praw algebry zbiorów.
Dwa zbiory są równe wtedy i tylko wtedy kiedy posiadają te same elementy
symbolicznie: A= BÔ!śą " xźąśą x" AÔ! x"Bźą
Działania boolowskie na zbiorach i ważniejsze prawa algebry zbiorów.
Aksjomaty algebry Bool'a(inaczej Działania boolowskie na zbiorach):
Prawo przemienności:
(B1) A*" B=B*" A (B1') A)" B=B)" A
Prawo łączności:
(B2) śą A*"Bźą*"C =A*"śą B*"C źą (B2') śą A)"Bźą)"C =A)"śąB)"C źą
Prawo rozdzielności:
(B3) A*"śą B)"C źą=śą A*"Bźą)"śą A*"C źą (B3') A)"śąB*"C źą=śą A)"Bźą*"śąA)"C źą
Prawo zbioru pustego i uniwersum(gdzie X to uniwersum):
(B4) A*""=A (B4') A)" X = A
Prawo dopełnienia:
(B5) A*"śą-Aźą= X (B5') A)"śą-Aźą="
Ważniejsze prawa algebry zbiorów:
Prawa idempotentności:
A*" B= A A)" A= A
Prawa łączności:
śą A*"B źą*"C= A*"śą B*"C źą śą A)"B źą)"C= A)"śą B)"C źą
Prawa przemienności:
A*" B=B*" A A)" B=B)" A
Prawa rozdzielności:
A*"śą B)"C źą=śą A*"Bźą)"śą A*"C źą A)"śą B*"C źą=śą A)"Bźą*"śą A)"C źą
Prawa zbioru pustego:
A*""=A A)""="
Prawa dla różnicy zbiorów:
A " A="
"" A="
A ""= A
śą A*"B źą"C=śą A"C źą*"śą B "C źą
śą A)"B źą"C=śą A"C źą)"śą B "C źą
Prawa De Morgana dla różnicy zbiorów:
A "śą B*"C źą=śą A" Bźą)"śą A"C źą
A "śą B)"C źą=śą A" Bźą*"śą A"C źą
Definicja stosunku inkluzji i prawa z inkluzją i działaniami. ?
AÄ…" BÔ! " xśą x" AÒ! x"Bźą
Relacja inkluzji ma następujące własności:
1.zwrtotność, tzn. Aą" A
2.antysymetria, tzn. AÄ…" B'"BÄ…" AÒ! A=B
3.przechodniość, tzn. AÄ…" B'"BÄ…"C Ò! AÄ…"C
Prawa z inkluzjÄ…
suma: A‚" B'"C ‚"D Ò! A*"C‚"B*"D
przekrój: A‚" B'"C ‚"D Ò! A)"C‚"B)"D
różnica: A‚" B'"C ‚"D Ò! A" D‚"B "C
Para uporządkowana i iloczyn kartezjański.
Para uporzÄ…dkowana )# x , y *# jest wyznaczona jednoznacznie przez elementy x i y. Ponadto
)# x , y*#=)#u , v *# wtedy i tylko wtedy, gdy x=u i y=v
Niech dane będą dwa zbiory X i Y. Produktem (iloczynem) kartezjańskim zbiorów X i Y nazywamy zbiór
X ×Y ={)# x , y*#: x" X '" y"Y }
Relacje, dziedzina, przeciwdziedzina, relacja odwrotna, złożenie relacji.
A×B
Relacją nazywamy każdy podzbiór iloczynu
Dziedzina
DR={x"R :śą" y"r źąśą xRyźą}
Przeciwdziedzina
Dż ={y"R:śą" x"rźąśą xRyźą}
R
Złożenie
Dla R= A×B i S= B×C
R° S ={śą x , zźą"A×C :śą" y"Bźąśąśą x , yźą"R'"śą y , zźą"S źą}
Odwrotność
Dla R= A×B
R-1 ={śą y , xźą"B× A:śą x , y źą"R}
Funkcje jako relacje, funkcje różnowartościowe i "na", ważniejsze własności.
Funkcja:
Def. RelacjÄ™ R Ä…" AxB nazywamy funkcjÄ… jednoargumentowÄ…
wtedy i tylko wtedy, gdy spełnione są następujące warunki:
" x"DR " y"Bśą xRyźą
(i)
" x"DR " y "B " z"B śąxRy'" xRzÒ! y=zźą
(ii)
Funkcje różnowartościowe (iniekcja)
" x , y"DRśą f śą xźą= f śą y źąÒ! x= yźą
Funkcje  na (suriekcja)
" y"Dż " x "DRśą y= f śą xźąźą
R
Bijekcja = iniekcja i suriekcja
WA
ASNOÅšCI RELACJI:
Def. Niech R bÄ™dzie relacjÄ… w zbiorze X, to znaczy zachodzi RÄ…" X × X . Mówimy, że relacja R jest:
1. zwrotna wtw, gdy " x" X śą xRxźą
2. przeciwzwrotna wtw, gdy " x" X Źśą xRxźą , czyli innymi słowy Ź" x"X Źśą xRxźą
3. niezwrotna wtw, gdy Ź" x" X śą xRxźą , czyli innymi słowy " x" X Źśą xRx źą
4. symetryczna wtw, gdy " x" X " y" X śą xRyŚą yRx źą
5. przeciwsymetryczna (asymetryczna) wtw, gdy " x" X " y" X śąxRyŚąŹ yRxźą
6. antysymetryczna (słabo antysymetryczna; na wpół przeciwsymetryczna wtw, gdy
" x" X " y" X śą xRy "yRxŚą x= y źą
7. przechodnia wtw, gdy " x" X " y" X " z"X śą xRy'" yRz Śą xRzźą
8. spójna wtw, gdy " x" X " y" X śąxRy(" yRx("x = yźą
9. diagonalna wtw, gdy " x" X [ xRx'"" y"X śą y`" xŚąŹxRy'"ŹyRxźą]
10. totalna wtw, gdy " x" X " y" X śą xRyźą
WA
ASNOÅšCI FUNKCJI:
1. f : X ŚąY '"g :Y Śą Z Ò! f ° g : X Śą Z (dziaÅ‚a dla iniekcji, suriekcji i bijiekcji)
-1
2. (DOTYCZY TYLKO INIEKCJI!)
f : X ŚąY Ò! f : D' f Śą X
-1
3. (DOTYCZY TYLKO BIJIEKCJI!)
f : X ŚąY Ò! f :Y Śą X
Relacje równoważności, klasy abstrakcji, zasada abstrakcji.
Def. Niech R bÄ™dzie relacjÄ… binarnÄ… w zbiorze X, czyli RÄ…" X × X . Mówimy, że R jest relacjÄ… równoważno-
ści wtedy i tylko wtedy, gdy R jest:
1.zwrotna, tzn. " x" X śąxRxźą
2.symetryczna, tzn. " x" X " y" X śą xRy Ò! yRxźą
3.przechodnia, tzn. " x" X " y" X " z"X śą xRy'" yRzÒ! xRzźą
Def. Niech R będzie relacją równoważności w zbiorze X i niech x "X . Klasą abstrakcji (klasą rów-
[ x ]R={ y"X : xRy }
noważności) elementu x względem relacji R nazywamy zbiór
Tw.Niech R będzie relacją równoważności w niepustym zbiorze X . Wtedy dla dowolnych elementów
x , y , z" X
x "[ x ]R
1.
[ x ]R=[ y ]R
2. wtedy i tylko wtedy, gdy xRy
[ x ]R`"[ y ]R [ x ]R)"[ y ]R="
3.jeśli , to
Tw. (zasada abstrakcji) Każda relacja równoważności R w niepustym zbiorze X ustala podział zbioru
X na rozłączne i niepuste podzbiory (mianowicie na klasy abstrakcji) w taki sposób, że dwa elementy
x , y zbioru X należą do tego samego podzbioru wtedy i tylko wtedy, gdy
Relacje porządkujące, elementy największe, najmniejsze, maksymalne i minimalne, kres górny i
kres dolny.
Def. Relację R na zbiorze X nazywamy częściowo porządkującą jeżeli jest:
1.zwrotna śą" x" X źą xRx
2.sÅ‚abo antysymetryczna śą" x , yźąśąxRy'" yRx Ò! x= y źą
3.przechodnia śą" x , y , zźąśą xRy'" yRzÒ! xRzźą
4.Jeśli relacja R jest dodatkowo spójna, to nazywamy ją relacją liniowo porzadkującą
śą" x , y" X źąśąxRy(" yRx źą
Def. Jeśli R jest relacją częściowo (odpowiednio liniowo) porządkującą na zbiorze X , to parę
śą X , Rźą nazywamy zbiorem częściowo (odp. liniowo) uporządkowanym.
Def. Niech (X, R) bÄ™dzie zbiorem częściowo uporzÄ…dkowanym. Niech Y ‚" X . Element a"Y nazywamy
największym (odp. Najmniejszym) w Y jeżeli śą" y"Y źą yRa (odp. śą" y"Y źąaRy )
Def. Element a "Y nazywamy elementem maksymalnym (odp. minimalnym) w zbiorze Y jeżeli nie
istnieje element b"Y , taki że a`"b'"aRb (odp. a`"b'"bRa )
Liczby naturalne i zasada indukcji matematycznej.
Zasada indukcji matematycznej:
Tw.
Niech )# X ,d" *# bÄ™dzie zbiorem dobrze uporzÄ…dkowanym i niech Ëąśąvźą bÄ™dzie funkcjÄ… zdaniowÄ… o jednej
zmiennej wolnej v przebiegającej zbiór X. Załóżmy, że:
1. Najmniejszy element zbioru X ma wÅ‚asność ËÄ… ,
2. Dla dowolnego elementu x"X , jeżeli wszystkie elementy poprzedzajÄ…ce x majÄ… wÅ‚asność ËÄ… , to również
element x ma wÅ‚asność ËÄ… .
Wtedy każdy element zbioru X ma wÅ‚asność ËÄ… .
Liczby naturalne jako zbiór
0="1={"}2={" , {"}}3={" ,{"}, {" , {"}}}
nƒÄ…1={0, 1,2, 3...n}={0, 1, 2, 3...n-1}*"{n}=n*"{n}
{X}  singleton X, po prostu zbiór, którego jedynym elementem jest zbiór X
Def. Następnik
S śą X źą= X *"{ X }
Def. Zbiór induktywny:
INDśą xźąÔ! ""x'"" y"xśąS śą yźą"x źą
Aksjomat nieskończoności: istnieje zbiór induktywny (przynajmniej jeden)
Def. Liczby naturalne
NAT śą xźąÔ!" yśą INDśą yźąÒ! x" y źą
NAT(x) czytamy  x jest liczbÄ… naturalnÄ…
!={x: NAT śą xźą}