Matematické Fórum

hrt · 14. 02. 2010 03:59

Ahoj,
prosím o radu ohledně následující úlohy z pred. logiky, všechny příklady jsem spočítal, ale s tímhle si nevím rady :((

---- Dokažte, že struktury <Z,+,0> a <Z x Z,+,0> nejsou elementárně ekvivalentní. Nápověda: Parita (??)

Nějaké definice: Struktury M, N jsou elementárně ekvivalentní, pokud v nich platí stejné sentence, tj. Thm(M) = Thm(N). Kde Thm(M) je teorie sentencí dané struktury: každá struktura M určuje úplnou teorii Thm(M) = {fí; fí je uzavřená a M |= fí}

Poraďte prosím, pokud tušíte... Díky.

Rumburak

Předpokládám, že Z je množina všech celých čísel a že scítání v <Z x Z,+,0> se provádí po složkách.
Vezmeme-li celé číslo $x$ a definujeme-li $1\cdot x \,:= x,\,(n+1)\cdot x \,:= n\cdot x + x$ , pak máme definováno násobení celých čísel
čísly přirozenými. Obdobně v ZxZ : $1\cdot [x,y] \,:= [x,y],\,(n+1)\cdot [x,y] \,:= n\cdot [x,y] + [x,y]$ .

Dále (obdobně jako v Z) prohlásíme v ZxZ, že [a, b] je sudé , právě když [a, b] = 2.[x,y] pro vhodné [x,y] ze ZxZ
(s dodatkem, že dvojice [c,d], které nejsou sudé, prohlásíme za liché).

V Z platí věta "Jsou-li a, b lichá , potom a + b je sudé. "

Obdobná věta v ZxZ neplatí. Sestrojíš vhodný příklad sám ?

hrt · 15. 02. 2010 17:25 — Editoval hrt (15. 02. 2010 23:24)

přímo konkrétně? třeba takto?

v Z:
a = 9 ... != 2x, tj. liché
b = -5 ... != 2x, tj. liché
a+b = 4 ... == 2x, tj. sudé

v ZxZ:
a = [1,2] ... != 2[x,y], tj. liché
b = [3,7] ... != 2[x,y], tj. liché
a+b = [4,9] ... != 2[x,y], tj. též liché

děkuju, moc jsi pomohl!!

Kondr · 15. 02. 2010 23:33

↑ hrt: Až na to, že v Z nehledáme jednu dvojici, pro kterou by to platilo, ale (chceme-li mít formálně kompletní řešení) potřebujeme ukázat, že to platí pro všechna lichá a,b. Ale to je důkaz tak triviální, že jej netřeba psát.

↑ Rumburak: Můžeme do sentencí přidávat predikáty jako "být součinem" nebo "být přirozeným číslem"? Určitě by prošlo "být sudý", protože to "x je sudé" umíme zapsat bez rekurze jako $\exists y:x=y+y$ .

Rumburak

↑ Kondr: Bral jsem to tak, že teorii přirozených čísel včetně přincipu indukce si "jednoúčelově vypůjčíme" pro konstrukci
jistých posloupností (a_n) v Z resp. ZxZ (kde a_n formálně zapisujeme jako součin n.a), aniž bychom se starali o to, je-li mezi
přirozenými a celými čísly nějaká jiná souvislost než ta, kterou jsem definoval. Připadalo mi, že při tomto pojetí by to mohlo projít.
Nebo se pletu ?

Každopádně jsi mi ukázal, že jsem na to šel zbytečně složitě, což s díky kvituji :-).

Kondr · 16. 02. 2010 12:01

↑ Rumburak: Myslím, že sentence musí být tvořena pouze konstantami, proměnnými, funkčními symboly, logickými spojkami, kvantifikátory a predikátem =. Alespoňtak jsem to pochopil z http://cs.wikipedia.org/wiki/Sentence

Rumburak · 16. 02. 2010 14:28

↑ Kondr: Hmm, nejspíš to tak bude.

Pokusím se zapřemýšlet, jaké nutno zavést funkční symboly a atomické formule, aby pomocí nich bylo možno "čistým" způsobem
ve smyslu http://cs.wikipedia.org/wiki/Sentence definovat grupu <Z,+,0> v obvyklém pojetí. Zatím si neumím představit, že by se to
dalo obejít bez nějakého předpokladu, v němž by se indukce vyskytovala aspoň skrytě. Ale blíže jsem tyto otázky nezkoumal,
takže mohu být na omylu.

(Připadá mi, že by nemělo smysl "čistým" způsobem zkoumat strukturu, kterou bychom neuměli "čistým" způsobem popsat.)

Rumburak

Tk už jsem trochu zapřemýšlel :-).

Je to otázka řádu jazyka. Pokud budeme trvat na jazyce 1. řádu, který by obsahoval proměnné pouze pro celá čísla (a nikoliv proměnné
pro množiny sestavené z celých čísel), pak ten princip indukce asi opravdu nevybudujeme, i když popsat aditivní grupu, která by byla
komutativní a uspořádaná (tak, aby pro libovolná x,y, w platilo x < y -----> x + w < y + w) není těžké.
Rovněž lze pak zavést pojem kladného čísla (splňujícího x > 0 , kde 0 je neutrální prvek) a vydat axiom, že existuje nejmenší kladné číslo
(pro které předem vyhradíme konstantu 1).
Zdá se, že touto cestou by mohla být grupa celých čísel zavedena, pokud tam ještě někde nečíhá nějaká zrada.

Matematické Fórum

#1 14. 02. 2010 03:59

Elementární ekvivalence dvou struktur

#2 15. 02. 2010 10:01 — Editoval Rumburak (15. 02. 2010 10:13)

Re: Elementární ekvivalence dvou struktur

#3 15. 02. 2010 17:25 — Editoval hrt (15. 02. 2010 23:24)

Re: Elementární ekvivalence dvou struktur

#4 15. 02. 2010 23:33

Re: Elementární ekvivalence dvou struktur

#5 16. 02. 2010 09:17 — Editoval Rumburak (16. 02. 2010 09:51)

Re: Elementární ekvivalence dvou struktur

#6 16. 02. 2010 12:01

Re: Elementární ekvivalence dvou struktur

#7 16. 02. 2010 14:28

Re: Elementární ekvivalence dvou struktur

#8 18. 02. 2010 10:26 — Editoval Rumburak (18. 02. 2010 10:33)

Re: Elementární ekvivalence dvou struktur

Zápatí