MatHelP

ne(ne(intuicionizam)) :-P

2011-02-15T10:45:00.000+01:00

(In response to questions on www.intuitionism.org)
For a mathematician, and especially for an intuitionist, your questions are incredibly vague, and your "explanations" even more so. I'm sorry I won't be able to provide a string for you (or I can provide [#^10], but that would of course be cheating), but I'll try to explain how I feel about each item, and you can interpret those as answers.

The question can be regarded as mildly sensible, but the explanation is lunatic. By that thinking, no functions other than constants are total (because if we don't know what x is, we never know the value of the function), and if we change the rules so drastically, even constant functions aren't surely total, because if it is possible we don't know x, what makes us think that we know which constant we have?
The way IVT is normally stated, precision never enters the picture. The theorem speaks about two lines intersecting. And it is usually explicitly said that the statement is in no way constructive. Your idea of functions as computations to some precision is practically irrelevant for this matter.
Here again you (ok, Brouwer) change the rules so drastically that the question loses any trace of sense. If the power set of a given set might not exist as a finished whole, then obviously we aren't talking about sets (or "finished wholes" are special kind of sets? If so, please define them). Let's call these objects "xets". What makes us think that xets have cardinalities in the first place, and more importantly, that they should have the monopoly on using such terms? Theory of cardinality of sets is surely more rich and structurally interesting than the theory of cardinality of xets, and if one of them is to be called just "cardinality", I know which one I'll choose.
Another problem: however you define "finished wholes", I don't think they can really be infinite. Can you give me an example of "countably infinite" xet which is not "countably infinite unfinished"? I tried to find out more about this, but only Google result for "countably infinite unfinished" was your page.
Ok, this one is interesting, quasi-meaningful, and I might even be willing to answer '+', if it weren't for the word "definite" in the question. Yes, CH is meaningful. It holds in some well-understood models of ZF, and it has many interesting consequences (CH was one of themes of my Master thesis, so I know quite a bit about it), but your "definite" seems to me as if you want to fix one particular model now and forever. I don't think math works that way. Even when we someday agree whether CH is true or false, it still won't be "definite" in that sense - we reserve the right to change our opinion.
"Many people" consider intuitionism meaningless, also. :-] The very idea that inaccessible cardinals are "so big that they are completely irrelevant for all 'normal' mathematics" is itself very useful (in 'abnormal' - or better, 'meta-normal' - mathematics:), because it gives us the way to construct models of 'normal' mathematics (for example, ZF). I'd dare say that inaccessible cardinals wouldn't be nearly as interesting to study if they didn't have the property you stated as an argument for their meaninglessness.
(Ok, I suppose this one is a '+'. Spirit of set theory demands so. If no other theory will lend it a helping hand, it must appoint its own model builders.)
This is so ridiculous I don't know where to start. At a basic level, it is the same as the old riddle "which month has 28 days", with the intended answer "every one". I mean, to a question "is it easy to build a machine..." you answer "yes, just build two machines..." I'd like to see you as a real world machine builder for some factory with tight budget, interpreting your contract in such a way. :-] The essential part of "building a machine" (especially until you actually start physically building one, which I hope is not the issue here) is obviously designing it. If you fork every time a decision is needed, I don't think it can be called "building".
Also, if such a thing is allowed, I can build a machine with any behavior at all - I just build all possible machines. [I can even build a machine to decide which one of two starting machines is the right one, and then build it.:] The question is very uninteresting (to say the least) if interpreted that way.
Contrary to wishful thinking of some wannabe formal logic popularizers, there is no semantic-preserving isomorphism between propositional logic and natural language. In particular, "\rightarrow" is not the same as "implies", even to a classical logician (I'm sure you understand that intuitionistic "\rightarrow" is also not the same as "implies"). Nor is "\vee" the same as "or", it has nothing to do with implication itself. It is just an approximation, that is nice enough to do natural deduction, resolution, and some other stuff, but fundamentally, those are different things. I think no mathematician would interpret "imply" in such a way.
So explanation is meaningless. But the question? It is interesting, and might even have '+' as an answer. Personally, I don't believe that, but I can't give you a pair ((p,q),R), such that p and q are statements, and R is a transformation that takes a pair (i,S) (such that i is 0 and S is a transformation from a proof of p to a proof of q, or i is 1 and S is a transformation from a proof of q to a proof of p) and converts it to a proof of 0=1 - and I have a gut feeling that intuitionist will accept nothing less. ;-)
There is a word missing in your question. Before "gives". Is it "usually", "always", "sometimes"...? Constructive proofs are so different beasts than most classical ones, that it's not very hard to imagine two proofs, one classical and one constructive, such that the first one gives much more insight than the second one. In fact, it is trivially true if we remember that constructive proofs are also classical proofs. So if we interpret a question as "always", the answer is a '-'. If we interpret it as "sometimes", it is obviously '+'. And if we interpret it as "usually"... well, it depends on the measure on the space of proofs. :-) But I wouldn't say so. By your "analogy", would you really say that quantum mechanics explanation of some (classical) physical phenomenon gives more insight than classical mechanic one? Maybe only to a narrowly specialized quantum physicist.
(The "analogy" above is in quotes because the inclusion is in fact opposite: quantum mechanics embodies classical one - whatever you can explain by classical, you can explain by quantum. Whatever you can prove by classical logic, you won't necessarily be able to prove using intuitionistic one.)
It depends on the notion of reasoning. Your explanation makes sense (for a change:) on one level, but there is also the notion of reasoning that distinguishes mathematicians from physicists, philosophers, artists and mystics. It is the one of formulating precise and disclosed axioms, using precise rules of inference, and preserving certainty along the way. You can say that "doing mathematics" is broader than the above, but I still think that there is something in common to all reasoning in mathematics, that defines math as a discipline, even if it can't be easily formalized.
Another interesting question with totally bogus explanation. You can't really think that number of people who accept some mathematical claim is a sensible measure of its truthfulness?! If we think like that, even preserving truth can't survive - I think many more people accept AC than Banach-Tarski theorem. :-)
And the statement in Animal Farm was obviously sarcasm... it was precisely saying that animals were not equal. I don't think you'd like such argument to apply to your question. :-]

Sorry if it seems too harsh for you, and it is quite possible that I missed the point of your test completely. But you tried to give people some provocative ideas to think about, so I thought it would be fair to give you some provocative counterarguments to think about. :-)

2011-02-14T14:28:00.002+01:00

Rješavamo x^2+y^2+z^2+3(x+y+z)+5=0 u |Q.
Ok, pretpostavimo da to čudo ima racionalno rješenje R=:(r1,r2,r3). Tada su q1:=2r1+3, q2:=2r2+3 i q3:=2r3+3 (kratko pišemo Q:=2R+3) također racionalni, i vrijedi R=(Q-3)/2, uvrštavanjem čega u početnu jednadžbu dobivamo da je -5 jednak zbroju tri izraza oblika
ri^2+3ri=((qi-3)/2)^2+3(qi-3)/2=(qi^2-6qi+9)/4+(3qi-9)/2=(qi^2-6qi+9+6qi-18)/4=(qi^2-9)/4,
pa množenjem s 4 imamo -20=q1^2-9+q2^2-9+q3^2-9, odnosno (Q|Q)=7.
Tu smo s (|) označili skalarni produkt vektora:
((v1,v2,v3)|(w1,w2,w3)):=v1w1+v2w2+v3w3. Lako se vidi da je to komutativno, nenegativno ako su faktori jednaki, distributivno prema zbrajanju, kvaziasocijativno prema množenju skalarom, i cjelobrojno ako su V i W cjelobrojni vektori.
[Primijetimo (*) da Q ne može biti cjelobrojni vektor: ne postoje cijeli brojevi q1,q2,q3 čiji zbroj kvadrata je 7. Naime, ti kvadrati moraju biti <=7, dakle 0, 1 ili 4, s tim da je 4*2=8>7, dakle četvorki može biti najviše jedna, ostali kvadrati su najviše 1. No tada je
q1^2+q2^2+q3^2<=4+2*1=6<7, pa se jednakost ne može postići.]
Sada svedimo Q=(q1,q2,q3) na zajednički nazivnik (neka je to a@|N, štoviše zbog [*] a>1), dakle Q=X/a gdje je X cjelobrojni vektor. Imamo
7=(Q|Q)=(X/a|X/a)=(X|X)/a^2, dakle (X|X)=7a^2. Zapamtimo ovu jednadžbu, trebat će nam kasnije.
Označimo s yi najbliži cijeli broj broju qi (ako je qi na pola puta između dva cijela broja, uzmemo manji), dakle qi=xi/a=yi+fi, gdje je |fi|<=1/2. Množenjem s a dobivamo xi=ayi+afi, dakle (jer su xi i yi cijeli brojevi) afi=:zi@\Z.
Sada je X=aY+Z, te naša jednadžba postaje
7a^2=(X|X)=(aY+Z|aY+Z)=(aY|aY)+(aY|Z)+(Z|aY)+(Z|Z)=a^2(Y|Y)+2a(Y|Z)+(Z|Z).
Vidimo da svi članovi osim (Z|Z) imaju faktor a, pa i (Z|Z) mora biti djeljiv s a, recimo (Z|Z)=:ab za neki b@\Z.
[U kojem intervalu se kreće b? Kako je (Z|Z)>=0 i a>0, očito je b>=0. Štoviše, b=0 bi značilo 0=ab=(Z|Z)=z1^2+z2^2+z3^2, dakle z1=z2=z3=0, odnosno X=aY, pa bi bilo Q=X/a=Y, odnosno Q bi bio cjelobrojni vektor. Po [*] je to nemoguće, dakle b>0. Također,
ab=(Z|Z)=(aF|aF)=a^2(F|F)=a^2(f1^2+f2^2+f3^2)<=a^2*3*(1/2)^2=a^2*3/4, dakle dijeljenjem s pozitivnim a dobivamo b<=3/4*a, što je strogo manje od a. Dakle b je prirodan broj strogo manji od a. To je vrlo korisno, razlog čemu će postati uskoro jasan.]
Uvrstimo (Z|Z)=ab gore, i dobivamo
7a^2=a^2(Y|Y)+2a(Y|Z)+ab, odnosno skraćivanjem pozitivnog a
a(7-(Y|Y))=b+2(Y|Z). Označimo s t:=7-(Y|Y) drugi faktor na lijevoj strani. (Primijetimo da t sigurno nije 0 zbog [*] - Y je cjelobrojni vektor.) Iz toga dobivamo 2(Y|Z)=at-b, što je korisno za računanje mješovitih produkata koji uključuju Y i Z.
Kao naprimjer: [:-)]
(tZ-bY|tZ-bY)=(tZ|tZ)-(tZ|bY)-(bY|tZ)+(bY|bY)=t^2(Z|Z)-2bt(Y|Z)+b^2(Y|Y)=
=t^2*ab-bt(at-b)+b^2(7-t)=abt^2-abt^2+tb^2+7b^2-tb^2=7b^2.
A-ha! Krenuli smo od cjelobrojnog vektora X, koji kvadriran (skalarno pomnožen samim sobom) daje 7a^2 (a je bio prirodan broj). Proučavanjem tog X dobili smo broj b, prirodni broj strogo manji od a, te cijeli broj t i cjelobrojne vektore Z i Y, takve da cjelobrojni vektor tZ-bY kvadriran daje 7b^2. Dakle, ako sa S označimo skup svih prirodnih brojeva čiji kvadrati pomnoženi sa 7 se mogu dobiti kvadriranjem nekog cjelobrojnog vektora, upravo smo vidjeli da ako je a@S, tada postoji b<a takav da je b@S. No to je jedino moguće tako da je S prazan (inače bi S kao podskup od |N imao najmanji element, a onda nitko manji od njega ne bi mogao biti u S). Dakle, nema takvog broja, odnosno (X|X)=7a^2 nema rješenja u cjelobrojnim vektorima. Pa, kontrapozicijom, ni ona jednadžba s početka nema racionalnog rješenja. Kved.
Primijetimo da smo činjenicu da se radi baš o broju 7 koristili samo u [*]. Za bilo koji broj koji nije zbroj 3 cjelobrojna kvadrata svo dalje argumentiranje izgledalo bi potpuno isto. Dakle, dobili smo zanimljiv
Božićni teorem(-: Cijeli broj je zbroj 3 racionalna kvadrata ako i samo ako je zbroj 3 cjelobrojna kvadrata.
Pitanja za razmišljanje:
* Božićni teorem očito ne vrijedi za općenite racionalne brojeve: naprimjer, 3/4=(1/2)^2*3 je zbroj 3 racionalna kvadrata, ali očito nije zbroj tri cjelobrojna. Gdje smo u dokazu koristili činjenicu da je 7 cijeli broj? :-]
* Jesmo li negdje bitno koristili činjenicu da se radi o 3 kvadrata? Drugim riječima: vrijedi li Božićni teorem za 2 kvadrata? Za 4 kvadrata? Za 1 kvadrat (taj slučaj vjerojatno znate pod nekim drugim imenom;)?

Rješenja 3. zadaće iz UM

2008-02-03T18:24:00.000+01:00

Struktura 2. kolokvija iz UM

2008-02-02T19:23:00.000+01:00

Prvi zadatak tiče se polinomâ, i dijelovi (a) i (b) ne bi trebali predstavljati nikakvo iznenađenje nekom tko je riješio 3. zadaću. 1(c) zahtijeva malo bolje poznavanje strukture prstena polinoma.

Treći zadatak je rješavanje jednadžbî, a četvrti nejednadžbî. Njihovi (a) i (b) dijelovi bi trebali biti jednostavni nekom tko je riješio 4. zadaću. Zadatak 3(c) zahtijeva trik-rješenje bazirano na svojstvima funkcijâ, dok 4(c) nije nešto posebno konceptualno težak, ali ima dosta pisanja i provjerâ.

Drugi zadatak su svojstva funkcija: (a) je provjera injektivnosti i surjektivnosti za prilično jednostavnu funkciju, (b) je ispitivanje inkluzijâ između dvije funkcijske slike (rađeno na vježbama), dok je (c) jedan od "dodatnih zadataka za zadaću za naprednije studente" koje sam zadao nakon zadataka u kojima smo ispitivali svojstva kompozicije funkcijâ.

Sretno na kolokviju!

Rješenja prve zadaće iz UM

2007-11-19T20:10:00.000+01:00

Uvod u matematiku - 1. zadaća

2007-10-25T10:07:00.000+02:00

[PDF]

Zadaća se mora predati na vježbama 5. studenog 2007. (10h)

Lokalna invertibilnost holomorfne funkcije

2007-10-06T23:57:00.000+02:00

Marko: hej. jedno pitanje o lok.inv.hol.f-je

imas lim{w'->w}((g(w')-g(w))/(w'-w))

i to ti je =

lim{z'->z}((z'-z)/(f(z')-f(z)))

sto je =lim{z'->z}((f(z')-f(z))/(z'-z))

ups

ovo zadnje ne

nego =lim{z'->z}(1/((f(z')-f(z))/(z'-z)))

ziher sam negdje fulao zagrade :)

i sad kaze, ovaj zadnji limes postoji jer je f derivabilna

u z

(htjeli smo dokazati da je g derivabilna u w)

ono sto me zanima:

Ungi pise da smo mogli lim po w' mogli zamijeniti s lim po z' jer su te f-je
homeomorfizmi (to se dokaze malo prije).

zasto je to tako? zasto moraju biti homeomorfizmi?

to se dokaze = da su f-je homeomorfizmi

da ne bi bilo da pitam nesto sto znam. :)

Veky: Pa ne moraju vjerojatno. Ali ako jesu, onda je trivijalno da možemo zamijeniti. :-)

Jer homeomorfizmi su izomorfizmi u topološkoj kategoriji.

Dakle bilo što topološki definirano (recimo limes) ostaje isto.

Marko: rekao si kategorija. :)

ne znaci mi to prevec. :)

ja bih elementarnije objasnjenje. :)

Marko: ne bih intuitivni razlog ovaj put.

bas strogo.

(ne kazem da je ovo gore objasnjenje intuitivno i ne-strogo, samo kazem da ga ne kuzim :))

Veky: Za strogi dokaz prvo trebaš strogi iskaz. :-P

"limes po z možemo zamijeniti onim po w" nije pretjerano strogo.

Uglavnom, bilo kakvo kvantificiranje po okolinama od z možemo interpretirati kao isto takvo kvantificiranje (egzistencijalno ili univerzalno) po okolinama od w. Zato što imamo preslikavanje koje je neprekidno u oba smjera. Dakle, kad god nam se u provjeri limesa pojavi "za svaku okolinu od z", na primjer, možemo reći "za svaku okolinu od w", jer unutar svake okoline od w imamo izomorfnu kopiju neke okoline od z. (definicija neprekidnosti)

Marko: :D ali i opet mi nisu jasni limesi. ne znam koje veze nepr. ima

Veky: Slažem se. Ali sam uvjeren da ti je nejasno što zapravo treba dokazati, a ne kako to dokazati. :-) Neprekidnost ti treba da možeš okoline slike zamijeniti okolinama originala.

Marko: educiraj me. :)

Veky: Ajd. Recimo da imamo topološke prostore U i V, te f i g neprekidne između U i V (f:U->V & g:V->U) koje su jedna drugoj inverz s obzirom na kompoziciju (dakle, fog=1_V & gof=1_U).

Također, imamo istaknute točku z@U i točku w:=f(z)@V. Naravno, ovo gornje znači da je i g(w)=g(f(z))=(gof)(z)=1_U(z)=z.

Trebamo dokazati: ako postoji lim{z'->z}(z'-z)/(f(z')-f(z)) i jednak je L, tada postoji i lim{w'->w}(g(w')-g(w))/(w'-w) i također je jednak L, te vrijedi i obrat.

Stvar je simetrična zamjenom f<->g i U<->V (i w<->z), tako da je dovoljno dokazati jedan smjer: drugi dobivamo iz njega upravo navedenom zamjenom.

Dakle, pretpostavimo da za svaku A oko L ("A oko L" znači "A je okolina od L") postoji B oko z takva da za sve z'@B vrijedi (z'-z)/(f(z')-f(z))@A.

Neka je C proizvoljna okolina oko L.

Po upravo navedenom (A:=C) postoji B oko z takva da za svaki z'@B vrijedi (z'-z)/(f(z')-f(z))@C.

Po neprekidnosti funkcije g, i zbog z=g(w), imamo da za svaku okolinu oko z, pa tako specijalno i za B, postoji D oko w takva da za svaki ž@D vrijedi g(ž)@B.

No kako je g(ž)@B, a za sve elemente od B vrijedi ovo iz pretprethodnog odlomka, zaključujemo (z':=g(ž)) da vrijedi (g(ž)-z)/(f(g(ž))-f(z))@C.

Ako to napišemo malo drugačije (z=g(w), f(z)=w, te f(g(ž))=(fog)(ž)=1_V(ž)=ž), vidimo da zapravo vrijedi (g(ž)-g(w))/(ž-w)@C.

I sada pogledajmo što smo napravili:

za proizvoljnu C oko L,

našli smo D oko w,

takvu da za sve ž@D,

vrijedi (g(ž)-g(w))/(ž-w)@C.

To upravo znači da je L=lim{ž->w}(g(ž)-g(w))/(ž-w).

Da smo bili pametniji, mogli smo vezanu varijablu ž nazvat i w'. :-)

I dakako, U i V moraju biti topološki potprostori od |C, ne proizvoljni - kako bih imao oduzimanje i dijeljenje. :-D

Neka sitnija pitanja

2007-09-28T22:04:00.001+02:00

From: Vedran Čačić <veky@math.hr>
Date: Sep 28, 2007 9:55 PM
Subject: Re: Teorija skupova
To: Marina

On 9/26/07, Marina wrote:

Poštovani,

molim Vas, ako možete, da mi riješite sljedeće zadatke iz Teorije skupova:

1.Neka su A i B neprazni disjunktni skupovi. Dokažite kard(AUB)=kard(Bx{0,1}).

Tvrdnja ne vrijedi. A:={1,2} i B:={3} su neprazni disjunktni skupovi, card(AUB)=card({1,2}U{3})=card{1,2,3}=3, dok je card(Bx{0,1})=card({3}x{0,1})=card{(3,0),(3,1)}=2 != 3.

((Inače, tvrdnja vrijedi ako su A i B još i ekvipotentni, odnosno postoji bijekcija f:A<->B. Tada je formulom h(x):=(x∈A?(f(x),0):(x,1)) (dakle, (f(x),0) ako je x iz A, a (x,1) za x iz B) zadana bijekcija između AUB i Bx2.))

2.Neka je X skup, S neprazan skup uređajnih relacija na X takvih da je (S, ⊆) TUS. Dokaži da je US uređajna relacija na X.

Pod "uređajnom relacijom" se ovdje vjerojatno misli parcijalni uređaj, dakle relacija koja je irefleksivna i tranzitivna.

irefleksivnost: pretpostavimo da postoji x∈X takav da je (x,x)∈US. To znači da postoji R∈S takva da je (x,x)∈R, no to je nemoguće jer su sve relacije u S irefleksivne.
tranzitivnost: neka je (x,y )∈US i (y,z)∈US. To znači da postoje R i Q iz S takve da je xRy i yQz. No kako je (S,⊆) TUS, svaka dva elementa u S su usporediva s obzirom na ⊆, pa tako i R i Q. BSOMP R⊆Q. Tada iz xRy slijedi i xQy, pa iz toga i yQz zaključujemo xQz (Q je tranzitivna, jer je parcijalni uređaj: svi u S su takvi). No kako je Q∈S, imamo Q⊆US, pa je i (x,z)∈US.

3. Neka je α redni broj. Dokažite da je 1+ α= α ako i samo ako α ≥ω.

Jedan smjer: za sve α≥ω vrijedi 1+α=α. Dokazujemo transfinitnom indukcijom po α.
Baza: 1+ω=1+sup_{n∈ω}n=sup_{n∈ω}(1+n)=sup{1,2,3,4,....}=ω.
Sljedbenici: pretpostavimo 1+k=k. Tada je 1+(k+1)=(1+k)+1=k+1.
Granični: pretpostavimo 1+m=m za sve m∈g, te da je g granični. Tada je 1+g=sup_{m∈g}(1+m)=sup_{m∈g}m=sup g=g (zadnja jednakost jer je g granični).

Drugi smjer (kontrapozicija): ako nije α≥ω, tada nije ni 1+α=α.
Dokaz: ako nije α≥ω, tada je po usporedivosti ordinala α<ω. To znači da je α prirodni broj, a kako je i 1 prirodni broj, te za zbrajanje prirodnih brojeva vrijedi komutativnost, 1+α=α+1, što je strogo veće od α=α+0 (jer je 1>0). Dakle nisu jednaki.

Pismeni iz Teorije skupova održan 07-09-14

2007-09-17T01:57:00.000+02:00

Pismeni iz Teorije skupova održan 07-09-03

2007-09-06T03:06:00.000+02:00

Rješenja:

Analiza x-gramâ

2007-03-15T21:15:00.000+01:00

#!/usr/bin/perl -w
@q=undef$/;
($sifrat=<>)=~s/\W//g;
print"$sifrat\n";
sub analyze($){
undef%f;
$f{$_}=scalar(@q=$sifrat=~/$_/g)
    for 'A'x$_[0]..'Z'x$_[0];
$f{$_} and print"$_: $f{$_}\t"
    for sort{$f{$b}<=>$f{$a}||$a cmp $b}keys%f;
print"\n"
}
analyze $_ for 1..3;
__DATA__
VIWIV IPDQF ...cyphertext deleted to protect the lazy... ;-)

Još jedan dokaz(čić?;) u PD

2007-01-30T08:44:00.000+01:00

Neki dokazi u sistemu prirodne dedukcije

2007-01-29T00:33:00.000+01:00

Zornova lema i aritmetika ordinalâ - detaljnije nego obično

2006-10-03T23:44:00.000+02:00

---------- Forwarded message ----------
From: Veky <vedgar@gmail.com>
Date: Oct 3, 2006 11:32 PM
Subject: Re: Pitanje
To: Mario

On 10/3/06, Mario wrote:

Zamolio bih vas da mi ipak raspisete 5.zadatak sa
zadnjeg roka

Neka je (A,<) proizvoljni TUS. Označimo sa S skup svih u sebi gustih podskupova od A. Kako je A TUS, u njemu nema neusporedivih elemenata, pa ni u jednom njegovom podskupu nema neusporedivih elemenata: dakle, svaki element G od S je također TUS. Za takve TUSove "gust u sebi" znači da za svaka dva elementa x i y iz G, takve da je x<y, postoji element z iz G takav da je x<z<y.

Prvo, za sve elemente praznog skupa vrijedi bilo što, pa je prazan skup svakako gust u sebi. Kako je prazan skup uvijek također i podskup od A, vrijedi da je prazan skup element od S, pa je S neprazan. S je očito parcijalno uređen relacijom "biti podskup" (ta relacija je uvijek refleksivna, antisimetrična i tranzitivna). Dakle, imamo neprazan, parcijalno uređen skup.

Uzmimo proizvoljni lanac L u S. Primijetimo da, kako su u S svi elementi bili podskupovi od A, tako će i svi elementi od L biti podskupovi od A. Unija tog lanca (svih skupova u tom lancu) UL je očito gornja međa za L (nadskup od svakog elementa od L). Također, svaki element od UL nalazi se u nekom elementu G od L, pa se nalazi i u A (jer je G kao element od L podskup od A). To znači da je UL podskup od A.

Neka su x i y proizvoljni elementi od UL takvi da je x<y. Kako je x u UL, postoji element X lanca L u kojem se nalazi x. Također, y je element nekog (možda drugog) elementa od L, kojeg označimo s Y. Sada, kako je L lanac, a X i Y njegovi elementi, X i Y su usporedivi (s obzirom na relaciju koja uređuje L, dakle "biti podskup"). To znači da je X podskup od Y, ili Y podskup od X.

Ako je X podskup od Y, tada x, kao element od X, mora biti i u Y. Tada imamo x i y elemente od Y, a na početku smo uzeli da je x<y. Kako je Y u lancu L, a L je podskup od S, gdje se nalaze u sebi gusti podskupovi od A, i Y je takav: Y je u sebi gust podskup od A. To znači da su x i y elementi od A, te da postoji element z u Y takav da je x<z<y. z se nalazi u Y, a Y se nalazi u L, dakle z je element od UL.

Ako je pak bio Y podskup od X, također možemo ponoviti prethodni odlomak, samo zamijenimo X i Y. Zaključujemo da se između svaka dva različita elementa iz UL nalazi element iz UL, pa je UL u sebi gust. Gore smo vidjeli da je podskup od A, dakle UL je element od S. Odnosno, UL je gornja međa za L u S, pa kako je L bio proizvoljan, zaključujemo da svaki lanac u S ima gornju među u S.

To, zajedno s ovim što smo vidjeli gore -- S je neprazan parcijalno uređen skup -- znači da su ispunjeni uvjeti Zornove leme za S, pa u S postoji (bar jedan) maksimalni element. Ako pogledamo koji su elementi u S, vidimo da je taj maksimalni element upravo maksimalni podskup od A koji je u sebi gust, čije postojanje smo trebali dokazati. QED

i jos imam pitanje iz ordinalnih brojeva
da mi pojasnite zasto je (w+alfa)*w=w^2

Well... nije za sve alfa. Ali za alfa<omega^2, jest. Naime, tada je alfa oblika omega*i+j, za neke prirodne i i j -- pa je omega+alfa=omega+(omega*i+j)=[asocijativnost zbrajanja](omega+omega*i)+j=[lijeva distributivnost * prema +]omega*(1+i)+j. Taj ordinal je očito veći od omega*(i+1) (i+1=1+i jer su i i 1 prirodni brojevi, a za njih vrijedi komutativnost zbrajanja), a manji je (jer je j<omega) od omega*(1+i)+omega=[lijeva distributivnost]omega*(1+i+1)=[i je prirodni broj]omega*(i+2).

Kako je množenje ordinalâ rastuće, (nestroge) nejednakosti omega*(i+1)<=omega+alfa<=omega*(i+2) se čuvaju množenjem zdesna s omega, pa imamo (omega*(i+1))*omega <= (omega+alfa)*omega <= (omega*(i+2))*omega. Lijeva strana je po asocijativnosti množenja omega*((i+1)*omega). Kako su i i 1 prirodni brojevi, i njihov zbroj i+1 je prirodan, a svaki prirodan broj pomnožen s omega daje omega (napravljeno na vježbama). Dakle, lijeva strana je omega*omega=omega^2. Analogno se dobije i za desnu stranu, zamjenom 1 s 2 svuda.

Zaključujemo da je omega^2<=(omega+alfa)*omega<=omega^2, pa mora biti (omega+alfa)*omega=omega^2.

i sup(w^2*n +w*n + n)= w^3.

(Pretpostavljam da je supremum po n iz omega.) Svaki član niza na lijevoj strani ima n<omega, pa je omega*n+n<=omega*n+omega=omega*(n+1), a kako je i n+1 onda prirodan, to je manje ili jednako omega*omega=omega^2. Jednako tako, onda je omega^2*n+omega*n+n< =omega^2*n+omega^2=omega^2*(n+1), što je manje ili jednako od omega^2*omega=omega^(2+1)=omega^3. Dakle, omega^3 je gornja međa niza koji se pojavljuje na lijevoj strani.

Pokažimo da je to i najmanja gornja međa -- dakle, supremum. Pretpostavimo da postoji neka strogo manja, i označimo je s beta. Po definiciji, omega^3=omega^(2+1)=omega^2*omega= omega^2*sup{n<omega}n=sup{n<omega}omega^2*n. To znači da za svaki ordinal strogo manji od omega^3 (pa tako i za beta) postoji neki član niza omega^2*n koji se nalazi između njih. Dakle, postoji prirodni n takav da je beta<omega^2*n, a to je pak manje ili jednako od omega^2*n+omega*n+n.

Dobili smo da za svaki beta<omega^3 postoji član našeg niza na lijevoj strani koji je strogo veći od beta, pa beta nikad nije gornja međa tog niza. Kako smo vidjeli da omega^3 jest gornja međa tog niza, proizlazi da je to najmanja gornja međa, dakle supremum.

--
~Veky

Rješenja pismenog ispita iz Teorije skupova 06-09-15

2006-09-30T12:21:00.000+02:00

1. Ako je S skup čiju kardinalnost tražimo, vrijedi S⊆ℂ, pa je cardS≤cardℂ=c. S druge strane, svakom realnom broju x∈[0,2π> možemo (injektivno) pridružiti kompleksan broj e^ix modula 1∈ℚ. To znači i cardS≥card[0,2π>=c, pa je cardS=c.
2. Očito ih ima najviše koliko i svih funkcijâ s ℝ u ℝ, dakle ≤c^c=2^c. S druge strane, svakoj funkciji f s ℝ₀⁻ u ℝ možemo pridružiti f∪(rd|_ℝ⁺), gdje je rd funkcija "razlomljeni dio", rd(x):=x-⌊x⌋. Tako dobivena funkcija očito poprima svaku vrijednost y∈<0,1> beskonačno mnogo puta (bar u svim točkama skupa ℕ+y), i pridruživanje je injekcija jer ako se dvije funkcije razlikuju na ℝ₀⁻, tada se razlikuju i na ℝ. Dakle, naših funkcija nema manje nego svih funkcijâ s ℝ₀⁻ u ℝ, a to je opet 2^c. Zaključak: ima ih točno 2^c.
Tražimo sumu S:=∑_i∈ω+1α_i, gdje je α_i:=∏_j∈ω+1(ω²+ω⋅i+j)= ∏_j∈ω(ω²+ω⋅i+j)⋅(ω²+ω⋅i+ω). Svi faktori se nalaze između ω² i ω³, pa se ovaj početni produkt (po j∈ω) nalazi između (ω²)^ω=ω^2⋅ω=ω^ω i (ω³)^ω=ω^3⋅ω=ω^ω — dakle, jednak je ω^ω. Tada je α_i=ω^ω⋅(ω²+ω⋅i+ω)= ω^ω+1⋅(ω+i+1) (možemo izlučivati slijeva), pa je S=∑_i∈ω+1(ω^ω+1⋅(ω+i+1))= ω^ω+1⋅∑_i∈ω+1(ω+i+1). Ova posljednja suma je ∑_i∈ω(ω+i+1)+(ω+ω+1), čiji je prvi dio ω², pa je S=ω^ω+1⋅(ω²+ω⋅2+1).
Nijedna inkluzija ne vrijedi općenito (iako za svaki takav A vrijedi bar jedna od njih — pokušajte to dokazati!), kao što pokazuju sljedeći kontraprimjeri:
- Za A={0,{1}}, imamo ⋂A=0∩{1}=0, pa je i ⋃⋂A=⋃0=0. S druge strane je ⋃A=0∪{1}={1}, pa je ⋂⋃A=⋂{1}=1⊈0.
- Za A=(1,0)={{1},2} imamo po definiciji uređenog para ⋃⋂A=1, dok je ⋃A={1}∪{0,1}={0,1}, te ⋂⋃A=0∩1=0⊉1.
Primjeri skupova uređenih standardno (antileksikografski) s danim uređajnim tipovima su S₁:=ℤ⁻×{0}∪ℤ×ℕ×{1} i S₂:=ℤ×ℤ⁻×{0}∪ℕ×{1}. Ako pokažemo da S₁≄S₂, znat ćemo da su ta dva tipa različiti.
Svaki element od S₁ je par — uređene trojke shvaćamo ovdje kao (a,b,c):=((a,b),c) — i ako je to (x,y), razlikujemo dva slučaja, ovisno o y.
Ako je y=0, mora biti x<0, pa je (x-1,0)∈S₁ neposredni prethodnik od (x,0)=(x,y). Ako je pak y=1, mora x biti par, x=(u,v), i tada je ((u-1,v),1) opet neposredni prethodnik od ((u,v),1)=(x,y). Dakle, u S₁ svaki element ima neposrednog prethodnika.
S druge strane, (0,1)∈S₂, ali svaki njegov prethodnik u S₂ mora biti oblika ((u,v),0), pa je ((u+1,v),0) u S₂ između ((u,v),0) i (0,1) — dakle, (0,1) nema neposrednog prethodnika u S₂. Kako je "svaki element ima neposrednog prethodnika" invarijanta sličnosti, S₁ i S₂ nisu slični, pa su ω^*+π⋅ω i π⋅ω^*+ω različiti uređajni tipovi.
Standardno, primjenom Zornove leme. Skup svih konveksnih podskupova od S je neprazan (∅⊆S je konveksan), uređen standardno relacijom ⊆, i u njemu svaki lanac ℒ ima gornju među ⋃ℒ koja je trivijalno ⊆S, treba još pokazati da je konveksna. Ako su sad X i Y dvije proizvoljne točke iz ⋃ℒ, postoje A i B iz ℒ takvi da je X∈A∧Y∈B, pa su zbog usporedivosti od A i B oba u jednom, recimo A. Sada, kako je A konveksan, čitava dužina XY je podskup od A, pa tako i od njegovog nadskupa ⋃ℒ.
Po Zornovoj lemi, postoji maksimalni konveksni podskup od S, odnosno konveksna skela.
Primjer za nejedinstvenost: za S:={(0,0),(1,0)}⊆ℝ², svaki njegov jednočlan podskup je očito konveksna skela od S: jednočlan skup je uvijek konveksan, a i maksimalan je jer jedini njegov pravi nadskup, S, nije konveksan.

Je li nula paran broj?

2006-09-14T09:55:00.000+02:00

From: Veky <vedgar@gmail.com>
Date: Sep 14, 2006 9:47 AM
Subject: Re: Nula
To: demi lucy

On 9/14/06, demi lucy wrote:

Je li nula paran ili neparan broj?

Da vidimo prvo što znači "paran".

Što je zajedničko brojevima 2,4,18,42,...., a da to svojstvo s njima ne dijele brojevi 1,3,13,257,....? Možemo se izvući na zadnju znamenku, no znamo da zadnja znamenka ionako ovisi o brojevnom sustavu u kojem računamo. To što znamenaka ima onoliko koliko imamo prstiju na obje ruke zajedno, očito nije matematička, već biološko-psihološka činjenica. Htjeli bismo da definicija parnosti ipak bude malo univerzalnija.

Naravno, definicija koja ne ovisi o brojevnom sustavu je "broj je djeljiv s 2". Time smo definirali što mislimo pod "broj je paran", samo što sada moramo definirati što znači "biti djeljiv s". (Za "dva" pretpostavljamo da znamo što znači.:)

Broj je djeljiv s nekim drugim brojem ako se njime može podijeliti bez ostatka. Teorem o dijeljenju (u cijelim brojevima) kaže da za svaki broj a ( djeljenik) i svaki broj različit od nule b (djelitelj -- znamo da nulom ne možemo dijeliti) postoje jedinstveni brojevi q ( količnik) i r (ostatak) takvi da vrijedi q*b+r=a. Ako je dijeljenje bez ostatka, znači da je r=0, pa mora biti q*b=a za neki q. To sada može poslužiti kao definicija djeljivosti i u slučaju b=0, no to nas ovdje neće zanimati -- nama treba slučaj a=0.

Došli smo do definicije (u cijelim brojevima) "a je djeljiv s b ako i samo ako postoji q takav da je a=b*q". Specijalno, nula je djeljiva s dva ako i samo ako postoji q takav da je 0=2*q. Postoji li takav q? Naravno da da: 0=2*0, pa cijeli broj q=0 zadovoljava tu jednakost -- odnosno, nula je djeljiva s dva, pa je paran broj.

Inače, više o djeljivosti možeš naći na http://web.math.hr/~veky/em/vjezbe/djeljivost.html.
HTH,
--

~Veky

Rješenja pismenog ispita iz Teorije skupova 2006-09-04

2006-09-14T00:49:00.000+02:00

1. Skup svih takvih označimo sa S. S je podskup od ℘(ℝ), pa vrijedi cardS≤2^c. S druge strane, preslikavanje f:℘([0,1])→S;A↦A⋃[2,3] je injekcija (presjekom s [0,1] dobijemo original, a za svaki A je ℝ~[2,3]⊆A⋃[2,3]⊆ℝ, pa je po Cantor-Bernsteinovoj lemi ℝ~A⋃[2,3]), pa je i 2^c=card℘([0,1])≤cardS. Dakle, ima ih koliko i svih podskupova od ℝ, 2^c.
2. Svaki konstantan niz je takav, pa ih ima ne manje nego konstantnih nizova u ℕ, dakle prebrojivo. S druge strane, jer je ℕ dobro uređen, svaki niz u ℕ poprima najmanji element (recimo da ga prvi put poprima u indeksu k — primijetimo da ovdje još jednom koristimo dobru uređenost od ℕ, ovaj put kao domene niza), a ako je padajući, nakon indeksa k mora biti stacionaran: i>k⇒a_i=a_k. Ako sad svakom takvom nizu (a_i)_i∈ω pridružimo konačni niz (a_i)_i≤k, dobit ćemo injekciju: iz slike je trivijalno reorganizirati original, samo posljednji element ponovimo još beskonačno mnogo puta. Dakle, gornja ograda za naš kardinalni broj je cardℕ^*=ℵ₀, pa zaključujemo da padajućih nizova u ℕ ima prebrojivo.
Sumand za konačne indekse iznosi i⋅ω+ω⋅i=ω+ω⋅i=ω⋅(i+1), pa tom dijelu sume odgovara ω⋅∑_i∈ω(i+1)=ω⋅ω=ω². Na to treba još nadodati ω⋅ω+ω⋅ω=ω²⋅2, zatim (ω+1)⋅ω+ω⋅(ω+1)=ω²+ω²+ω=ω²⋅2+ω, i još (ω+2)⋅ω+ω⋅(ω+2)=ω²+ω²+ω⋅2=ω²⋅2+ω⋅2, tako da je krajnji rezultat ω²+ω²⋅2+ω²⋅2+ω+ω²⋅2+ω⋅2=ω²⋅7+ω⋅2 (ω se apsorbira u ω²⋅2).
Ako je x∈⋃A², postoji neki element p∈A² takav da je x∈p. Svaki element od A² je uređen par elemenata od A, pa je tako i p=(a,b)={{a},{a,b}} za neke a i b iz A. Sada x∈p znači x={a}∨x={a,b}. U svakom slučaju x⊆A, dakle x∈℘(A). Zaključak: vrijedi ⋃A²⊆℘(A).
Druga inkluzija nikada ne vrijedi, jer je uvijek ∅∈℘(A), ali ∅ nikada nije uređeni par (svaki uređen par ima 1 ili 2 elementa).
irefleksivnost:
Pretpostavimo da je A⊆ω takav da je A⊏A. To bi značilo da postoji n∈A\A=∅, a to je očito nemoguće.
tranzitivnost:
Neka je A⊏B i B⊏C. To znači da postoje m∈B\A takav da je A∩m=B∩m, i n∈C\B takav da je B∩n=C∩n. Kako je m∈B, a n∉B, zaključujemo m≠n, a kako su m i n prirodni brojevi, vrijedi m<n (dakle m⊂n, također i m∈n) ili m>n (dakle m⊃n, pa i m∋n). (Napomena: ovo nije trivijalno simetrična situacija, dakle ne možemo BSO pretpostaviti jednu od tih mogućnostî — trebamo dokazati A⊏C za svaku od njih.)
U prvom slučaju je m=n∩m, pa je C∩m=C∩(n∩m)=(C∩n)∩m= (B∩n)∩m=B∩(n∩m)=B∩m=A∩m. Također vrijedi m∈B∩n=C∩n⊆C∧m∉A, dakle postoji m∈C\A takav da je C∩m=A∩m, odnosno vrijedi A⊏C.
U drugom slučaju je n=m∩n, pa je C∩n=B∩n=B∩(m∩n)=(B∩m)∩n= (A∩m)∩n=A∩(m∩n)=A∩n. Sada za n vrijedi n∈C, i još samo treba dokazati n∉A. Kad bi bilo n∈A, zbog n∈m bi vrijedilo n∈A∩m=B∩m⊆B, što je nemoguće jer je n∈C\B. Dakle, postoji n∈C\A za koji je C∩n=A∩n, pa je opet A⊏C.
totalnost:
Za proizvoljne različite podskupove od ω, A≠B, pogledajmo simetričnu razliku A△B⊆ω. Ako su A i B različiti, tada je A△B neprazan (kontrapozicija toga je aksiom ekstenzionalnosti) podskup od ω, pa zbog dobre uređenosti od ω ima najmanji element — označimo ga s x. Dakle, x∈A△B=(A\B)∪(B\A), pa zbog simetrije BSOMP x∈B\A. Ako je sada y∈x proizvoljan, tada je y<x, pa y∉A△B (x je najmanji). To znači da je y∈A⇔y∈B (za y∈x), pa je A∩x=B∩x. Dakle, postoji x∈B\A takav da je A∩x=B∩x, pa je A⊏B, odnosno A i B su usporedivi.
Označimo sa ℬ skup svih algebrî skupova ℱ⊆℘(ℝ), takvih da je ℚ∉ℱ. Skup ℱ₀:={∅,ℝ} očito zadovoljava aksiome, pa je ℱ₀∈ℬ, odnosno ℬ≠∅. ℬ parcijalno uredimo standarno relacijom ⊆.
Neka je ℒ⊆ℬ, ℒ≠∅ lanac u ℬ. Želimo dokazati postoji gornja međa za ℒ u ℬ. ⋃ℒ je uvijek gornja međa za ℒ ako je uređaj ⊆, no treba dokazati ⋃ℒ∈ℬ — odnosno, da je ⋃ℒ algebra skupova, i da ℚ∉⋃ℒ.
- Kako je ℒ neprazan, postoji ℱ₁∈ℒ. ℱ₁ je algebra skupova, pa po prvom aksiomu imamo ∅∈ℱ₁, a time i ∅∈⋃ℒ.
- Ako je A∈⋃ℒ proizvoljan, postoji ℱ∈ℒ takav da je A∈ℱ. Opet, kako je ℱ algebra skupova, mora biti i ℝ\A∈ℱ⊆⋃ℒ.
- Ako su A₁,A₂,...,A_n proizvoljni skupovi iz ⋃ℒ, postoje elementi lanca ℱ₁,ℱ₂,...,ℱ_n takvi da je svaki A_i iz odgovarajuće algebre skupova ℱ_i. Kako su sve ℱ_i međusobno usporedive, a ima ih konačno mnogo, među njima postoji ⊆-najveća — označimo je s ℱ'∈ℬ. To znači da su svi A_i iz ℱ', pa kako je ℱ' algebra skupova, vrijedi i ⋃_i∈[1..n]A_i∈ℱ'⊆⋃ℒ.
- I za kraj, pretpostavka ℚ∈⋃ℒ bi značila da postoji ℱ∈ℒ⊆ℬ takva da je ℚ∈ℱ, što je nemoguće jer je ℱ∈ℬ, a elementi od ℬ po definiciji ne sadrže ℚ kao element.
Zaključujemo da je ⋃ℒ zaista algebra skupova koje ℚ nije element, pa je ⋃ℒ∈ℬ i kao takva je gornja međa za ℒ u ℬ.
Dakle, svaki lanac u ℬ ima gornju među u ℬ, a gore smo vidjeli da je PUS ℬ neprazan, pa po Zornovoj lemi postoji maksimalni element u ℬ, što je upravo maksimalna algebra skupova nad ℝ koja ne sadrži ℚ kao element.

Rješenja pismenog ispita iz Teorije skupova 06-07-07

2006-09-13T23:23:00.000+02:00

1. Očito ih ima manje nego svih prirodnih brojeva, dakle ≤ℵ₀. S druge strane, preslikavanje n↦100ⁿ je očito injekcija (koja svakom prirodnom broju n pridružuje prirodni broj s 2n+1 znamenaka), koja pokazuje da ih ima i ≥ℵ₀. Dakle, ima ih prebrojivo mnogo.
2. Po tranzitivnosti je i A⊆ℝ, pa ih nema više nego svih parova podskupova od ℝ; dakle ≤card(℘(ℝ))²=(2^c)²=2^c⋅2=2^c. S druge strane, svakom podskupu C⊆[0,1] možemo pridružiti par (C,ℝ) koji zadovoljava uvjet, i to je injekcija (po definicijskom svojstvu uređenog para) sa ℘([0,1]) u naš skup, koja govori da je njegov kardinalitet ≥2^card[0,1]=2^c. Zaključujemo da ih ima 2^c.
Budući da je indeks sumacije sigurno manji od ω⋅3, prvi faktor u sumandu je između ω i ω⋅4, pa je sam sumand između ω⋅ω=ω² i ω⋅4⋅ω=ω⋅(4⋅ω)=ω⋅ω=ω². Drugim riječima, svi sumandi su jednaki ω², pa ω² možemo izlučiti (lijevo) izvan sume, koja onda postaje trivijalno jednaka ω⋅2+3. Rezultat je time ω²⋅(ω⋅2+3)=ω³⋅2+ω²⋅3.
Unija od ℘(A) je najveći element od ℘(A), a to je naravno A. Također, ako je x∈A, svaki element od x je i element od ∪A, pa je x⊆∪A — odnosno, x∈℘(∪A). Dakle, A⊆℘(∪A). Obrnuta inkluzija ne vrijedi općenito, npr. ℘(∪{{1}})=℘({1})={∅,{1}}⊈{{1}}.
Nisu slični: u skupu ℝ×ℚ između svaka dva različita elementa ima neprebrojivo mnogo elemenata. Ako je b<d, između (a,b) i (c,d) se nalaze npr. svi (e,b), gdje je e∈<a,+∞>. Ako je pak b=d∧a<c, između se nalaze svi (e,b) za koje je e∈<a,c>. Dok u skupu ℚ×ℝ, to ne vrijedi: na primjer, (0,0)<(1,0), ali između njih se nalaze samo parovi oblika (r,0), gdje je r racionalan broj između 0 i 1 — dakle, samo prebrojivo mnogo njih.
Budući da sličnosti čuvaju krajeve intervalâ, kao i (ne)prebrojivost, svojstvo "između svaka dva različita elementa postoji neprebrojivo mnogo elemenata" je invarijanta sličnosti po kojoj se ℝ×ℚ i ℚ×ℝ razlikuju.
Da za svaki a∈A postoji maksimalni lanac koji ga sadrži, dokazuje se standardno, Zornovom lemom (jedan lanac koji je dobar je {a}, a unija lanca dobrih lanaca je ponovo dobar lanac: sadrži a, i svaka dva elementa su usporediva). Sada, budući da ≺ nije totalni uređaj, sigurno postoje bar dva neusporediva elementa: fiksirajmo takva dva, i označimo ih s b i c. Za svakog od njih po upravo dokazanom postoji maksimalni lanac koji ga sadrži, označimo ih s B∋b i C∋c. To su zaista različiti lanci, jer npr. b∈B∧b∉C (pretpostavka b∈C bi, jer je C lanac, značila da su b i c usporedivi).

Sve žene su plavuše

2006-09-06T23:07:00.000+02:00

to: Nesi (koja nikako nije plavuša:)

Dokažimo da za svaki prirodni n, za svaku skupinu od n ženâ, vrijedi sljedeće svojstvo (PFP): ako je bar jedna žena u toj skupini plavuša, onda su sve žene u toj skupini plavuše. Dokaz ide (naravno:) matematičkom indukcijom po n. Za n=1 tvrdnja se svodi na "za svaku skupinu koja se sastoji od jedne žene, ako je jedna žena u toj skupini plavuša, onda su sve žene u toj skupini plavuše", sto je očito točno, pa je baza indukcije ispunjena. Sad pretpostavimo da sve skupine od n ženâ zadovoljavaju [PFP], i uzmimo bilo koju skupinu od n+1 ženâ, od kojih je jedna plavuša. Označimo tu plavušu sa z0, a ostalih n ženâ u toj novoj skupini sa z1..n . Ako sad gledamo skupinu ženâ z0..(n-1), vidimo da ona ima n članova, pa zadovoljava [PFP] po pretpostavci indukcije. Budući da ta skupina ima bar jednu plavušu (namely z0), slijedi da su i sve žene z1..(n-1) plavuše. Specijalno, z1 je plavuša. Sad pogledamo skupinu ženâ z1..n . Ona takoder ima n članova (članicâ:-?), pa zadovoljava [PFP]. Budući da i ta skupina ima bar jednu plavušu (namely z1), slijedi i da su sve žene z1..n plavuše. Budući da za z0 znamo već otprije da je plavuša, imamo da su sve z0..n plavuše, što daje [PFP] za sve skupine od n+1 ženâ. Budući da [PFP] vrijedi za sve 1-skupine, i iz pretpostavke da vrijedi za sve n-skupine slijedi da vrijedi za sve (n+1)-skupine, po principu matematičke indukcije slijedi da, za svaki n, [PFP] vrijedi za sve n-skupine, odnosno, [PFP] vrijedi za sve (konačne:) skupine žena. Specijalno, vrijedi i za Z0, skupinu svih žena na Zemlji. Budući da Z0 očito ima bar jednu plavušu (dokaži za vježbu:), slijedi da su sve žene u Z0, dakle, sve žene na Zemlji, plavuše." Budući da si ti (bar trenutno:) _žena_ _na Zemlji_, dakle element od Z0, slijedi da si plavuša. Priznaj!:-)

Rješenja pismenog ispita iz Teorije skupova 06-06-23

2006-07-03T13:04:00.000+02:00

1. Ako skup svih takvih skupova označimo sa S, tada je funkcija sort (koja svakom n-članom skupu pridruži n-torku njegovih elemenata uređenih po velični) injekcija sa S u ℂ^*, pa je card S≤card ℂ^*, što je c (napravljeno na vježbama). S druge strane, preslikavanje z↦{z,z+1} je injekcija sa ℂ u S, pa je c≤card S. Dakle, S je kardinaliteta kontinuum.
2. Preslikavanje f↦f(1) je bijekcija između našeg skupa i ℤ (inverzno preslikavanje cijelom broju k pridruži množenje brojem k), budući da su sve aditivne funkcije na ℤ oblika n↦k⋅n. Dakle, traženi kardinalitet je card ℤ=ℵ₀.

Traženi produkt je jednak sup_n∈ω(0⁰⋅1¹⋅2²⋅…⋅(n-1)^n-1) ⋅ω^ω⋅(ω+1)^ω+1⋅(ω+2)^ω+2. Prvi faktor je očito supremum neograničenog niza prirodnih brojeva, dakle ω. Umnožak prvog i drugog faktora je onda ω⋅ω^ω=ω^1+ω=ω^ω. Nakon toga je (ω+1)^ω+1=(ω+1)^ω⋅(ω+1), te još (ω+2)^ω+2=(ω+2)^ω⋅(ω+2)². Za i=1 ili i=2, imamo ω<ω+i<ω², pa je ω^ω≤(ω+i)^ω≤(ω²)^ω=ω^2⋅ω=ω^ω, iz čega slijedi (ω+1)^ω=(ω+2)^ω=ω^ω.
Traženi produkt sada postaje ω^ω⋅ω^ω⋅(ω+1)⋅ω^ω⋅(ω+2)². Još ponešto možemo pojednostaviti: (ω+1)⋅ω^ω se nalazi između 1⋅ω^ω i ω²⋅ω^ω=ω^2+ω=ω^ω, dakle jednak je ω^ω. Pored toga, (ω+2)²=(ω+2)(ω+2)=(ω+2)ω+(ω+2)⋅2=ω²+ω+2+ω+2=ω²+ω⋅2+2.
Dakle, rezultat je ω^ω⋅ω^ω⋅ω^ω⋅(ω²+ω⋅2+2)=ω^ω⋅3⋅(ω²+ω⋅2+2)= ω^ω⋅3+2+ω^ω⋅3+1⋅2+ω^ω⋅3⋅2.

Postoji. Da bismo to dokazali, prvo primijetimo da je s B_x:={q∈ℚ:q<x} zadana analogna familija podskupova od ℚ (budući da između svaka dva realna broja postoji racionalni, x<y zaista povlači B_x⊂B_y). Sada, ako je q:ℚ→ℕ neka bijekcija (koja postoji jer su ℚ i ℕ ekvipotentni), sa A_x označimo sliku od B_x po funkciji q. Kako je q bijekcija, gornje svojstvo se čuva.

Ako je A neprazan, po aksiomu utemeljenosti postoji a∈A koji je disjunktan s A. Kad bi a imao neki element b, po tranzitivnosti bismo imali i b∈A, što je u kontradikciji s disjunktnošću. Dakle, a je prazan skup, element od A.

Zadatak se mogao riješiti kao i obično primjenom Zornove leme, ali se u ovom slučaju primjer traženog skupa mogao i direktno naći: na primjer, <-1,1>\{0}. Taj skup je očito neprazan, ne sadrži nijedan cijeli broj, i zatvoren je na množenje. Štoviše, kada bismo ubacili bilo koji necijeli broj x unutra, budući da je 1/x već u skupu, da bismo očuvali zatvorenost na množenje, morali bismo ubaciti i 1 u skup, a tada bismo izgubili svojstvo disjunktnosti sa ℤ. Dakle, <-1,1>\{0} je maksimalan skup s traženim svojstvima.

Rješenja pismenog ispita iz Teorije skupova 2006-04-25

2006-06-21T14:22:00.000+02:00

1. Neka je S skup čiji broj elemenata tražimo. Preslikavanje f:S→ℤ²;(a₀,a₁,a₂,…)↦(a₀,a₁-a₀) je bijekcija (inverzno preslikavanje je f⁻¹:ℤ²→S;(a,d)↦(a,a+d,a+2d,a+3d,…)), dakle card S=card ℤ²=ℵ₀²=ℵ₀.
2. Budući da je prebrojivi skup ℂ_ℚ (kompleksni brojevi s racionalnim koordinatama) gust u ℂ, svaka neprekidna funkcija s ℂ u ℂ je jednoznačno zadana svojim djelovanjem na ℂ_ℚ. Odnosno, preslikavanje g↦g|_{ℂ_ℚ} je injekcija sa skupa C(ℂ→ℂ) u skup ℂ^ℂ_ℚ, pa je card C(ℂ→ℂ)≤card ℂ^ℂ_ℚ= c^ℵ₀²=c^ℵ₀=c. S druge strane, svaka konstatna funkcija je neprekidna, a njih ima koliko i kompleksnih brojeva - kontinuum. Dakle, card C(ℂ→ℂ)=c.

Ako opći faktor u produktu označimo s α_j, vidimo da je traženi produkt jednak sup_n∈ω(α₀⋅α₁⋅…⋅α_n-1)⋅α_ω.
Za konačne j je α_j=sup_m∈ω(ω^j+ω^j+1+…+ω^j+m-1). Zbog apsorpcije je suma pod supremumom jednaka zadnjem članu ω^j+m-1, pa je taj supremum α_j=ω^ω (neprekidnost potenciranja, a j+m-1 je neograničeni niz prirodnih brojeva po m).
Zadnji faktor je α_ω, suma od ω članova, koji su svi jednaki ω^i+ω=ω^ω. Dakle, sama suma je jednaka ω^ω⋅ω, odnosno α_ω=ω^ω+1.
Sve u svemu, traženi produkt je
sup_n∈ω(α₀⋅α₁⋅…⋅α_n-1)⋅α_ω=
=sup_n∈ω(ω^ω)ⁿ⋅ω^ω+1=
=(ω^ω)^ω⋅ω^ω+1=ω^ω⋅ω⋅ω^ω+1= ω^ω²+ω+1.

Budući da je ℱ familija disjunktnih nepraznih podskupova, za nju postoji funkcija izbora f:ℱ→∪ℱ. Kako su elementi familije disjunktni, f je injekcija, pa je card ℱ≤card ∪ℱ=ℵ₀. No kada bi ℱ bila konačna, njena unija - unija konačno mnogo konačnih skupova - bi također bila konačna. Dakle, ℱ mora biti prebrojiva.

U skupu ℕ×ℚ, antileksikografski uređenom, vrijedi (1,5)<(2,5), no ne postoji nijedan element iz ℕ×ℚ strogo između njih: morao bi biti oblika (x,5), gdje je x prirodan broj strogo između 1 i 2. Dakle, ℕ×ℚ nije gust, pa nije ni tipa η (gustoća je invarijanta sličnosti, a η je gust).
Skup ℚ×ℤ je prebrojiv (ℵ₀⋅ℵ₀=ℵ₀), nema najmanjeg ni najvećeg elementa (od svakog (a,b) uvijek postoji strogo veći (a+1,b) i strogo manji (a-1,b)), i gust je: neka je (a,b)<(c,d) u ℚ×ℤ. Ako je b<d, tada se (a+1,b) nalazi strogo između njih; ako je pak b=d∧a<c, tada se ((a+c)/2,b) nalazi strogo između njih. Dakle, ℚ×ℤ ispunjava uvjete uređajne karakterizacije od ℚ, pa je sličan s ℚ - odnosno, tipa je η.
Skup ℝ×ℚ je neprebrojiv (c⋅ℵ₀=c), dakle ne postoji bijekcija između njega i ℚ, pa pogotovo ne može postojati sličnost.
Zaključak: od gornja tri skupa sa standardnim (antileksikografskim) uređajem, samo ℚ×ℤ ima uređajni tip η.

Označimo s ℬ skup svih balansiranih podskupova od ℝ disjunktnih s ℚ, i uredimo ga standardno relacijom ⊆. Skup {√2} je balansiran i disjunktan s ℚ, pa je ℬ neprazan. Ako je ℒ⊆ℬ lanac, svi njegovi elementi su disjunktni s ℚ, pa je i njihova unija disjunktna s ℚ (distributivnost presjeka prema uniji). Dokažimo da je ∪ℒ također balansiran skup (to je tada gornja međa za ℒ u ℬ).
Neka su x i y proizvoljni elementi skupa ∪ℒ. To znači da postoje skupovi B i C iz ℒ, takvi da je x∈B∧y∈C. No ℒ je lanac, pa su B i C usporedivi: vrijedi B⊆C ili C⊆B. BSOMP da vrijedi B⊆C. Tada je i x∈C, pa kako je C balansiran, aritmetička sredina x i y se nalazi u C. C je element lanca, pa je podskup njegove unije - odnosno, (x+y)/2∈∪ℒ. Dakle, ∪ℒ je balansiran podskup od ℝ, disjunktan s ℚ - drugim riječima, lanac ℒ ima gornju među ∪ℒ u ℬ. To skupa s gornjim daje da su ispunjeni svi uvjeti Zornove leme, pa ℬ ima maksimalni element: maksimalni balansirani podskup od ℝ, disjunktan s ℚ.

Neke očitosti o integralima

2006-04-05T00:49:00.000+02:00

imam zadatak
odredite površinu (duljinu) domene funkcije
i kada rjesim domenu kako odredim njenu duljinu???

Ako pričamo o funkciji jedne realne varijable (što bi se dalo zaključiti na osnovu tvog poistovjećivanja površine i duljine):

domena je u većini slučajeva (disjunktna) unija (konačno mnogo) nekih intervala (bilo otvorenih, zatvorenih, poluotvorenih...), i pojedinih točaka (singletonova). Jednostavno zbroji duljine svih tih intervala. Duljina od intervala a,b (bilo [a,b], bilo [a,b>,...) je b-a .
Na primjer, duljina od [1,2>U<3,7>U{-2,0} je (2-1)+(7-3)=1+4=5 . Duljina od <-oo,-4>U[0,5] je, naravno, beskonačna.
Teoretski, možeš tako izračunati i ako imaš prebrojivo mnogo takvih intervala, samo što tada ovo "zbroji duljine" postaje izračunavanje sume reda. Npr. duljina od <-1,-1/2>U<-1/4,-1/8>U<-1/16,-1/32>U.... je 1/2+1/8+1/32+....=(1/2)/(1-1/4)=2/3 .
**
Ako se radi o funkciji više varijabli, stvari su kompliciranije. No jednom kad imaš neku razumnu karakterizaciju domene (npr. jednadžbama ili nejednadžbama), to je standardni problem "odredi površinu/volumen/.... nekog skupa", koji se onda najčešće rješava geometrijski (crtanjem i uočavanjem geometrijskih likova/tijelâ), ili u kompliciranijim slučajevima, integriranjem.

i kako odretiti povrsinu i duljinu slike neke fnkcije?

Jednakim postupkom. :-) Samo prvo sliku prikažeš kao uniju intervalâ... ili, za funkcije s višedimenzionalnom kodomenom, karakteriziraš je (ne)jednadžbama i onda to integriraš (preciznije, integriraš konstantu 1 po tom području, odnosno karakterističnu funkciju tog područja po nekom pravokutniku koji ga sadrži).

i broj siljaka?

Broj čega? [:-)]
Vjerojatno se misli na (izolirane) točke u kojima je funkcija neprekidna, ali nije derivabilna. Dobri kandidati za to su točke na kojima se susreću razna pravila definicije, za funkcije definirane po slučajevima. U svakoj takvoj točki treba provjeriti neprekidnost i derivabilnost, i na kraju prebrojiti.

Rješenja pismenog ispita iz Teorije skupova 2006-02-24

2006-03-01T12:41:00.000+01:00

1. Označimo skup beskonačnih podskupova od ℚ sa S. Očito je S⊆℘(ℚ), pa vrijedi card S≤card ℘(ℤ)=2^ℵ₀=c. S druge strane, lako je konstruirati injekciju sa ℝ u S: svakom realnom x pridružimo {y∈ℚ:y≤x}. (To je injekcija jer između svaka dva realna broja postoji bar jedan racionalan broj.) Dakle, card S≤c, što skupa s ovim gore daje card S=c.
2. Sigurno ih ima ne više nego svih segmenata u ℝ, dakle najviše kontinuum. S druge strane, svakom realnom x iz segmenta [1/4,1/3] možemo injektivno pridružiti segment [x,1/2] koji je disjunktan sa ℤ. To znači da ih ima barem koliko i realnih brojeva u segmentu [1/4,1/3], a to je kontinuum.
  Možemo i direktno: ako skup takvih segmenata označimo s T, funkcija f:ℤ×〈0,1〉×〈0,1〉→T;(m,y,z)↦[m+y⋅z,m+y] je bijekcija (dokažite).
∑_{α∈ω⋅2+2}(2+α+2^α)= ∑_α∈ω(2+α+2^α)+ ∑_α∈ω(2+(ω+α)+2^ω+α)+ (2+ω⋅2+2^ω⋅2)+ (2+(ω⋅2+1)+2^ω⋅2+1)= sup_n∈ω∑_α=0..n-1(2+α+2^α)+ sup_m∈ω∑_α=0..m-1(ω+α+2^ω⋅2^α)+ (ω⋅2+(2^ω)²)+ (ω⋅2+1+(2^ω)²⋅2)= sup_n∈ω(2+0+2⁰+2+1+2¹+...+2+n-1+2^n-1)+ sup_m∈ω(ω⋅(1+2⁰+1+2¹+...+1+2^m-1))+ (ω⋅2+ω²+ω⋅2+ω²⋅2)= ω+ω⋅sup_m∈ω(1+2⁰+1+2¹+...+1+2^m-1)+ω⋅(2+ω+2+ω⋅2)= ω+ω⋅ω+ω⋅(ω+ω⋅2)= ω²+ω²⋅3=ω²⋅4.
Tvrdnja ne vrijedi, kontraprimjer je kanonski ne-dobro uređen skup ω^*. Za njega stvarno postoji jedinstvena auto-sličnost, što nije problem dokazati matematičkom indukcijom, ili na sljedeći način: uzmemo konkretni skup tipa ω^*, recimo ℤ⁻ uređen standardno, i neka je f:ℤ⁻→ℤ⁻ sličnost. Tada, budući da je s m(x):=-x zadana sličnost između ℤ⁻ i ℤ⁺, te je kompozicija sličnosti sličnost, vidimo da je m∘f∘m sličnost između ℤ⁺ i ℤ⁺. Budući da je ℤ⁺ dobro uređen, za njega postoji jedinstvena sličnost i to je identiteta. Dakle m∘f∘m je identiteta na ℤ⁺, a onda je f identiteta na ℤ⁻. Dakle, svaka auto-sličnost od ℤ⁻ je identiteta, odnosno postoji jedinstvena takva. No ℤ⁻, naravno, nije dobro uređen, jer sâm nema najmanji element.
Promotrimo skup T:={y∈S:y≼x}. T je parcijalno uređen restrikcijom uređaja ≽, obrnutog uređaju ≼, odnosno možemo pisati da je (T,≽) PUS. Budući da imamo refleksivan uređaj, vrijedi x≼x, dakle x∈T, pa T nije prazan. Svaki lanac u T je neprazan totalno ≽-uređen podskup u T, dakle i neprazan totalno ≼-uređen podskup u S, odnosno lanac u S, pa po pretpostavci zadatka ima ≼-donju među u S; označimo je s d. Budući da je lanac neprazan, u njemu postoji bar jedan element l. Budući da je lanac u T, vrijedi l∈T, odnosno l≼x. Budući da je d ≼-donja međa za taj lanac, specijalno vrijedi d≼l, pa po tranzitivnosti d≼x, odnosno d∈T. Sada primijetimo, budući da je T uređen obrnuto od S, da je d gornja međa za naš lanac u skupu T. Odnosno, svaki lanac u T ima gornju među u T. Vidimo da su ispunjeni svi uvjeti Zornove leme za skup T, pa postoji maksimalni element u T; nazovimo ga z. Budući da je z∈T, odmah imamo z≼x. Treba još vidjeti da je z minimalan element u S (Zornova lema nam daje da je maksimalan u T). Pretpostavimo da postoji w∈S takav da je w≺z. Po tranzitivnosti bi tada bilo i w≺x, odnosno w∈T, što je u kontradikciji s maksimalnošću od z u skupu T (sjetimo se, T je obrnuto uređen). Dakle, z je stvarno minimalan element u skupu S, i vrijedi z≼x.
Neka su x i y elementi od ℕ, takvi da x ne završava znamenkom 0 (nije djeljiv s 10). Ako zadnju znamenku od x označimo s a, a prvu znamenku od y označimo s b (b:=0 ako je y=0), vidimo da je x u relaciji R s 10a+b, te je 10a+b u relaciji R s y. Dakle, x je u relaciji R² s y, pa je pâr (x,y) u tranzitivnom zatvorenju od R (svaka tranzitivna relacija koja sadrži R mora sadržavati i parove (x,y) i (y,z), a time i (x,z)). S druge strane, ako je x djeljiv s 10, on je u relaciji jedino s 0. Budući da je 0 također djeljiva s 10, svaki "lanac" oblika xRyR...Rz mora završavati nulom, odnosno za tranzitivno zatvorenje možemo dodati samo još (x,0), gdje su x djeljivi s 10. Dakle R⁺=R²=((ℕ\10ℕ)×ℕ)∪(10ℕ×{0}).

Rješenja pismenog ispita iz Teorije skupova 2006-02-10

2006-02-28T20:45:00.000+01:00

1. Označimo skup čiji broj elemenata tražimo sa S. Očito je S⊆℘(ℤ), pa vrijedi card S≤card ℘(ℤ)=2^ℵ₀=c. S druge strane, svaki podskup od ℕ je dobro uređen i podskup od ℤ. Dakle, ℘(ℕ)⊆S, odnosno card ℘(ℕ)=2^ℵ₀=c≤card S. Sve u svemu, card S=c.
2. Ako je T skup takvih funkcijâ, preslikavanje g:T→C¹(ℝ⁻)×ℝ×C²(ℝ⁺);f↦(f|_ℝ⁻,f(0),f|_ℝ⁺) je bijekcija. (Injekcija je jer se dvije funkcije s ℝ u ℝ koje se razlikuju, razlikuju ili na ℝ⁻, ili u nuli, ili na ℝ⁺. Surjekcija je jer se svaka uređena trojka (f₁,a,f₂) u kodomeni može dobiti kao g(f), gdje je f po slučajevima definirana kao f₁, a, odnosno f₂.) Dakle, card T=card(C¹(ℝ⁻)×ℝ×C²(ℝ⁺))=(card C¹(ℝ⁻))⋅(card ℝ)⋅(card C²(ℝ⁺)). Prvi i treći kardinalni broj su jednaki c, argumentom koji je napravljen na vježbama. Odnosno, card T=c⋅c⋅c=c³=c.
Tvrdnja vrijedi. Da bismo je dokazali, dokazujemo dvije inkluzije.
- (⊆) Neka je x∈⋃⋃A² proizvoljan. To znači, po definiciji unije, da postoji y∈⋃A² takav da je x∈y. Opet po definiciji unije, imamo da postoji z∈A² takav da je y∈z. Budući da je z∈A², z je uređen par elemenata iz A, recimo z=(a,b)={{a},{a,b}}, gdje su a i b elementi iz A. Sada, po definiciji para y∈z znači y={a} ili y={a,b}, a u svakom od tih slučajeva opet po definiciji para x∈y povlači x=a ili x=b. U svakom slučaju x∈A.
- (⊇) Neka je s∈A proizvoljan. Tada je (s,s)={{s}}∈A², pa je {s}∈⋃A² (jer je {s}∈{{s}}∈A²), te je s∈⋃⋃A² (jer je s∈{s}∈⋃A²).
∏_α∈ω+2(α+2)^α+1= (∏_α∈ω(α+2)^α+1)⋅(ω+2)^ω+1⋅(ω+3)^ω+2=
(sup_n∈ω∏_α=0..n-1(α+2)^α+1)⋅(ω+2)^ω⋅(ω+2)⋅(ω+3)^ω⋅(ω+3)⋅(ω+3)=
sup_n∈ω(2¹⋅3²⋅...⋅(n+1)ⁿ)⋅ω^ω⋅(ω+2)⋅ω^ω⋅((ω+3)⋅ω+ω+3+ω+3+ω+3)=
ω⋅ω^ω⋅ω^ω⋅(ω²+ω⋅3+3)= ω^ω⋅2+2+ω^ω⋅2+1⋅3+ω^ω⋅2⋅3
2≤ℵ₀≤2^c, pa je 2^c≤ℵ₀^c≤(2^c)^c=2^c⋅c=2^c, odnosno ℵ₀^c=2^c.
1≤ℵ₁≤c (ovo zadnje jer je ℵ₁ najmanji od svih kardinalnih brojeva većih od ℵ₀, a c je veći od ℵ₀ po Cantorovom teoremu), pa je c=1⋅c≤ℵ₁⋅c≤c⋅c=c, odnosno ℵ₁⋅c=c.
Dakle, (ℵ₁⋅c)^ℵ₀=c^ℵ₀=(2^ℵ₀)^ℵ₀=2^{ℵ₀⋅ℵ₀}=2^ℵ₀=c.
Sve u svemu, rezultat je 2^c+c, što je između 2^c+0=2^c i 2^c+2^c=2⋅2^c=2^c+1=2^c; dakle jednak je 2^c.
Promotrimo skup T:={y∈S:y≻x}.
T je parcijalno uređen restrikcijom uređaja ≺, možemo pisati da je (T,≺) PUS.
Također, budući da x nije maksimalan, postoji bar jedan y∈S takav da je y≻x, odnosno T nije prazan.
Svaki lanac u T je neprazan totalno uređen podskup u T, dakle i neprazan totalno uređen podskup u S, odnosno lanac u S, pa kao takav ima gornju među u S; označimo je s g. Budući da je lanac neprazan, u njemu postoji bar jedan element l. Budući da je lanac u T, vrijedi l∈T, odnosno l≻x. Budući da je g gornja međa za taj lanac, specijalno vrijedi g≽l, pa po tranzitivnosti g≻x, odnosno g∈T. Dakle, svaki lanac u T ima gornju među u T.
Vidimo da su ispunjeni svi uvjeti Zornove leme za skup T, pa postoji maksimalni element u T; nazovimo ga z. Budući da je z∈T, odmah imamo z≻x.
Treba još vidjeti da je z maksimalan element u S (Zornova lema nam samo daje da je maksimalan u T). Pretpostavimo da postoji w∈S takav da je w≻z. Po tranzitivnosti bi tada bilo i w≻x, odnosno w∈T, što je u kontradikciji s maksimalnošću od z u skupu T. Dakle, z je stvarno maksimalan element u skupu S, i vrijedi z≻x.

Aksiom izbora i (bes)konačni izbori

2006-02-17T12:51:00.000+01:00

From: Veky <vedgar@gmail.com>
Date: Feb 17, 2006 12:49 PM
Subject: Re: Teorijsko pitanje iz teorije skupova...
To: Goran

On 2/16/06, Goran wrote:

Ima jedna stvar u koju nisam siguran pa bih trebao pomoć...
Radi se o aksiomu izbora. Koliko sam ja zaključio AC nam treba samo kada je familija iz koje "čupamo" elemente beskonačna?

Ukratko, da. Evo relativno jednostavnog heurističkog objašnjenja za to:
dokaz je slog od konačno mnogo izjavâ, koje slijede jedna iz drugih po strogo definiranim pravilima. Ako imamo konačno mnogo nepraznih disjunktnih skupova, možemo za svaki od njih reći "taj skup je neprazan, dakle po definiciji nepraznog skupa postoji element u njemu". To efektivno znači i da ga možemo izabrati, jer kad ne bismo mogli, skup bi bio prazan.

No kada imamo beskonačno mnogo skupova, ne možemo koristiti gornji argument, jer bismo na taj način imali beskonačno mnogo koraka u dokazu. Treba nam ili algoritamsko pravilo po kojem možemo u konačno mnogo izjavâ izabrati po jedan element iz beskonačno mnogo skupova (poznata je ona Russellova "Aksiom izbora nam treba za odabrati po jednu čarapu iz beskonačno mnogo parova čarapâ, ali za cipele nam ne treba: možemo iz svakog para odabrati lijevu cipelu.":), ili pak aksiom koji će nam reći da kao što nešto možemo u konačnosti (izabirati elemente), tako možemo i u beskonačnosti -- uvijek -- iako, naravno, ne kaže kako.

Mislim, jer kada smo dokazivali na predavanjima da je konačna unija prebrojivih skupava prebrojiva, onda nismo koristili AC, dok smo za prebrojivu familiju koristili AC...

Naravno. Jer da je skup prebrojiv, to samo znači da postoji bijekcija između njega i ℕ. Odnosno, jezikom TS, skup svih takvih bijekcijâ je neprazan. Ako imamo konačno mnogo prebrojivih skupova A_i, tada imamo i konačno mnogo nepraznih skupova bijekcijâ između A_i i ℕ. Da bismo iz svakog od tih skupova bijekcijâ odabrali po jednu (što nam treba za nastavak dokaza), nije nam potreban aksiom izbora.

No kada imamo prebrojivo mnogo prebrojivih skupova A_i, to znači da imamo, za svaki i, neprazan skup bijekcijâ između A_i i ℕ, te da bismo odabrali po jednu iz svakog skupa (što nam treba za nastavak dokaza), treba nam aksiom izbora (nekom algoritamskom pravilu se ne možemo nadati, ako su A_i proizvoljni skupovi).

Nadalje, nije mi jasno gdje se točno koristi AC kod dokaza
da beskonačan skup A ima prebrojiv podskup: Uzmemo element x0 iz A, pa je A\{x0} neprazan, pa uzmemo x1 iz A\{x0}, pa je A\{x0,x1} neprazan i tako dalje...

Nadam se da je sad jasnije. Ako je A beskonačan, on ima i beskonačno mnogo (čak i više:) nepraznih podskupova. U svakom od njih se može odabrati po jedan element, no da bismo to učinili u konačno mnogo koraka, treba nam aksiom izbora. Netko može reći da ne moramo izabrati po jedan element iz jako puno (neprebrojivo) nepraznih podskupova od A, kad nam treba samo prebrojivo mnogo akata izbora za dokaz. I to je točno, i postoje slabije varijante, poput aksioma zavisnih izborâ, koji nam može poslužiti ovdje. No treba reći da iako imamo puno manje akata izbora nego što na prvi pogled možemo pomisliti da nam treba (za svaki neprazni podskup od A), još uvijek nam ih treba beskonačno mnogo, i algoritamsko pravilo se (za proizvoljni A) ne može naći, pa moramo koristiti aksiom izbora.

Puno više o tome, i zanimljivo za čitanje, može se naći na http://www.math.vanderbilt.edu/~schectex/ccc/choice.html .

--
~Veky

Teorijska pitanja iz prvog kolokvija iz UM

2006-02-17T11:30:00.000+01:00

Napišite definiciju jednakosti skupova.
Karakterizirajte jednakost skupova pomoću inkluzije.
Napišite definiciju relacije ekvivalencije, s detaljnim opisom svojstava, te dajte jedan primjer.
Iskažite teorem o odnosu među klasama ekvivalencije.
Iskažite osnovni teorem aritmetike (o kanonskom rastavu prirodnog broja), te dajte jedan primjer.

Napišite definiciju uređenog para.
Karakterizirajte jednakost uređenih parova.
Napišite definiciju parcijalnog uređaja, s detaljnim opisom svojstava, te dajte jedan primjer.
Napišite definiciju klase ekvivalencije, te dajte jedan primjer.
Iskažite teorem o dijeljenju s ostatkom.

Napišite definiciju particije skupa, te dajte jedan primjer.
Napišite definiciju Kartezijevog produkta skupova.
Napišite definiciju kogruencije.
Iskažite teorem o odnosu među klasama ekvivalencije.
Iskažite teorem o dijeljenju s ostatkom.

Zornova lema i (a)tipični uređaji

2006-02-09T23:33:00.000+01:00

From: Veky <vedgar@gmail.com>
Date: Feb 8, 2006 1:43 PM
Subject: Re: ts,kolokvij
To: Kristina

On 2/8/06, Kristina wrote:

...me zanima na cemu sam izgubila bod:) u zadatku sa Zornovom lemom. Jeli nesto bas vezano za Z. lemu ili nesto s vektorskim potprostorima. Dakle, nije da se zalim, nego me cisto zbog usmenog zanima ako nesto krivo radim s Z. lemom.

Hm... ima jedna trivijalna stvar, a to je da ne možete reći "BSOMP V₁<V₂" ako situacija nije simetrična. Kod Vas nažalost nije, jer ste za opću linearnu kombinaciju uzeli x+λ∙y, dakle x i y nisu ravnopravni (preciznije, ako je V₂<V₁, onda trebate još jedan korak da zaključite da je λ∙x u istom prostoru kao i x). No čovjek bi trebao biti puno veća cjepidlaka čak i od mene da bi Vam za to skinuo bod. :-)

Stvar zbog koje ste izgubili bod je ova: ako imamo standardni parcijalni uređaj "⊂" na familiji skupova ℱ, onda znamo da je ⋃ℒ gornja međa lanca ℒ. Štoviše, znamo da je to najmanja gornja međa, i prirodno je za nju provjeravati je li u ℱ. No ako imamo neki drugi uređaj (na primjer "<", "biti potprostor", u Vašem slučaju), to ne možemo znati. Tada imate dvije mogućnosti:

Dokazati da je za Vašu familiju ℱ "biti podskup" ekvivalentno s "biti potprostor" (što je ok, jer se u ℱ nalaze samo potprostori od V), slično kao što smo napravili za podgrupe na vježbama: jedan smjer očito vrijedi (potprostor je podskup), a za drugi: ako je V₁⊂V₂, te su V₁ i V₂ potprostori od V, to znači da je V₁ vektorski prostor s obzirom na restringirane operacije, dakle V₁<V₂.
Uzeti pravu "najmanju gornju među" s obzirom na relaciju "biti potprostor", a to je, kao što možda znate iz LA, suma potprostora (ne unija). Tada, naravno, ima malo posla na drugom kraju: dokazati da se u toj sumi ne može kojim slučajem naći vektor x.

Ja sam zamislio da se zadatak riješi na prvi način (jer smo tako riješili analogni zadatak s grupama na vježbama), ali nemam ništa protiv (dapače, drago mi je:) ako netko riješi na ovaj drugi način (npr. kolega G.R. — tako da za detalje te metode možete njega pitati:).

HTH,
--
~Veky

Rješenja kolokvija iz Uvoda u matematiku 2006-02-06

2006-02-09T17:28:00.000+01:00

Dokazujemo matematičkom indukcijom.
Baza
1³=1>(1-1)⋅(2⋅1-1)=0⋅1=0
Pretpostavka
Pretpostavimo da je za neki k∈ℕ, k³>(k-1)⋅(2k-1)=2k²-3k+1.
Korak
Trebamo dokazati da je (k+1)³>(k+1-1)(2(k+1)-1)=k(2k-1)=2k²-k.

Koristeći pretpostavku, možemo dobiti (k+1)³=k³+3k²+3k+1>2k²-3k+1+3k²+3k+1=5k²+2.

Dakle, sve što još trebamo dokazati je 5k²+2>2k²-k za sve prirodne k. No to je ekvivalentno s 3k²-k+2>0, što vrijedi čak za sve realne k (jer je diskriminanta=-23 negativna, a vodeći_član=3 pozitivan).
Tri uvjeta zadana u zadatku nam znače p(1)=2, p(-1)=0, te p(0)=2. Ako p(x) podijelimo s x³-x (stupnja 3), dobit ćemo ostatak stupnja strogo manjeg od 3 (ili nulpolinom), dakle nešto oblika r(x)=ax²+bx+c. Sve u svemu, imamo p(x)=(x³-x)q(x)+ax²+bx+c. Uvrštavajući u to za x brojeve -1, 0 i 1, dobijemo 0=a-b+c, 2=c, te 2=a+b+c, iz čega se lako dobije b=-1 i a=1. Dakle ostatak je r(x)=x²-x+2.
Budući da je zadani polinom jednak f(x)=2x³+7x²+4x-4, cjelobrojna nultočka mora biti djelitelj slobodnog člana 4, dakle iz skupa {1,-1,2,-2,4,-4}. Uvrštavanjem (npr. pomoću Hornerove sheme) se dobije da je -2 nultočka. Uvrštavajući -2 redom u derivacije od f(x) (ili u kvocijente koji se dobiju iz Hornerove sheme), dobije se da je f'(-2)=0, te f''(-2)=-10≠0. Dakle, kratnost nultočke -2 jednaka je 2.
Prebacivši 1 na lijevu stranu nejednadžbe, faktoriziranjem nazivnika i svođenjem na zajednički nazivnik, dobije se ekvivalentna nejednadžba 2(5x+4)/(x-2)(x-1)≥0. To se može riješiti pomoću tablice, gledanjem predznaka pojedinih faktorâ na intervalima određenim točkama -4/5, 1 i 2. Nakon toga još treba izbaciti 1 i 2 kao nultočke nazivnika. Konačno rješenje je x∈〈-∞,-4/5]∪〈1,2〉.

Dokazujemo matematičkom indukcijom po n. Primijetimo da na lijevoj strani eksponenti broja 3 idu od 0 do 6n-2 s korakom 2, dakle suma na lijevoj strani ima 3n članova.
Baza
Za n=1, imamo tri člana na lijevoj strani: 1+3²+3⁴=1+9+81=91=13⋅7, što je djeljivo s 13. (Zadnji član u sumi je 3^6⋅1-2=3⁴.)
Pretpostavka
Pretpostavimo da je za neki prirodni k, 1+3²+3⁴+...+3^6k-2 djeljivo s 13, odnosno jednako 13q za neki cjelobrojni q. Suma na lijevoj strani ima 3k članova.
Korak
Za n=k+1, na lijevoj strani imamo 3n=3(k+1)=3k+3 člana: to su 3k iz pretpostavke indukcije, i još 3 sljedeća (nakon 3^6k-2 s korakom 2 u eksponentu): 3^6k, 3^6k+2 i 3^6k+4. Primijetimo da je posljednji jednak 3^6(k+1)-2, kao što i treba biti. Naša suma je sada jednaka (1+3²+3⁴+...+3^6k-2)+(3^6k+3^6k+2+3^6k+4) =
13q+3^6k(1+3²+3⁴) = 13q+91⋅3^6k = 13(q+7⋅3^6k), što je djeljivo s 13.
Prvo provjerimo je li nulpolinom rješenje. Za p(x)=0, dobivamo istinitu jednakost 0=0, dakle nulpolinom je jedno rješenje. Ako pak p nije nulpolinom, tada ima stupanj: označimo n:=st(p). Stupanj kompozicije je produkt stupnjeva, a stupanj produkta je zbroj stupnjeva faktorâ, dakle stupanj lijeve strane je 2n, a desne 2+n (primijetimo da sada nijedna od njih nije nulpolinom). Ako su one jednake, moraju imati i jednake stupnjeve, odnosno 2n=2+n, iz čega dobijemo n=2. Dakle p(x) koji nije nulpolinom mora biti stupnja 2, odnosno imati oblik ax²+bx+c (gdje a kao vodeći koeficijent nije 0). Uvrstivši to u zadanu jednadžbu, dobijemo a(1+x²)²+b(1+x²)+c=(1+x+x²)(ax²+bx+c). Kad to raspišemo po potencijama od x, dobijemo:
- uz x⁴: a=a
- uz x³: 0=a+b
- uz x²: 2a+b=a+b+c
- uz x: 0=b+c
- slobodno: a+b+c=c
Iz toga se dobije rješenje a=-b=c, odnosno p(x)=a(x²-x+1), gdje je a proizvoljan realan broj različit od 0. Ako je a=0, dobije se upravo nulpolinom (za koji smo gore vidjeli da je rješenje), pa je opće rješenje p(x)=a(x²-x+1) za proizvoljni a∈ℝ.
Imamo jednakost (x²+x+1)ⁿ=a_2nx²ⁿ+...+a₁x+a₀. Uvrštavanjem x=1 i x=-1 u nju, dobijemo
3ⁿ=a_2n+a_2n-1+...+a₁x+a₀ i
1=a_2n-a_2n-1+...-a₁x+a₀. Zbrajanjem te dvije jednakosti, i dijeljenjem s 2, dobijemo
(3ⁿ+1)/2=a_2n+a_2n-2+...+a₂+a₀. Da bismo dobili ono što se od nas u zadatku traži, treba još oduzeti od toga slobodni član a₀, koji se može dobiti uvrštavanjem x=0: 1=a₀. Dakle traženi izraz je (3ⁿ+1)/2-1=(3ⁿ-1)/2.
Prebacivši 2 na lijevu stranu nejednadžbe, faktoriziranjem nazivnika i svođenjem na zajednički nazivnik, dobije se ekvivalentna nejednadžba -(5x-17)/(x-3)(x+2)≤0. To se može riješiti pomoću tablice, gledanjem predznaka pojedinih faktorâ na intervalima određenim točkama -2, 3 i 17/5. Nakon toga još treba izbaciti -2 i 3 kao nultočke nazivnika. Konačno rješenje je x∈〈-∞,-2〉∪〈3,17/5].

Simboli kao skupovi?

2005-12-12T19:44:00.000+01:00

---------- 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

2005-12-12T19:42:00.000+01:00

---------- 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?

2005-12-12T19:32:00.000+01:00

---------- 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:

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

2005-12-12T19:31:00.000+01:00

---------- 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

2005-12-12T19:30:00.000+01:00

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

2005-12-01T21:40:00.000+01:00

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.

diskriminanta manja od nule. tada nema rješenja, odnosno skup rješenja je prazan. - jedna mogućnost.
diskriminanta jednaka nuli. tada je rješenje jedinstveno, odnosno skup rješenja je singleton {x}, za proizvoljan realan x - 𝔠 mogućnosti.
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â

2005-11-25T15:18:00.000+01:00

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

1+1=2, 00=1, i još neke trivijalnosti

2004-12-22T23:17:00.000+01:00

Helios:

zasto je 1 + 1 = 2?

[lesson title="1+1=2"]
Odgovorit ću ti čim mi odgovoriš što je 1 i što je 2 ... :-)

Seriously, s obzirom na to da math postoji vec jaako dugo, ljudi su kroz povijest prilično različito gledali na te stvari. Kao posljedica toga, danas imamo hrpu matematičkih, mathematičkih i "matematičkih" interpretacijâ osnovnih pojmova kao sto su zbrajanje, prirodni brojevi itd. Naravno da je u takvom mindsetu teško dati definitivan odgovor na gornje pitanje. Evo ti jedan odgovor koji malo kombinira PA, ZF, pa čak i filozofiju tamo gdje mora (gdje bi bez nje bilo preteško na ovoj razini):

Prirodni brojevi (nulu smatram prirodnim brojem) su konačni ordinali. Ordinali su skupovi koji imaju zgodno svojstvo da se mogu uspoređivati ("manji", "veći") pomoću relacije "@" (biti element). Na taj način (znamo otprije da je skup S upravo skup svih x koji su elementi od S), svaki ordinal postaje skup svih ordinalâ koji su manji od njega.

Prvi ordinal, nula, tad ne može biti ništa drugo nego prazan skup (jer još nema nijednog ordinala koji bi bio manji od njega). Sljedeći ordinal, jedan, bit će skup svih dosad napravljenih ordinalâ, a jedini takav dosad je 0, dakle 1:={0}. Onaj nakon njega, dva, bit će skup tih dosad definiranih ordinalâ, dakle 2:={0,1}.

I tako dalje... vjerujem da je sad jasno da je 3:={0,1,2}, 4:={0,1,2,3}, and so on. Naravno, za taj pristup trebamo izmisliti beskonačno mnogo imenâ za brojeve, a to je teško. Puno je bolje shvatiti da je sve što radimo samo primjenjivanje jednog te istog postupka over&over again, na početni ordinal 0.

Koji je to postupak? Onaj kojim od 0 dobivamo 1, isti kao onaj kojim od 1 dobivamo 2, od 2 dobivamo 3 itd. ... da vidimo:
1={0} & 2={0,1}. Što smo napravili? Dodali smo u skup element 1. 2=1U{1}. Isto tako, 3=2U{2}. Vrijedi i dolje: 1=0U{0} (sjetimo se, 0 je prazan skup). Sad je već jasno da sljedeći ordinal nakon x dobivamo kao xU{x}. Taj ordinal zove se sljedbenik od x i označava s x⁺. Dakle, x⁺:=xU{x}.

So, ono što smo gore rekli se svodi na to da prirodne brojeve dobivamo naštukavanjem operacije ⁺ na broj 0: zaista, 1=0⁺, 2=0⁺⁺, 3=0⁺⁺⁺ (provjerite:), itd. No početak ne mora biti 0, možemo ga jednako tako prebaciti u bilo koji ordinal k. To prebacivanje zove se pribrajanje broja k (i označava s +k, a vrijednost tog preslikavanja u ordinalu l označava se, uobičajeno, u postfiksu s k+l). Dakle, ono umjesto od 0 kreće od k, a dalje nastavlja potpuno jednako kao i standardna izgradnja prirodnih brojeva, pomoću naštukavanja operacije ⁺:


 0+k=k (početak nije 0 već k) (pravilo 0+)

 x⁺+k=(x+k)⁺ 

(ali sljedbenik ostaje sljedbenik) (pravilo ⁺+)

Sad je iz ovog jasno:

 1+1=         (*1={0}*)

 ={0}+1=      (*X=0UX*)

 =(0U{0})+1=  (*X⁺=XU{X}*)

 =0⁺+1=       (*⁺+*)

 =(0+1)⁺=     (*0+*)

 =1⁺=         (*X⁺=XU{X}*)

 =1U{1}=      (*1={0}*)

 ={0}U{1}=    (*{x}U{y}={x,y}*)

 ={0,1}=      (*2={0,1}*)

 =2           QED.

Za domaću zadaću: 2+2=?. Sve potrebno imate. :-)
[/lesson]

[lesson title="Što je zapravo potenciranje? - ZF view"]
Dakle ovako... uobičajenu "definiciju" kardinalnih brojeva vjerujem da znaš (ono, bijekcije, "imati jednako mnogo elemenata", različite beskonačnosti, alef-nula, kontinuum i tome slično)

E sad, time smo uspjeli brojeve (as in kardinalne brojeve) povezati sa skupovima. Sad je fora povezati operacije s tim brojevima s operacijama sa skupovima... i to je uglavnom jednostavno. Npr. umnožak dva kardinalna broja je kardinalni broj Kartezijevog produkta odgovarajućih skupova.

Zbroj dva kardinalna broja je kardinalni broj njihove tzv. disjunktne unije ([VTN:]xunije[/], po uzoru na "xor":), koja se definira kao AUB :=(Ax{0})U(Bx{1}). Ovdje je kao sto vidiš mala komplikacija zbog toga što A i B ne moraju biti disjunktni in the first place, ali lako se učine disjunktnima - Ax{0} i Bx{1} su uvijek disjunktni, a istog su kardinaliteta kao A i B redom.

(Zašto su Ax{0} i Bx{1} disjunktni? XxY je po definiciji skup svih uređenih parova (x,y), gdje je x@X & y@Y. Specijalno, Ax{0} je skup svih uređenih parova (a,0), gdje je a@A. Analogno, Bx{1} je skup svih (b,1), za b@B. Da nisu disjunktni, neki element jednog bio bi jednak nekom elementu drugog, E_a@AE_b@B((a,0)=(b,1)). No jednakost uređenih parova tad bi dala a=b (irelevantno) i 0=1 ("nemoguće"), što je kontradikcija.)

No što je s potenciranjem? Da bismo odgovorili na to pitanje, prvo promotrimo specijalne slučajeve potenciranja kao iteriranog množenja. Naj"jednostavni"ji je valjda A²:=AxA - Kartezijev produkt skupa sa samim sobom. Naravno, njegovi "ad hoc" elementi su uređeni parovi, no lako se vidi da je takav pristup očajno biased prema broju 2, i da se ne može lako generalizirati na ostale brojeve.

Što želim reći? Ako mi treba A³, "očito" ću ga definirati kao A²xA.
Hm... a možda i kao AxA²... (to nije isto. ((x,y),z)!=(x,(y,z)) npr. za x:=(0,1) & y:=0 & z:=0 :)
Hmm... dakle, možda i nije tako "očito". [:-|]

Naravno, ono što bismo htjeli, je da u A³ ne žive nikakve hibridne tvorevine, kvaziparovi kojima je jedan element par, već ono što znamo pod imenom "uređene trojke". That's nice, ali što je uređena trojka (ako nije par kojem je jedan element par)? Već smo imali dovoljno neprilikâ s uvođenjem uređenog para kao "nedefiniranog" pojma u naivnoj teoriji skupova (inFact, on se može
definirati, ali ovdje to nije toliko bitno)... želimo li reći da nam treba još jedan, bez ikakve veze s ovim prvim?
I ofCourse, ne samo jedan - što je s uređenim četvorkama, petorkama, i sličnim čudovištima? A o N-torkama, R-torkama da i ne govorim...:-o

"Očito":-), svi su oni ipak specijalni slučajevi jednog šireg pojma... samo kojeg? Odgovor na to ćemo dobiti ako pogledamo što zahtijevamo npr. za uređene petorke. Sjetimo se da smo za uređen par rekli nešto tipa "to je objekt (x,y), koji ima svojstvo da su dva takva jednaki, (x,y)=(z,w), akko x=z&y=w". Pogledajmo za 5orku... htjeli bismo nešto tipa "uređena petorka je objekt (x₁,x₂,x₃,x₄,x₅) , koji ima svojstvo da su dva takva jednaka, (x_i)_i:1~5=(y_i)_i:1~5, akko A_i:1~5(x_i=y_i)".

Eh... sad to već liči na nešto. Preciznije, ovaj uvjet jako liči na definiciju jednakosti funkcijâ...
i zaista, ako umjesto x_i pišemo f(i-1) (zašto -1? Pa sad... recimo zasad samo da je brojanje od 1 jako neprirodno ustvari, i da je puno bolje početi brojati od 0... sto uostalom C-programeri znaju jako dobro;), a umjesto y_i pišemo g(i-1), vidimo da možemo 5orke smatrati funkcijama... ovu prvu funkcijom f, a ovu drugu funkcijom g. Na kojoj domeni? Očito, {0,1,2,3,4}. Taj skup ima i lijepo ime - ako si pratio prethodne lessone (recimo onaj "1+1=2"), znaš da se on zapravo zove imenom 5.

Dakle, 5orke su funkcije s domenom 5. Lijepo zvuči, zar ne? (Uostalom, kao i sva prava mathematika.:) Naravno, sad je jasno i što su 124orke , i N-torke (poznatije pod imenom "nizovi":), i R-torke (poznatije pod imenom "funkcije realne varijable"), i puno zahtjevniji objekti tog tipa.

No naše su 5orke ipak malo specijalnije, ako pogledamo A⁵. Naravno, to je sad skup svih uređenih 5orkî s komponentama iz A. U gornjem viewu, n-torke postaju funkcije, komponente očito postaju funkcijske vrijednosti, a A onda postaje skup iz kojeg se vade funkcijske vrijednosti, koji je još poznat pod imenom kodomena funkcije. Dakle, svaki objekt u A⁵ je funkcija f:5->A. Štoviše, A⁵ je upravo skup svih funkcijâ s 5 u A, a njegov kardinalni broj itekako ima smisla zvati petom potencijom kardinalnog broja od A.

Sad je jasno da je u cijelog gornjoj priči 5 bio samo placeholder, kojeg je prilično jednostavno apstrahirati. Dakle, A^B je skup svih funkcijâ s B u A, a njegov kardinalni broj može dobro poslužiti da se definira potenciranje kardinalnih brojeva.

Jupi... dakle, (bar za konačne brojeve m i n, lako je to i kombinatorički provjeriti), mⁿ jednak je broju funkcijâ sa nekog n-članog skupa u neki m-člani skup.
[/lesson]

Sad, koristeći ovo, za domaću zadaću dokaži (ili opovrgni:) :

	3²=9

	a¹=a za svaki a 

	1^a=1 za svaki a

	0⁰=1

	a⁰=1 za svaki a

	0^a=0 za svaki a>0

	2^card(A)=card \P(A)

 \P(A) je partitivni skup, ie skup svih podskupova od A

	2^alef₀=continuum

 realnih brojeva ima koliko i skupova prirodnih

	continuum^alef₀=continuum 

 realnih nizova ima koliko i realnih brojeva

Naravno, za neke od njih trebat će ti prilično precizna definicija pojma "funkcija", no o tome jednom drugom prilikom...

Kokoš ili jaje -- analitički

2004-12-19T05:22:00.000+01:00

vjeran:

Molim dokazati: Sto je prije nastalo: KOKA ili JAJE?

KOKA := { X ; x@@JAJE & (Ek@Životinje/_~repr)(Biserka@k & x@k) }

gdje je 'Životinje' definirano u [1] Darwin, The Origin of Species, a ~repr je ekvivalencijsko zatvorenje relacije repr na skupu Životinje, koja je definirana s
x repr y :<=> <>E_z(z<x & z<y & <>E_w(w<z)) .
S <> je označen modalni operator "moguće je da" (ie, <>E_zP(z) znači "moguće je da postoji z sa svojstvom P", odnosno njegovo postojanje ne dovodi ni do kakvih novih kontradikcijâ), a s '<' je označen parcijalni uređaj "biti potomak od" na skupu Životinje.

Naravno, X:=veliki(x).
A Biserka je definirana u mom dvorištu. ;-)

Za domaću zadaću:

raspisati riječima relaciju repr (i uvjeriti se da je to ono što suvremena biologija smatra pod pripadnošću istoj vrsti)
objasniti zašto već repr nije relacija ekvivalencije na Životinje (i time zašto je suvremena biologija u krivu gore;)
potražiti u [1] egzaktnu definiciju od Životinje (i shvatiti zašto nije navedena ovdje:)
dokazati da je '<' parcijalni uredaj na Životinje i objasniti zašto općenito nije totalan. Je li to dobro utemeljen uređaj (ie, ima li svaki neprazni podskup od Životinje minimalni element?) i treba li nam Aksiom izbora (ili neki njegov ekvivalent) da to zaključimo?
izraziti svojstvo z-a iz definicije repr pomoću viših pojmova iz teorije parcijalnih uređajâ (hints: gornja/donja međa, infimum/supremum, minimalni/maksimalni element, najveći/najmanji element)
dati heurističku definiciju funkcije veliki (bar restringirane na Životinje) (hint: geometrijski pojam sličnosti)

Za research:

popraviti sve sloppynesse u gornjim definicijama
dati kvazianalognu definiciju od JAJE
eliminirati KOKA iz te definicije (mislim da teorem o fiksnoj točki iz lambda-računa neće biti potreban:)
dati dobar heuristički argument zašto se JAJE ne može eliminirati iz definicije KOKA
zaključiti iz toga odgovor na gore postavljeno pitanje
na osnovu svega pročitanog, zaključiti nešto o Vekyjevom trenutnom mentalnom stanju :-)

Baza, linearna ljuska, potprostor, dimenzija,... -- konceptualni pristup

2004-12-19T04:43:00.000+01:00

Ana:

Možeš mi malo pojasnit neke pojmove: baza, linearna ljuska i potprostor?

Vektorski prostor je skup vektorâ s nekim operacijama. Preciznije,
imamo dva skupa u igri -

skup vektorâ V i
skup skalara F ;

četiri operacije:

zbrajanje vektorâ, +:VxV->V
zbrajanje skalarâ, +:FxF->F
množenje skalarâ: *:FxF->F
množenje vektora skalarom: *:FxV->V

(npr. ovo zadnje znači da se neki element iz F pomnoži nekim elementom iz V, i dobije se element od V.)
Te operacije zadovoljavaju neke aksiome:

F sa zbrajanjem i množenjem skalara je polje
V sa zbrajanjem vektora je Abelova grupa
(za značenje pojmova Abelova grupa i polje vidjeti ovaj post)
Vrijedi kvaziasocijativnost, distributivnost prema zbrajanju skalara, i distributivnost prema zbrajanju vektora, operacije množenja vektora skalarom
Vrijedi tzv. permanencija jedinice: 1*v=v za svaki vektor v, ako je 1 neutralni element za množenje u F.

To bi bili aksiomi. No kako vektorski prostor pretvoriti u nešto upotrebljivo za računanje?

Well... osnovni račun koji možemo napraviti s (konačnom) hrpom vektorâ zove se linearna kombinacija: odaberemo neke skalare za te vektore, svaki vektor pomnožimo "njegovim" skalarom, i to sve skupa zbrojimo. Mogu se postaviti mnoga pitanja u vezi linearnih kombinacijâ, kao što su:

imam vektore v₁,...,v_n (skraćeno v_1..n) i još neki vektor w. Može li se vektor w prikazati kao linearna kombinacija od v_1..n? Odnosno, postoje li skalari a_1..n takvi da je w=a₁v₁+...+a_nv_n?

Skup svih linearnih kombinacijâ vektorâ v_1..n zove se njihova
linearna ljuska, i označava s [{v_1..n}]_lin. Općenito, ako je S neki skup vektorâ, njegova linearna ljuska (skup svih linearnih kombinacijâ od po konačno mnogo vektorâ iz S) označava se sa [S]_lin. Na taj način, pitanje se može zapisati kao: je li w@[{v_1..n}]_lin ?
je li gornji prikaz (preciznije, skalari u njemu) jedinstven? Jednom kad imam v_1..n, i znam da mi je neki w element njihove linearne ljuske, može me zanimati može li se on dobiti kao njihova linearna kombinacija na više načinâ, ili samo na jedan. Pokazuje se, jer su vektorski prostori dosta uniformni, da je za dane vektore v_1..n dovoljno na to pitanje (jedinstvenost) odgovoriti samo za jedan vektor w - odgovor za jednog jednak je odgovoru za sve ostale koji se mogu prikazati (ako te zanima dokaz ovog, reci). Pa uzmimo specijalno vektor w=0vektor, nulvektor -- neutralni element u grupi vektorâ. To ima dobru stranu što za njega sigurno imamo jedan zapis -- ako uzmem sve skalare 0, lako se pokazuje (0*v=0vektor) da ću dobiti
0v₁+...0v_n=0vektor; dakle samo je pitanje postoje li još neki takvi skalari.
ako, za dane v_1..n, takvi skalari (dakle, koji nisu svi 0,...,0 -- a da linearna kombinacija ipak bude 0vektor) postoje, vektori v_1..n zovu se linearno zavisni. Inače, dakle ako je 0vektor (a onda, po gore rečenom, i bilo koji drugi vektor njihove linearne ljuske) moguće zapisati kao linearnu kombinaciju vektorâ v_1..n na jedinstven način (u slučaju nulvektora to znači samo pomoću koeficijenata 0,...,0), vektori v_1..n zovu se linearno nezavisni.
vidjeli smo da, ako su vektori v_1..n linearno nezavisni, svaki vektor koji se uopće može prikazati kao njihova linearna kombinacija, može se tako prikazati na jedinstven način. Ako se svaki vektor dade prikazati kao njihova linearna kombinacija (pa onda i na jedinstven način), dakle ako je (uz to što su linearno nezavisni) V=[{v_1..n}]_lin, tada se (uređeni) skup vektorâ {v_1..n} zove baza za vektorski prostor V. Dakle, jednom kad imam fiksiranu bazu v_1..n za V, svaki vektor mi je jedinstveno određen pomoću n skalarâ, dakle pomoću neke n-torke (a_1..n) elemenata iz F. I za svaki vektor iz V, ta n-torka skalara je jedinstvena.
štoviše, n je čak jedinstven (za dani V) neovisno o bazi. Bazâ
(linearno nezavisnih skupova čija je linearna ljuska cijeli prostor) može biti više (i obično ih ima puno), no pokazuje se da svake dvije baze imaju jednako mnogo elemenata, odnosno taj n je svojstvo samog prostora; i zove se njegova dimenzija. Pišemo n=dimV. Dakle, dimenzija vektorskog prostora je broj elemenata bilo koje njegove baze.
još je ostalo razjasniti što ako je skup vektorâ {v_1..n} linearno nezavisan, ali njegova linearna ljuska nije nužno cijeli prostor V -- dakle ne moraju se moći svi vektori prikazati kao linearne kombinacije
od v_1..n, ali za one koji se mogu (označimo ih generički slovom w), taj prikaz je jedinstven. Skup svih takvih vektorâ (dakle ovdje [{v_1..n}]_lin), pokazuje se, zatvoren je na operacije zbrajanja vektorâ i množenja proizvoljnim skalarima (konkretno, zbroj dvije linearne kombinacije s vektorima v_1..n opet je linearna kombinacija s vektorima v_1..n -- samo zbrojimo odgovarajuće koeficijente. Također, produkt proizvoljne linearne kombinacije vektorâ v_1..n s proizvoljnim skalarom, opet je linearna kombinacija istih vektorâ -- samo pomnožimo svaki koeficijent tim skalarom).
to znači da, ako skup svih takvih w-ova označimo s W, iako W ne mora biti cijeli prostor V, on također ima "iste" operacije zbrajanja i množenja skalarom kao i V, i svi aksiomi i na njemu vrijede (jer
aksiomi su obično univerzalne životinje -- ako vrijede "za svaki vektor iz" V, onda vrijede i "za svaki vektor iz" W, jer je svaki vektor iz W ujedno i vektor iz V). Drugim riječima, W je mali vektorski prostor sam za sebe (primijetimo, skup {v_1..n} je tada njegova baza), unutar vektorskog prostora V. Kažemo da je W
potprostor od V. Općenito, potprostor nekog prostora je bilo koji njegov podskup koji je i sâm prostor istog tipa s obzirom na iste (preciznije, restringirane) operacije.
vidjeli smo gore da se potprostori mogu dobiti npr. kao linearne ljuske nekih (gore linearno nezavisnih) skupova. To vrijedi i općenito -- ako je W potprostor od V, lako se vidi da je W=[W]_lin (sve linearne kombinacije vektorâ iz W ponovo su u W, kad je W zatvoren na zbrajanje vektorâ i množenje skalarima), odnosno bilo koji vektorski potprostor jest linearna ljuska (samog sebe, ako već ničeg drugog). No ta dva pojma imaju drugačije psihološko značenje -- dok je potprostor svojstvo podskupa, koji se gleda kao cjelina, linearna ljuska je prvenstveno ljuska nekog (manjeg, često konačnog) skupa, dakle odaberemo neke vektore i gledamo što je razapeto njima.

al mene sad malo kopka èemu slu¾e ti reci;

A služe, eto... no dobro, ajmo i to malo raspisati.
Dakle, u onom uvodu spomenuta su dva svijeta, jedno polje i jedan vektorski prostor nad njim. U prvom žive tzv. skalari, u drugom žive tzv. vektori. Oni su povezani na razne načine, na primjer vektori se mogu množiti skalarima, i to množenje ima neka svojstva. No povezani su i tješnje. Jednom kad imamo bazu, imamo teorem o koordinatizaciji, koji kaže da svaki vektor možemo predstaviti pomoću n skalara (gdje je n dimenzija prostora), i time uspostaviti vezu između vektorâ kao apstraktnih objekata, i n-torki skalarâ (kao malo manje apstraktnih objekata:).

E sad, pored ova dva, postoji i treći svijet, tzv. dualni prostor. U njemu žive bića koja se zovu "funkcionali" (zapravo punim imenom "linearni funkcionali", no radi kratkoće zapisa zvat ćemo ih samo funkcionalima). Oni se definiraju kao funkcije s vektorskog prostora u pripadno polje, koje poštuju operacije (zbrajanje vektora pretvaraju u zbrajanje skalara, i množenje vektora skalarom pretvaraju u obično množenje dva skalara u polju -- kao linearni operatori, ako shvatimo polje kao vektorski prostor nad samim sobom). I njihov svijet je također vektorski prostor nad istim poljem, i oni se dakle mogu međusobno zbrajati, i množiti skalarima iz tog polja (naravno, znamo kako se dvije npr. realne funkcije zbrajaju, i kako se množe realnim
brojevima). ((Štoviše, mogu se, osim te dvije operacije, i primjenjivati na vektore (i time davati skalare), baš kao što se bilo koja funkcija iz A u B može primjenjivati na elemente od A i time davati elemente od B.))

Dakle, i u dualnom prostoru možemo promatrati linearno nezavisne funkcionale, skupove izvodnica, i naći bazu, tzv. dualnu bazu -- pokazuje se da dualni prostor ima jednaku dimenziju kao i polazni prostor, pa nas to dovodi do ideje da pokušamo uspostaviti neku dobru bijekciju (izomorfizam) između vektorskog prostora i njegovog duala. I
ona zaista postoji... jednom kad fiksiramo bazu u početnom prostoru, na prirodan način se dobiva njoj dualna baza u dualnom prostoru (i-ti funkcional dualne baze definiramo kao i-tu koordinatu vektora zapisanog u početnoj bazi), i tako imamo zajednički jezik za opisivanje i vektorâ i funkcionalâ -- n-torke skalarâ (rekli smo već prije da je dimenzija duala jednaka dimenziji početnog prostora, dakle ovdje n).

((Ovo dalje se uglavnom odnosi na realne prostore... bar terminološki.Konceptualno, mnoge stvari ostaju i u prostorima nad bilo kakvim poljima.))
Postavlja se pitanje, što ako interpretiramo objekt jednog svijeta kao objekt drugog? Na primjer, uzmemo funkcional, zapišemo ga u dualnoj bazi, dobijemo n-torku skalara (njegove koordinate), i onda tih n skalara interpretiramo kao koordinate vektora u primarnom prostoru (složimo linearnu kombinaciju vektorâ početne baze s tim skalarima). Dobit ćemo vektor koji je očito tijesno povezan s funkcionalom od kojeg smo krenuli, bar uz fiksiranu bazu na početku tog procesa. Taj vektor se zove reprezentant tog funkcionala, i imamo čuveni teorem o reprezentaciji, koji kaže da općenito (u konačnodimenzionalnim prostorima, barem) svaki linearni funkcional na taj način može biti reprezentiran određenim vektorom, i obrnuto.

Kakva je to točno veza? Ako uzmem vektor a, i njemu gornjim (obrnutim) postupkom pridružim funkcional a*, kako će on djelovati na proizvoljni vektor b? Očito, pridružit će mu neki skalar. Dakle, efektivno, od dva vektora a i b, ja sam dobio novi skalar a*b. Tako sam dobio operaciju koju zovem skalarno množenje, a skalar a*b, koji se još ponekad označava s (a|b), skalarnim umnoškom a i b. Eto,
dobih novu operaciju, koja sad zadovoljava još neke aksiome, i ako nju uvedem u definiciju prostora zajedno sa zbrajanjem vektorâ i množenjem vektorâ skalarom, dobivam novu, poboljšanu strukturu, koja se zove unitarni (ovdje realni) prostor. No to nam nije trenutni cilj.

Cilj nam je vidjeti kako reprezentirati stvari da bismo njima lakše računali. Vidjeli smo da vektore možemo interpretirati kao n-torke skalara, i da te n-torke ima smisla pisati vertikalno. Analogno tome, funkcionale isto možemo interpretirati kao n-torke skalara, no sad ih treba drugačije zapisati. Pokazuje se da horizontalan zapis ima smisla, i kada se želi prikazati neki potprostor dualnog prostora, on se često prikazuje matricom koja u recima ima koordinate funkcionalâ koji ga razapinju, baš kao što se u primarnom prostoru potprostor prikazuje matricom u čijim su stupcima koordinate vektora koji ga
razapinju.

Ali, ne dovodi li to do toga da je jedna matrica mxn zapravo ambigous,
jer može predstavljati dualni potprostor razapet s m funkcionalâ (njenih m redaka), ili primarni potprostor razapet s n vektorâ (njenih
n stupaca)? Dovodi... ali, kao što mathematičari često kažu, it's not a bug, it's a feature. Drugim riječima, to je namjerno, i vrlo koristan pogled na jednu te istu stvar iz dva različita ugla.

Pogledajmo to na jednom primjeru. (Za ovo nam zapravo treba 2D, no snaći ćemo se valjda nekako). Uzmimo matricu [2 3//1 0//5 7]@R^3x2 ("//" je oznaka za novi red). Ta matrica ima tri retka i dva stupca, i može predstavljati i prostor vektorâ razapet vektorima (2,1,5) i (3,0,7) (potprostor od R³), kao i prostor funkcionalâ razapet funkcionalima f, g, h koji odgovaraju vektorima (2,3), (1,0) i (5,7) (potprostor duala od R²). Na primjer, ovaj "srednji" funkcional je ništa drugo nego funkcija "prva koordinata":
eg, g(-3,-9)=-3.

Uzmimo sad neki vektor iz linearne ljuske od {(2,1,5),(3,0,7)} --
dakle neku njihovu linearnu kombinaciju, npr. 8*(2,1,5)-5*(3,0,7)=(1,8,5), i pogledajmo kakve veze gornja tri funkcionala imaju s tim.

Treba nam neki vektor iz R², na kojem će gornji funkcionali f, g i h djelovati. Uređen par skalara koji se gore prirodno pojavio je (8,-5). Pogledajmo kako gornji funkcionali djeluju na njega:
f(8,-5). f je reprezentiran vektorom (2,3), dakle on množi svoj argument skalarno s (2,3). Iz toga f(8,-5)=((2,3)|(8,-5))=16-15=1.
g(8,-5)=8, jer je g jednostavno "prva koordinata". Naravno, to je ujedno i skalarno množenje s vektorom (1,0).
h(8,-5)=((5,7)|(8,-5))=40-35=5.
Tri funkcionala na jednom vektoru dala su nam tri skalara: 1, 8 i 5.
Poznato? :-)

Dakle, ako ta tri funkcionala gledamo kao jednu cjelinu (kao što se npr. dvije realne funkcije sin i cos mogu gledati kao jedna funkcija u R², r(x):=(sinx,cosx)), i tu cjelinu nazovemo npr. "linearni
operator";-), slika tog linearnog operatora bit će upravo skup svih uređenih trojki poput ove gornje (1,8,5) -- dakle, onih koje se mogu dobiti kao linearna kombinacija od (2,1,5) i (3,0,7) -- all in all, bit će to upravo potprostor razapet tim vektorima. Gornju matricu od koje smo krenuli, tada zovemo matricom tog linearnog operatora. Ona zaista pruža zgodan način kako zapisati prostor razapet s n vektora, no isto tako i način kako zapisati simultano djelovanje m funkcionalâ.
Ili pak, prostor razapet funkcionalima i ujedno simultano djelovanje neke hrpe vektorâ. %-) ((Kako vektori mogu "djelovati" na funkcionale? Jednako kao i funkcionali na vektore: v(f):=f(v), pomalo neformalno. Formalno, skalarni produkt je, bar u realnim prostorima, komutativan.))

To je bila samo jedna od fascinantnih posljedica unificiranja gornjih svjetova, uvid u koje nam pruža linearna algebra. Puno više o tome, nadam se, čut ćete na LA2.

& jel mogu ja e.g. imat 3vektora u bazi, a da svaki od nijh nema po tri koordinate;

Hm. Primijetite da sam gore uvijek pisao "baza za" (nešto), kao i "skup izvodnica za" nešto. Jednostavno, skup B je baza za prostor X
ako je linearno nezavisan (pri čemu X ne igra neku veliku ulogu, samo priroda operacijâ), i skup izvodnica za X, odnosno svaki vektor iz
X se može zapisati kao linearna kombinacija vektorâ iz B. Naravno da ovo drugo svojstvo bitno ovisi o tome koliki je X. :-)

Jest, ponekad se ne kaže, i onda se misli na "cijeli (univerzalni) prostor" u kojem se radi. Konkretno ovdje gore, ako imate vektore s četiri (valjda realne) koordinate, radi se o prostoru R⁴. I ako Vaše pitanje, punom rečenicom, glasi "mogu li imati bazu za R⁴ od 3 vektora?", odgovor je naravno ne, jer bi to po definiciji dimenzije značilo da je dimR⁴=3, pa bi ovaj eksponent gore bio stvarno čudno odabran. :-)

Još raspisanije, sama činjenica da imate vektore s 4 koordinate znači da negdje u pozadini imate bazu (vjerojatno kanonsku) za taj vektorski prostor, od 4 elementa (koordinate od x nisu ništa drugo nego koeficijenti u linearnoj kombinaciji, kad se x zapiše na jedinstven način kao linearna kombinacija vektorâ baze). A to bi pak značilo da u jednom te istom prostoru (kako god se on zvao, R⁴ ili drugačije) imate dvije baze, jednu s 4 a drugu s 3 elementa. Što bi naravno bilo u kontradikciji s teoremom da svake dvije baze imaju jednak broj elemenata.

e.g. jedan vektor iz baze a1 = (1, 2, 3, 4) (ovo je sad napisano tek tak, samo za primjer); al me sad buni ¹to matrica nije kvadratna....

Hm... matrica, kao što smo vidjeli, reprezentira puno toga: potprostor, ali i funkcionale, linearni operator,... Da je kvadratna, to znači jednostavno da se ti funkcionali mogu primjenjivati na početne vektore. Ako nije kvadratna, nečega će biti viška.

Na primjer, da uzmete tu hipotetsku bazu za R⁴ od 3 elementa, i ta tri vektora (njihove koordinate) posložite u stupce matrice, to bi
bila matrica 4x3. Odnosno, mogla bi reprezentirati simultano djelovanje 4 funkcionala na R³. No to što je ovo gornje baza bi značilo da je prostor razapet njome cijeli R⁴, pa bismo imali da je slika simultanog djelovanja ta 4 funkcionala (bolje rečeno linearnog operatora s R³ u R⁴) cijeli R⁴ (tj. da je taj linearni operator surjekcija), što je nemoguće: linearno preslikati 3D na čitav 4D.

Minus puta plus, i algebarske strukture

2004-12-19T02:45:00.001+01:00

qmlwxealhfbn$.15ew0kk2ky0kj$.dlg@40tude.net:

jel mi netko moze objasnit zasto kad se mnoze dva broja sa negativnim predznakom kao rjesenje se dobije pozitivan broj a kad se mnoze pozitivan i negativan broj kao rjesenje se dobije negativan broj!?

Kao i obično, [veky:]mogu pokušati[/]. :-)

[lesson title="...široko mu polje"]
Prvo da raščistimo malu terminološku zapetljanciju koja te možda muči.
"s negativnim predznakom"... predznak broja je jednostavno neki drugi broj, i to: predznak od x je uniformiziran (što ovdje jedino znači da je 0 ako bilo koji broj zadovoljava uvjete) broj sgnx koji pomnožen s |x| daje x.
Na R, sve vrijednosti koje sgn može poprimiti (dokaži:) su 0, 1 i -1 (im(sgn|_R)={-1,0,1}): 0 u nuli, 1 na pozitivnim i -1 na negativnim brojevima. Dakle₁, jedini "negativan predznak" je -1, i on upravo odgovara negativnim brojevima.
Dakle₂, "broj s negativnim predznakom" i "negativan broj" su za nas ekvivalentni pojmovi. Dakle₃, ovo prvo je pleonazam.

No dobro, to je bilo prilično nebitno, ali za svaki slučaj. Idemo sad raspiliti ostale definicije. "Negativan" znači "manji od 0". "Pozitivan" znači "veći od 0". Hm. Sveli smo dva pojma na dva druga, "manji od" i "veći od". Možemo mi i bolje. (-:

"x je veći od 0" znači isto što i "0 je manja od x", pa se možemo izvući sa samo jednim pojmom, "manji od", odnosno relacijom "<". Ta relacija na R ima svojstva irefleksivnosti (nijedan broj nije manji od samog sebe) i tranzitivnosti (ako je jedan broj manji od drugog, koji je manji od trećeg, tad je i ovaj prvi manji od tog trećeg). Takva relacija zove se IPU (irefleksivni parcijalni uređaj), a budući da se i svaka dva različita broja mogu usporediti (x=yVx<yVy<x), ovdje imamo posla s običnim (irefleksivnim) uređajem.

Naravno, naziv "uređaj" se ovdje odnosi na svojstvo te relacije da pomoću nje možemo nekako urediti realne brojeve, odnosno znati od dva koji je veći a koji manji.

Toliko o uređaju (zasad). Spominješ još i množenje. Što bi to bilo? Očito, neka operacija: dakle preslikavanje koje djeluje na uređenim parovima realnih brojeva i pridružuje im realne brojeve: *:RxR->R. No malo je čudno pričati o množenju ad hoc, jer postoji jedna jednostavnija operacija na realnim brojevima, s malo pravilnijom strukturom, pa bih prvo nju raspilio: naravno, riječ je o zbrajanju. +:RxR->R

Koja svojstva ono ima? Sigurno znaš za asocijativnost i komutativnost.
No ima i par drugih, koja se uglavnom konceptualno trpaju pod novu operaciju: oduzimanje, odnosno omogućuju nam da po nekoj varijabli (svejedno kojoj) invertiramo to preslikavanje, odnosno rješavamo jednadžbe poput 2+x=5.
Kako to obično rješavamo? "prebacimo" 2 na desnu stranu, čime se on magično pojavi tamo sa suprotnim predznakom. Na to smo već toliko navikli da se ne pitamo puno o tome, no trenutno pogledajmo pažljivije. Ako je na lijevoj strani pisalo 2+x, a sad piše samo x , što smo učinili?

Oduzeli smo 2, odnosno (definicija oduzimanja) pribrojili smo -2. Sad je jasno da smo to učinili i na desnoj strani, i zašto smo dobili -2 tamo. Zapravo smo ga dobili i na lijevoj strani, no tamo je on "poništio" onu dvojku koja je tamo stajala.

Zadubimo se malo u to poništavanje.
Kao prvo, zbog komutativnosti i asocijativnosti možemo zbrajanje 2+x s -2 svesti na zbrajanje -2 i 2:
(2+x)+(-2)=(x+2)+(-2)=x+(2+(-2))
. Kao drugo, zbrajanjem 2 i -2 se dobije 0. To očito možemo napraviti za svaki broj: naći njemu suprotan, koji s njim zbrojen daje 0. To se zove egzistencija inverza (suprotan broj se još zove inverz s obzirom na zbrajanje).
Kao treće, ono što je posebno u nuli je to da ona zbrojena s bilo kojim brojem (ovdje s x) daje njega samog, odnosno ponaša se "neutralno" pri zbrajanju. Zato se i zove neutralni element za zbrajanje.

Dakle, zbrajanje na R ima svojstva: asocijativnost, komutativnost, egzistencija neutralnog elementa, i egzistencija inverza.

Ima li množenje ista ta svojstva? Pa, skoro:-) (još preciznije: ima, ali ne množenje na R). No da bismo vidjeli gdje je problem, pokušajmo dočarati obrise slike koju želimo stvoriti.

Imamo R, i na njemu dvije operacije, + i *, i jednu relaciju, <. Skužili smo da one imaju puno lijepih svojstava sa zanimljivim nazivima, pa se čak i skupine tih svojstava vezane uz jedno preslikavanje nazivaju nekako (npr. ako promatramo samo zbrajanje, ova četiri gore navedena svojstva kažu da imamo nešto što algebraičari zovu "(Abelova) grupa". Dakle, R je uz zbrajanje Abelova grupa, odnosno Gr_A(R,+). Također, uz <, R je tzv. totalno uređen skup: tos(R,<)). No kad bi samo takva svojstva bila u igri, to zapravo ne bi bila velika koherentna struktura (R,+,*,<), već bi to bile tri male strukture: (R,+), (R,*) i (R,<). Dakle, trebaju nam svojstva koja povezuju gornja tri elementa.

Svojstvo koje povezuje zbrajanje i množenje vjerujem da ti je isto odavno dobro poznato: naravno, distributivnost množenja prema zbrajanju.

Još uskladiti uređaj sa zbrajanjem i množenjem... no to ćemo poslije. Sad ćemo iskoristiti distributivnost da pokažemo jednu zanimljivu činjenicu, a to je da nula pomnožena s bilo kojim brojem daje nulu. Zaista, ako je x bilo koji realan broj,

  0=0*x+(-0*x)=       (*0=0+0 , jer 0 je neutralni za +*)

  =(0+0)*x+(-0*x)=    (*distributivnost*)

  =(0*x+0*x)+(-0*x)=  (*asocijativnost*)

  =0*x+(0*x+(-0*x))=  (* -0*x je suprotni od 0*x *)

  =0*x+0=             (* 0 je neutralni *)

  =0*x .

Eh... eto. A što to znači? Znači da analognu jednadžbu onoj gore, samo za množenje, a*x=b, ne možemo riješiti (naći x) ako je a=0 (a b nije).
Neutralni element za množenje postoji, i zove se 1, naravno, ali ako 1 != 0 (ovo se moze činiti kao trivijalna napomena, ali ulazi u popis aksioma realnih brojeva:-) - zove se netrivijalnost polja), tad ne postoji inverzni (s obzirom na množenje) element za nulu - broj koji pomnožen s 0 daje 1, iz prostog razloga što svaki broj, kao što gore stoji, pomnožen s nulom mora davati nulu.

Kako se izvući iz ovog, i sačuvati što više od onog "...je grupa"?
Možemo pokušati modificirati svojstva, no puno elegantnije je modificirati skup. *:-) Naime, 0 nam uopće ne treba za multiplikativnu strukturu na R, i ako promotrimo R\.{0}, vidimo da taj skup zaista jest grupa s obzirom na množenje: ima neutral 1, jer 0 != 1, a svaki element u njemu ima inverz (jer 0 ionako nije ničiji inverz s obzirom na množenje, iz istog razloga), x|->1/x.

Još smo ostali dužni uklađenost < s operacijama.
< sa zbrajanjem... to jednostavno znači da je pribrajanje nekog broja rastuća funkcija, odnosno čuva smjer nejednakosti.
S množenjem... to je ono što nisi ni pitao u svom pitanju, jer ti je intuitivno očito, a to je da množenjem pozitivnih brojeva dobiješ pozitivan broj.

Super. Ponovimo sve što dosad imamo:

(R,+,*,<)

  +:RxR->R

  *:RxR->R

  <:R--R

+ :)  Gr_A(R,+)

  a+(b+c)=(a+b)+c

  a+b=b+a

  E_0@RA_a@R(0+a=a)

  A_a@RE_-a@R(a+(-a)=0)

* :)  Gr_A(R\.{0},*)

  a*(b*c)=(a*b)*c

  a*b=b*a

  E_1@R\.{0}A_a@R\.{0}(1*a=a)

  A_a@R\.{0}E_a^-@R\.{0}(a*a^-=1)    

< :)  tos(|R,<)

  !(a<a)

  a<b & b<c => a<c

  a=b V a<b V b<a

+&*:)  a*(b+c)=a*b+a*c

+&<:)  a<b => a+c<b+c

*&<:)  0<a & 0<b => 0<a*b

Ovakva struktura zove se uređeno polje. Dakle, to je struktura oblika (F,+,*,<) koja zadovoljava sve gornje aksiome.
Oni su nam dovoljni da damo odgovor na bilo kakvo pitanje koje se tiče uređenih poljâ, pa i ono tvoje gore. No kad sam već tu ne mogu ne napraviti još jedan mali korak i time dati malo materijala za razmišljanje onima što dolje pričaju o multiverzumu i sličnim (gledano iz perspektive matha!) baljezgarijama. :-)

Radi se o sljedećem zanimljivom svojstvu uređaja: ako imaš neprazan skup realnih brojeva, koji ima gornju među (svi brojevi tog skupa su manji od npr. 100), tada on sigurno ima najmanju gornju među - realan broj sa svojstvom da su svi elementi skupa i dalje ispod njega, no nijedan broj ispod njega nema to svojstvo. Da bismo to zapisali simbolički, prvo uvedimo oznaku S<=x, gdje je S neki skup realnih brojeva a x realan broj, za A_y@S(y<=x) (x je gornja međa za S).
Sad to postaje:
S != 0 & E_y@R(S<=y) => E_z@R(S<=z&!E_w@R(S<=w<z)) .
To svojstvo zove se potpunost uređaja, a uređeno polje s takvim uređajem zove se potpuno uređeno polje. No možemo ga slobodno nazvati i skup realnih brojeva:-), i to zbog jednog od najljepših teoremâ analize, koji glasi:

Postoji jedinstveno (do na izomorfizam) potpuno uređeno polje, i to je R.

Dakle, ako dodaš to svojstvo na popis aksiomâ gore, ne samo da ćeš dobiti impresivan popis stvari koje R zadovoljava, već ćeš dobiti svojevrsnu R-ovu "osobnu iskaznicu", popis svojstava koje zadovoljava jedino struktura R i nitko drugi.
Dakle, pomoću njih ćeš moći odgovoriti na bilo koje pitanje na koje uopće možeš očekivati da možeš suvislo math-odgovoriti u vezi realnih brojeva. Sve što znamo o R u standardnom mathu posljedica je tih aksiomâ.

Okej, pa odgovorimo onda na tvoja pitanja, kad smo već dovde došli.
Prvo, ako je a pozitivan, onda je -a negativan. Zaista, 0<a, dodamo -a na obje strane, usklađenost + i <, dobijemo -a<0.

Potpuno analogno, ako je a negativan, -a je pozitivan.
Također, -(-a)=a, jer a+(-a)=0 po komutativnosti zbrajanja znači da je a takav broj koji zbrojen s -a daje 0, odnosno inverz od -a (ovdje nam "inverz" znači "aditivni inverz", odnosno suprotan broj).

Super. Sad idemo množiti pozitivan broj negativnim.
Neka je a neki pozitivan broj, a b neki negativan. Po gornjem, c:=-b je pozitivan, i b=-(-b)=-c.
Dakle a i c su dva pozitivna broja, pa im je umnožak pozitivan: 0<a*c.
No a*b+a*c=a*(b+c)=a*(-c+c)=a*0=0*a=0, odnosno a*b je inverz od a*c.
(a*(-c)=-(a*c), ovo će nam trebati još)
No kako je ovaj pozitivan, a*b mora biti negativan. Etoga.

Sad negativni negativnim. a i b su negativni, dakle a=-c, b=-d, c i d su pozitivni (pa je i c*d pozitivan).

(-c)*(-d)=(*po gornjem*)

  =-((-c)*d)=-(d*(-c))=(*opet*)

  =-(-(d*c))=d*c=c*d <- pozitivno.

Dakle, overview odgovora:
negativni brojevi su aditivni inverzi pozitivnih.
Svojstvo "biti aditivni inverz" se čuva množenjem, pa a puta aditivni inverz od b je isto što i aditivni inverz od a puta b, odnosno umnožak s negativnim brojem je negativan, ako je umnozak s pozitivnim pozitivan (što jest, ako množimo pozitivne brojeve).

Također, svojstvo "biti aditivni inverz" je involutorno (aditivni inverz aditivnog inverza je sâm početni broj), pa množenjem dva aditivna inverza pozitivnih brojeva (ie, dva negativna broja) dobivamo aditivni inverz aditivnog inverza produkta početnih pozitivnih brojeva, odnosno sam taj produkt, koji smo vidjeli da je pozitivan.
[/lesson]

Jupi. Eto i prvog lessona u 2004oj. Znam da je malo čudan, ali takvi su moji lessoni općenito. :-) Ima pitanja?

Motivacija, akronimi, i ostali nebitni detalji

2004-12-19T02:31:00.000+01:00

Ana:

Moram priznat da poprilično dobro objašnjavaš pa ne kužim sve one rasprave na forumu o tvojim vježbama (brze i nerazumne...)?!?

Vrlo je jednostavno. Here, I have all the time in the world. Ne funkcioniram dobro u vremenskoj stisci, a na vježbama nažalost uvijek ima više gradiva nego što se dade ispredavati tempom koji bi meni odgovarao.

Druga stvar, individualno objašnjavanje mi puno bolje ide.
Prilično dobro mogu procijeniti nečiju math-stranu ličnosti, i ustanoviti koji stil objašnjavanja mu odgovara. Predavati tako da bude zanimljivo svoj 70orici ljudi, koji su došli iz školâ od srednje zdravstvene pa do matematičke gimnazije, nažalost ne znam.
(Zato cijelo vrijeme molim ljude da mi dolaze na konzultacije, ali oni to obično krivo shvate.)

Treće, kao posljedica raznih okolnosti, specijalizirao sam "digitalno" objašnjavanje. Newsgrupa, Forum, Email,... u tome sam dosta dugo, i vjerujem da sam to razvio bolje od većine ljudi koji još uvijek ne mogu odgovarajuće povezati objašnjavanje matha s digitalnim medijima.

Inace, sta tocno znaci HTH i RDTV?

HTH je standardna engleska Usenet-skraćenica, geslo mojeg objašnjavanja, "Hope This Helps".
RDTV je moj poluhumoristični hrvatski akronim "Recimo Da Ti Vjerujem".
Pogodi koje mu je intendirano značenje. ;-)

Ma nesto mi nije bas jasno... mozda ce ti se cinit cudnim ali ne kuzim zasto ti odgovaras svim ljudima na mail i rjesavas im zadatke?

Jesi li čitala priče o Sherlocku Holmesu? S razumijevanjem? :-) E, ako znaš odgovoriti zašto je on pomagao ljudima, na dobrom si tragu. ;-)
...
No dobro, da se više ne igramo lovice... Sherlock nije na to nikada gledao kao na prvenstveno pomaganje ljudima. To je bila nuspojava, protiv koje se nije bunio jer mu je osiguravala sredstva za život. No njegov primarni cilj nije bio dobrobit čovjeka, pa čak niti društva u cjelini - njegov primarni cilj bio je rješavanje zanimljivih slučajeva. Sva humanost i altruizam koju je pokazivao, bila je samo jednostavna posljedica neutažive želje njegovog neumornog logičkog uma za zanimljivim zadacima.

Zašto mi pišu neki hijeroglifi umjesto è, ž, š.... u mailovima svih ljudi koji koriste gmail?

Zato što Gmail koristi UTF-8 , jedini način da se konzistentno zapišu sva slova svih jezikâ svijeta. You see, tradicionalno je jedno slovo bilo jedan byte (8 bitova), i to je sasvim dovoljno za englesku abecedu i engleskogovorni način pisanja. Štoviše, primijećeno je da je čak 7 bitova dovoljno (128 mogućnosti), i tako je nastao ASCII -
standardni način za Amerikance da razmjenjuju slovne poruke preko kompjuterskih mreža. ("ASCII" znači "American Standard Code for Information Interchange" - primijeti "American".) Ostali narodi sa svojim pismima i jezicima, budući da su Amerikanci predvodili tehnološki razvoj kompjuterskih mrežâ, prilagođavali su se manje ili više ASCIIu. To prilagođavanje je išlo u više smjerova, ovisno o tome
koliko se dana abeceda razlikuje od engleske.

Za par dodatnih znakova: neke od manje korištenih kombinacijâ bitova (od tih 128), zamijenjene su svojstvenim znakovima pojedine abecede. Tako je jedno vrijeme kod nas bio na snazi tzv. YUSCII, u kojem su npr. uglate i vitičaste zagrade zamijenjene velikim i malim slovima š i ć . Naravno, grozno rješenje, pogotovo kad čovjek u tom encodingu pokuša pročitati neki C-kôd. ;-o
Za dosta novih znakova, ili za grupe jezikâ koje žele međusobno razmjenjivati informacije: iskoristi se 8. bit, jer se pretpostavlja da se znakovi ionako spremaju u byteove, pa osmi bit stoji neiskorišten. To daje novih 128 mogućnostî (ukupno 256), što se može činiti puno, ali i nije toliko. Npr. tako je nastao famozni Latin1 (poznat i pod službenim nazivom ISO-88591-1), proširenje ASCIIa, koji su stvorile zapadnoeuropske zemlje iznervirane nedostatkom naglašenih e-ova (Francuzi), prekriženih o-ova (Danci) i raznih umlauta (Nijemci)... Kasnije su se i ostale, ne baš tako zapadne ali ipak europske;-) zemlje sjetile da bi i one mogle tu uskočiti, no već je bilo prekasno - Latin1 , odnosno novih 128 znakova, već je bilo skoro
popunjeno.
Stvoren je Latin2 (ISO-88591-2), "alternativno" proširenje ASCIIa, koje je uključivalo između ostalog i hrvatska karakteristična slova, ali je naravno bilo nekompatibilno s Latin1 proširenjem. Kasnije se sva sila jezika sjetila upasti u shemu, pa tako danas imamo do Latin8 (IIRC). Naravno, to nije bilo baš dobro za razmjenu informacija (da stvar bude još gora, Latin2 je službeno prihvaćen tek _nakon_ što je Microsoft izdao verziju Windowsa98 za hrvatsko tržište, tako da je ona
imala opet neki svoj ludi encoding, nazvan Win1250), i trebalo je nešto napraviti ako smo htjeli da Hrvati Francuzima šalju poruke, ili čak Hrvati s američkog Yahooa Hrvatima s hrvatskim Windowsima, ili... no dobro, shvatila si. Da bi se vidjelo što se može učiniti, dobro je pogledati i ostale opcije.
Za totalno nove alfabete, koji nemaju veze s američkim (npr. rusi, ćirilica), ali imaju otprilike jednako slovâ, kompletan charset (128 ili 256 znakova) je zamijenjen novim slovima. Živi užas od "rješenja", jer ubija čak i kompatibilnost s osnovnim ASCIIem. Jedini način na koji ovo može poslužiti je kao loš primjer; kako _ne_ napraviti stvar - kakvo god univerzalno rješenje bilo, _ne dirati donjih 7 bitova_ u kojima leži ASCII.
Za nove alfabete koji nemaju veze s američkim, ali imaju puno više slovâ (Japanci, Kinezi,...) - samih slovâ je više od 256, pa je očito da jedan byte nije dovoljan. Iskoristimo ih 2 ili više (čak do 6 uzastopnih)... no problem je u tome da mrežama i dalje putuju byteovi. Kad kompjuter dobije niz byteova preko mreže, on ne zna a priori gdje počinje i gdje završava pojedini znak. To je rješavano na razne čudne načine, ali nijedan nije bio baš zadovoljavajući.

Napokon, učeći na greškama svojih prethodnikâ, stvoren je Unicode - ogromna potencijalno beskonačna mapa karaktera koja preslikava sve znakove svih stvarnih (i nekih izmišljenih, poput Tolkienovih:) jezikâ ikad izmišljenih o kojima postoji povijesni zapis, u proizvoljne binarne brojeve. Štoviše, prvih 127 tih brojeva upravo odgovara dobrom starom ASCIIu. I problem je riješen - bar teoretski.

Praktično, još uvijek postoji problem zapisivanja tih proizvoljnih binarnih brojeva u byteove koji idu preko mreže. Dugo su ljudi mozgali o tome, i napravljeno je dosta encodingâ, najuspješniji od kojih je bio genijalni UTF-8 -- koji je u punom smislu nadskup ASCIIa, odnosno mreže koje razmjenjuju čisti ASCII (otprilike 90% njih:) automatski su (UTF-8)-kompatibilne. Jedino će dodatni kodovi (u rješenju broj 2.)
nastradati, no to je ionako neminovno - oni su sami sebi iskopali jamu. Čak i da su (UTF-8)-dizajneri odlučili sačuvati npr. Latin1 , bili bi nekompatibilni s Latin2 -- a izgubili bi dragocjeni 8. bit, za kojeg je napokon nađena suvisla svrha.

Naime, sasvim je jasno da nam sad treba, kao u rješenju 4., više byteova za pojedini znak, no 8. bit možemo iskoristiti upravo u svrhu razgraničavanja znakova. (UTF-8)-sekvenca je proizvoljno konačni niz byteova, od kojih _prvi_ ima osmi bit 0 , a svi ostali imaju osmi bit 1 . Na taj način, em je trivijalno pregledavajući byteove grupirati ih u karaktere, em je ASCII ostao sačuvan -- niz byteova s vrijednostima
1..127 točno je isto što i niz jednočlanih nenul-sekvenci byteova u kojima svaki prvi u sekvenci (dakle svaki, jer su sekvence jednočlane:) ima osmi bit 0 . Weee...

Sad je još samo preostalo uvjeriti sve kompjuterske sustave na svijetu da je Unicode/UTF-8 pravi put u budućnost razmjene informacijâ, no naravno, to je najteži dio projekta. Mentalitet se teško mijenja, pogotovo mentalitet Amerikanaca koji još uvijek vode igru, a nemaju sami nikakve direktne koristi od (UTF-8)-sustava -- oni se i dalje mogu nastaviti dopisivati čistim ASCIIem, i ne primijetiti ništa.

Zato recimo Yahoo još uvijek koristi stari Latinx sustav, i kao takav čini apsolutno nemogućim Hrvatima razmjenjivati poruke s Francuzima, Rusima, Kinezima, Elfovima, pa čak i npr. Hrvatima s Windowsima 98.
Dok Gmail koristi UTF-8 , i njime ja mogu nekom Kinezu poslati svoje podatke bez bojazni da će moje prezime njemu izgledati kao psovka na njegovom jeziku. ;-))

Kartezijev produkt -- uvjet za pripadnost

2004-12-19T01:55:00.000+01:00

studentica:

Rješavajući zadatke koji se tiču Kartezijevog produkta skupova, sve je bilo ok dok nisam došla do onih što u sebi sadržavaju skupovne razlike i nekak me vodi do kontradikcije, makar mi je iz skice jasno da je ono s lijeve i ono s desne strane jednako.
Konkretno: ( s "/" ću označavati skupovnu razliku; mislim da nemam pravu oznaku na tastaturi)

Imate. Ako imate tipku AltGr s desne strane razmaknice, pritisnite nju skupa s tipkom Q.
Ako nemate tipku AltGr, može poslužiti Ctrl+Alt (dakle, tri tipke
odjednom: Ctrl, Alt i Q. Grozno, znam, ali većina modernih
(hrvatskih) tipkovnicâ ima AltGr).

A X (B/C) = (A X B) / (A X C) prikazat ću samo desnu

Ok, ovdje sam uspio shvatiti što mislite, ali općenito, nije baš jasno što je "lijeva" a što "desna" inkluzija. U svakoj inkluziji sudjeluju i lijeva i desna strana. :-) Možda je bolje, u ovom ASCII-svijetu siromašnom math-simbolima, govoriti o C-inkluziji i D-inkluziji (oblik slovâ C i D donekle podsjeća na prave znakove za inkluzije između skupova).

inkluziju: (za svaki p e A X (B/C))( p e (A X B) / (A X C)) proizvoljan p: p e A X (B/C) x e A y e B/C=> y e B y nije element C dakle, xeA i yeB=> p e A X B i xeA i y nije element C. Moje pitanje: kako mogu napisati da p nije element A X C kada je xeA za svaki y, bio taj y element od B ili ne bio element od C, tj. zar y diktira hoće li x u određenom slučaju biti element od A?

Ne, ali to nije bitno. Bitno je je li p=(x,y) element od AxC. Sjetite se, kako je Kartezijev produkt definiran:
AxC := { (x,y) ; x@A & y@C }
Primijetite "&" gore. To znači da je
(x,y)@AxC <=> x@A & y@C, odnosno da bi (x,y) bio u AxC, mora biti x@A i y@C. Ako je x@A true, a y@C false, konjunkcija je false, dakle da bi ekvivalencija vrijedila, (x,y)@AxC mora također biti false, odnosno (x,y) nije element od AxC.

Singletonovi, urelementi i ostala čudovišta

2004-12-19T01:53:00.000+01:00

studentica:

P(A) nije podskup P(B); dalje sam bila napisala da postoji x koji je element P(A), ali nije element P(B)- sad pitanje: kako mogu napisati da je neki član element partitivnog skupa kad je partitivni skup skup svih podskupova skupa S?

Ne znam što Vam znači "član". Inače, "član" je samo drugo ime za "element". U ovom slučaju, da, partitivni skup (od S ) je skup svih podskupova od S , dakle elementi (članovi) od P(S) su točno podskupovi od S .

Ako Vas to zbunjuje, x ne mora biti oznaka za element skupa S - i u ovom slučaju to općenito i nije. Zato sam ga i bio na konzultacijama označio velikim X - da više podsjeća na oznaku za skup. Jednostavno, X je neki podskup od A - koji nije podskup od B . X nije (općenito) element tih skupova.

Ako je S neki skup čiji su članovi 1,2,3; onda je 1 element
od S, singleton 1 je element od P(S), a singleton 1 je podskup od S, zar ne?

Točno, ali: "singleton" nam je samo riječ da bismo mogli lakše
govorno razlikovati skupove od elemenata koje oni sadrže. Nema
nikakvog smisla pisati tu riječ, između ostalog i zato što je
napisati "{1}" puno kraće. :-) A znači jedno te isto. Samo je u govoru
čudno reći "otvorena vitičasta zagrada, jedan, zatvorena vitičasta
zagrada". Pa se zato to može kraće reći "singleton jedan".

Ako Vas ta riječ zbunjuje (što je vjerojatno istina, uzevši u obzir
ovo dolje), možete slobodno umjesto toga govoriti "skup čiji je jedini
element jedan", ili nešto slično. Samo ga nemojte zvati jednostavno
"jedan", jer on to nije. {1} nije isto što i 1.

P(A) nije podskup P(B)
egzistira singleton x koji je element P(A), a nije element P(B)

Ne.
Singletoni su samo jednočlani skupovi, i oni nisu jedino što živi u partitivnim skupovima. Npr. u P({1,2,3}) živi i {2,3}, koji nije singleton - on je tzv. "par". No opet, to je samo riječ u govoru, koja služi pri čitanju oznake {2,3} - nema je smisla pisati ovako.

No cijela ova priča dobiva puno više smisla ako "singleton" u njoj
jednostavno zamijenite sa "skup". Pod tom zamjenom, idemo dalje.

skup x je element P(A)
skup x nije element P(B)
skup x je podskup od A
skup x nije podskup od B
za svaki y koji je element skupa x, y je element od A
egzistira y koji je element skupa x, a y nije element od B
iz toga svega slijedi: A nije podskup od B
što je u kontradikciji s pretpostavkom da je A=B.
( Nisam pisala BSOMP matematičkim znakovima jer nemam pojma gdje bi se nalazio, npr.znak za egzistenciju).

ASCII nije baš prilagođen math-pisanju, slažem se. :-/ Najbolje što
Vam mogu ponuditi je MathSCII. Naravno, uvijek
možete i pisati riječima - ovdje se ne morate žuriti. (-:

DeMorgan, redoslijed kvantifikatora, te logika i hrvatski jezik

2004-12-19T01:37:00.000+01:00

studentica:

Pa krenimo: De Morganov princip je način provjeravanja istinitosti sudova pomoću tablica istinitosti ili...

Ne baš. DeMorganov princip se danas primarno spominje kod skupova, i označava tvrdnju da je komplement unije jednak presjeku komplemenata, te da je komplement presjeka jednak uniji komplemenata pojedinih skupova:
S\.(AuB)=(S\.A)n(S\.B) & S\.(AnB)=(S\.A)u(S\.B) .

S vremenom, pojam se proširio i na ostale izomorfne teorije, gdje imamo sličnu situaciju. Npr. u logici sudova (to je ovo što smo mi radili na prvim vježbama, bar kao uvod), negacija disjunkcije je konjunkcija pojedinih negacijā, a negacija konjunkcije je disjunkcija pojedinih negacijā
(!(P&Q)<=>!Pv!Q) & (!(PvQ)<=>!P&!Q) .

Bit će možda još takvih primjera, i svi će se oni u nekom smislu zvati "De Morganov princip", ali ovo su dva najvažnija. Zanimljivih stvari o logici sudova, između ostalog i o De Morganovim pravilima, može se naći na ovom mjestu.

1. Relativne izjave, npr. 'Osijek je daleko.', nisu sudovi jer sve
ovisi o tome tko to govori; meni npr.nije daleko, al će nekom iz, kaj ja znam, Madrida (pazi primjera...) biti; jel to to?

Otprilike. Nisam vas htio s tim zbunjivati na vježbama, zato što stvarno mislim da je to zbunjivanje. Vjerujte mi, nikad u toku svog studiranja matematike nećete trebati procjenjivati je li takva izjava sud. :-) No možda dobro dođe da se ponovi definicija... rekosmo na vježbama:

Sud je svaka tvrdnja za koju možemo (principijelno) nedvojbeno utvrditi je li istinita ili lažna.

Naravno, "Osijek je daleko." jest tvrdnja. No mislim da ćete se složiti da se baš i ne može nedvojbeno utvrditi je li istinita ili lažna, ne samo iz razloga koji se gore naveli, već i zato što nemamo preciznu definiciju pojma "daleko". Npr. možda nekome iz Madrida također neće biti daleko, jer je astronom, pa mu "daleko" znači "dalje od jedne svjetlosne godine" npr. :-)

2. Mi smo u srednjoj naveli primjer za nepotpunu disjunkciju 'Bilo Branka bilo Višnja idu u Požegu.', a mi smo veznik 'illi' naveli za ekskluzivnu disjunkciju...

Također, rekoh na vježbama: sudovi nisu rečenice (općenito). Pokušati doslovno preslikati logičku strukturu na jezičku (baš kao i općenito doslovno prevoditi bilo koji jezik na neki drugi), nema smisla iz više razlogā, jedan od kojih je i ta famozna ekskluzivna disjunkcija (u hrvatskom, that is. Latinski je imao sasvim ok ekskluzivnu disjunkciju, ali mu je zato falio gros drugih stvari:). Pa i onaj "ako i samo ako", za ekvivalenciju, vjerujem da bi jezikoslovcima zadavao glavobolje. [:-)]

Zato su matematičari (uglavnom:) pošteni, pa uvedu novu riječ, koja znači točno ono što oni žele da znači (usp. Humpty Dumpty;). U slučaju ekvivalencije to je "akko" - po uzoru na engleski "iff" . U slučaju ekskluzivne disjunkcije to isto tako može biti
"illi", po uzoru na engleski "orr" . U slučaju nekih drugih logičkih veznikâ to mogu biti i uobičajeni hrvatski veznici (npr. konjunkcija se obično prevodi s "i", iako, kao što smo vidjeli, može značiti i "a", i "ali", i još hrpu drugih), ali treba imati na umu da nijedan prijevod nije uvijek potpuno čist, pogotovo kad želimo prevesti nešto što je nedvojbeno logički puno konzistentnije u nešto tako vague poput prirodnog jezika.

Bottom line: "akko", "illi" i tome slični (naučit ćete ih još hrpu tijekom studija) nisu "službena matematika" - npr., meni je mentor izbacio jedan "akko" iz magistarskog rada:-o. Samo predstavljaju neki prijelazni sleng, za ljude koji bi htjeli pisati logiku hrvatskim jezikom, a još se nisu potpuno sprijateljili sa simbolima poput "<=>", "V", i sličnih.

3. Na tvom site-u ima primjer, mislim da je neš o prirodnim
brojevima, uglavnom, radi se o tom da se mora pazit koji se kvantifikator stavlja prvi i da sudovi nisu semantički jednaki ako je prvo uptrebljen univerzalni, a drugi put egzistencijalni kvantifikator, unatoč tome što se ništa drugo ne mijenja; dakle, mijenja se samo redoslijed.

Točno. A napravili smo ga i na vježbama, ako se ne varam... "od svakog realnog broja postoji veći prirodni broj" nije isto što i "postoji prirodni broj veći od svakog realnog broja", da i to doslovno prevedemo na hrvatski. :-)

Geneza i eksplicitna formula za Ar ch, kodomena i slika, restrikcije i inverzne funkcije

2004-12-19T01:29:00.000+01:00

David:

Pitanje je: Treba ispitat da li je cosinus hiperbolan bijekcija

Nije. ch(-1)=ch1 (općenito, ch je parna funkcija), dakle nije injekcija (realno). Također, ch (realno) je uvijek pozitivan (štoviše, >=1), pa nikad ne poprima vrijednost npr. 0 - nije ni surjekcija.

i ako je napraviti inverznu funkciju?

Traži se valjda restrikcija koja će biti bijekcija na prikladno odabran skup, i onda njena inverzna funkcija.

Cos hiperbolan ima oblik parablole

Misliš na graf, valjda.
Ne, nema oblik parabole, iako je sličan. Možda znaš (razvoj u red) da je
chx=1+x²/2+x⁴/24+x⁶/720+.....
Ovaj dio 1+x²/2 bi još mogao predstavljati jednadžbu parabole, no ovaj "ostatak" nakon toga to nikako nije. Doduše, nazivnici u "ostatku" jako brzo rastu, pa za male xeve stvar izgleda slično.

i znam da se onda uzima pozitivni krak u podrucju [0 , ~+>

Točnije, domena se restringira na R⁺₀=[0,+oo> (da bismo imali injektivnost). Kodomena se restringira na [1,+oo> (da bismo imali surjektivnost).

Sada mene zanima da li se ona formula od ch(x) mjenja zbog restrikcije ili ostaje ista?

Sama formula ((e^x+e^-x)/2) ostaje ista, mijenja se samo područje primjene - u njoj je uvijek x>=0, i znaš da ćeš kao rezultat dobiti nešto >=1 . Te dvije stvari ti omogućuju da nađeš "inverznu funkciju", koja se u ovom kontekstu zove Ar ch .

Znaci uzmem restrikciju na [0,+oo> i radim ineverznu funkciju od y=(e^x+e^-x)/2. Nakon rjesavanja dobijem u^2 - 2yu + 1 = 0 (napravio sam supstituciju u = e^x )
Onda dobijem dva slucaja ali uzmem samo u > 0 zbog restrikcije i dobijem u = y + ( y^2 - 1)^1/2

Ovo je ok, ali argument za to nije dobar.
Naime, i drugo rješenje, y-sqrt(y^2-1), je isto >0 za y>=1 (to se lako vidi: razlika hipotenuze i jedne katete, ako je druga kateta jednaka 1).

Problem je u tome što (ref drugo rješenje) nije veće od 1, a moralo bi biti ako je e^x za x>=0. Zato i jesmo restringirali x na R⁺₀.

Još jednom: u>0 uvijek. No restrikcija domene nam kaže da treba biti i u>=1, i onda ovo drugo rješenje otpada.

(Inače, restrikcija kodomene nam kaže da i y>=1, i to moramo imati eda bi onaj korijen gore imao realnog smisla.)

i onda dobije da je e^x = y + ( x^2 - 1)^1/2 i onda
x = ln ( y + ( y^2 - 1)^1/2 )
I na kraju dobijem da je ch^-1(x)= ln ( x + ( x^2 - 1)^1/2 )

Please, ne zovi ga ch^-1 . Postoji razlog zbog kojeg se zove posebnim imenom, Ar ch. A naveden je (ref razlog) gore - to nije
prava inverzna funkcija od ch, jer nju ch ni nema - nije bijekcija.
Baš kao što npr. arc sin nije sin^-1, jer sin nema inverznu funkciju - nije bijekcija.

uglavnom sam sve shvatio samo imam jos jedno pitanje
U tome zadatku moram uzeti restrikciju domene da je od [1,+oo> da drugo rjesenje ne vrijedi ako, stavi da je od [0,+oo> onda drugo rjesenje ulazi u obzir.

Ne. Restrikcija domene je na [0,+oo>. Ali varijabla iz domene je x, ne u. u je e na x. A ako je x@[0,+oo>, onda je u@[1,+oo>.

Dakle, [1,+oo> nije domena (bar ne za funkciju Ch - jest za funkciju Ch o ln). To je samo "pomoćna domena" za pomoćnu varijablu u.

Ana:

Koja je razlika izmeðu slike funkcije i kodomene?

Hm. Kodomena je nešto eksterno, dio definicije funkcije a priori. Jedna od tri stvari koje su zadane kad se funkcija zadaje kao uređena trojka - domena, kodomena i graf (ponekad "domena, kodomena i pravilo preslikavanja").

Dok je slika funkcije nešto interno, ne zadano, a posteriori, što se zaključuje na osnovu domene i pravila preslikavanja. Uvijek je podskup kodomene (ako je funkcija dobro definirana), a ako su jednake (slika i kodomena funkcije), funkciju zovemo surjekcijom.

Npr. za funkciju f:[2,3]->R⁺;x|->1/x, R⁺ je kodomena. To jednostavno piše u definiciji. No slika je nešto što se treba izračunati, i ovdje se lako dobije da je slika od f skup [1/3,1/2]. Dakle, f nije surjekcija.

Da stvari budu malo kompliciranije, u analizi se često realne funkcije realne varijable zadaju samo pravilom preslikavanja f(x)=nešto. Za kodomenu se tada po defaultu uzima R, a za domenu tzv. prirodna domena - skup svih x-eva iz R za koje gornje "nešto" ima realnog smisla. (Takva funkcija se, prirodno, onda smatra surjekcijom ako za svaki realni y postoji x iz prirodne domene koji se preslikava u njega.) Primijetimo da to malo twista gornju karakterizaciju - "domena" je sada nešto a posteriori, što nije eksplicitno zadano, već se računa iz pravila preslikavanja. No to nije domena u punom smislu riječi - zato se zove dodatnim imenom "prirodna" domena, u smislu "defaultna domena" - ako se ne kaže drugačije.

to znači da x^2 nije surjekcija (kodomena je R, a slike [0,+beskon.>)? Mogu li onda odredit inverz te funkcije?

Striktno govoreći, ne te funkcije. I pri tome nije toliki problem surjektivnost ("inverzna" funkcija jednostavno neće biti definirana u točkama koje ova funkcija ne poprima), koliko injektivnost (ako se nekoliko točaka preslikava u isti y, pitanje je koju od njih odabrati za inverznu sliku y-a ). A kvadriranje nije ni injektivno -- (-x)^2=x^2, za svaki x.

No tzv. "vlakna" (skupovi točaka koji se preslikavaju u istu vrijednost) kvadriranja su mala i organizirana - imaju najviše dva elementa, i tada su oni međusobno suprotni. To čini izbor prilično jednostavnim - od dva suprotna broja, točno jedan je pozitivan i točno jedan negativan, pa u tom slučaju možemo uniformno uvijek odabrati onaj pozitivan broj. Za nulu, naravno, odaberimo nulu.

To odgovara "sužavanju" funkcije - kako kodomene da bi se postigla surjektivnost, tako i domene da bi se postigla injektivnost. U ovom konkretnom slučaju, ako suzimo kodomenu na sliku, [0,+oo> , te domenu na skup gore odabranih brojeva - pozitivni i nula, što se ovdje slučajno poklapa s [0,+oo>; tako dobivena funkcija Sq:R⁺₀->R⁺₀ ;x|->x² će biti bijekcija, i imat će inverznu funkciju. Ta inverzna funkcija se zove (realni) drugi korijen. Ona neće biti inverzna funkciji od koje smo krenuli na cijelom njenom području djelovanja, ali na restringiranim domenama i kodomenama zadržat će svojstvo inverza (komponirana sa Sq daje identitetu, gdje god je kompozicija definirana).

I općenito, za mnoge nebijekcije možemo jednostavno napraviti sličnu stvar. Npr. realna funkcija cos (kosinus) nije surjekcija (poprima samo vrijednosti između -1 i 1), niti injekcija (periodična je, dakle, beskonačno točaka se preslika u jednu vrijednost). No ako restringiramo kodomenu na [-1,1], a domenu na [0,pi], dobijemo novu funkciju Cos:[0,pi]->[-1,1];x|->cosx, koja je bijekcija. Njen inverz zove se arkus kosinus i označava arc cos.

Derivacija, matematika, fizika, malo povijesti i puno filozofiranja

2004-12-19T01:19:00.000+01:00

Rade:

Derivacija je temelj više matematike, a nju su izumili fizičari da bi si olakšali računanje trenutne brzine.

Obje tvrdnje su krive, i to u više aspekata. Ono što se obično u engleskom kolokvijalizmu zove "calculus", diferencijalni i integralni račun, nije danas više "viša" matematika, već nešto prilično nisko na listi intelektualne zahtjevnosti (da, naziv se još uvijek tu i tamo čuje, ali u međuvremenu je izgrađena ogromna hrpa stvari potpuno nezavisno o calculusu, koje su od njega u svakom pogledu "više").

Osim toga, temelj calculusa nikako ne može biti derivacija, pojam koji je zapravo samo vrlo specijalni slučaj legendarnog pojma na kojem je terminološki izgrađen calculus, a to je limes. Naravno, ozbiljni apstrakntni matematičar neće ni limes proglasiti temeljem, nego će to odvesti još dublje, u sam pojam (topološke) potpunosti skupa R, na kojem je izgrađen pojam supremuma, koji onda u jednoj svojoj inkarnaciji stvara pojam limesa.

Za drugu tvrdnju, možda bi bilo informativno pogledati ovaj prikaz. Derivaciju (zapravo calculus u cijelosti) su paralelno izumili Newton i Leibniz, oba matematičari, i kotroverze oko toga tko od njih dvojice treba dobiti veći credit obično se ne gledaju kao sukob matematičara i fizičara, već na nacionalnoj osnovi. Čak i ako ćeš Newtona smatrati fizičarem (ali prethodno se informiraj npr. o kombinatornim aspektima binomnog teorema), derivaciju je paralelno s njim izumio čisti mathematičar Leibniz, koji bi, danas je sasvim jasno, do tih otkrićâ došao i da Newtona nije bilo (samo što bi trebao/imao više vremena da to posloži, no to bi u globalu bilo pozitivno - danas ljudi vjerojatno ne bi imali krive pojmove o "razlomcima" dy/dx).

Štoviše, Leibniz je čak bio proglašen prvim autorom calculusa, no to je bilo samo zato što je Newton bio prelijen objavljivati službene radove, i što se sjetio "braniti svoju intelektualnu čast" tek kad je već bilo prekasno.
I, ne manje bitno, derivacija koja se danas uči po školama, je ona po Leibnizovom pristupu. Nisu fluksije, nego su limesi - čak i kod računanja brzine. Također, notacija je dobrim dijelom Leibnizova, i trećih ljudi - od Newtonove notacije nije ostalo ništa.

Za kraj, zapitaj se što će (empirijskim) fizičarima uopće pojam trenutne brzine? Za sve primjene, sasvim je dovoljna brzina tijekom nekog vremenskog intervala. Gledati brzinu kao posebnu veličinu, kao "koordinatu" koja se mijenja u vremenu na isti način kao i put, je definitivno skok apstraktnosti, kartezijansko-geometrijski filozofski notion koji je doveo do graspanja akceleracije i time do 2. Newtonovog zakona, ali sve se moglo računati i bez njega. Ono što se nije moglo, ili bar ne jednostavno, je matematički(!) modelirati fizikalne sustave, i rješavati ih kao matematičke, interpretirajući rezultate natrag u stvarnom svijetu. Neki bi sad rekli "halleluja za primjene, then"... ali to bi bilo izuzetno kratkovidno. Četvrt tisućljeća kasnije, napokon je jedan fizičar (Einstein, jel) uspio pokazati ono što su mathematičari odavno znali - da je newtonovsko modeliranje svijeta, baš kao i svaki matematički model s gornjim ciljevima, pojmovno pogrešan i u najboljem slučaju samo jako dobra aproksimacija.

U biti, derivacija je neposredan dokaz da je matematika sama za sebe suvišna,

Iako derivacija nikako nije dokaz za to, math definitivno jest sama za sebe suvišna, u smislu da se nijedan mathematičar ne osjeća izvana primoranim baviti mathom. No znanostima poput fizike nikako nije suvišna, i fizičari bi se vjerojatno još uvijek mučili s interpretiranjem Galileievih rezultata, da nije bilo insighta mathematičarâ.

te da ona ne bi mogla postojati da nema fizike, jer ne bi imala
praktičnih rezultata.

Tales se bavio mathom dok pojam "fizika" još nije bio ni definiran.

Praktični rezultati (fizikalnog tipa) nisu esencijalni, njih su kriterijem proglasili fizičari da bi imali kontrapunkt čistoći matha. Poznata je priča o Euklidu i o tome kako je proglasio jednog čovjeka nedostojnim svoje geometrijske škole, zato što je pitao nakon prvog predavanja "a što će to meni u životu?". Vrijedni praktični rezultati matha postoje, ali oni su duboko individualni, u ljudskom umu, psihologiji i pogledu na život - a ne u primjeni math-modela na stvarni svijet.

Naprotiv, primjene zagađuju čisti math, i smanjuju taj blagotvorni efekt na psihu o kojem gore pričah. No u današnjem svijetu tehnologije, one su nužno zlo - slažem se, ali nisu time postale vrijedne.

Što nas dovodi do zaključka: fizika je znanost, sve ostalo je
materija :-)

Fizika definitivno jest znanost (dok math, na primjer, nije - i ja ću prvi to s veseljem izjaviti) - temeljno je empirijska, provjerava rezultate, prvi kriterij nije estetika već sinhronizacija sa stvarnim svijetom (koji je često vrlo ružan), ima vanjski model, ne može dokazati univerzalnu negativnu tvrdnju, itd. Math je direktno suprotno od toga.

No potpuno je bezveze reći da je sve ostalo materija. In fact, od fizike i matematike, fizika je daleko više materijalistička, i s tim će se svi, čak i fizičari, složiti. Math bi mogla postojati i da nemamo nikakav koncept o materiji. Fizika, već puno teže.

Mathematica -- smart programming without loops

2004-12-19T01:07:00.000+01:00

Ralf:

My question is, how it would be possible to avoid the for loop in order to apply a function to all values of Y in a array of tuples {{X1,Y2},{X2,Y2}, {...},...
thus creating a new array of tuples with new calculated Y-values.

Well...
(in further text, I'll assume that l has the list in question, and f is the function you want applied. For example



--> l = {{5, 3}, {2, 8}, {1, 0}, {2, 3}}

--> f@x_:=2x+3

First, a simulated loop:--> MapAt[f, l, {i, 2}~Table~{i, Length@l}]
Here Table constructs loop indices, and MapAt uses them to apply f. The most straightforward solution, directly translated from the loop
one.
A solution that you probably want:
--> l /. {x_, y_} :> {x, f@y}
This uses pattern matching, and it most clearly communicates your intention. Also, for this one you don't have to define f... just write 2y+3 or whatever you want instead of f@y.
But, if you search for completely general solution, this is not it. The problem is that, if l has exactly two elements, pattern matching will do the wrong thing. Although, maybe your list ("array", as you call it) will never have exactly two elements, and then it will be fine.
Kludge for the previous one.
If you really like the previous one, but can't use it because you
can't guarantee that Length@l!=2, you can use
--> # /. {x_, y_} :> {x, f@y} & /@ l
as a kludge. It works in all cases, but it's slightly more convoluted.
The Mathematica way:
How a Mathematica apprentice would probably solve it.
--> Transpose@MapAt[f /@ # &, Transpose@l, 2]
First you transpose l to get all Ys together. Then you map f to them (MapAt 2), and transpose back.
A bizzare one:
Just to be different (and shorter:).
If you really want to hide what exactly you do in that part of code. :-)
--> Inner[#1@#2&,{#&,f},#,{}[[0]]]&/@l
Of course, if you want the result to end up in the same list
variable (l), just prepend "l=" to any of these solutions.

Anyway all of these solutions are much shorter than my elaborate "For-loop" construct.

I believe that. :-) For-loops are sooo old fashioned (NHF). They are
in Mma for(:) the same reasons that eg. goto is in Pascal - backward
compatibility, if you really want it. In fact, Mma also has a Goto.
I suppose you wouldn't use that.:-)

(Except if you want to do something REALLY bizarre, like I did in this post. :-D It's in Croatian, but if you have no translator around, just look at the end of post. There is a BASIC program written in Mma - with Let, Goto, Gosub, Dim, Print, and stuff - if you still remember those things.)

must miss something more than the final square bracket

O, no. Never. :-)
I might miss an ordinary parenthesis (as I did in my previous mail, opened before "in further text") in writing mails, but bracket in Mma code - no way. ;-)

Read it better. There are three closed brackets right after "0" (but
just two right before it). I know it's weird, but that solution was supposed to be weird. ;->

Ok thanks a lot and I might come back to you during the term.

Just one little warning: if you do, send me small pieces of code (there can be a lot of them, but keep them small) - like this one would probably be, just if you remembered to really attach it:-p. I'm talking from experience, for your own good... if you send me a big chunk of code, I'll optimize it in such a way that you might not recognize it. ;-) Not to mention keying in my solution, five rows full of #&/@{}[[0]]s . :-o

Površina poligona pomoću koordinatâ vrhova

2004-12-18T23:26:00.000+01:00

Timi:

Dakle, odmah cu prijeci na stvar, naravno. Frend mi radi nekakav programcic i treba mu knjiga iz Analiticke geometrije. Tocnije, treba mu formula kako izracunati povrsinu tijela (poligona), ako imas zadane koordinate.

Hej... poligon nije tijelo, poligon je lik. Poliedar je tijelo. U 3D prostoru problem je prilično kompliciraniji.

Uostalom, poliedar ne može ni biti zadan samo popisom točaka, jer se mora specificirati koje su s kojima spojene... a da ne govorim o tome da ono moje telefonsko pitanje, jesu li točke po redu, ne bi uopće imalo smisla...

Dakle, pretpostavit ću da se radi o poligonu u 2D... ako nije tako, preciziraj.

Ok, so, zadano nam je n točaka (x_i,y_i) , za i:1~n (n>=3). Također u skladu s telefonskim razgovorom, neka su one tim redom i spojene, odnosno za svaki i, točka (x_i,y_i) je spojena dužinom s točkom
(x_i+1,y_i+1). Preciznije, za svaki osim zadnjeg - točka (x_n,y_n) nije spojena ni sa kakvim (x_n+1,y_n+1) jer njega ni nema, već s točkom (x₁,y₁). No tome možemo doskočiti tako da uvedemo novi vrh s indeksom n+1, i izjednačimo ga s prvim. Dakle,
(x_n+1,y_n+1):=(x₁,y₁). Tako će formula biti jednostavnija.

Prilično je jednostavno. Nacrtaj poligon (u prvom kvadrantu je najlakše pratiti što se događa, ali možeš bilo gdje), i iz svakog vrha spusti okomicu na y-os. Svakom vrhu (x_i,y_i) sad odgovara spojnica (x_i,y_i) s točkom na y-osi (0,y_i), a svakoj dužini koja spaja dva vrha (x_i,y_i) i (x_i+1,y_i+1), sada odgovara pravokutni trapez s vrhovima (0,y_i), (x_i,y_i), (x_i+1,y_i+1) i (0,y_i+1). Osnovice su mu paralelne s x-osi, dakle visina mu je paralelna s y-osi, pa je duljina visine upravo razlika y_i+1-y_i (zapravo apsolutna vrijednost od toga, ali predznak će nam biti od velike pomoći kasnije).

Duljine osnovicâ su mu, naravno, x_i i x_i+1, pa je duljina srednjice njihova aritmetička sredina (x_i+x_i+1)/2. Površina trapeza je umnožak visine i srednjice, dakle površina i-tog trapeza je
P_i :=(y_i+1-y_i)(x_i+1+x_i)/2. Opet, apsolutna vrijednost, no kao što rekoh, predznak će nam trebati.

E sad... imamo n trapezâ. Ti trapezi se dijele u dvije grupe - oni koji djelomično prekrivaju poligon (dakle, odgovaraju stranicama poligona koje su "dalje" od y-osi), te oni koji su u potpunosti "lijevo" od njega (odgovaraju bližim stranicama). Ono što je fora, je da

Kad zbrojimo sve površine trapezâ u prvoj grupi, i od toga oduzmemo ukupnu površinu trapezâ u drugoj grupi, razlika je upravo površina mnogokuta.
Je li trapez u prvoj ili drugoj grupi upravo je izrečeno usporedbom y_i+1 i y_i, odnosno predznakom gornje površine. Dobro, kojoj grupi odgovrara koji predznak, to ovisi o tome kojim redom smo išli obilaziti vrhove ("nadesno" ili "nalijevo"), no to i nije toliko bitno. Ako to fulamo, svi plusevi će postati minusi i obrnuto, pa ćemo dobiti točno suprotno od onog što smo htjeli. Budući da znamo da moramo dobiti pozitivan broj (površina!), možemo to riješiti stavljanjem apsolutne vrijednosti oko svega.

Dakle, površina mnogokuta je apsolutno od sume svih P_i (Zadnji, P_n, se računa s (x_n,y_n) i novom fiktivnom točkom (x_n+1,y_n+1):=(x₁,y₁)). Ona dvojka u nazivniku se može izlučiti iz svega, pa dobijemo formulu P=|sum_i:1~n (y_i+1-y_i)(x_i+1+x_i)|/2 , odnosno
P=|(x₁+x₂)(y₁-y₂) + (x₂+x₃)(y₂-y₃) +...+ (x_n+x₁)(y_n-y₁)|/2 .
Susjedne x-eve zbrajamo, y-ove oduzimamo, i to množimo. Umnoške zbrojimo, uzmemo apsolutnu vrijednost i podijelimo s 2.

Evo i jedan primjer. Izračunajmo površinu peterokuta nastalog spajanjem točaka (2,3),(3,4),(4,7),(3,6),(2,4).

P=|(2+3)(3-4) + (3+4)(4-7) + (4+3)(7-6) + (3+2)(6-4) + (2+2)(4-3)|/2=

=|5*(-1)+7*(-3)+7*1+5*2+4*1|/2=

=|-5-21+7+10+4|/2=|-26+21|/2=|-5|/2=5/2 .

Stvar se može i ljepše zapisati...

2 3    5 *-1 = -5

3 4    7 *-3 =-21

4 7    7 * 1 =  7

3 6    5 * 2 = 10

2 4    4 * 1 =  4

2 3 <-ponovo  +--

               -5 --> 5/2

stvar je u tome da mislim da sam ti jedan podatak zaboravio napomenuti, a to je da taj geometrijski lik nije pravilan.

Gr. "Pravilan" može biti na puno načina.
No iz ovog što je nacrtano, zaključujem da se vjerojatno htjelo reći da nije konveksan (otprilike, ima prevelike kutove:). To je sasvim ok za navedenu formulu.

Moguce je da ovaj nacin koji si mi opisao sljaka i na ovom primjeru, no nisam bas siguran, a ti ces to puno prije skuziti nego ja.

Da, šljaka. Samo izvod treba malo ušminkati, ako ti treba... no mislim
da ti to i nije toliko potrebno. Ukratko, nemaš samo + i - , već
višestruke +eve i -eve, ali svi oni ti točno izlaze iz formule ovako kako je napisana. Nemaš brige. :-)

Nego... u međuvremenu sam uspio malo pojednostaviti formulu. Dakle, onaj izraz pod sumom se može staviti da bude x_i(y_i-1-y_i+1). Naravno, sad imamo dva fiktivna y-a ... y₀:=y_n, s druge strane.

Sve skupa,
P=|x₁(y_n-y₂) + x₂(y₁-y₃) +...+ x_n(y_n-1-y₁)|/2 .
Prilično manje računanja... nema više zbrajanja x-eva.

Duljina krivulje -- "paradoks"

2004-12-18T22:57:00.000+01:00

Boris Davidovič:

Jasno mi je da mogu interpolirati samu funkciju s točnošću epsilon, ali to ništa ne govori o točnosti pronađene duljine (npr polukrug radijusa jedan, čiji je dijametar zapravo spline duljine dva, dok je duljina luka pi, tj. greška određivanja duljine je pi-2, a interpolacija je točna do jedan).

Ne mogu odoljeti da ne navedem jedan primjer te pojave, koji je mene svojedobno vrlo čudio. Možda nekome od mlađih bude zanimljiv. :-)

Cilj nam je aproksimirati spojnicu točaka (0,0) i (1,1) (označimo je s l) izlomljenim linijama koje se sastoje od dužinâ paralelnih koordinatnim osima (ukratko, dozvoljeno je kretanje samo gore, dolje, lijevo i desno - za proizvoljno male pomake). Naravno, na taj način se lako možemo proizvoljno približiti našoj l - npr. konstruiramo niz izlomljenih linijâ:

l₀:=1gore1desno

l₁:=(1/2)gore(1/2)desno(1/2)gore(1/2)desno

l₂:=((1/4)gore(1/4)desno)x4

l_n:=((2^-n)gore(2^-n)desno)x2ⁿ

koji očito "konvergira" k l (maksimalna udaljenost od l_n do l je 2^-n-1/2). No ono što je zanimljivo, je da duljine od svih l_n iznose 2, i nemaju apsolutno ništa s duljinom od l , koja naravno iznosi sqrt2. Još zanimljivije, svaka izlomljena linija gornjeg tipa koja spaja (0,0) i (1,1) imat će duljinu bar 2. Dakle, nema šanse da uđemo već u (1/2)-okolinu od d(l). :-)

(Mislim da primjer, između ostalog, dobro pokazuje kako priče o "beskonačno dugačkim obalama" i "duljinama" fraktalâ nisu tako jednostavne kakvim ih popularna matematika često nastoji prikazati.)

Konvergencija rekurzivno zadanih nizova -- metoda za rješavanje mnogih zadataka

2004-12-18T19:56:00.000+01:00

atv:

Zamolio bih neku dobru dušu da mi kaže kako se riješavaju ovakvi zadaci i da riješi ovaj zadatak : NIZ (An ) zadan je rekurzivno sa A1 =1 An+1=2/3An + 1/11.
Dokazati da je niz konvergentan i odrediti mu limes.(m.analiza 1, 3.kolokvij, 27.1.2003).

Teži dio je dokazati konvergentnost. Nakon toga, odrediti limes je relativno trivijalno. No da bismo dokazali konvergentnost, dobro je imati kandidata za limes. Zato valjda najintuitivniji put rješavanja ide ovako:

Prvo pretpostavimo da je niz konvergentan. Tad ima limes, kojeg označimo s l:=lim_n a_n.
a_n+1=2/3*a_n+1/11 (za svaki n) možemo shvatiti kao jednakost dva niza: lijevi je početni niz pomaknut za 1 , a desni je linearna (afina) transformacija početnog niza. Ta dva niza su jednaka, pa su im i limesi jednaki. Limes lijevog jednak je l , jer pomak indeksa za 1 ne mijenja limes, a limes desnog je 2/3*l+1/11 (jer je afina transformacija neprekidna). Iz jednadžbe l=2/3*l+1/11 lako dobijemo l=3/11.

E sad... to je jedini kandidat za limes (dokazali smo, ako je niz konvergentan, limes mu je 3/11). Treba još vidjeti da niz zaista konvergira. Kako? Po teoremu: ako je monoton i ograničen, npr.

Početni član a₁=1 je veći od l=3/11, pa niz, ako je već monoton, mora padati (zašto?:). Također, u tom slučaju, da bi konvergirao k l, mora biti ograničen odozdo s l (i ovo probaj egzaktno dokazati...). Dakle, cilj nam je dokazati

za svaki n, a_n+1<a_n, i
za svaki n, a_n+1>3/11.

Te dvije tvrdnje je puno lakše dokazati ako se skombiniraju u jednu,

za svaki n, 3/11<a_n+1<a_n,

koja se onda dokazuje indukcijom po n.
Baza je ispunjena: a₂=2/3+1/11, što je očito između 3/11 i 1 (11>3, pa je 1/11<1/3, pa je a₂<2/3+1/3=1 npr.:).

Uzmimo proizvoljan n i pretpostavimo 3/11<a_n+1<a_n.
(Napomena: to ne znači "pretpostavimo da 3/11<a_n+1<a_n vrijedi za proizvoljan n"!)

Množeći to s 2/3 (što je pozitivno, dakle smjer nejednakostî ostaje isti), i dodajući 1/11, dobijemo upravo 3/11<a_n+2<a_n+1, dakle korak je proveden. Po indukciji tvrdnja vrijedi, dakle niz je padajući i ograničen odozdo. Po poznatom teoremu, niz je konvergentan. No gore smo dokazali, ako je konvergentan, limes mu mora biti l .

Zaključak: da, (a_n)_n je konvergentan i limes mu je l=3/11 . QED.

Matematička indukcija -- pogreška pri formuliranju pretpostavke

2004-12-18T05:20:00.000+01:00

Ok, idemo redom.

Da, i mene je fenomen začudio. Činjenica je da je math-dokazivanje jedna prilično osjetljiva stvar, i sva poanta i snaga dokaza je u logičkom odmaku završne konkluzije od početnih premisâ. Kod indukcije je to naročito izraženo: iz tvrdnje da nešto vrijedi za samo jedan prirodni broj, i jedne univerzalne implikacije, ja mogu zaključiti univerzalnu tvrdnju da nešto vrijedi za svaki prirodan broj. Moćno, zar ne?

Samo treba tu univerzalnu implikaciju dokazati kako treba, i iz ispravnih premisâ. Ona ima oblik (Ak@|N)(P(k)=>P(k+1)). Nažalost, ovo je jedno od mjestâ gdje kvantifikatori nisu distributivni prema logičkim veznicima, te gornji zapis nije ekvivalentan zapisu (Ak@|N)P(k)=>(Ak@|N)P(k+1). A to je, nažalost, ono što je jaako puno studenata, i to dobrih studenata, napravilo. U pretpostavci indukcije, napisali su "Pretpostavimo da P vrijedi za svaki k@|N". :-(

E sad, zašto je to tako strašno? Kao što rekoh gore, sva bit math-dokaza je u, da tako kažem, "udaljenosti" između premisa i konkluzije. Ako sam dokazao nešto što je prilično daleko i na puno većoj "visini" od premisâ, dokaz je moćan.
Nažalost, vrijedi i dualno: ako sam dokazao neku od svojih pretpostavki, dokaz je bezvrijedan. Mislim da ćemo se složiti da iz P dokazati P (bar neformalno:) stvarno nije neko umijeće. :-/

A to je upravo ono što ispada kad čovjek čita gore skiciran "dokaz" indukcijom. Prvo se dokaže baza, a onda se iz pretpostavke koja je potpuno jednaka onom što treba dokazati dokaže to isto (zapravo slabije: dokaže se da tvrdnja vrijedi za svaki prirodni broj od 2 nadalje. Tek s bazom to postaje ekvivalentno pretpostavci). Dokaz na taj način ima oblik dokaza P=>P, i zaista se tu ne dokazuje zapravo ništa.

E sad, činjenica je da su ti ljudi uglavnom bar bazu riješili kako treba, i obično je praksa da se za bazu dade koji bod. No kao što napisah gore, baza tek pretvara taj napisan dokaz u dokaz oblika P=>P. Dakle, čak i uz nju dokaz zapravo nema logičke vrijednosti. Nema svrhe dokazati P(1), ako već u sljedećem koraku pretpostavim puuno snažniju stvar (Ak@|N)P(k).

Možda postoji i argument za suprotnu tezu ovdje, a to je princip "nema negativnih bodova". Odnosno, ako je netko napisao samo bazu, dobio je (ja mislim 1 ) bod. Može se argumentirati da ako je netko napisao više od toga, kakvu god glupost napisao, nije fer kazniti ga oduzimanjem tog boda koji je već zaradio. To sad ovisi o asistentu Pažaninu, koji je ispravljao taj zadatak, i bit će na žalbama u utorak. Ja sam pričao s njim o tom problemu, i rekao mi je da je ionako davao samo jedan bod za sâmu bazu, te da smatra da ljudi valjda neće za jedan bod ići na žalbe. Možda vas je potcijenio... u svakom slučaju, osim baze koja može biti diskutabilna (iako sam prezentirao gore argument da ni ona ništa ne vrijedi u ovom kontekstu), smatram da nemate pravo na bodove.

Samo još jednu stvar da napomenem, za ljude koji ovo gledaju "izvana". Brucoši još nemaju dovoljno fluentno math-izražavanje (treba samo vidjeti što sve ja moram čitati na 1. zadatku :-o), i često im se tu debelo gleda kroz prste. No ovo je specifičan slučaj. Na vježbama je posvećeno nekoliko minuta nabrajanju (i možda pokazivanju primjerâ) najčešćih grešaka kod dokazivanja math-indukcijom, i ova je zasigurno bila spomenuta kao najozbiljnija. Dakle, bili ste upozoreni. Matematičkoj strogosti se morate naučiti prije ili kasnije. Ako vam netko eksplicitno kaže da je neko argumentiranje pogrešno, očekuje se da ga ne koristite. :-/

Nesi:

ok, call me blind/stupid/votevr
no koliko mene moj mozak sluzi, ovo je forma indukcije koju su meni uviejk tupili...... ovo u zagradama se kao podrazumijeva, a sad mi se cini da se cijelo vrijeme podrazumijevalo nesto sasvim krivo.....

(*)baza n=1 (recimo)
pretp: n=n (da li ovo zapravo znaci da pretp. da nesto vrijedi za neki, pa onda dokazavsi da vrijedi i za n+1 to povlaci da vrijedi za sve?!!?)
korak... n=n+1 (dokazujemo za n+1)
blabla

jerbo..... prva verzija koju napisah je bila n=n (pretp da vrijedi za svaki n)
a obzirom na raspravu...... [b]a i na razum kojeg upravo ukljucih[/b].... nesto mi tu smrdi.....

dakle, u konacnici pitanje: ovo moje sto napisah(*) je ok?

Ok, idemo još jednom. Pun zapis aksioma matematičke indukcije glasi
P(1) & (Ak@|N)(P(k)=>P(k+1)) => (An@|N)P(n)
, gdje je P nešto dosta komplicirano za definirati, ali neformalno recimo "neko svojstvo prirodnih brojeva" (P(ž) znači da prirodni broj ž ima to svojstvo).

Dakle, indukcija (kao i većina teorema u mathu) ima oblik implikacije. Da bi se ona mogla iskoristiti (konzultiramo tablicu istinitosti), treba dokazati njenu pretpostavku, dakle
P(1) & (Ak@|N)(P(k)=>P(k+1))
, i onda možemo izvući kao zaključak njenu posljedicu,
(An@|N)P(n)
, što je u većini slučajeva upravo ono što nam treba.

Dakle, treba dokazati P(1) & (Ak@|N)(P(k)=>P(k+1)),
i to ima oblik konjunkcije. Opet konzultiramo tablicu istinitosti, i vidimo da treba dokazati oba njena dijela:
P(1)
i
(Ak@|N)(P(k)=>P(k+1)
, da bismo mogli zaključiti da ona vrijedi.

Ovo prvo se obično lako dokaže, i zove se baza. Ovo drugo se obično malo teže dokaže, i zove se korak. Bacimo se na to.
Ta izjava ima oblik univerzalne kvantifikacije po k@|N. Sad nažalost ne možemo konzultirati tablicu istinitosti (to bi bila kao fol konjunkcija beskonačno mnogo implikacijâ tipa (P(1)=>P(2))&(P(2)=>P(3))&....), pa moramo primijeniti neku drugu taktiku.

Razmišljamo ovako: ja moram, in effect, dokazati P(52)=>P(53). No to moram napraviti tako da se u tom dokazu broj 52 može zamijeniti bilo kojim prirodnim brojem (zovem ga k) (a broj 53 njegovim sljedbenikom). Na prvi pogled, to je stvarno dobro napraviti metodom "sve muhe jednim udarcem", odnosno pretpostaviti P(k) univerzalno. Ali gledajmo korak dalje... ako smo stvarno pretpostavili P(k) univerzalno, čemu dovvaga dokazivati P(53) (i to, ironično, koristeći od naše univerzalne pretpostavke samo totalno loše odabran komad P(52):-])? To je onda stvarno samo specijalni slučaj naše pretpostavke, i nije ga nikakav problem dokazati. Pitamo se zašto je to tako? Ofcourse -- zato što smo, silly us, kompletno pretpostavili upravo ono što smo trebali dokazati.

Dakle, treba nam nešto drugo. Intuitivno, trebamo dokazati P(52)=>P(53), ali zapravo ne pretpostavljajući P(52). Zašto to ne moramo pretpostavljati? Zato što će slijediti iz implikacije P(51)=>P(52) koju smo hopefully dokazali, jednom kad imamo P(51). To će također slijediti iz P(50), po implikaciji P(50)=>P(51) koju smo također već dokazali, i tako dalje... odnosno, preciznije, i tako bliže jedinici. :-)

Dakle, na neformalnoj razini, imamo nešto poput beskonačne varijante onog što se obično zove BSOMP. Sjetimo se što je BSOMP... kad jednom shvatimo da se dokaz od točke na koju smo došli račva u dvije grane, koje su međusobno izomorfne ("jednakog oblika", prelaze jedna u drugu jednostavnom zamjenom nekih slovâ nekim drugim slovima, pri čemu zadatak ostaje isti pri toj zamjeni), možemo dokazati samo jednu od njih (svejedno koju), i iz toga će asistent znati zaključiti da smo znali dokazati i drugu.:-) Da umjesto dvije grane imamo njih 20, koje su također izomorfne, dovoljno bi bilo dokazati samo jednu od njih (napisavši na početak nešto poput "BSOMP da vrijedi prvi slučaj od njih 20"). Ta jedna bi onda poslužila kao template pomoću kojeg bi se mogle dokazati i ostalih 19, samo trivijalnim zamjenama slova ili uvrštavanjima specijalnih slučajeva. Da ih umjesto 20 imamo beskonačno, po jednu za svaki prirodni n, dovoljno bi bilo dokazati da za neku granu od njih, za neki n@|N, dokaz prolazi.

I zato korak indukcije ima takav oblik. Pretpostavi se da za neki n@|N (koji se onda obično označi s k, da se izbjegne konfuzija s čudnom notacijom n=n+1:) vrijedi P(k) , i iz toga se dokaže P(k+1). Na taj način dokazana je implikacija P(k)=>P(k+1), koja je zaista template za sve implikacije u gornjoj beskonačnoj konjunkciji: P(1)=>P(2), P(2)=>P(3), itd. Dakle, dokazano je (Ak@|N)(P(k)=>P(k+1)), i to bez pretpostavke (Ak@|N)P(k) (koja je naravno samo drugo ime za (An@|N)P(n), što trebamo dokazati). A to je upravo ono što smo tražili.

Primijetimo podvučenu riječ "intuitivno" gore. To pretpostavlja da univerzalna kvantifikacija ima oblik "beskonačne konjunkcije", što baš i nije logički definabilno u istom frameworku (tzv. logika prvog reda) unutar koje se obično radi gorespomenuta indukcija. Postoji i strogo logičko objašnjenje za to, no bojim se da je pomalo izvan opsega ove diskusije. Zato bih samo napisao jedan jednostavniji slučaj, koji dobro pokazuje zbog čega tu univerzalna kvantifikacija prelazi u egzistencijalnu.

To će biti za slučaj da P(k+1) zamijenimo tvrdnjom koja ne ovisi o k. Dakle, recimo da je to neka tvrdnja Q. To jest bitno pojednostavljivanje, ali će, vjerujem, pokazati što se događa.
Dakle, imamo (Ak@|N)(P(k)=>Q). Pogledajmo tablicu istinitosti, i vidjet ćemo da je formula P=>Q ekvivalentna formuli (!P)vQ (i inutitivno, math-implikacija da P povlači Q upravo znači da P ne vrijedi, ili pak Q vrijedi).

So, imamo (Ak@|N)(!P(k)vQ) . Dakle, za svaki prirodan broj k, imamo dvije mogućnosti: u prvoj, !P(k) , a u drugoj, Q. No druga ne ovisi o k , pa ako vrijedi Q (neovisno o k), ne mora uopće vrijediti nijedan !P(k). S druge strane, ako Q ne vrijedi, druga mogućnost otpada za svaki k, pa uvijek vrijedi !P(k). Sve u svemu, univerzalno imamo dva slučaja: u prvom Q , a u drugom (Ak@|N)!P(k). Odnosno, imamo tvrdnju ((Ak@|N)!P(k))vQ. Ako je hoćemo napisati u obliku implikacije (da izvučemo tu implikaciju van), pogledajmo gore, moramo je dovesti u oblik !P'vQ', odnosno prvi disjunkt mora biti negacija.

To možemo, ako se sjetimo formule za negiranje kvantifikatora -- negacija egzistencijalnog je univerzalni. Odnosno, naš prvi disjunkt, (Ak@|N)!P(k) je zapravo !(Ek@|N)P(k) . So, naša tvrdnja ima oblik
(!(Ek@|N)P(k))vQ , pa je možemo zapisati kao implikaciju
(Ek@|N)P(k)=>Q.

Sjetimo se od čega smo krenuli, i vidimo da je
(Ak@|N)(P(k)=>Q)
ekvivalentno s
((Ek@|N)P(k))=>Q.

Dakle, da za svaki k tvrdnja P(k) povlači Q, ekvivalentno je tome da tvrdnja "za neki k vrijedi P(k)" povlači Q . Naravno, kao što rekoh gore, kad Q ovisi također o k, stvari su kompliciranije jer se scopeovi zapetljavaju, ali u osnovi se događa ista stvar -- u pretpostavci, univerzalna kvantifikacija prelazi u egzistencijalnu. "Pretpostavimo da vrijedi za neki k."

i drugo, zasto se prije nije RIJECIMA govorilo? i ZAPISALO na plocu RIJECIMA?

Da bih napisao ovo gore, trebalo mi je vremena kao za jedne prosječne vježbe ( 2 sata). Ok, s pripremom bi možda bilo malo manje. Ali definitivno, takve stvari se pri ovom programu i tempu _ne stignu_ napraviti.

Sad jasno zašto želim logiku i teoriju skupova na prvoj (zapravo nultoj) godini? Ne da mučim studente... već da im omogućim da govore konzistentno, i da ih ne razumijemo mi , već i oni sami sebe.

Gore je boldano tvoje "a i na razum kojeg upravo ukljucih"... koliko si dosad dokaza indukcijom napravila? Neću reći da su svi bili potpuno bezvrijedni, ali definitivno bi imalo više smisla da ti je ovo gore netko prije rekao, zar ne?

a ne samo napisati n=n ili k=n ili neku inkarnaciju istog..... i smatrati da se podrazumijeva ovo 'neki n', kao sto rekoh, moj prvi impuls je bio reci 'za svaki'

Da, i ovo "n=n" isto vidjeh, i apsoštrumfno mi nije jasno kako netko može takvo nešto napisati. Što je onda korak, "n=n+1"?? :-/ "Za n=n+1" vrijedi sve, jer to ne zadovoljava nijedan n@|N.

Ako se već želi labelirati etape dokaza bez puno razmišljanja, standardne labele su "n=1","n=k"&"n=k+1".

Nesi:

zapravo sam mislila na sljedece:
ne pisati [latex]\forall k \in N[/latex] vec pisati [b]za neki [/b][latex]k \in N[/latex]

na ploci nisam (I believe) NIKADA vidjela da pise 'pretpostavimo da za neki k iz N vrijedi'

Pa iskreno se nadam da nisi ni vidjela da piše [latex]\forall k\in\bf N[/latex] (u pretpostavci indukcije po k).

to su mozda rekli - ali to ispari...... :roll:

Hm... pa da ti i piše u bilježnici iz kolegija koji si slušala prije dvije godine, jednako bi dosad isparilo kao i iz glave... ne li?

a jedino pisano bi bilo 'n=k' ili 'n=n' bez icega vise, uz, kao sto rekoh [u]mozda[/u] receno, ali cisto sumnjam.....

Mi smo to rekli. Bar se nadam, svi. Jer u vježbama po kojima svi radimo (krckovim), bilo je eksplicitno naglašeno kao česta greška. A što se tiče pisanja, čitaj dolje...

a cini se da je upravo tu big problem - prvih par puta bi bas rijecima trebalo zapisati 'pretp. da za NEKI k iz N vrijedi....' 'idemo provjeriti da li vrijedi za k+1'....<blabla dalje>

a tako necega se ne sjecam.....

The problem is, ljudima se previše na prvoj godini tupi s izomorfizmom intuitivnog shvaćanja i strogo logičkog kvantificiranja. I zato (IMO) ljudi imaju toliko problema sa shvaćanjem implikacije, zato mnogi ne kuže poantu dokaza metodom kontradikcije, prazan skup im predstavlja konceptualne probleme, i hrpa drugih stvari.

Kakve to veze ima s ovim? Kod mnogo njih, pogotovo ovih naprednijih studenata (koji su češće i napravili tu grešku), kvantifikatori su samo nešto što se onako "ofrlje" doda na izjavu, čisto kao neko pojašnjenje. I u tom mindsetu, [latex]\forall[/latex] znači "razmišljam univerzalno" (ono što engleski jezik označava članom "a"), dok [latex]\exists[/latex] znači "razmišljam partikularno" (ono što se u engleskom označava s "the"). A to u mnogim primjerima dovodi do gadnih miskoncepcijâ. Nemogućnost shvaćanja da za sve elemente praznog skupa vrijedi bilo što, je jedna od njih. Ovo o čemu ovdje pričamo je druga.

Jer stvarno, u tom mindsetu, čovjek samo želi reći "ovo što tu pišem, moći će se pretpostaviti, i iz toga dokazati što već treba, što god k bio. Razmišljam univerzalno". Da smo napisali na ploču "za neki", i to podvukli/istakli/whatever, dogodilo bi se nešto još gore /iako bi se možda za to dobilo više bodova:/. Čovjek bi rekao "aha, razmišljam partikularno", dokazao da recimo P(1)=>P(2), i gotova stvar. Suptilne stvari poput dosega pojedinih pretpostavki, i ostali detalji koji su bolno detaljno raspisani u gornjem postu, ostaju zauvijek skriveni.

Zato ja jednostavno eksplicitno upozorim ljude da ne smiju napisati "za svaki", i objasnim im zašto (otprilike kao ono što napisah gore, samo kraće:), ali ne pišem ni "neki", jer bih to vjerojatno prije ili kasnije napisao kao "[latex]\exists[/latex]", a iz gore opisanih razlogâ, mislim da bi ih to zbunilo još više. Jednostavno objasnim šprancu, dam intuitivno objašnjenje zašto ona radi, i nakon toga koristim labele "n=1","n=k"&"n=k+1" , uz napomenu da će o striktnim scopeovima pojedinih varijablî ovdje naučiti tek nešto kasnije.

(Osim toga, kad se piše strogo simbolički, nesporazum nestaje. Samo treba zatvoriti zagradu na pravom mjestu.
"(.za svaki k.)(pretpostavimo da vrijedi P(k) ...i iz toga dokažimo P(k+1)...)" je sasvim ok. No ljudi onda pišu polusimbolički, jednostavno ne stave zagrade, i u prvom retku ostane samo
za svaki k, pretpostavimo da vrijedi P(k).
Još se to onda "prevede" na klasični Analiza-dijalekt, koji stavlja kvantifikatore na kraj, i dobiješ
pretpostavimo da vrijedi P(k) za svaki k,
dakle, katastrofu.)

tuzno je da tek na trecoj godini postanem svjesna sto indukcija zbilja jest, a za nju mi pile vec 7 godina.... ali taj famozni 'neki' mi prije (u srednjoj) nije bas nesto posebno znacio
a na faxu su ga zaboravili propisno istaknuti.....

Da ti pravo kažem, nemam blagog pojma gdje bi ljudi ovo (što gore napisah) trebali čuti. Pravo mjesto bi bila neka nulta godina, gdje se uči jezik i samo jezik. (Pa zaBoga, ne učiš npr. norveški tako da te netko baci u Norvešku i pusti te da učiš metodom pokušaja i pogrešaka... prvo imaš bar neku probnu simulaciju.) Ovako, stvarno to ostavljam "za poslije", kao i hrpu stvari, misleći "a valjda će to naučiti na logici/teoriji_skupova/...", no nekako više nisam siguran da je to dobra taktika. Anyhow, uvijek postoji hr.sci.matematika, gdje se mogu raspisati koliko želim. ;-)

meni su to uglavnom bile samo labele.......
cinimise da mi je tek sad jasno zasto mi nikad nije sve stimalo s indukcijom...... uvijek mi je nes fallio i nikad mi nije 'legla'
do sada :g:

Meni se čini da je tako sa svim math-nerazumijevanjima. Glavni problem je što se uči obrnutim redom. Skoro svaku stvar prvo naučiš kao glupu mehaničku metodu, a tek onda, često i desetak godina kasnije, naučiš _zašto_, dovvaga. :-/