Ukol na zapocet

karel89 · Příspěvek od **karel89** » 11. 2. 2010 20:50

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 "

Pitr2311 · Příspěvek od **Pitr2311** » 11. 2. 2010 22:41

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

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

karel89 · Příspěvek od **karel89** » 12. 2. 2010 11:33

Jooo, to vypadaa dobře, ale jak bude formálně zapsaná ta relace P(x)??

Pitr2311 · Příspěvek od **Pitr2311** » 12. 2. 2010 16:57

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

Fórum studentů MFF UK

Ukol na zapocet

Ukol na zapocet

Re: Ukol na zapocet

Re: Ukol na zapocet

Re: Ukol na zapocet