Matematické Fórum

Sokolik · 27. 01. 2012 14:55

Zdravím,
matika mi do hlavy nikdy moc nelezla, i když jsem ji studoval... takže mám takovej širší dotaz, na kterej by asi odpověď byla dost rozsáhlá, tak mi stačí jen částečná pro přibližnou orientaci.

Definice: množina M je definovatelná, když existuje formule F(x), která platí v daném modelu právě pro taková x, která jsou prvky M. (Čili formule F definuje množinu M.)

Otázka 1: Jak asi velká část z potence N je definovatelná ve struktuře (N,+,.,<)?

Uvažme funkci, která každý formuli jednoznačně přiřadí přirozený číslo.
Otázka 2: Je množina všech formulí, kerý definujou nějakou množinu v N, definovatelná v (N,+,.,<)?
Otázka 3: Jak asi velká část z potence takovýchto formulí je v dané struktuře definovatelná?

FailED · 27. 01. 2012 18:14

Zdravím

ad 1)
Jazyk té struktury je spočetný, formule jsou konečné posloupnosti symbolů jazyka, je tedy spočetně formulí a nejvýš spočetně definovatelných množin. Není těžké si rozmyslet, že jich bude právě spočetně.

ad 2)
Myslíš množinu formulí, které definují neprázdnou množinu? Myslíš definovatelnost množiny obrazů takových formulí? Obecně to platit nemusí - podle 1) existuje nekonečná nedefinovatelná podmnožina $\mathbb{N}$ , stačí když obrazem přiřazovací funkce bude tato.

ad 3)
Podobně jako 1)

Sokolik · 27. 01. 2012 19:44

↑ FailED:

1 a 3: jak geniálně prosté, díky.

2: Nechával jsem otevřeno, jestli myslím formule definující neprázdnou množinu, nebo prostě "nějakou" množinu :) Ale máš pravdu, "nějakou" množinu definuje každá formule.
Je možný, aby obrazem přiřazovací fce byla nedefinovatelná množina?

FailED · 27. 01. 2012 20:15 — Editoval FailED (27. 01. 2012 20:16)

↑ Sokolik:

Podmnožin N je nespočetně.

Konečných podmnožin N je spočetně.

Proto musí existovat nespočetně nekonečných podmnožin N.

Z nich je definovatelných jen spočetně, proto můžeme vybrat X nekonečnou nedefinovatelnou.

Počet formulí, které definují neprázdnou množinu je spočetně, proto existuje bijekce mezi X a těmi formulemi. To je hledaná přiřazovací funkce.

*To je pro prostou přiřazovací funkci, kdyby to měla být bijekce, bude se postupovat podobně.

Sokolik · 27. 01. 2012 21:18

↑ FailED:

Ano, to dává smysl, jen jsem se nemoh smířit s tím, že taková funkce je zkonstruovatelná, když vyhazuje nedefinovatelnou množinu. Ale ona ji vyhazuje jen pro určitou podmnožinu z P(N), takže asi OK.

Matematické Fórum

#1 27. 01. 2012 14:55

Otázky kolem kardinality definovatelných množin

#2 27. 01. 2012 18:14

Re: Otázky kolem kardinality definovatelných množin

#3 27. 01. 2012 19:44

Re: Otázky kolem kardinality definovatelných množin

#4 27. 01. 2012 20:15 — Editoval FailED (27. 01. 2012 20:16)

Re: Otázky kolem kardinality definovatelných množin

#5 27. 01. 2012 21:18

Re: Otázky kolem kardinality definovatelných množin

Zápatí