Nije li PA sigurno konzistentna jer ima za model prirodne brojeve?

 To je svakako zanimljivo pitanje. Prvo treba precizirati što si zapravo htio reći - vjerojatno to da je _skup_ prirodnih brojeva, zajedno s odgovarajućim funkcijama za operacije, i relacijom uređaja, i nulom kao istaknutim elementom, struktura prvog reda u kojoj vrijede svi aksiomi PA. No kako točno znaš da ta struktura postoji? (Ne direktno povezano, ali da ti pokažem koliko su stvari komplicirane: čak i ako postoji, kako znaš da je jedinstvena do na izomorfizam? Jesi li siguran da neka od brojnih hipoteza o prirodnim brojevima (npr. Collatzov problem) nije zapravo nezavisna od aksioma, što bi bila prilična besmislica ako doista vjerujemo u _the_ strukturu opisanu tim aksiomima?:)

Iako je točno da "skup" gore ne mora značiti "ono što je opisano punom teorijom skupova" (npr. teorija Triv koja se sastoji samo od formule "postoji x postoji y ne (x jednako y)" očito ima za model bilo kakav naivni skup od dva različita elementa - recimo, same varijable 'x' i 'y' mogu poslužiti:), za beskonačne skupove praktički nemamo drugi način konstrukcije. Praktički jedina općeprihvaćena struktura unutar koje imamo beskonačne skupove (ne potencijalno, nego aktualno beskonačne) je kumulativna hijerarhija.

Dakle, ono što si zapravo htio reći, u drugoj aproksimaciji, je da, popikani na prava mjesta, u kumulativnoj hijerarhiji skupova opisanoj aksiomima ZF, žive točno oni skupovi koji tebi trebaju: \N, 0, ', +, *, <. No sad je jasno da si samo zamijenio problem težim: kumulativna hijerarhija je model za ZF jednako kao što je struktura prirodnih brojeva model za PA. Dakle, ono što si zapravo rekao, u trećoj aproksimaciji, je da unutar svakog modela od ZF živi model za PA. Ta relacija među teorijama je dobro poznata u logici, i zove se interpretabilnost. Dakle, u četvrtoj aproksimaciji, tvoja tvrdnja glasi: PA je interpretabilna u ZF. I to je sasvim točno, jedino što takva tvrdnja daje samo relativnu konzistentnost. _Ako_ je ZF konzistentna, _tada_ je i PA konzistentna. ("U svakom modelu od ZF živi model za PA" ne povlači "postoji model za PA" ako nemamo još pretpostavku "ZF je konzistentna".) Odnosno, obratom po kontrapoziciji, ako je PA inkonzistentna, tada je i ZF inkonzistentna. No tada ionako imamo većih problema. :-D

Naravno, ovo ti se može činiti kao prevara, "sve visi na ZF". Ali za inherentno beskonačne strukture, to jest doista najbolje što imamo. Probajmo finitistički. Ti bi htio da se ne može u PA dokazati 0=1 (gdje je 1 oznaka za 0', sljedbenik od 0). Kao argument za to navodiš neku strukturu N koja je s početka sasvim jasna, a kraj joj se gubi u daljini. Kažeš da maglovit kraj uopće nije bitan ("don't pay attention to the infinity behind the curtain":), i pokazuješ prva dva objekta u njoj, i kažeš da su sasvim jasno vidljivi i očito različiti. Ja se slažem s tobom, ali iz toga nikako ne slijedi da PA ne može _dokazati_ da su različiti. Grozota inkonzistentnih teorija je upravo da mogu dokazati što god hoće. :-)

Ok, ono što ti zapravo želiš reći je da sve formule koje možemo dokazati u PA moraju biti _istinite_ u N, a 0=1 očito nije istinita u N. No problem je u bazi: za vidjeti da su svi aksiomi PA istiniti u N, trebalo bi istražiti i onaj magloviti dio, a to je problem - sve veći kako idemo dalje. A da se u maglovitom dijelu mogu skrivati svakakvi zmajevi, po mom mišljenju dobro pokazuje sljedeća pričica:

Znamo, po drugom Gödelovom teoremu, da se u PA (ako je konzistentna) ne može dokazati Con, formula koja na prirodan način iskazuje tvrdnju da je PA konzistentna. (Con je jednostavno formula oblika "ne postoji x (x je kod konačnog niza čiji je svaki element ili kod neke instance aksioma PA ili postoje elementi prije njega iz kojih je izveden pravilom generalizacije ili modus ponensa, i čiji je zadnji element kod formule 0=0')".) Međutim, opća je logička stvar (propozicija tamo negdje kod Lindenbaumove leme) da ako T ne dokazuje F, tada je T+{ne F} konzistentna teorija. Drugim riječima, postoji -PA, teorija koja je dobivena tako da se na aksiome od PA doda (ne Con), i ta teorija je konzistentna ako je PA konzistentna. Odnosno, ako postoji N, tada postoji i -N, model za -PA. Štoviše, -N i N ispočetka izgledaju skroz isto: imaš nulu, imaš njenog sljedbenika 1, imaš njegovog sljedbenika 2, 1+1=2, itd. Međutim, u -N je istinita tvrdnja (ne Con), što znači da negdje u njegovom maglovitom dijelu postoji objekt (s kojim treba valuirati x u (ne Con)), koji doista jest kod konačnog niza čiji svaki element je ili kod neke instance aksioma PA (ne -PA!) ili postoje elementi prije njega iz kojih je izveden pravilom generalizacije ili modus ponensa, i čiji je zadnji element kod formule 0=0'. S obzirom na to da je -N (između ostalog) model za PA (svi aksiomi od PA su ujedno i aksiomi od -PA), prirodno je njegove elemente zvati "prirodni brojevi", zar ne? A onda se čini da smo u velikom problemu, jer smo upravo našli prirodan broj koji kodira dokaz 0=1 u PA.

Jesmo li time dokazali da je PA inkonzistentna? Nipošto. Primijetimo da smo ga našli u modelu za -PA. Ako je PA inkonzistentna, tada je i -PA inkonzistentna, pa nema model, pa smo cijelu priču pričali uprazno. Ali ono što priča definitivno pokazuje, je da moramo obratiti pažnju i na magloviti dio - jer nam je netko, da je bio baš jako zločest, umjesto "lijepe" strukture prirodnih brojeva N mogao podvaliti -N. S početka ne bismo primijetili ništa, jer -N jest model za PA. A ipak, -N tamo negdje "iza zavjese beskonačnosti" sadrži objekt koji pokazuje da je PA inkonzistentna.

Sad se vjerojatno osjećaš još više prevarenim - pobogu, kako isti swindle ne prolazi za očito konzistentne teorije, poput one gornje teorije Triv? Kvaka je u prvom koraku. Drugi Gödelov teorem ne prolazi za prejednostavne teorije - između ostalog i zato što u njima nema smislenog pojma kodiranja jezika, formula i dokaza, pomoću kojeg se može konstruirati formula koja iskazuje konzistentnost. Čak ni beskonačnost modela nije dovoljan uvjet: recimo Presburgerova aritmetika, koja je otprilike "PA bez množenja", je odlučiva i time dokazivo konzistentna, a ima samo beskonačne modele. Ali je svakako nužan uvjet: svaki konačan model je u potpunosti opisiv s konačno mnogo formula.

Eto, mislim da ti je ovo pokazalo koliko "model od PA" može biti netrivijalna beštija. Naravno, ako imaš ZF, onda imaš aksiom beskonačnosti, koji više-manje kaže "postoji model za PA". Ali to je varanje - u smislu da si samo konzistentnost jedne teorije sveo na konzistentnost puno jače teorije. S druge strane, ako si platonist, onda vjerojatno vjeruješ u strukturu N neovisno o našoj spoznaji nje, PA je samo naša nesavršena sjena nastala pokušajem da je spoznamo, i ako nije konzistentna, to je samo jer nismo u potpunosti uspjeli. No u matematičkom platonizmu je izuzetno teško biti dosljedan: recimo, hardcore platonisti vjerojatno vjeruju i u _the_ kumulativnu hijerarhiju H, čiji je ZF samo neprecizni pokušaj spoznaje. No čujem da se baš i ne mogu složiti vrijedi li hipoteza kontinuuma u strukturi H. ;-D

Ograničenje na slobodne varijable

> U TS skripti u odjeljku "Pokrate i proširenja jezika", zašto u "postoji jedinstven x phi", tj. u onome za što je to pokrata, tražimo da y ne bude slobodna u phi?

Uzmite φ:=(𝒙∈𝒚). Tada biste očito htjeli da ψ:=∃!𝒙φ znači "𝒚 je jednočlan", a jednočlani skupovi postoje, pa to nije univerzalno lažna tvrdnja.

No ako biste to raspisali kao ∃𝒚∀𝒙(𝒙=𝒚↔φ), relativno se lako vidi da to jest univerzalno lažna tvrdnja (dokažite za vježbu). Dakle nije ekvivalentna onom što smo htjeli formalizirati.

To je skroz formalni odgovor, koji Vas možda zadovoljava a možda i ne -- možda mislite da samo treba malo drugačije sintaksno iskazati tu pokratu, i bit će u redu. To nije istina, i vidi se ovako: φ ima dvije slobodne varijable, 𝒙 i 𝒚. Ako vežete 𝒙 kvantifikatorom jedinstvene egzistencije, i dalje varijabla 𝒚 mora ostati slobodna. Dakle formula ψ "ovisi" o 𝒚, u smislu da govori o nekom konkretnom objektu označenom varijablom 𝒚. No ovaj raspis o kojem govorimo veže varijablu 𝒚, pa ne "ovisi" o konkretnom 𝒚.

Postoje samo dva načina kako to možemo razriješiti. Jedan je da ne vežemo nijednu varijablu osim 𝒙 u raspisu, no kako očito moramo govoriti o dvomjesnoj relaciji jednakosti, nije jasno kako to napraviti bez uvođenja nove varijable. To ne mora biti 𝒚, može biti recimo 𝒛 -- ali tada, ako je 𝒛 vezana, imamo isti problem s formulom 𝒙∈𝒛; a ako je slobodna u raspisu, odjednom raspis ovisi o nekom objektu o kojem pokrata uopće ne govori (imamo isti problem s druge strane).

Drugi način je da se pomirimo s tim da će raspis pored 𝒙 vezati još neku varijablu, recimo 𝒚, ali onda moramo zahtijevati da ta varijabla ne smije biti slobodna u φ, jer očito neće biti slobodna u pokrati.

Također, "𝒚 nije slobodna u φ" ne valja gledati kao na ograničenje na φ, već je bolje to gledati kao ograničenje na 𝒚. U smislu, nađemo neku varijablu koja se ne pojavljuje u φ, recimo (BSOMP) da je to 𝒚, i onda shvatimo ψ kao pokratu za formulu s tom varijablom. [To je osnovni razlog zašto zahtijevamo beskonačno mnogo varijabli -- sve što nam zapravo treba je da uvijek postoji "nova" varijabla koju možemo uzeti.]

Dakle, naravno da mi znamo i što znači ∃!𝒙(𝒙∈𝒚) [i naravno da zapravo nisam pazio na to ograničenje kasnije:], samo što stroga formalizacija toga zahtijeva suptilnije alate od ovih koje trenutno imamo.

Apsorpcija binomnih koeficijenata

> Jel bi mi mogao pojasniti Veljanov dokaz svojstva apsorpcije binomnih
> koeficijenata, mislim strana 66. u novoj knjizi. Iako mi je samo
> svojstvo kombinatorno jasno (bar se nadam - od n objekata mozemo
> izabrati r na n povrh r nacina ili prvo mozemo izabrati jednog na n
> nacina, a onda od preostalih n-1 jos na r-1 nacina. Buduci da poredak
> nije vazan, dobit cemo r istih odabira (jer smo prvo mogli izabrati
> prvi, pa drugi, .. pa r-ti), pa jos podijelimo sa r i to je to.
>
> On uspostavlja neku fantomsku bijekciju za koju tvrdi da stima, a ja
> bih htio razumjeti i formalno matematicki dokaz jer ipak treba znati
> na taj nacin razmisljati.

Pa... treba se znati tako izražavati, jer si onda siguran da je ono što intuitivno misliš istina. No naravno da je stvar zapravo ovo što si ti opisao, samo preciznije. :-)

Dakle, prvo što treba razjasniti je da u kombinatornim interpretacijama nema razlomaka -- bar ne onih netrivijalnih. :-) Dakle, da bi dokazao (n#r)=n/r*(n-1#r-1) , ide prvo to pretvoriti u manifestno prirodne brojeve, kako bi znao to interpretirati kao kardinalne brojeve nekih skupova (npr. desna strana bi mogla značiti Kartezijev produkt, ali prvi faktor mu očito ne može imati n/r elemenata, ako r(!|)n ).

So, pomnoži s r i dobije r*(n#r)=n*(n-1#r-1) . Sad može obje strane jednakosti interpretirati kao kardinalnosti konačnih skupova, preciznije Kartezijevih produkata. Što je na lijevoj strani? Uređeni parovi (a, A), gdje je A@([n]#r) te a@A. Drugim riječima, broji r-člane podskupove od [n], svaki skupa s nekim njegovim istaknutim elementom.

Što je na desnoj strani? Uređeni parovi (b, B), gdje je (na prvi pogled) B@([n-1]#r-1) te b@[n]. No ovaj [n-1] je malo šašav... zašto bismo izbacivali baš n iz [n]? Puno je bolje izbaciti neki koji već imamo, konkretno b. (Primijeti da je i na lijevoj strani veza između a i A, samo je tamo pozitivna a@A. Ovdje je negativna b(!@)B.) Dakle, zapravo, na desnoj strani brojimo (b, B) takve da je b@[n] i B@([n]\{b}#r-1).

Sad stvarno nije teško vidjeti bijekciju. Ako ti netko da (a, A), gdje A ima r elemenata među kojima je a, ti vratiš (a, A\{a}) -- to je očito par kojem drugi član ima r-1 elemenata među kojima nije prvi član (a). U suprotnom smjeru, ako ti netko da (b, B) gdje B ima r-1 elemenata među kojima nije b, vratiš (b, BU{b}) -- i to je očito na lijevoj strani.

Ta dva preslikavanja su jedno drugom inverzi (ako ubaciš b pa ga izbaciš, dobit ćeš isto ako b nije bio na početku unutra, a isto tako ako izbaciš a koji jest unutra pa ga vratiš, dobit ćeš isto), pa su bijekcije odnosno broj elemenata lijevog skupa jednak je broju elemenata desnog. Kved.

Dynamic vs static typing

(This is a response to a post "Dynamic Languages are Static Languages". I tried to post a comment, but Wordpress told me it couldn't send it, probably because the post in question is too old. So I'm putting it here.)

Your thesis sounds wrong to me. My experience is that strong typing simply disallows some perfectly normal easy programs to be written. And that shouldn't be true if dynamically typed languages are just a special case of statically typed ones.

A few months ago, in order to learn Haskell (in an academic setting), I tried to write a Haskell function to test if a Boolean function was valid (always true). The literature I was using (The Haskell Road to Logic, Math and Programming, by Doets and van Eijck) did that in stages, valid1 for unary functions, valid2 for binary ones... I, as a diligent professional programmer, saw a common bit of code in those, and naively thought I could use recursion (and currying) to make a function valid, so that valid 1 was valid1, valid 2 was valid2, and so on. That way, my code would be much more general, _and_ easier to write.

Imagine my shock when I got an occurs check error. Of course, the problem is that valid1 had type (Bool->Bool)->Bool, but valid2 had type (Bool->Bool->Bool)->Bool, so there simply was no way for valid to have a type, and the GHC told me so. In fact, to be completely honest, valid _has_ a type: a dependent product type, n:Integer->(Bool->...->Bool)->Bool, where there are n arrows inside parentheses. But Haskell can't represent such types, at least as far as I learned (please correct me if I'm wrong).

So, you'll probably tell me I was simply using too weak a type system. But Haskell is the poster child for functional programming. If I can't use that, then what? Miranda is even weaker. Standard ML is not pure, it seems. Coq is not even Turing complete. _Where_ do you find that ideal typing engine you're constantly talking about? Or is it just a platonic ideal, with no implementations in the real world?

Or you're going to tell me that valid function is simply not a function. It is a nonsensical notion, since in a well-typed language you could only have valid1, valid2 and so on. To that I'll tell you it's nonsense. I have perfectly well represented valid in Coq, and Coq surely knows its type theory (however, as I said, it has other problems).

Or you're going to tell me that it's no better in the world of dynamically typed languages. That's simply not true. I can write valid in Python in a few minutes. (Thanks to Python's introspection capabilities, I can even drop the first parameter, and ask my argument function how many bools it would like to receive. But I know static typing fans would probably scream at such an idea.:)

Or you're going to tell me to shut up and simply use lists. Integer->([Bool]->Bool)->Bool is a good approximation, and I did use that variation in the end. But it feels like a horrible kludge. I don't want lists, at least I surely don't want Haskell's interpretation of them as codata. It makes no sense to ask if a Boolean function receiving an infinite list of arguments is valid. And even if it did, I have no way to put something in the "Integer" place. Yes, I can get rid of it, and get it from the length of the list. But the situation is even worse than that: I seem to have no way of restricting the argument to only receive lists with _same_ length. Boolean function that knows how to handle both 2-element and 3-element lists is simply not a valid argument for the function valid I was intended to write.

I don't think I can change your opinion, you obviously know a lot about those things. But maybe you can change mine, by communicating your idea better. What am I missing?

Zanimljivosti za mlađe matematičare

Evo par stvari koje sam napisao nedavno (za Školsku knjigu i znanstveni portal). Na kraju ništa od toga nije ispalo, pa stavljam online. Namijenjeno uglavnom osnovnoškolcima.
Zašto ne smijemo dijeliti nulom?
Generalizirani Fibonacci
Uvod u množenje cijelih brojeva (programi 1,2,3 - pokrenuti u IDLEu, Python 3.3)

Pitfalls of using Mathematica blindly

(I sent this to David Monniaux. Unfortunately, I never got a reply.)

I was reading your article "The pitfalls of verifying floating-point computations". On page 18, you discuss the computing of sin(14885392687), and say:

Both the Pentium 4 x87 and Mathematica yield a result ≈1.671e−10. However, GNU libc on x86 64 yields ≈1.4798e−10, about 11.5% off!

Although your article is meant to show that exact analysis of floating point computations is feasible (and within human reach for simple examples), the quoted sentence is quite a good counterargument:-). Namely, despite appearance, the correct result (formally, the more correct result) is the latter one, 1.48e-10. That can be proved using Taylor series estimates (exact, and pretty simple for such a small argument modulo 2pi) and integer arithmetic (exact, you just have to believe the first 20 or so digits of pi). I can send you computations if needed.

By the way, I think I know what went wrong in your use of Mathematica. You probably used N@Sin@14885392687 (or Sin@14885392687.), which works with machine precision, and doesn't guarantee any digits. In fact, it just calls the C function. If you call Sin with exact argument 14885392687, and use the second argument of N to request specific number of decimals (for example, N[Sin@14885392687,20]), thus employing Mathematica's precision-tracking engine, you will see that the second significant digit is 4, not 6. (For more details see http://reference.wolfram.com/mathematica/tutorial/NumericalPrecision.html#10697.)

ne(ne(intuicionizam)) :-P

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

1. 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?
2. 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.
3. 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.
4. 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.
5. "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.)
6. 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.
7. 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. ;-)
8. 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.)
9. 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.
10. 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. :-)

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

Struktura 2. kolokvija iz UM

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

 
 

Uvod u matematiku - 1. zadaća

[PDF]

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

Lokalna invertibilnost holomorfne funkcije

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

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

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

Rješenja:

Analiza x-gramâ

#!/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

Neki dokazi u sistemu prirodne dedukcije

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

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