# 6.1. predtermin <{ForumPost(poster="adamo", timestamp=2012-01-06 23:48:22)}> Zdravim. mohli by ste niekto napisat ake otazky boli na tomto predtermine? <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-07 12:35:51)}> Ahoj, vcerejsi predtermin u Zemlicky na Karline byl drsny, byli jsme tam jen 4:) Zkusim prilozit naskenovanou pisemku... <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-07 13:03:54)}> Nejak se mi nepodarilo nahrat prilohu (nevim, cim to je), takze externi odkaz: [http://www.uloz.to/12356202/str01-jpg](http://www.uloz.to/12356202/str01-jpg) [http://www.uloz.to/12356204/str02-jpg](http://www.uloz.to/12356204/str02-jpg) <{/ForumPost}> <{ForumPost(poster="Jookyn", timestamp=2012-01-07 15:13:12)}> Super, díky moc. Jinak nějaký správný řešení pro 7. někoho nenapadá? <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-07 18:58:44)}> Jo, to mi vysvetlil takhle: Algebry typu (2, 0, 0)... tj. binarni a 2 (ruzne) konstanty. Univerza 2-prvkova (pro kazdou konstantu jeden prvek). Tim je jednoznacne urcen homomorfismus (prislusne konstanty se musi zobrazit na sebe, to lze jedinym zpusobem). Ted staci vytvorit "tabulku definujici binarni operaci" pro kazdou z algeber (tedy ktery dvojice daji jaky vysledek). Homomorfismus by mel prevadet jednu tabulku na druhou (az na prejmenovani prvku ze vzoru do obrazu homomorfismu, tj. obraz vysledku bude vysledkem obrazu puvodnich operandu). Staci zadefinovat operaci tak, aby to neslo: napr. v jedne algebre se vsechno zobrazuje do jednoho prvku, v te druhe se zobrazuje ruzne na vsechny prvky. Pak ten jediny kandidat na homomorfismus nema sanci byt homomorfismem:) <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-07 19:38:53)}> BTW tyhle otazky nejsou vsechny. Ke kazdemu cislu otazky je nahodne vybrano zadani ze 3-4 moznych alternativ, cimz je kazda pisemka takrka unikatni. Dalsi otazky lze zjistit od dalsich absolventu predterminu, ale nejsem si jistej, jestli se tyhle vubec vyskytnou u dalsich terminu (i kdyz na druhou stranu by dalo dost prace vymyslet dalsi nove otazky:). Ale tak se aspon podivejte, at vite, jak to priblizne vypada... <{/ForumPost}> <{ForumPost(poster="Davpe", timestamp=2012-01-07 19:47:59)}> Taky prispeju svoj verzi ( 7 bodu) : obe ulohy stejne jako kolega vyse (1 bod) : 3) Def. grupu invertibilnich prvku $Z_n^* (\cdot)$. Za jakych podminek cyklicka? 4) Def. rmod pro grupy 5) Napsat aspon 4 neizomorf osmiprvkove grupy -- $Z_8, Z_2 \times Z_4 , Z_2 \times Z_2 \times Z_2, ?$ 6) Existuji dve neizomorf. cyklicke grupy radu $2^{1000}$? Zduvodnete. -- ne. Plyne z 1) 7) Def. typ algebry -- pozn: tuto ulohu jsme meli 3 lide, vsichni tri jsme ji meli spatne. zemlicka se pak podival do skript a zjistil ze tam tu definici nema, takze nam to uznal a tato uloha na letosnich pisemkach uz nebude ;) 8) Aspon dve kongruence na nekonecne algebra -- id, ? 9) Jsou grupy $Z_{12}(+)$ a $Z_3 \times Z_4 (+)$ isomorfni? Zduvodnit -- Ano. Staci zobrazit generator 1 na generator (1, 1) a vypsat prirazeni prvku jedne grupy na druhou. 10) Def. Booleovu algebru 11) Nakreslit nejmensi svaz, ktery neni booleovou algebrou. -- cesta o trech vrcholech na vysku. 12) Pospat vsechny idealy okruhu celych cisel (2 body): 13) Spocitat $13^{-1}$ v monoidu $Z_{19}(\cdot)$ -- Pomoci euklidova algoritmu 14) Kolik je homomorfismu z grupy $Z_{30}(+)$ do grupy $Z_{50}(+)$ 15) Obsahuje grupa $S_6$(skladani) podgrupu radu a) 5 b) 8 ? -- a) ano grupa generovana permutaci (1, 2, 3, 4 , 5) -- b) ne. delky cyklu by musely mit soucet 6 a soucin 8 (protoze rad permutace je nsn delek cyklu). tedy moznosti jsou bud delky cyklu 2 a 4, ale pak je rad permutace nsn (2, 4) = 4 nebo delky cyklu 2, 2, 2 a pak je rad permutace 2. 16) Grupa $Z \times Z (+)$ cyklicka? Zduvodnit. -- Rekl bych ze ne, protoze je nekonecna a musela by byt isomorfni Z coz neni. Neprislo mi to uplne lehke, navic pokud se clovek v dukazech zasekl a nemohl se odseknout, tak to byl (aspon pro me) docela problem. Vysledek: dve jednicky dve trojky. ja jsem dostal za 3 s tim, ze zemlicka nabizel trojkarum si to prijit nekdy opravit, takze se na Karline mozna jeste ukazu. <{/ForumPost}> <{ForumPost(poster="Jookyn", timestamp=2012-01-07 20:29:29)}> > Davpe wrote: > 6) Existuji dve neizomorf. grupy radu $2^{1000}$? Zduvodnete. > -- ne. Plyne z 1) a Nemají to náhodou být neizomorfní CYKLICKÉ grupy ... ? Pro obecné grupy to zdůvodnění nedává podle mě smysl a asi budou i nějaké neizomorfní existovat, ne? <{/ForumPost}> <{ForumPost(poster="Jookyn", timestamp=2012-01-07 20:31:29)}> > mathemage wrote:i kdyz na druhou stranu by dalo dost prace vymyslet dalsi nove otazky:) Myslim, že ani ne, viz sbírka loňských otázek od D. Stanovského (byla předem daná a známá tahle množina a z toho to náhodně generoval varianty) - [http://www.karlin.mff.cuni.cz/~stanovsk ... _ulohy.pdf](http://www.karlin.mff.cuni.cz/~stanovsk/vyuka/alg_inf_ulohy.pdf) <{/ForumPost}> <{ForumPost(poster="Davpe", timestamp=2012-01-07 20:44:25)}> > Jookyn wrote: > > Davpe wrote: > > 6) Existuji dve neizomorf. grupy radu $2^{1000}$? Zduvodnete. > > -- ne. Plyne z 1) a > > Nemají to náhodou být neizomorfní CYKLICKÉ grupy ... ? Pro obecné grupy to zdůvodnění nedává podle mě smysl a asi budou i nějaké neizomorfní existovat, ne? jasne, diky - prepsal jsem se. opraveno. <{/ForumPost}> <{ForumPost(poster="Jookyn", timestamp=2012-01-09 23:23:57)}> Mimochodem, ještě jsem vypozoroval, že oba důkazy, který byly na prvnim termínu jsou ve skriptech opravdu vedený jako "Věta" a nikoli jako "Poznámka". Myslíte, že je to náhoda, nebo že bude dávat dokazovat jen věci vedený jako věty? Protože tim by odpadlo tak 70% důkazů, který jsou u poznámek... Neřikal o tom náhodou něco na přednášce? <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-11 00:09:17)}> > Davpe wrote: > 5) Napsat aspon 4 neizomorf osmiprvkove grupy > -- $Z_8, Z_2 \times Z_4 , Z_2 \times Z_2 \times Z_2, ?$ Jeste $D_8$ - dihedralni grupa (vsechny symetrie ctverce). Ma prvky radu (1, 2, 2, 2, 2, 2, 4, 4). $\mathbb{Z}_8$ ma prvek radu 8. $\mathbb{Z}_2\times\mathbb{Z}_4$ ma 4 prvky radu 4. $\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2$ ma zase jen prvky radu nejvejs 2. Informace o radech prvku se zrovna daji zapsat pomoci uzavrenych formuli, ktere by mely platit stejne v izomorfnich strukturach, takze $D_8$ je skutecne neizomorfni k ostatnim;) <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-11 00:11:01)}> > Davpe wrote: > 6) Existuji dve neizomorf. cyklicke grupy radu $2^{1000}$? Zduvodnete. > -- ne. Plyne z 1) Spis proto, ze cyklicke grupy takovych radu jsou vzdy izomorfni $\mathbb{Z}_{2^{1000}}$, takze by k sobe byly stejnak vzdycky izomorfni. <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-11 00:12:06)}> > Davpe wrote: > 8) Aspon dve kongruence na nekonecne algebra > -- id, ? Jeste treba relace se vsemi prvky, tj. $A\times A$ <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-11 00:13:06)}> > Davpe wrote: > 9) Jsou grupy $Z_{12}(+)$ a $Z_3 \times Z_4 (+)$ isomorfni? Zduvodnit > -- Ano. Staci zobrazit generator 1 na generator (1, 1) a vypsat prirazeni prvku jedne grupy na druhou. Nebo staci rict kratce "Cinska zbytkova veta";) <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-11 00:15:20)}> > Davpe wrote: > 11) Nakreslit nejmensi svaz, ktery neni booleovou algebrou. > -- cesta o trech vrcholech na vysku. Jak se tady prijde na to, ze se nejedna o Booleovu algebru? *(Jediny co me napada, je, ze kazda konecna BA je isomorfni potencni algebre mnoziny vsech svych atomu, a ta ma velikost mocniny 2, coz 3 neni. Ale urcite je nejake jednodussi vysvetleni:)* <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-11 00:19:24)}> > Davpe wrote: > 12) Pospat vsechny idealy okruhu celych cisel $k\mathbb{Z}$ ... (idealy okruhu jsou podgrupy scitaci grupy tohoto okruhu) -> Vsechny podgrupy $\mathbb{Z}$ jsou takovyho tvaru, navic jsou to i idealy (tzv. hlavni idealy) ... je to primo v Zemlickovych skriptach, ale ne uplne detailne vysvetleny <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-11 00:47:49)}> > Davpe wrote: > 14) Kolik je homomorfismu z grupy $Z_{30}(+)$ do grupy $Z_{50}(+)$ #homomorfismu ze $\mathbb{Z}_m$ do $\mathbb{Z}_n$ je NSD(m, n). Dukaz nepatri zrovna k tem nejtrivialnejsim, ale pokusim se o nej: Zkoumejme, na jake podgrupy $\mathbb{Z}_n$ se muze homomorfismus $f$ zobrazit (tj. velikost obrazu, oznacme ji $r$): 1) $Im(f) \leq \mathbb{Z}_n$, tj. $r$ deli $n$ 2) $Im(f) \simeq \mathbb{Z}_m/Ker f$, jejiz velikost je index $[\mathbb{Z}_m:Ker f]$, ktery je z Lagrangeovy vety delitel radu grupy $\mathbb{Z}_m$, neboli $r$ deli take $m$ Tudiz $r$ deli i NSD(m, n). (jinymi slovy: Muzem tedy homomorfismem zobrazovat jen na podgrupu radu spolecneho delitele m a n). Jak konkretne? Budeme zobrazovat $1$ (generator v $\mathbb{Z}_m$) na nejaky generator podgrupy (grupy $\mathbb{Z}_n$) vhodne velikosti r. Zbyvajici prvky jsou jasne dane, tj. $f(k):= k f(1)$ Ale kolik takovych generatoru je? - Presne jich je: $$\sum_{r \mid NSD(m,n)} \varphi(r)$$ coz se uplnou nahodickou i rovna NSD(m,n). To se dokaze pocitanim 2 zpusoby: spocitame vsechny prvky $\mathbb{Z}_{NSD(m,n)}$ (1) trivialne je to NSD(m,n) (2) kazdy prvek generuje prave 1 podgrupu nejake velikosti r, a ta je delitelem NSD(m, n) (dokonce podgrupa teto velikosti je prave 1!!). Tenhle prvek je generatorem teto podgrupy (a zadne dalsi), takze prispeje prave jednou $1$ do (prave jedne) Eulerovy funkce $\varphi(r)$. V Eulorove funkci je prave jedna $1$ za kazdy generator a nic dalsiho, a velikosti podgrupy (v sume jsou to ty "r") jsou prave jen delitele NSD a nic dalsiho. shrnuto: #homomorfismu = #moznosti zobrazeni $1$ na generator podgrupy vhodne velikosti r (viz vyse) = #takovych generatoru = NSD(m, n) Q.E.D. BTW nemate nekdo napad, jak jednodusejc to dokazat? Prijde mi, ze to urcite jde nejak zkratit/zjednodusit:) <{/ForumPost}> <{ForumPost(poster="mathemage", timestamp=2012-01-11 00:51:55)}> > Davpe wrote: > Neprislo mi to uplne lehke, navic pokud se clovek v dukazech zasekl a nemohl se odseknout, tak to byl (aspon pro me) docela problem. Nelze nez dodati: SVATA PRAVDA! :) <{/ForumPost}> <{ForumPost(poster="Ganef", timestamp=2012-01-12 20:17:57)}> > mathemage wrote: > > Davpe wrote: > > 11) Nakreslit nejmensi svaz, ktery neni booleovou algebrou. > > -- cesta o trech vrcholech na vysku. > > Jak se tady prijde na to, ze se nejedna o Booleovu algebru? > > *(Jediny co me napada, je, ze kazda konecna BA je isomorfni potencni algebre mnoziny vsech svych atomu, a ta ma velikost mocniny 2, coz 3 neni. Ale urcite je nejake jednodussi vysvetleni:)* Ano, jde to jednodušeji. Spodní prvek je 0, horní prvek je 1 a prostřední ať dělá co dělá, tak je mezi nimi a nemá k sobě doplněk. Ale operátor doplňku by měl být definovaný pro všechny prvky. <{/ForumPost}> <{ForumPost(poster="Ganef", timestamp=2012-01-12 20:43:00)}> > mathemage wrote: > > Davpe wrote: > > 14) Kolik je homomorfismu z grupy $Z_{30}(+)$ do grupy $Z_{50}(+)$ > > #homomorfismu ze $\mathbb{Z}_m$ do $\mathbb{Z}_n$ je NSD(m, n). Dukaz nepatri zrovna k tem nejtrivialnejsim, ale pokusim se o nej: S výsledkem souhlasím, ale možná někomu více sedne toto zdůvodnění: Všimneme si, že pokud je zobrazení homomorfismus, tak je jednoznačně dáno tím, kam se nám zobrazí generátor (BÚNO jednička). Takže stačí jen zjistit, kam se nám 1 může zobrazit, aby jsme dostali homomorfismus. Nahlédneme, že ker f má všechny ekvivalenční třídy stejně velké, protože 1 se nám zobrazí do \[1] a m-1 se musí zobrazit do \[-1] (aby se zachovaly inverzní prvky). => 1 se může zobrazit na takové prvky k, že n dělí k*m (50 dělí k*30). Nejmenší k, které splňuje tuto vlastnost je n/NSD(m, n) a počet čísel, které vlastnost splňují je n/(n/NSD(m, n)) = NSD(m, n). <{/ForumPost}> <{ForumPost(poster="babca_", timestamp=2012-01-12 21:03:33)}> Ahoj > 15) Obsahuje grupa S_6(skladani) podgrupu radu a) 5 b) 8 ? U b) Dle lagrange rad podgrupy deli rad grupy, rad S_6 je 6! = 6*5*4*3*2*1 a tedy 8 | 6! => B) Ano Je to pravda? O:-) <{/ForumPost}> <{ForumPost(poster="Jookyn", timestamp=2012-01-12 21:17:22)}> > babca_ wrote:Ahoj > > > 15) Obsahuje grupa S_6(skladani) podgrupu radu a) 5 b) 8 ? > > U b) Dle lagrange rad podgrupy deli rad grupy, rad S_6 je 6! = 6*5*4*3*2*1 a tedy 8 | 6! => B) Ano > > Je to pravda? O:-) Myslim si, že neni a že argument, proč podgrupa neexistuje je v původním příspěvku správně... Podle mě je úvaha chybná protože Langangeova věta neni postačující podmínka pro existenci podgrupy řádu k|n, ale pouze nutná. Pak tam sice byla věta, že pro každé k|n existuje práve jedna podgrupa řádu k, jenže to bylo pouze pro cyklické grupy. Kdyžtak mi pls někdo opravte, pokud se v něčem mýlim... <{/ForumPost}> <{ForumPost(poster="babca_", timestamp=2012-01-12 21:48:47)}> > Jookyn wrote: > > babca_ wrote:Ahoj > > > > > 15) Obsahuje grupa S_6(skladani) podgrupu radu a) 5 b) 8 ? > > > > U b) Dle lagrange rad podgrupy deli rad grupy, rad S_6 je 6! = 6*5*4*3*2*1 a tedy 8 | 6! => B) Ano > > > > Je to pravda? O:-) > > Myslim si, že neni a že argument, proč podgrupa neexistuje je v původním příspěvku správně... > > Podle mě je úvaha chybná protože Langangeova věta neni postačující podmínka pro existenci podgrupy řádu k|n, ale pouze nutná. > Pak tam sice byla věta, že pro každé k|n existuje práve jedna podgrupa řádu k, jenže to bylo pouze pro cyklické grupy. > > Kdyžtak mi pls někdo opravte, pokud se v něčem mýlim... Jo mas pravdu, ta jednoznacnost je jenom pro cyklicke grupy. Dekuji za opravu :) <{/ForumPost}> <{ForumPost(poster="Mirek", timestamp=2012-01-12 22:00:41)}> Mohli byste mi, prosím, vysvětlit, jak se počítá 14) počet homomorfismů? Díky <{/ForumPost}> <{ForumPost(poster="Mirek", timestamp=2012-01-12 22:01:53)}> > Mirek wrote:Mohli byste mi, prosím, vysvětlit, jak se počítá 14) počet homomorfismů? Díky Tak po refreshi se to zdá zbytečné :) <{/ForumPost}>