# Ukol na zapocet

<{ForumPost(poster="karel89", timestamp=2010-02-11 20:50:40)}>
Ahoj, nevim si rady s nasledujicim ukolem na zápočet. Už je to to poslední, co mi chybí, tak kdyby někdo veděl a byl ochotnej sem napsat řešení, byl bych moc rád,   
Dííky  
  
Ukol je zadefinovat konzervativni rozsireni Robinsonovy aritmetiky a v nem formalne zapsat "existuje nekonecne mnoho prvocisel "
<{/ForumPost}>

<{ForumPost(poster="Pitr2311", timestamp=2010-02-11 22:41:43)}>
k tomu konzervativnemu rozsireni staci, aby si tam pridal nejaku dokazatelnu formuli v Q, napriklad teda:  
$$(\exists x)( (\forall y)(y 
eq S x) \wedge (\forall y)( (y 
eq x) \rightarrow (\exists z)(z = S y) ) )$$  
tato formule vznika spojenim axiomov (Q1) a (Q7), takze je v Q dokazatelna a jej pridanim teda nepribudne ziadna nova dokazatelna formule... v druhej casti sa nam bude este hodit pridat jeden unarni relacny symbol: P(x) <=> x je prvocislo... ide o rozsirenie jazyka, teda tiez sa nic nemeni na dokazatelnosti L(Q)-formuli  :wink:  
k druhej otazke: tu teraz vyuzijeme symbol P a nadefinujme si mnozinu M nasledovne:  
$$M = \{ \varphi_n | n \in \mathbb{N} \}$$  
$$\varphi_n: (\exists x_1) \cdots (\exists x_n)( \bigwedge_{0 \leq i < j \leq n} (x_i 
eq x_j) \wedge P(x_1) \wedge \cdots \wedge P(x_n) )$$  
kazda formule fi_n hovori, ze "existuje aspon n prvocisel", cela mnozina M potom axiomatizuje existenciu nekonecneho poctu prvocisel, kedze vsetky formule musia platit naraz...  
verim, ze som nikde neurobil chybu a snad to pomoze.. vela stastia  :wink:
<{/ForumPost}>

<{ForumPost(poster="karel89", timestamp=2010-02-12 11:33:45)}>
Jooo, to vypadaa dobře, ale jak bude formálně zapsaná ta relace P(x)??
<{/ForumPost}>

<{ForumPost(poster="Pitr2311", timestamp=2010-02-12 16:57:48)}>
tu relaciu P(x) si mozeme nadefinovat napriklad takto:  
$$P(x) \iff ( (\forall y)( (\exists z)(y \cdot z = x) \rightarrow ( (y = S0) \vee (y = x) ) ) ) \wedge (x 
eq S0)$$  
posledna cast zarucuje, ze 1(=S0) nie je prvocislo, co sa by podla predchadzajuceho urcilo opacne
<{/ForumPost}>