Simboli kao skupovi?

---------- Forwarded message ----------
From: Veky <vedgar@gmail.com>
Date: Dec 11, 2005 4:18 PM
Subject: Re: Simboli
To: Konrad

On 12/9/05, Konrad wrote:

Zanima me kako bi mogli skupovno definirali slova?

Slova su elementi skupa
{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}.
;-]]

Ili opcenito, bilo kakve simbole?

Hmda. Teorija skupova se obično bavi definicijama matematičkih objekata pomoću skupova. Simboli, koliko god to čudno zvučalo, a priori nisu matematički objekti -- već su na neki način metaobjekti, objekti jezika koji nam služe za označavanje nekih konkretnih matematičkih objekata.

U redu, jezik se može matematički definirati (unutar logike), pa se tamo mogu definirati i simboli, no takve definicije su obično suhoparne poput ove gornje (definicija "slovâ"). That is, obično se kaže: podrazumijevamo da imamo skup logičkih simbolâ (simboli za negaciju, disjunkciju, univerzalni kvantifikator, jednakost, dvije zagrade i zarez), te imamo još "neki skup" simbolâ, koje dijelimo na konstantske, funkcijske i relacijske. Nigdje se ne kaže što su oni točno, i kad nam npr. zatreba novi funkcijski simbol, uzmemo oznaku f0, f1, f2, ili već prvu sljedeću slobodnu. Razlog za takvo nešto je upravo proizvoljnost koja se vidi iz ovog tvog "ipak" na kraju:

Recimo, meni pada na pamet nekakav ASCII ili cak Unicode kod, ali ipak ...

... jer se ne možemo oteti dojmu da su ASCII, Unicode, ili bilo što drugo, samo grube aproksimacije onog što smatramo simbolima, i uz to su užasno proizvoljne. Zašto imati simbole WHITE FROWNING FACE, WHITE SMILING FACE i BLACK SMILING FACE, ali ne i BLACK FROWNING FACE? I zašto bi uskličnik dolazio prije plusa?

Jeli pojam 'biti simbol' isto tako elementaran kao npr. pojam 'biti skup' u naivnoj TS?

Ne bih rekao da je elementaran (jer u logici se poprilično raščlanjuje ovisno o svojoj funkciji u jeziku), nego da jednostavno nije matematički. Za neke metamatičke objekte (kolekcija) imamo dobre aproksimacije (skup, klasa), za neke druge (istina) imamo koliko-toliko zadovoljavajuće aproksimacije (dokazivost), dok za neke (simboli) imamo samo vrlo proizvoljne reprezentacije (ordinalni kodovi, Unicode, Gödelovi brojevi) koje se promatraju samo u specijaliziranom kontekstu.

Dali bi se moglo nekako skupa 'zakodirati' i simbol i njegovo značenje?

Jednom kad bismo imali zadovoljavajuću matematičku reprezentaciju simbola, rekli bismo jednostavno "uređen par kojem je prva komponenta simbol, a druga matematički objekt kojeg taj simbol označava".

--
~Veky

Aksiomi TSa

---------- Forwarded message ----------
From: Veky <vedgar@gmail.com>
Date: Dec 11, 2005 3:55 PM
Subject: Re: Aksiomi TS-a
To: Ana

On 12/11/05, Ana wrote:

Hej,
na predavanjima je Guljas spomenuo aksiom poptunosti,ali nigdje nismo
rekli sto je to,a nema niti u Papicevoj knjizi.....
Na vjezbama u petak si spomenuo aksiom temeljnosti.....Ni to nerme naci
nigdje...
Mozes mi reci sto kazu ta 2 aksioma?
Na predavanjima smo radili samo aksiom ekstenzionalnosti,praznog
skupa,partitivnog skupa,para,unije,separacije i izbora.....

Hm... ajmo redom.
Aksiom potpunosti nije aksiom teorije skupova, već analize. Aksiomi teorije skupova opisuju strukturu kumulativne hijerarhije, koja u sebi uključuje sve skupove koji nam trebaju. Aksiomi analize (i drugih matematičkih granâ) opisuju strukturu izgrađenu na jednom konkretnom skupu (za analizu, skupu realnih brojeva ℝ).
Za Teoriju skupova, aksiom potpunosti ("svaki neprazan skup koji ima gornju među, ima supremum") ima značenje, ali ne kao njen aksiom, već kao tvrdnja koju neki TUSovi zadovoljavaju, a neki ne — i predstavlja invarijantu sličnosti, dakle učinkovit način da razlikujemo uređajne tipove (na primjer, za λ vrijedi aksiom potpunosti, dok za λ+λ ne vrijedi — dakle, λ+λ≠λ, odnosno ℝ×2≄ℝ).

Aksiom utemeljenosti (fundiranosti) je pak aksiom koji se odnosi na samu kumulativnu hijerarhiju, i kaže da su, efektivno, razine kumulativne hijerarhije dobro uređene, odnosno: svaki neprazni skup ima element na minimalnoj razini.
∀a(∃b(b∈a)→∃b(b∈a∧∄c(c∈b∧c∈a))
(ovaj b je "na minimalnoj razini", jer ne postoji c koji je "ispod" njega)
Odnosno, koristeći pokrate,
a≠∅→(∃b∈a)(a∩b=∅)

Nama je na vježbama trebala samo jedna jednostavna posljedica aksioma fundiranosti, a to je da nijedan skup ne može biti element samog sebe — specijalno, ω∉ω. Dokaz je jednostavan: promotrimo skup a:={ω}. On je neprazan (ω∈a), pa ima element na minimalnoj razini. No to može biti jedino ω (jer je to jedini element od a). Kad bi bilo ω∈ω, imali bismo ω∈ω i ω∈a, dakle postojao bi element od a koji je "ispod" ω (to je upravo ω), što je kontradikcija.

Od aksiomâ standardnog ZFCa u gornjem popisu još nedostaje aksiom zamjene, koji kaže da je funkcijska slika skupa ponovo skup, no tim aksiomom ćete se vjerojatno baviti kasnije.
Pregled aksiomâ možeš naći na http://en.wikipedia.org/wiki/Zermelo-Fraenkel_set_theory .
HTH,
--
~Veky

Koliko ima mogućih rješenjâ kvadratne nejednadžbe?

---------- Forwarded message ----------
From: Veky <vedgar@gmail.com>
Date: Dec 12, 2005 7:13 PM
Subject: Re: Zadatak za domacu zadacu
To: pipi_in_melkijad

On 12/12/05, pipi_in_melkijad wrote:

Mozete li nam pomoci sa sljedecim zadatkom:
Koliko ima skupova rjesenja kvadratne jednazbe

Valjda nejednadžbe. :-) 

a*x^2+b*x+c>0, za a, b, c iz  |R?
Hvala!

Sjećate se zadatka "koliko ima intervala (svih vrsta) u |R"? Ovo ide slično.
Mogući skupovi rješenja su:

1. <-oo,x1>U<x2,+oo> (ako je diskriminanta pozitivna, te a pozitivan). Tome pridružimo (1,x1,x2).
2. |R\{x0} (ako je diskriminanta jednaka 0, te a pozitivan). Tome pridružimo (2,x0,0).
3. |R (ako je D<0 i a>0). Tome pridružimo (3,0,0).
4. <x1,x2> (ako je D>0 & a<0). Tome pridružimo (4,x1,x2).
5. 0 (prazan skup) (ako je D<=0, i a<0). Tome pridružimo (5,0,0).

Vidimo da imamo funkciju sa traženog skupa (S) u skup |R^3. To je injekcija (dokažite!), pa je
cardS<=card|R^3=c^3=c^2*c=c*c=c^2=c (kontinuum).

S druge strane, za svaki r iz |R, promotrimo kvadratnu nejednadžbu x^2-2rx+r^2>0. Njen skup rješenja je očito |R\{r}. Dakle, različitim r-ovima odgovaraju različiti skupovi rješenja, odnosno imam injekciju s |R u S. Dakle
card|R=c<=cardS,

što zajedno s gornjim daje cardS=c.
HTH,
--
~Veky

Koliko ima podskupova od |R koji sadrže |N?

---------- Forwarded message ----------
From: Veky <vedgar@gmail.com>
Date: Dec 12, 2005 7:21 PM
Subject: Re: Zadatak sa roka
To: Ana

On 12/12/05, Ana wrote:

Hej,
u jednom Frankim roku(gle cuda) treba naci broj poskupova od R koji
sadrze N?
Ja sam ovako razmisljala:
1.element biramo na 2^c nacina
2.element biramo na 2^c-1nacina itd......
Krajnje dobivamo umnozak neki=2^(alef0 * c)=2^c
Je to O.K. ili naravno nije?
A

Naravno. :-p
Mislim, odgovor je točan, ali 2^c-1 i slični brojevi ne postoje u standardnoj teoriji skupova. Ako se sjećate, za kardinalne brojeve smo definirali zbrajanje, množenje i potenciranje, ali oduzimanje (s razlogom) nismo. Koliko je na primjer alef0-alef0? Ako iz |N (njih alef0) izbacimo sve brojeve veće od 5 (njih alef0), dobit ćemo 5. Ako izbacimo sve brojeve veće od 123 (njih alef0), dobit ćemo 123. Ako izbacimo sve parne brojeve (njih alef0), dobit ćemo sve neparne -- njih alef0. Vidite?

Koliko nečega ima, određuje se nalaženjem bijekcije -- ili, pomoću CB teorema, dvije injekcije. U ovom slučaju:

Označimo dani skup (svih podskupova od |R koji sadrže |N) sa S. Očito je S podskup partitivnog skupa od |R, pa je
cardS<=card\P(|R)=2^c.

S druge strane, proizvoljnom podskupu A od |R^- (negativni brojevi) možemo pridružiti podskup AU|N od |R, koji sadrži |N. Dakle, imam preslikavanje sa partitivnog skupa od |R^-, u S. To preslikavanje je injekcija (ako je A1 različito od A2, tada je A1U|N različito od A2U|N -- dokažite!), pa mi je
card\P(|R^-)<=cardS.

No card\P(|R^-)=2^card|R^-, a card|R^-=card|R=c, dakle cardS>=2^c. To zajedno s gornjim daje cardS=2^c.
--
~Veky

RPU vs. IPU

On 12/12/05, Petra wrote:

    Evo već jedno vrijeme me mući jedan zadatak iz teorije skupova rješen na vježbama.Kad sam to pitanje postavila kolegama samo sam sve uspjela zbuniti tako da vas molim za pomoć.Zadatak je glasio:Zadan je R PUS(N\{ 0.1},|). Odredite(ako postoji) najmanji,najveći,minimalni i maksimalni elemenat. U rješenju je da su minimalni elementi prosti brojevi,a kada bi bio I PUS onda nebi bilo minimalnih elemenata.

? Mislim da to nisam rekao, a ako jesam, ispričavam se. :-(

Je li nešto IPU ili RPU, ne utječe na to hoće li u PUSu biti minimalnih elemenata. Minimalni element se definira kao element a∈A PUSa (A,<) (ili (A,≤)), takav da je ne postoji b∈A takav da je b<a. Primijetite da piše b<a neovisno o tome gledamo li (A,<) ili (A,≤). Jedina razlika je što bi u slučaju (A,<) direktno imali što znači b<a (to znači da je uređen par (b,a) element relacije <), a u slučaju (A,≤) bismo b<a morali definirati preko relacije ≤ (to znači, (b,a) je u relaciji ≤, i ne vrijedi a=b).

Dakle, u našem (R)PUSu (ℕ\{0,1},|) minimalni elementi su prosti brojevi. Da smo imali IPU, zadan s
a⊰b :⇔ a|b ∧ a≠b ("stroga djeljivost"),
opet bi minimalni elementi bili prosti brojevi. To je efektivno jedan te isti PUS, samo se njegove reprezentacije razlikuju po tome što je u njima zadano.

U vježbama online ima detaljnije o vezi između RPUova i IPUova.

HTH,
--
~Veky

Neki jednostavni zadaci s kardinalnim brojevima

On 12/1/05, j.antolic wrote:

BOK! IMAM PAR PITANJA IZ TEORIJE SKUPOVA:

Hm. Prvo, CAPS LOCK nije pristojan u modernoj email komunikaciji. Smatra se vikanjem.

All caps in Email is widely understood to be shouting or yelling at someone.

1. KAK DA DOKAŽEM 2 na C=(n!)na c, n>2

Prvo pogledajte (2^𝔠)^𝔠=2^(𝔠·𝔠)=2^𝔠. I onda, za svaki broj a između 2 i 2^𝔠 (dakle specijalno n! za n prirodan i veći od 2),
2≤a≤2^𝔠 dignete na 𝔠, i dobijete (monotonost potenciranja)
2^𝔠≤a^𝔠≤2^𝔠. Dakle a^𝔠=2^𝔠.

(treći zadatak na strani 23 u online vježbama ilustrira nešto slično).

2. KOLIKO IMA REALNIH NIZOVA ČIJI JE LIMES JEDNAK a, a
CIJELI BROJ

Općenito, svih realnih nizova ima 𝔠^ℵ₀=𝔠. Dakle, ako skup čiji kardinalitet tražite označite s A, imate card(A)≤𝔠.

S druge strane, nije problem konstruirati za svaki realan broj x, po jedan niz iz A: (x,a,a,a,a,....). Dakle card(ℝ)≤card(A), odnosno card(A)=𝔠.

3. KOLIKO IMA MOGUČIH RJEŠENJA KVADRATNE JEDNADŽBE

Mislite valjda skupove rješenja? U ℝ, moguća su tri slučaja.

1. diskriminanta manja od nule. tada nema rješenja, odnosno skup rješenja je prazan. - jedna mogućnost.
2. diskriminanta jednaka nuli. tada je rješenje jedinstveno, odnosno skup rješenja je singleton {x}, za proizvoljan realan x - 𝔠 mogućnosti.
3. diskriminanta veća od nule. tada ima dva rješenja, odnosno skup rješenja {x1,x2} je proizvoljan dvočlani podskup od ℝ. Lako se vidi da i tada ima 𝔠 mogućnosti.
   

Sveukupno (gornji slučajevi su disjunktni) 1+𝔠+𝔠=𝔠 mogućnosti.

U ℂ (kompleksnim brojevima), vjerujem da sada možete sami riješiti. Ako bude problema, pitajte.

Sume do ω∙3, i računanje kofinalnosti ordinalâ

On 11/24/05, Ksenija wrote:

1. Kad kod ordinalnih brojeva imamo sumu po i iz omega*3 koje
slucajeve treba razmotriti - kod sume po omega*2 smo gledali supremum po alfa i imali slucajeve n i omega+n;

Mala ispravka: to baš i nisu "slučajevi": između njih nije "ili", nego "plus". Odnosno, oba ulaze u rezultat istovremeno, i zbrajaju se. (To što će ovaj prvi obično biti manji od ovog drugog, pa će se apsorbirati tipa 1+ω=ω, je druga stvar.)

da li za omega*3 promatramo iste te slucajeve i slucaj omega+omega+n ili nesto sasvim drugo?

Upravo tako. ω∙2={0,1,2,....,ω,ω+1,ω+2,....}. Dakle u ω*2 se nalaze dvije kopije od ω: jedna "normalna" ({0,1,2,....}), i jedna translatirana za ω ({ω+0,ω+1,ω+2,....}). Ako sad sumu rastavimo na dvije sume, i u ovoj drugoj pomaknemo indeks (stari_i=novi_i+ω), te iskoristimo definiciju po kojoj je suma do ω upravo supremum po n svih parcijalnih sumâ do n, dobijemo točno ovo što ste napisali.
Jednako tako i za
ω∙3={0,1,2,....,ω,ω+1,ω+2,....,ω∙2,ω∙2+1,ω∙2+2,....}.

Zapišimo to i simbolički:
∑{i∈ω∙3}f(i)=

∑{i∈{0,1,2,....}}f(i)+
+∑{i∈{ω,ω+1,ω+2,....}}f(i)+
+∑{i∈{ω∙2,ω∙2+1,ω∙2+2,....}}f(i)=
=∑{i∈ω}f(i)+
+∑{i∈ω}f(ω+i)+
+∑{i∈ω}f(ω∙2+i)=
=sup{n∈ω}∑{i∈n}f(i)+
+sup{n∈ω}∑{i∈n}f(ω+i)+
+sup{n∈ω}∑{i∈n}f(ω∙2+i) .

2. kofinalnost ordinalnog broja - iz definicije mi nije jasno kako
izracunati cf od nekog konkretnog ordinalnog broja, npr. cf(10) ili
cf(omega)

Da, definicija je malo čudna. ☺
Intuitivno, kofinalnost od α je jednostavno odgovor na pitanje "koliko nam ordinalâ treba da dostignemo α odozdo", odnosno preciznije, koliki je najmanji ordinalni broj skupa čiji je supremum jednak supremumu od α.

("odozdo" znači da te ordinale smijemo uzimati samo strogo manje od α, a ne od α nadalje — inače bismo naravno uvijek mogli dostići α samo pomoću jednog ordinala, α. Formalno, to znači da kodomena funkcije koju moramo naći mora biti α.
Također, treba biti svjestan da se traži najmanji takav broj: naravno, α uvijek možemo dostići odozdo sa svih α ordinalâ koji su od njega manji. Dakle, cf(α)≤α. No može biti puno manji, naravno.)

Da vidimo...

• cf(10). Gledamo 10={0,1,2,3,4,5,6,7,8,9}, i pitamo se s koliko ordinalâ to možemo dostići odozdo. Očito je dovoljan jedan, i to ordinal 9. Dakle, cf(10)=1. Formalno, ona funkcija u definiciji je f:1→10, definirana s f(0):=9.
• cf(ω). Gledamo ω={0,1,2,3,4,....}, i pitamo se s koliko ordinalâ to možemo dostići odozdo. Probajmo ih uzeti nekoliko... na primjer, 4,5,12. Očito, time smo dostigli samo do uključivo 12 (dakle ordinal 13), i jasno je da će nam se to uvijek dogoditi kad uzmemo konačno mnogo ordinalâ: od svih njih postoji najveći, i bilo što nakon njegovog sljedbenika nam je izvan dosega. Dakle, moramo ih uzeti beskonačno, a najmanji beskonačni ordinalni broj je ω: slijedi da ih moramo uzeti bar ω. Toliko ih je i dovoljno, jer ih očito možemo uzeti sve: f:ω→ω;f(i):=i. (Naravno, i da smo uzeli od nekog nadalje — na primjer, 6,7,8,9,.... — također bismo dostigli ω; no time nismo uzeli ništa manje: skup {6,7,8,9,....} je jednako tako tipa ω kao i sâm {0,1,2,3,....}.

Za domaću zadaću izračunajte cf(0), cf(28), cf(ω∙5), cf(ω²).

Rješenja:
cf(0)=0 (Prazna funkcija :0→0.)
cf(28)=1 (f:1→28;f(0)=27)
cf(ω∙5)=ω (f:ω→ω∙5;f(n)=ω∙4+n)
cf(ω²)=ω (f:ω→ω²;f(n)=ω∙n)
HTH,

--
~Veky