tag:blogger.com,1999:blog-74465942014-11-20T00:49:36.188-08:00Bob WaltersRobert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.comBlogger238125tag:blogger.com,1999:blog-7446594.post-4925169722158924712014-11-10T09:03:00.000-08:002014-11-10T10:43:39.865-08:00Sleeping beauty problem IV<a href="http://rfcwalters.blogspot.com/2014/09/sleeping-beauty-problem-iii.html">Previous post in this series</a><br /><br />I have been waiting to see some conclusions coming from discussions of the problem at the <a href="http://www.stubbornmule.net/2014/09/sleeping-beauty-halfer/">Stubborn Mule blog</a>, however the discussion seems to have petered out without a final statement. I admit I did not read the details of Giulio Katis's mathematical model, even though it was very closely related to the (sequential part of ) the compositional model of Markov chains that de Francesco Albasini, Sabadini and I developed in "The Compositional Construction of Markov Processes, Applied Categorical Structures 2011", "The Compositional Construction of Markov Processes II, RAIRO - Theor. Inf. and Applic., 2011", and in Luisa's PhD thesis at the University of Insubria, Como, 2011.<br /><br />However I remain convinced that the matter is simple and I would like to make a couple of mathematical comments.<br /><br /><a name='more'></a><br /><br />A Markov chain is usually described as a particular type of stochastic process. However a simpler starting point is to consider a finite set of states, $\{ 0,1,2,\cdots k \}$ say,and for each pair of states $(i,j)$ a $probability$ $a_{i,j}$ $of\; the\; transition$ from $i$ to $j$, which probabilities form a $k\times k$ matrix $A$ whose row sums are all $1$, a stochastic matrix.<br /><br />It is then easy to see that $A^n$ also has row sum $1$, and we may identify the the $(i,j)$ element as the $probability\; of\; an\; n\; step\; transition$ from $i$ to $j$. This is a $definition$, not a theorem in this context. (It may be made a theorem about a stochastic process derived from $A$, but the (rather difficult) construction of a stochastic process from a matrix involves essentially using the matrix product.) <br /><br />Notice however that there are other row-sum-$1$ matrices related to $A$, for example $1/2(A + A^2)$. What I suggested in the first post in this series is that the $(i,j)$th element of this matrix might be identified with the $probability\; of\; a\; one-{\bf or}-two\; step\; transition$ from $i$ to $j$. Again this is a possible definition, not a theorem. Another example; the matrix $(I+A+A^2+\cdots +A^n)/(n+1)$ is a row-sum-$1$ matrix, which may be identified as the probability of a transition from $i$ to $j$ in from $0$ to $n$ steps.<br /><br />Suppose now we accept the sense of these definitions, let us look at the transition system in the<a href="http://rfcwalters.blogspot.it/2014/08/the-sleeping-beauty-problem-how.html"> first post</a> in this series, and the corresponding $5\times 5$ matrix $A$. To apply the mathematics, I claim that the sleeping beauty needs to make two calculations: (i) what is the probability that she has passed from state $0$ to $1$ in one step? and (ii) what is the probability that she has passed from state $0$ to state $3$ or state $4$ in one-or-two steps? The first step uses the matrix $A$ and results in $1/2$. For the second the matrix $1/2(A+A^2)$ yields a probability of $1/4$ for the probability of passing from $0$ to $3$ in one or two steps, and $1/4$ for passing from $0$ to $4$ in one or two steps, and hence a probability of $1/2$ for passing from $0$ to $3$ or $4$ in one or two steps.<br /><br />Her answer to the question of whether the coin was heads should be $1/2$.<br /><br />Notice that the matrix $(I+A+A^2+\cdots +A^n)/(n+1)$ tends to a limit as $n$ tends to $\infty$ (see [2] for a proof), the limit being a row-sum-$1$ matrix whose $(i,j)$th entry might be defined to be the probability of passing from $i$ to $j$ in any number of steps.<br /><br /><br />[1] Charles M. Grinstead and J. Laurie Snell. Introduction to Probability: Second Revised Edition. American Mathematical Society, 1997.<br /><br />[2] Carl D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM: Society for Industrial and Applied Mathematics, 2001.<br /><br />[3] E. Seneta, Non-negative Matrices and Markov Chains, Springer Series in Statistics, 1973,<br /><div><br /></div>Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-33412818474964542762014-09-19T08:25:00.003-07:002014-11-08T01:55:19.704-08:00Sleeping beauty problem III<a href="http://rfcwalters.blogspot.it/2014/08/the-sleeping-beauty-problem-how-some.html">Previous post in this series</a>, <a href="http://rfcwalters.blogspot.com/2014/11/sleeping-beauty-problem-iv.html">next post in series</a><br /><br />I am writing a third post about the sleeping beauty problem partly because I have seen <a href="http://www.stubbornmule.net/2014/08/sleeping-beauty/">Sean Carmody's post</a> (26th August) in which he describes the problem and expresses his uncertainty about it, and promises an opinion in a future post. We are waiting, Sean, for your ideas on the matter!<br /><br /><br /><a name='more'></a><br /><br />$\bf Note\; about\; comments\; on\; this\; blog $<br />I have never taken very seriously responses to posts at this blog because (apart from spam) there have been very few. After the sleeping beauty posts I did receive quite a few comments as a result of <a href="http://motls.blogspot.com/2014/08/sleeping-beauty-thirders-rudimentary.html">Lubos Motl's reposting </a> on his blog. I allowed several, mostly anonymous, but then I decided I prefer to have some idea of the identity of persons with whom I am discussing. I made it a bit harder to respond to posts. I may reverse that policy since the blog has returned to normal, however in general I will not accept anonymous responses. On popular blogs one sees hundreds of anonymous comments of very variable quality. It is not what I have in mind for this blog. Of course I am interested in serious responses which may persuade me to change my opinions.<br /><br />$\bf Remarks\; about\; the \; sleeping\; beauty\; problem$<br />I want to make a couple of remarks about the sleeping beauty problem. Most people who take the thirder position are not talking about probability but rather the average amount of time spent in a state, or similar concepts such as how much one could win by betting on a state. This is certainly not the probability of arriving in a state at a specified time or times, and in my opinion is not the question under consideration.<br />The other curious feature of discussion of this clearly stated problem is that everyone wants to consider modifications of the problem in trying to persuade their opponents. I am going to commit a similar sin in this post.<br /><br />But first a comment on a strange aspect of the thirder position. Conditional probability classically is about restricting the possible (atomic) events or actions, and results in some events having zero probability, while the remaining events have $\bf increased$ probability. Instead, in the thirder "solution" an action which has probability $1/2$ is changed to have a $\bf lesser$ probability (of $1/3$) as a result of a condition. Strange!<br /><br />$\bf A\; true\; story:\; The \; Tirano-Torino \; Problem$<br />$NOT\; the\; sleeping\; beauty\; problem$<br />(names changed to protect the innocent)<br />One day I was running to catch a train at Milano Centrale, and I had no time to check the platform. I found two trains which were just beginning to depart, one for Torino and one for Tirano, but I did not know which was which. I had to choose which I did with no information. Now it was a dark and stormy night, and the stations are badly signed so after one, two and three stations I was still unable to identify which station we were passing. What was my opinion as to whether I had caught the right train? I had not a clue. I estimated $50\%$.<br /><br />Now let's take the position that I could bet at each station which train I was on. There are more stations from Milan to Tirano than to Torino so I should bet that I am on the Tirano train.<br /><br />Or alternatively, as suggested by one commenter, I should imagine 1000 computers simulating the train voyages repeatedly starting at different times, and obviously I would see that more of the trains were on the Tirano line.<br /><br />Great arguments but I had no idea which train I was on, until of course I recognized a station.Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com2tag:blogger.com,1999:blog-7446594.post-5737780110286692712014-11-03T10:22:00.001-08:002014-11-03T10:24:25.209-08:00Stephen H. Schanuel and Dietmar SchumacherSteve and Dietmar are two mathematicians I knew who died earlier this year. I meant to write something earlier but have been distracted by my own health problems.<br /><br />I knew <b>Stephen Schanuel</b> (14 July 1933-25 July 2014) mainly from his visits to Sydney. During his 1988 visit my friend Bob Bolton took this photograph of him:<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-wnJJFib0FbM/VFfCQM8PKgI/AAAAAAAAB6A/fWSrNU3omfM/s1600/8jan14-4.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-wnJJFib0FbM/VFfCQM8PKgI/AAAAAAAAB6A/fWSrNU3omfM/s1600/8jan14-4.jpg" height="400" width="290" /></a></div><div class="separator" style="clear: both; text-align: left;">My memory of him is that he was enthusiastic as a mathematician, but also <a href="http://www.thefreedictionary.com/skepticism">Missouri-Skeptical </a>of exaggerated claims. I remember he was not very keen on the word "categorification" though of course being well aware of the process of abstraction from objective categories. To visit Buffalo was to be involved in the ongoing Lawvere-Schanuel mathematical discussions. I liked very much Fred Linton's remarks on Steve's death on the Categories List in which he said "no longer does Steve belong so exclusively to his peers, colleagues, friends, and family, as to History".</div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;">I also knew Dietmar (who died on 17th September 2014) from visits to Sydney (I think actually to Macquarie University), and from a visit I made to Wolfville, Nova Scotia. He was great company, and had the odd habit of apologizing, even to the extent of apologizing for apologizing. He was the founder with Bob Paré of the Atlantic Category Seminar and wrote extensively with Bob Paré on indexed categories</div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;"><br /></div><br /><br /><br />Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-28368620791997366502014-10-30T10:34:00.002-07:002014-10-31T07:32:05.946-07:00The mess we are in with scientific publishing II - not in the club<a href="http://rfcwalters.blogspot.it/2014/10/the-mess-we-are-in-with-scientific.html">previous post in this series</a>; next post in this series<br /><br />I mentioned various problems with scientific publishing in the previous post.<br /><br />I neglected to mention the most discussed problems like the ownership of results by private companies, the lack of free access, the uncontrolled costs, the publicly funded work by referees and editors, et cetera.<br /><br />Today I want to talk about another change in scientific publishing which has occurred in my lifetime. When I was young (1970) there were many fewer journals, mostly of scientific societies, and mostly journals of mathematics with a content intended to be of interest to all mathematicians.<br /><br /><br /><a name='more'></a><br /><br />During the last 40 years there has been a proliferation of subject journals owned by small groups of mathematicians, what might be called Clubs (I hesitate to use an Italian word). I am actually a member of the board of such a club, namely the editorial board of Theory and Applications of Categories (TAC). The journal TAC was actually formed partially because of the lack of journals which would accept category theory papers, so it was a defensive move.<br /><br />In any case, belonging to a club one can expect that one's work will be given a reasonable chance of publication in the club's journal. The work need only be of professional standard.<br /><br />The most serious problem arises when one would like to work between two different areas, which is exactly what I have been trying to do for the last 25 years, between Category Theory and Theoretical Computer Science (and in computer science we do not belong to any club).<br /><br />We have just for the nth time had a paper rejected by a computer science journal, this time edited by Rob van Glabbeek and Ernst-Ruediger Olderog.<br /><br />The strange thing is that neither of the two referees reports recommended rejection. One referee wrote in summary: "The paper may be useful to articulate this approach, which has clear connections with deep classical mathematics, but requires a major revision, both with respect to its contents and its presentation, before publication". The second referee recommends publication saying "the novelty is interesting (and substantial)" and further "their ideas are very deep, but often are not appreciated by computer scientists!". This second referee also recommended improving the presentation: "a better presentation would make their ideas more accessible and, hopefully, more appreciated".<br /><br />Of course the editors have the final say. In the covering letter the editors explain their rejection, and refer to other communications they have had, but which are hidden from us.<br /><br />One of the editors' criticisms is that "out of 30 citations, 10 are self citations" which fact is exactly explained by the referees comments to the effect that the work is original and rather outside the existing club. Originality does not seem a reason for rejection.<br /><br />As a result of repeated rejections our work is spread spottily between category theory journals and the occasional slip into computer science journals. This makes it very difficult to give a coherent account comprehensible to computer scientists, and hence their requests to rewrite.<br /><br />Going back to the general remarks about the splitting up of research into specialist journals, it is surprising that this has occurred when publishing outside journals has become extremely open (arXiv). It further supports my feeling that we should be moving towards the PLOS ONE model of general journals.<br /><br />In the next post in this series I would like to examine further our problem with research between category theory and computer science (including more details about our recent rejection).<br /><br /><br />Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-22878793668706099322014-10-04T02:35:00.000-07:002014-10-30T13:38:04.858-07:00The mess we are in with scientific publishing<a href="http://rfcwalters.blogspot.it/2014/10/the-mess-we-are-in-with-scientific_30.html">Next post in this series</a><br /><br />I am a little out of the Italian academic scene since my retirement, but if I understood the recent rounds of hiring in Italy they occurred in the following way. It was possible to apply for "abilitazione", that is a judgment was made if you were at an appropriate level to hold a post. This was made in most cases on the grounds of purely numerical indicators, and was supposed to be a threshold. It was not a competition. A deeper analysis, actually looking at the papers or asking experts who had read the papers, was clearly impossible since, for example, in Computer Science a committee of 5 had to judge in a year the qualities of approximately 900 applicants. (There were even complaints when more than numbers were used, since that gave power to the "barons".)<br />After this judgment a great number of the abilitati were given permanent posts, thus filling up vacancies for some time.<br /><br />The pressure this type of thing puts on scientific publishing is enormous. Referees, while trying to make judgments on papers, now have to consider that they are deciding the careers of young people, the grants for older people, that the prestige of the journal will affect jobs and grants. The reason the pressure is so enormous is that the job and granting committees don't look at the papers, just the numbers.<br />The job of a referee has become impossible, at the same time that there is more and more need for referees since scientists are being forced to publish more and more.<br /><br />Scientific publishing must free itself from these pressures.<br /><br />Thinking about this situation brought back to mind some thoughts of Bernhard Neumann.<br /><a name='more'></a><br />He started a journal, The Bulletin of the Australian Mathematical Society, in 1969 with very specific ideas. I found an account of his ideas in an <a href="http://www.google.it/url?url=http://journals.cambridge.org/article_S0004972700033463&rct=j&q=&esrc=s&sa=U&ei=n7svVK3YBNfzarTfgMgG&ved=0CBQQFjAA&sig2=4rAg5fCJk2nyUd6rsyqzsg&usg=AFQjCNEHM2H6ZxHycOcO_zO2CyoVfedikA">obituary by Cowling, Jones, Morris, Oates-Williams</a>, part of which I reproduce here:<br /><br />"... in his editorial Bernhard made it clear what his future policy would be. He was unhappy not only at the length of time taken by many journals to publish a paper, but also at the way some authors seemed to expect the referee to do half the work for them. He decided that there was a place<br />for a journal that would guarantee swift publishing; and would do this by making rapid decisions on each paper, and not accepting more papers that would fit into the next issue. And, most importantly, not accepting any papers that were not in publishable form; he felt that a paper that required more than half a day's work from a referee was not ready to be published."<br /><br />His idea was that the responsibility for the paper was in the hands of the authors. Referees made only a judgment that the paper was scientifically appropriate - not even that it was correct - that was the authors' problem. It was not the position of referees to put personal manufactured obstacles in the way of publication, as happens so often today.<br /><br />Of course this project failed. The journal soon became a normal journal, but it seems to me that if ever the scientific community manages to escape from the stranglehold of Government-promoted numerical evaluation, then Bernhard's ideas, arising from his experience of publishing in his youth, might be incorporated in a new system of scientific publishing. Bernhard's proposal was made before internet and to some extent arxive now plays the role of the journal he had in mind but without the " half a day's work from a referee" for each paper.<br /><br /><br /><b>Update 11 October 2014</b> I have just discovered from David Roberts' Google+ blog that there is a journal with very similar aims to Bernhard's. It is called PLOS ONE and, commencing in 2006, it has become the largest scientific journal.<br /><b>Update 18 October 2014</b> From a more recent post on David Roberts' blog it seems that there is very little chance for publishing mathematics in PLOS ONE.<br /><br /><br /><br /><br />Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-51895913794785393122014-09-04T01:31:00.001-07:002014-10-24T07:18:59.120-07:00Span(Graph) III: Circuits with feedback<a href="http://rfcwalters.blogspot.it/2014/08/spangraph-ii-circuits-with-feedback.html">Previous post in this series;</a> <a href="http://rfcwalters.blogspot.it/2014/10/spangraph-iv-circuits-with-feedback.html">next post in the series</a>.<br /><br />The two main operations in $\bf Circ$ are composition and parallel as for straight-line circuits, and there are a variety of constants.<br /><br />Today we describe the operation of composition of circuits with feedback in $\bf Circ$.<br /><br /><a name='more'></a><br /><br />$\bf Composition$ If $G$ is a component with left interface $B^m$ and right interface $B^n$ (an arrow in $\bf Circ$ from $B^m$ to $B^n$) and $H$ is a component from $B^n$ to $B^p$ then the composition denoted $G\bullet H$ has left interface $B^m$ and right $B^p$. The graph of $G\bullet H$ has states being all pairs $(x,y)$ of states, one $x$ of $G$ and one $y$ of $H$. A transition in $G\bullet H$ is a pair of transitions $(\alpha,\beta)$, one of $G$ and one of $H$, which however must satisfy the following requirement: the $n$-tuple of right labels of $\alpha$ must equal the $n$-tuple of left labels of $\beta$.<br /><br />This is just the obvious requirement that for both components to change state the signals on the connected ports must be equal.<br /><br />It remains to say what are the left and right labellings of transitions of the composite. The left labelling of a transition $(\alpha,\beta)$ is the left labelling of $\alpha$, and the right labelling of $(\alpha,\beta)$ is the right labelling of $\beta$.<br /><br />The picture of the composite will be the two components joined side-by-side with the right ports of $G$ joined to the left ports of $H$.<br /><br />To make sure that the definition is clear we will calculate the composite of two delay elements.<br />(I notice that I did not say that the delay component is an arrow in $\bf Circ$ from $B$ to $B$ - I hope that was obvious.)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-VbMsI5FqE9o/VAtG4PGzIfI/AAAAAAAAB0w/blCLPB3ui4A/s1600/delay2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-VbMsI5FqE9o/VAtG4PGzIfI/AAAAAAAAB0w/blCLPB3ui4A/s1600/delay2.jpg" height="92" width="320" /></a></div><br /><br />The states of this composite are the four pairs of states, namely $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ which I will write more briefly as $00$, $01$, $10$, $11$ to reduce clutter.<br /><br />There are $16$ candidates for transitions, namely all pairs of transitions but not all satisfy the condition that the labels on the common ports are equal.<br /><br />One transition of the composite comes from the pair $(0\xrightarrow{1/0}1, 1\xrightarrow{0/1}0)$ since these two transitions have the common signal $0$ on the middle wire.<br />This transition of the composite is then $01\xrightarrow{1/1}10$; that is it goes from state $01$ to state $10$, with the labelling being the labels of the free ports. <br /><br />A pair which does not give rise to a transition of the composite is $(0\xrightarrow{1/0}1, 1\xrightarrow{1/1}1)$ since the labels on the middle wire do not agree.<br /><br />I will list all the transitions which do occur in the composite:<br />$00\xrightarrow{0/0}00$, $00\xrightarrow{1/0}10$, $01\xrightarrow{0/1}00$, $01\xrightarrow{1/1}10$, $10\xrightarrow{0/0}01$, $10\xrightarrow{1/0}11$, $11\xrightarrow{0/1}01$, $11\xrightarrow{1/1}11$.<br />Here is the resulting component:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-yTD3-DYAxXs/VAtHAdTquLI/AAAAAAAAB04/HXirMHiMM6M/s1600/delay2b.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-yTD3-DYAxXs/VAtHAdTquLI/AAAAAAAAB04/HXirMHiMM6M/s1600/delay2b.jpg" height="172" width="320" /></a></div><br /><br />You may think of a state as the state of a 2-bit register. On a transition the first bit moves to the second place, the second bit exits as a right signal, and the left signal is inserted in the first bit of the register. The result is a step 2 delay. It is easy to generalize this to the composite of $n$ delay elements: states are the states of a $n$ bit register; on a transition all the bits are moved to the right by one place, the last bit exits as a right signal, and the left signal is recorded in the first place. All this occurs in one transition of the composed $n$ delays.<br /><br />$\bf A\; very\; important\; remark!$ The delay element is a very particular component in which the left signal drives the component into a new state, and the state determines the right signal. We will be soon dealing with components which are quite different, in which the left hand ports are nothing like input ports and in which the the signals on the ports do not determine the transitions.<br /><br /><i>You should not think (in general) of components having input and output ports. Instead you should think that the component has its own transitions, and that the left and right signals are a reflection of the transitions of the component on the interfaces.</i>Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-447320805426939022014-10-19T05:27:00.000-07:002014-10-19T05:27:50.397-07:00Google+I just linked up this blog with Google+. This is a test to see what the effect of that is. I assume my posts will now be visible from Google+.Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com2tag:blogger.com,1999:blog-7446594.post-36497171615226946662014-10-04T13:12:00.002-07:002014-10-04T14:01:59.190-07:00My 1992 FTP site Don't believe any links, or email addresses. Almost all have disappeared. Notice the strange domain name for mathematics at Sydney. <p>We did not get to see the web until at least 1993 when Mosaic came out (though we had to use Chimera on the Appollos). I haven't found my first email but I think it was around 1985 when I went to conferences announcing the importance of email, in particular to us in Australia. Hard to remember those times. <p> <head><title>ftp site at the University of Sydney</title><link href="mailto:walters_b@maths.su.oz.au" rev="made"></link></head><body></body><!--X-User-Header--><!--X-User-Header-End--><!--X-TopPNI--><br /><hr /><a href="https://www.blogger.com/%22msg00060.html%22">[Prev]</a><a href="https://www.blogger.com/%22msg00062.html%22">[Next]</a><a href="https://www.blogger.com/%22index.html#00061"">[Index]</a><a href="https://www.blogger.com/%22threads.html#00061"">[Thread]</a><!--X-TopPNI-End--><!--X-MsgBody--><br /><h1>ftp site at the University of Sydney</h1><hr /><ul><li><i>To</i>: types </li><li><i>Subject</i>: ftp site at the University of Sydney </li><li><i>From</i>: <a href="https://www.blogger.com/%22mailto:walters_b@maths.su.oz.au%22">walters_b@maths.su.oz.au</a> (Bob Walters) </li><li><i>Date</i>: Thu, 02 Apr 92 11:24:12 EST </li><li><i>Sender</i>: <a href="https://www.blogger.com/%22mailto:meyer@theory.lcs.mit.edu%22">meyer@theory.lcs.mit.edu</a> </li></ul><hr /><pre>Date: Thu, 2 Apr 92 13:35:18 +10<br /><br /> SYDNEY CATEGORY THEORY SEMINAR <br /> SYDNEY CATEGORIES IN COMPUTER SCIENCE SEMINAR<br /> Category theory material<br /> Available by Anonymous FTP<br /> from maths.su.oz.au<a name='more'></a><br /><br /><br />This file is README in the sydcat directory of maths.su.oz.au,<br />129.78.68.2, accessible by anonymous ftp.<br /><br />The sydcat directory is for FTP distribution of recent publications, programs,<br />seminar listings and other material of the Sydney Category Theory Group, and the <br />Sydney Categories in Computer Science Group. These groups consist <br />of mathematicians and computer scientists and students at the University <br />of Sydney and Macquarie University, Sydney, Australia,<br />including the following:<br /><br /> Murray Adelman murray@macadam.mpce.mq.edu.au<br /> Brian Day<br /> Robbie Gates gates_r@maths.su.oz.au<br /> Amitavo Islam islam_a@maths.su.oz.au<br /> Mike Johnson mike@macadam.mpce.mq.edu.au<br /> Giulio Katis katis_p@maths.su.oz.au<br /> Max Kelly kelly_m@maths.su.oz.au<br /> Stephen Lack lack_s@maths.su.oz.au<br /> Mark Leeming leeming_m@maths.su.oz.au<br /> Stephen Ma ma_s@maths.su.oz.au<br /> Wafaa (Moynham) Khalil moynham_w@maths.su.oz.au<br /> Wesley Phoa <br /> Usha Sridhar sridhar_u@maths.su.oz.au<br /> Ross Street street@macadam.mpce.mq.edu.au <br /> Sun Shu-Hao sun_s@maths.su.oz.au<br /> Bob Walters walters_b@maths.su.oz.au<br /><br /><br />==========================Instructions======================================<br /><br />FTP LOGIN. Give the following commands.<br /><br /> ftp maths.su.oz.au<br />Login: anonymous (if you don't have an account on maths)<br />Paswd: yoursurname (though any string will work)<br /> bin (if you are retrieving a .dvi file)<br /> prompt off (if you want no ? prompts from mget)<br /> cd sydcat (change directory to _public/sydcat<br /> ls -lt (see what's there, most recent first)<br /> mget filename-1 ... filename-n (e.g. mget catcurrent.Z)<br /> quit (exit from FTP)<br /><br /><br />DVI. If you wish to print paper, calg say, retrieve calg.dvi and<br />associated .eps and .sty files from the subdirectory calg (cd calg first).<br />You must first give the bin command to ftp since .dvi files are not <br />text files. You will then need a dvi to postscript converter<br />which will include the .eps files. Print the resulting postscript file<br />on your host.<br /><br />PROBLEMS. If you have problems in either retrieving or compiling<br />papers, please contact Bob Walters.<br /><br />NOTE. Please note that the IP satellite link between Australia and the rest of the<br />world is saturated most of the time. Large file transfers to non-Australian<br />sites should be spaced out, and should preferably take place between the<br />hours 2300 and 0800 local Eastern Australian time (the local time appears in<br />the ftpd banner at connection).<br /><br />===========================Available papers================================= <br /><br /><br />The following files and directories are available:<br /><br />addresses/catcurrent The Category Theory address list <br /> maintained by Max Kelly and Michael Johnson<br /> Updated 5 March 1992<br /><br />addresses/structdir Vaughan Pratt's latest email address list<br /> Updated 1 December 1991<br /> Release 3.0<br /> Master copy: Boole.Stanford.EDU:~ftp/pub/struct.dir<br /> Maintainer: Vaughan Pratt, pratt@cs.stanford.edu<br /><br />addresses/structdir_max Max Kelly's corrections to structdir<br /> 3 Dec 1991<br /><br />papers/walters/af A directory containing af.dvi for the paper<br /><br /> M. S. Johnson, R.F.C. Walters, Algebra Families<br /><br />papers/walters/como A directory containing como.dvi and<br /> some associated postscript files for the paper:<br /><br /> S. Carmody, R.F.C. Walters, Computing quotients of<br /> actions of a free category.<br /><br />papers/walters/calg A directory containing calg.dvi and<br /> some associated postscript files for the paper:<br /><br /> S. Carmody, R.F.C. Walters, The Todd-Coxeter Procedure<br /> and Left Kan Extensions.<br /><br />papers/walters/coinv A directory containing coinv.dvi for the <br /> paper<br /><br /> G.M. Kelly, Stephen Lack, R.F.C. Walters<br /><br />papers/walters/imp A directory containing imp.dvi.Z for the paper<br /> <br /> R.F.C. Walters, An imperative language based on <br /> distributive categories<br /><br />papers/walters/imp2 A directory containing imp2.dvi.Z for the paper<br /> <br /> Wafaa Khalil, R.F.C. Walters, An imperative language<br /> based on distributive categories, II.<br /><br />papers/walters/ext A directory containing ext.dvi.Z for the paper<br /><br /> Aurelio Carboni, Stephen Lack, R. F. C. Walters, An introduction to <br /> extensive and distributive categories.<br /><br />papers/phoa Contains notes and papers by Wesley Phoa.<br /> His current email address, till July 1992, is: wkp@dcs.ed.ac.uk <br /><br /> [Note that the subdirectories contain postscript files only. The papers<br /> fibs,topoi,(bohm),poly,pcf may not be in their final form and should<br /> be treated as drafts. Comments will be gratefully received. 8/3/92]<br /><br />papers/phoa/fibs.ps "Fibrations (outline)"<br /> --an informal introduction to fibrations, with a<br /> view to the semantics of typed lambda-calculi<br /><br />papers/phoa/topoi.ps "Toposes (outline)"<br /> --an informal introduction to toposes, with a<br /> categorical flavour, including a detailed<br /> description of the internal language of a topos<br /><br />papers/phoa/synth.ps "Effective domains and intrinsic structure"<br /> --describes a category of `synthetic domains'<br /> in the effective topos<br /><br />papers/phoa/graph.ps "Building domains from graph models"<br /> --ditto, in the realizability topos arising from<br /> the r.e. graph model of the lambda-calculus <br /><br />papers/phoa/bohm.ps "From term models to domains"<br /> --ditto, for the closed term model in which<br /> terms with the same Bohm tree are identified<br /><br />papers/phoa/sml.ps "A proposed categorical semantics for Pure ML"<br /> (with M. P. Fourman, LFCS)<br /> --sketch of a semantics for SML using synthetic<br /> domain theory; focuses on the Modules system<br /><br />papers/phoa/subtypes.ps "Using fibrations to understand subtypes"<br /> --informal account of categorical models for <br /> subtyping and bounded quantification<br /><br />papers/phoa/poly.ps "A simple categorical semantics for first-order<br /> polymorphism"<br /> --describes how any cartesian closed category can<br /> be used to model ML polymorphism, using the<br /> notion of `polynomial category'<br /><br />papers/phoa/pcf.ps "A note on PCF and the untyped lambda-calculus"<br /> --proof of computational adequacy of an untyped<br /> translation of call-by-name PCF<br /><br />papers/phoa/eff "The effective topos (outline)" -- also a draft!!<br /> --an informal introduction to recursive realizability,<br /> the PER model, omega-sets, the effective topos and<br /> the small complete category of modest sets<br /><br />pmreports List of Research Reports of the Pure Mathematics<br /> Department, University of Sydney, Australia<br /> Updated regularly.<br /><br />seminars/sydcat A directory containing sydcat.tex and macros.<br /> sydcat.tex is a listing of seminars given at the<br /> Sydney Category Seminar<br /> Not being currently maintained.<br /><br />seminars/cics A directory containing cics.tex and macros.<br /> cics.tex is a listing of seminars given at the<br /> Sydney Categories in Computer Science Seminar.<br /> Updated regularly.<br /> <br />programs/kan_1.0 A directory containing source and input files for<br /> kan (vers 1.0) (Sean Carmody, Craig Reilly, Bob Walters)<br /> <br /> An implementation of the algorithm developed in 1990 by <br /> Carmody & Walters to compute (finite) left Kan extensions <br /> is now operational (programmed by Reilly and Carmody).<br /><br /> There are also some sample input files as well as a file <br /> called KAN.info which gives further details of the program<br /> and one called README which describes the sample input files. <br /> If you experiment with the program, we would be very interested <br /> to hear any comments or suggestions (especially with regards <br /> any bugs which you -- hopefully won't -- find).<br /> <br /> Future versions of the program will include a more <br /> standardised i/o format, and will renumber the elements of <br /> the output sets will be of the form {1,2,..,n} (a set which <br /> may currently be given as {1,3,7} would become {1,2,3}).<br /><br /> Sean Carmody.<br /> email: carmody_s@maths.su.oz.au<br /> 21 May 1991<br /><br />programs/kan_2.0 A later version of kan, but Sean left Sydney for Cambridge<br /> before it was properly documented.<br /><br />old A directory containing old versions of things prior to deletion.<br /><br /> <br />--<br />Bob Walters<br />Department of Pure Mathematics, University of Sydney, NSW 2006, Australia<br />Internet: walters_b@maths.su.oz.au Phone: +61 2 692 2966 FAX: +61 2 692 4534<br /><br />============================================================================<br /></pre>Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-59195077159682583652014-10-04T01:56:00.000-07:002014-10-04T02:56:50.319-07:00Arguments for fundingFrom the blog of <a href="http://backreaction.blogspot.it/2014/10/is-next-supercollider-good-investment.html">Sabine Hossenfelder</a> regarding the argument for funding the next supercollider:<br /><br />"The next argument I keep hearing is that the worldwide web was invented at CERN which also hosts the LHC right now. If anything, this argument is even more stupid than the war-also-wastes-money argument. Yes, Tim Berners-Lee happened to work at CERN when he developed hypertext. The environment was certainly conductive to his invention, but the standard model of particle physics had otherwise very little to do with it."<br /><br />I am glad that some physicists are being a bit more honest in their arguments for science funding. (However even this statement is inaccurate since Berners-Lee did not invent hypertext.)Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-76750608779192553472014-08-05T02:10:00.006-07:002014-09-19T08:38:50.022-07:00The sleeping beauty problem: how some philosphers and physicists calculate probability<a href="http://rfcwalters.blogspot.it/2014/08/the-sleeping-beauty-problem-how-some.html">Next post in this series</a><br /><br />Recently there have been surprising discussions and disputes amongst philosophers and physicists about an elementary probability problem called the Sleeping Beauty problem. The following remarks are, as usual in this blog, the result of discussions with Nicoletta Sabadini.<br /><br />The problem goes as follows: A beauty is told that the following procedure will be carried out. On Sunday a fair coin will be tossed without her knowing the result. She will go to sleep. Then on Monday one of two possibilities will occur.<br /><br />In the case that the toss of the coin resulted in tails she will be wakened and asked her opinion of the probability that the result of coin was heads. She will then have her memory of what happened on Monday erased and will be put to sleep. On Tuesday (again in the case of tails, without a further toss of the coin) she will be wakened and asked her estimate of the result of the coin toss being heads.<br /><br />In the case of heads, on Monday she will be asked her estimate of the probability that the result of the coin toss was heads. In that case she will not be asked again.<br /><br />It seems clear intuitively that, when this procedure is carried out, in all three responses she has learnt nothing about the result of the coin toss, and that she should answer in each case $1/2$.<br /><br />Strangely a considerable number of philosophers and physicists make an elementary error in the calculation of probabilities and believe that she should answer $1/3$.<br /><br /><b>Update:</b> I see also that a recipient of the COPSS Presidents' Award (the Nobel Prize of Statistics, according to Wikipedia), Jeffrey S. Rosenthal, believes the $1/3$ answer.<br /><br /><a name='more'></a>The philosophers who come to this conclusion include professors at Princeton (Adam Elga) and Oxford (Nick Bostrom). The physicists include a Senior Research Associate at Caltech, Sean Carroll, who manages to involve quantum mechanics and the multiverse. Another seems to be a Dirac and Milner prizewinner, Joe Polchinski. (Not all physicists agree - for example, the maverick (or main stream?) physicist <a href="http://motls.blogspot.it/2014/07/the-sleeping-beauty-problem.html">Lubos Motl </a>is scathing about the answer $1/3$.)<br /><br /><b>Update</b>: Lubos Motl has reblogged <a href="http://motls.blogspot.it/2014/08/sleeping-beauty-thirders-rudimentary.html">this post on his blog</a>, with additional interesting comments.<br /><br />Let's see how they manage to come to the $1/3$ conclusion and what their elementary error is.<br /><br />We can describe the procedure by a simple Markov chain, pictured below, in which the initial state (Sunday) is $0$, the state $1$ is Monday in the case of heads, the state $2$ is Tuesday and subsequent dates after heads, the state $3$ is Monday in the case of tails, the state $4$ is Tuesday and subsequent dates in the case tails.<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-okVWhawInl4/U-DIckLs5JI/AAAAAAAABzY/qBMeTS1gCB8/s1600/markov.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-okVWhawInl4/U-DIckLs5JI/AAAAAAAABzY/qBMeTS1gCB8/s1600/markov.jpg" height="234" width="320" /></a></div>Now the argument of the philosophers/physicists mentioned above is that when the beauty is awakened she knows she is in one of states 1, 3 or 4 but she doesn't know which.<br />They claim that being in each of these three states has the same probability, and hence this probability must be $1/3$ (the sum must be $1$). But in state $1$ she knows the coin was heads, and in $3$ and $4$ the coin was tails. So in a third of cases the coin is heads, so she must answer $1/3$.<br /><br /><i><b>The egregious error!</b></i><br />In a Markov process one cannot in general talk about <i>the probability of being in a state. </i>One must talk about the probability<i> </i>of passing from state $x$ to state $y$ in $n$ steps.<br /><i> </i>(If the process is ergodic then in a limiting distribution there is some sense of talking about the probability of being in a state, but that is not the case here.)<br /><br />The three probabilities discussed above are (i) the probability $p_1$ of going from $0$ to $1$ in <i>one step</i>, (ii) the probability $p_3$ of going from $0$ to $3$ in <i>one step</i>, and (iii) the probability $p_4$ of going from $0$ to $4$ in<i> two steps</i>. Each of these three values is clearly $1/2$.<br /><br />What however should the beauty calculate for the probability $p_{3,4}$ of being <i>either</i> in $3$ in one step or $4$ in two steps? The philosophers/physicists are claiming that $p_{3,4}=2p_1$. I claim $p_{3,4}=p_1$. To see this we need to think in general how to calculate the probability of going from state $x$ to $y$ in $m$ or $n$ steps in a Markov chain.<br /><br />Take $x$ to be a fixed initial state, which we wont mention again. The sum over all $y$ of $p_{one}(y)$ (the probability of reaching $y$ in one step) is $1$. The sum over all $y$ of $p_{two}(y)$ (the probability of reaching $y$ in two steps) is $1$. Hence taking $p_{one,two}(y)=p_{one}(y)+p_{two}(y)$ as the physicists/philosophers do would yield $\sum_yp_{one,two}(y)=2$ whereas the total probability should be one.<br />A reasonable definition for $p_{one,two}$ would be $p_{one,two}(y)=\frac{1}{2}( p_{one}(y)+p_{two}(y))$.<br /><br />This definition yields in the sleeping beauty problem that $p_{3,4}=\frac{1}{2}(p_3+p_4)= \frac{1}{2}=p_1$.<br /><br /><br /><br /><br />Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com8tag:blogger.com,1999:blog-7446594.post-40775908205269622232014-08-09T04:54:00.001-07:002014-09-19T08:37:18.830-07:00The sleeping beauty problem: how some statisticians calculate probability<a href="http://rfcwalters.blogspot.it/2014/09/sleeping-beauty-problem-iii.html">Next post in this series</a>; <a href="http://rfcwalters.blogspot.it/2014/08/the-sleeping-beauty-problem-how.html">previous post</a><br /><br /><br />This problem was drawn to my attention by calculations of physicists and philosophers (see my last post), but I see that some eminent statisticians (Jeffrey S. Rosenthal) are also convinced that the answer is $1/3$.<br /><br />What I think is the real problem is that statisticians immediately start calculating with conditional probability, Bayes formula etc without modelling the problem mathematically. It is also important to generalize a problem to avoid being confused by particular details.<br />In any case, I want to clarify what I said in the last post by considering a simple example.<br /><br /><a name='more'></a>The essential point of the sleeping beauty problem (see my last post) is that the beauty is asked to estimate a probability without knowing how many steps of the process have occurred.<br /><br /><b>A simpler problem</b><br />Consider the following Markov chain with $100$ states meant to represent the birthdays of my life:<br />$0\xrightarrow{1}1\xrightarrow{1}2 \xrightarrow{1}\cdots \xrightarrow{1}99\xrightarrow{1}100 $,<br />with also a loop of probability $1$ at $100$ when I am in my tomb.<br /><br />Now it is clear that the probability of my being $1$ after $1$ year if $1$, the probability of being $2$ after $2$ years is $1$, the probability of being $n$ after $n$ years is $1$ ($n\leq 99$).<br /><br />Moreover if you ask me what is the probability of being $5$ say during my life (that is, after $0$ or $1$ or $\cdots$ or $99$ years) I might be tempted to answer $1$ since it is certain I will be $5$ during my life.<br /><br />However the sum of the probabilities that I am $n$ ($n\leq 99$) during my life must add to total probability $1$, and hence I must answer that the probability of being $5$ in my life is $1/100$. That is, rarely am I five.<br /><br />Notice that if I ask what is the probability of being alive (that is, in one of the states $n$ (0$\leq n \leq 99$) in a period of $\leq 99,999$ years, I must answer $1/(1000)$; that is, mostly you will find me dead.<br /><br /><b>The sleeping beauty problem</b><br />Applying the same reasoning to the sleeping beauty Markov chain in the last post, sleeping beauty must calculate the probabilities in the case of tails not knowing whether one or two days have passed, and so she must assign $1/4$ to the probability of Monday after tails, and $1/4$ to the probability of Tuesday after tails, so that the probability of Monday or Tuesday after tails is $1/2$.<br /><br />There is a complication I didn't mention explicitly in the last post. In the case of heads the beauty knows that only one step has occurred. Hence she should calculate the probability of the heads case using the probabilities in one step, not one or two steps. Hence she should estimate the probability of Monday as $1/2$ after heads.<br /><br />Notice that she has calculated probabilities in two different probability spaces. The fact that the sum of these two probabilities is $1$ means that knowing that she is being interviewed gives her no new information, or said in another way, conditioning on the fact that an interview is in process does not require normalization of the probabilities.<br /><br /><b>A statistician's argument against</b> $1/2$<br />Let us see how one statistician claims to get a contradiction from this estimate. I will describe an argument from a paper. (The article begins sloppily because in stating the problem it does not specify that the beauty knows the protocol of the procedure to be carried out.)<br /><br />The sample space is not described, and only partial inference is made about probabilities but sufficient to convince the author that $P(Heads)< \frac{1}{2}$. We will see that the error in the argument is that the beauty must make calculations in two different probability spaces (one step, and one or two step).<br /><br />The argument begins as follows: $P(Heads|Monday)=1/2$, $P(Heads|Tuesday)=0$, $P(Tuesday)\geq 0$, $P(Monday)=1-P(Tuesday)$ and hence $P(Monday)< 1$. All these probabilities are conditioned on the fact that an interview is taking place.<br /><br />Aside from the fact that he is really talking about two probability spaces (one step, and one or two steps) I could agree with these probabilities. However the real error comes in his next step, when he seeks to apply the law of total probability:<br />$P(Heads)=P(Heads|Monday)P(Monday)+P(Heads|Tueday)P(Tuesday)$ <br />$P((Heads)=(1/2)P(Monday)+0\times P(Tuesday)< (1/2)$<br />contradicting $P(Heads)=1/2$.<br /><br />The error comes from applying the law of total probability to two different probability spaces where it is not valid. Part of the equation refers to probabilities for one step, the other part to one or two steps.<br /><br /><br /><br /><br /><br /><br /><br /><br />Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com6tag:blogger.com,1999:blog-7446594.post-78931135912137543942014-09-19T06:35:00.002-07:002014-09-19T07:24:20.949-07:00Opera d'abbaco del reverendo padre don Smiraldo BorghettiHere are some pages from a book I bought some years ago on arithmetic, published in 1594.<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-8l_Yqzv-6iQ/VBwaH9XTK8I/AAAAAAAAB2A/2w91t5bzAGs/s1600/20140919_124834.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-8l_Yqzv-6iQ/VBwaH9XTK8I/AAAAAAAAB2A/2w91t5bzAGs/s1600/20140919_124834.jpg" height="240" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-1u2URgkVgMk/VBwvXF-IlOI/AAAAAAAAB3U/SOSJacGShHY/s1600/2014-09-19%2B15.22.00.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-1u2URgkVgMk/VBwvXF-IlOI/AAAAAAAAB3U/SOSJacGShHY/s1600/2014-09-19%2B15.22.00.jpg" height="240" width="320" /></a></div><div class="separator" style="clear: both; text-align: left;">It is interesting to read that without numbers the world would be without order, and a horrible chaos.</div><div class="separator" style="clear: both; text-align: left;">Strangely the current popular view (which I do not share) is that the world is chaos, even to the extent that the laws of physics are the casual effect of which universe of the multiverse we happen to inhabit.<a href="http://1.bp.blogspot.com/-cKvgefGFmW4/VBwaFPmKd4I/AAAAAAAAB14/yPmcPJcBF_o/s1600/20140919_124849.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br /></a></div><br />Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-81479698627079948722014-09-14T10:15:00.001-07:002014-09-18T00:45:46.827-07:00Lex total categories and Grothendieck toposes IV<a href="http://rfcwalters.blogspot.it/2014/09/lex-total-categories-and-grothendieck.html">Previous post in this series</a>; next post.<br /><br />The aim of this post is to complete the proof that well-powered lex total categories are elementary toposes, by proving that they have subobject classifiers.<br /><br /><a name='more'></a><br />But first let's do something simpler, namely prove that a total category ${\bf A}$ has a terminal object. (We will use the same strategy later for constructing the subobject classifier of a well-powered lex total category.)<br /><br />$\bf Terminal\; object$<br /><br />It is clear that ${\bf A}$ has a terminal object iff the constant functor ${\bf A}^{op}\to Sets: A\mapsto 1$ is representable; its representing object is a terminal object. Further, in general, the colimit of a representable functor considered as a discrete fibration is the representing object. But the constant functor considered as a discrete fibration over ${\bf A}$ is the identity functor $1_{\bf A}:{\bf A}\to {\bf A}$ which has small fibres and so we can form $colim(1_{\bf A})$, which we write informally as $colim_{A\in {\bf A}}A$ and also $Q$ for short. We claim that this object is the terminal object of ${\bf A}$.<br /><br />Denote the universal cocone from $1_{\bf A}$ to $Q$ as $\lambda_A:A\to Q \; (A\in {\bf A})$. The $\lambda_A$ provide the existence of arrows from each object to $Q$; what remains to show is the uniqueness. Notice that for each $f:A\to Q$ we have the cocone property $\lambda_{Q}f=\lambda_A$, so in particular taking $f=\lambda_A:A\to Q$ we have $\lambda_Q\lambda_A=\lambda_A=1_A\lambda_A$. By the uniqueness property of the universal cocone this implies that $\lambda_Q=1_Q$. Then returning to the equation $\lambda_{Q}f=\lambda_A$ we see that $f=\lambda_A$ for any $f:A\to Q$, the uniqueness. <br /><br />It is clear, by the way, that a similar argument shows that totally cocomplete categories have all small limits.<br /><br />$\bf Subobject\; classifier$<br /><br />We want to do the same thing now representing a different functor $sub:{\bf A}^{op}\to Sets:A\mapsto sub(A)$ where $sub(A)$ is the set of subojects of $A$ which is small by assumption. We will denote the subobject of $A$ containing the mono $U\to A$ as $[U\to A]$ or just $[U]$. The effect of $sub$ on arrow $f:A\to B$ is $[U\to B]\mapsto [f^{-1}(U)]$. To obtain the subobject classifier we take the colimit of the corresponding fibration which we denote as $colim_{[U\to A]}A$ or more briefly as $\Omega$. Denote the universal cocone of the colimit as $\lambda_{[U\to A]}:A\to \Omega$ $(A\in {\bf A})$. Let $I$ be the terminal object of ${\bf A}$, and denote $\lambda_{[1_I:I\to I]}:I\to \Omega$ as $true:I\to \Omega$.<br /><br />Now to show that $\Omega$ is the subobject classifier we will prove (i) that given any $U\to A$ then the pullback of $true:I\to \Omega$ along $\lambda_{[U\to A]}:A\to \Omega$ is $U\to A$, and (ii) if $f:A\to \Omega$ satisfies $f^{-1}(true)=U\to A$ then $f=\lambda_{[U\to A]}:A\to \Omega$. Now (i) requires the left exactness of colimit, and we shall delay proving (i). <br /><br />First assuming (i) we will prove (ii). <br />Consider $f:A\to \Omega$ such that $f^{-1}(true)=U\to A$. Then $f$ is a morphism from $(A,[U])$ to $(\Omega,[true])$ in the domain of the fibration $sub$ and hence we have the equation (*) $\lambda_{true}f=\lambda_{[U]}$. Assuming (i) we may put $f=\lambda_{[U]}$ in this equation to yield $\lambda_{true}\lambda_{[U]}=\lambda_{[U]}=1_{\Omega}\lambda_{[U]}$. The uniqueness property of the universal cocone implies that $\lambda_{true}=1_{\Omega}$. Substituting this in (*) we obtain $f=\lambda_{[U]}$. <br /><br />Now to prove (i).<br />I am getting tired so I will just state the necessary facts and leave you to check them.<br />Consider mono $U\to A$. Consider the following arrows in $Sets^{{\bf A}^{[op]}}$: (i) $Hom(-,A)\to sub:1_A\mapsto [U]$, (ii) $Hom(-,I)\to sub:1_A\mapsto [1_I]$. It is easy to check that the pullback of these two arrows is $Hom(-,U)$ with the obvious projections. It is a little less easy to check, but straightforward, that $colim$ applied to this pullback diagram gives exactly the diagram we wish to show a pullback. Since $colim$ preserves finite limits we have the desired result.<br /><br />$\bf Note$<br />I just realized that the first statement that well-powered lex total categories are elementary toposes was made in my lecture to <a href="http://comocategoryarchive.com/Archive/temporary_new_material/Isle-of-Thorns-1976.pdf">The Isle of Thorns conference , July 25-31, 1976 entitled Total Cocompleteness.</a>Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-46478973420309278312014-09-17T00:11:00.002-07:002014-09-17T09:14:55.975-07:00Giuseppe PeanoOn Saturday I bought for 2 euros at the mercatino of Lavello a little book by Giuseppe Peano of numerical tables. It has an interesting preface by Peano.<div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-tNPdl7E0nU4/VBkyoQQFkUI/AAAAAAAAB1Q/l5BJl2UqkoM/s1600/20140917_083229.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-tNPdl7E0nU4/VBkyoQQFkUI/AAAAAAAAB1Q/l5BJl2UqkoM/s1600/20140917_083229.jpg" height="320" width="240" /></a></div><br /><a name='more'></a>I suppose Peano is best known for axiomatizing the natural numbers. He introduced the set theory symbols $\epsilon$, $\subset$, $\cap$, $\cup$.<br />The cover of the little book:<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-IbhmAMsILcw/VBkz77P9QdI/AAAAAAAAB1Y/1n2QMQ_Z2ng/s1600/20140917_083205.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-IbhmAMsILcw/VBkz77P9QdI/AAAAAAAAB1Y/1n2QMQ_Z2ng/s1600/20140917_083205.jpg" height="320" width="240" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-air6OKwOoEY/VBk0LShkz3I/AAAAAAAAB1g/9Ry5IIcZASA/s1600/20140917_083219.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-air6OKwOoEY/VBk0LShkz3I/AAAAAAAAB1g/9Ry5IIcZASA/s1600/20140917_083219.jpg" height="320" width="240" /></a></div><br /><br /><br />Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-80902079474617602322014-09-16T13:01:00.005-07:002014-09-17T06:05:12.099-07:00Ricordo di Aurelio Carboni, Matematico e Filosofo<div dir="ltr">I have just received a volume of "Il Protagora" in which there is a section devoted to Aurelio's memory.</div><div dir="ltr">There are four articles all in<br />Il Protagora, Volume XL, July-December 2013, sesta serie, n. 20</div><div dir="ltr">The articles are</div><div dir="ltr">Fabio Minazzi, Un ricordo di Aurelio Carboni, pp. 489-494</div><div dir="ltr">F. William Lawvere, Farewell to Aurelio, pp. 495-498</div><div dir="ltr">R.F.C. Walters, Working with Aurelio - Tangled Lives, pp. 49<u>9</u>-504</div><div dir="ltr">George Janelidze, An open letter to Aurelio Carboni and all Mathematicians who remember him, pp. 505-513</div><div dir="ltr"><br /></div><div dir="ltr"><br /></div><div dir="ltr">Prepublication versions of three of the papers are at the <a href="http://comocategoryarchive.com/Archive/conferences/aurelio-carboni/tributes/">Como Category Archive</a>.</div>Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-43740881635189645792014-09-03T17:28:00.002-07:002014-09-14T10:16:26.995-07:00Lex total categories and Grothendieck toposes III<br /><a href="http://rfcwalters.blogspot.it/2014/08/lex-total-categories-and-grothendieck.html">Previous post in this series</a>;<a href="http://rfcwalters.blogspot.it/2014/09/lex-total-categories-and-grothendieck_14.html"> next post in this series</a>.<br /><br />Today I want to give an application of the adjoint functor theorem for totally complete categories, namely to show that lex total categories are cartesian closed. The proof should be a generalization of the proof that locales are cartesian closed so we should look at that before attempting the case of lex total categories. We will be repeating some of the discussion of the first post in this series.<br /><br /><a name='more'></a><br /><br />(i) By the adjoint functor theorem for complete posets it is sufficient to show that if $A$ is a locale and $x$ is an element then the functor $x\wedge -:A\to A$ preserves sups of downsets. That is, we need to show that if $U$ is a downset then $x\wedge sup(U)=sup(x\wedge u; u\in U)$.<br /><br />(ii) We denote the downset generated by a subset $V$ as $\langle V\rangle $ and it is clear that $sup(V)=sup(\langle V\rangle )$.<br /><br />(iii) Notice that $\{x\wedge u;u\in U\}$ is not necessarily a downset. The crucial thing to prove is that $\langle \{x\wedge u; u \in U\}\rangle =\langle x\rangle \cap U$, since then, by the left exactness of $sup: PA\to A$ it follows that<br /><br /> $sup(\{x\wedge u; u\in U\})=sup(\langle \{x\wedge u; u \in U\}\rangle )$<br />$=sup(\langle x\rangle \cap U)=sup(\langle x\rangle )\wedge sup(U)$<br />$=x\wedge sup(U)$<br /> as required.<br /><br />(iv) To prove that $\langle \{x\wedge u; u \in U\}\rangle =\langle x\rangle \cap U$ notice that an element of the left-hand-side is an element $y\in A$ such that $y\leq x\wedge u; u \in U$; that is, such that $y\leq x$ and $y\leq u$ for some $u\in U$; that is, such that $y$ is in the right-hand-side. The converse is equally evident.<br /><br />$\bf Generalizing\;\; to\;\; categories:$<br /><br /> By the adjoint functor theorem for total categories it is sufficient to show that if $A$ is a lex total category and $x$ is an object then the functor $x\times -:A\to A$ preserves colimits of discrete fibrations $U:B\to A$ with small fibres. That is, we need to show that $x\times colim(U)=colim(x\times U(-))$ for such $U$.<br /><br />Notice that $x\times U(-):B\to A$ is not necessarily a discrete fibration, so we need the analogy of the downset generated by a subset, which for categories is achieved by the factorization into a cofinal functor followed by a discrete fibration.<br /><br /><br />$\bf Interlude\; about\; a\; factorization:$<br />The factorization of a functor $V:B\to A$ as $B\xrightarrow{V_1}\langle V\rangle \xrightarrow{V_2}A$ goes as follows. First I will describe the category $\langle V\rangle $. $\langle V\rangle $ is the category with objects equivalence classes of triples $(a,\alpha :a\to V(b),b);a, \alpha\in A,b\in B$. Notice that this generalizes the requirement in a poset that $a\leq V(b)$ but in a category $a$ may (be less than or equal to =) have an arrow to many $V(b)$ and with different arrows. Hence the equivalence relation to be explained. We will denote the equivalence class of $(a,\alpha :a\to V(b),b)$ by $[(a,\alpha :a\to V(b),b)]$. Then the equivalence relation is specified by the requirement that $[(a,\alpha :a\to V(b),b)]=[(a,\alpha V(\beta) :a\to (b'),b')]$ for any $\beta : b\to b'\in B$. Finally an arrow in $\langle V\rangle $ is an arrow $\alpha':a'\to a: [(a',\alpha'\alpha ,b)]\to [(a,\alpha ,b)]]$. (I omit the verification that this definition is unambiguous.)<br /><br />Now to describe the two functors of the factorization. $V_2:\langle V\rangle \to A$ is defined by $V_2([(a,\alpha ,b)])=a$ and $V_2(\alpha':a'\to a: [(a',\alpha'\alpha,b)]\to [(a,\alpha,b)])=\alpha'$. Again I omit the check that it is unambiguous. Given that, it is clear that $V_2$ is a discrete fibration. Finally the definition of $V_1$: $V_1(b)=[V(b), 1_{V(b)}, b]$ and<br />$V_1(\beta':b\to b')=V(\beta'):[V(b),1_{V(b)},V(b)]$<br />$=[V(b), V(\beta'), V(b')]\to [V(b'),1_{V(b')},V(b')]$.<br /><br />O.K. I have left out a lot of checking. I should also explain why $F_1$ is cofinal. What we need here is a little less, namely that $colimit(V)=colimit(V_2:\langle V\rangle \to A)$. The check is straightforward.<br /><br />$\bf Return\; to \; the\; proof:$ We have now reached point (iii) of the proof for posets which we would like to generalize to categories.<br />The crucial point to prove is that the discrete fibration $\langle (x\times U(-)\rangle \to A$ is $Elements(Hom(-,x))\times_A U(-)\to A$, because then the left exactness of $colim : PA\to A$ allows the following calculation:<br />$colim(x\times U(-))=colim(\langle x\times U(-)\rangle )$<br />$= colim(Elements(Hom(-,x))\times U(-) )$<br />$=colim(Elements(Hom(-,x))\times colim(U(-))$<br />$=x\times colim(U)$ as required.<br /><br /><br />So now to the crucial point, which should be a jazzed up categorical version of (iv) for locales above. We have two discrete fibrations which we want to show isomorphic (and at the same time verify that they have small fibres - I almost forgot to say that! In fact, $Elements(Hom(-,x))\times_A U(-)\to A$ clearly has small fibres).<br />I will only describe the two functors (and on objects only) which I claim form an isomorphism and leave the rest to you.<br /><br />The functor $\langle (x\times U(-)\rangle \to Elements(Hom(-,x))\times_A U(-)$.<br /><br />An object over $a$ of the left hand side is an equivalence class of the form $[(a, \alpha:a\to x\times U(b),b)]$. From a representative of the equivalence class we can extract two arrows $\alpha_1\to x$ and $\alpha_2:a\to U(b)$.<br />But since $U$ is a discrete fibration there is a unique object $b'\in B$ over $a$ and an arrow $\beta:b'\to b$ such that $U(\beta)=\alpha_2$. Clearly<br />$[(a, \alpha:a\to x\times U(b),b)]=$<br />$[(a,a\xrightarrow{\Delta}a\times a\xrightarrow{\alpha_1\times 1_a}x\times U(b')\xrightarrow{1_x\times U(\beta)}x\times U(b),b]=$<br />$[(a,a\xrightarrow{\Delta}a\times a\xrightarrow{\alpha_1\times 1_a}x\times U(b'),b']$.<br /><br />So from each equivalence class over $a$ we can extract an arrows from $a$ to $x$, and an object $b'\in B$ over $a$. But the elements over $a$ on the right hand side over $a$ are exactly such pairs.<br /><br /> The functor $ Elements(Hom(-,x))\times_A U(-)\to \langle (x\times U(-)\rangle$.<br /><br /> An object of the left hand side over $a$ consists of an arrow $alpha:a\to x$ and an object $b$ of $B$ such that $U(b)=a$. The functor takes this object to the equivalence class $[(a,a\xrightarrow{\Delta}a\times a\xrightarrow{\alpha\times 1_a}x\times U(b),b)]$.<br /><br /> I have run out of steam! I hope you see the analogy with the locale result.<br /><br />$\bf References$<br /><br />Ross Street and I announced the stronger result that well-powered lex total categories are elementary toposes in the paper<br />R.H. Street and R.F.C. Walters. Yoneda structures on 2-categories. Journal of Algebra, 50:350--379, 1978.<br />Looking around in subsequent literature however I cannot see where a proof has been published.<br /><br />A less elementary description of the comprehensive factorization was given in the original paper:<br />R. H. Street and R.F.C. Walters. Comprehensive factorization of a functor. Bull. Amer. Math. Soc., 79:936-941, 1973.<br /><br />Other papers on total and lex total categories:<br />Walter Tholen, Note on total categories, Bulletin of the Australian Mathematical Society, 21 (1980 ), 169 - 137<br /><br />Ross Street, Notions of topos, Bull. Austral. Math. Soc. VOL. 23 (1981) , 199-208.<br /><br />R.J Wood, Some remarks on total categories, J. Algebra 75:2, 1982, 538–545<br /><br />Ross Street, The family approach to total cocompleteness and toposes, Trans. Amer.Soc., 284 (1984) 355-369 <br /><br />Max Kelly, A survey of totality for enriched and ordinary categories, Cahiers de Topologie et Géométrie Différentielle Catégoriques, 27 no. 2 (1986), p. 109-132<br /><br />Brian Day, Further criteria for totality, Cahiers de Topologie et Géométrie Différentielle Catégoriques, 28 no. 1 (1987), p. 77-78Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-71445593195788768702014-08-15T10:27:00.002-07:002014-09-04T01:36:21.303-07:00Span(Graph) II: Circuits with feedback<a href="http://rfcwalters.blogspot.it/2014/08/spangraph-i.html">Previous Span(Graph) post</a>; <a href="http://rfcwalters.blogspot.it/2014/09/spangraph-iii-circuits-with-feedback.html">next Span(Graph) post.</a><br /><br />As an introduction to ${\bf Span(Graph)}$ I will describe how to extend the category of straight-line circuits to allow circuits with state and feedback. But before doing that I would like to point out a couple of things about straight-line circuits.<br /><br /><a name='more'></a><br /><br />Firstly, I introduced the operation of twisting two wires $twist:B^2\to B^2$. It is easy to see that using $twist$, $1_B$, product and composition we can write an expression which gives the twisting of two wires against two wires, or $m$ wires against $n$ wires, or in fact any permutation of wires. Let's just look at twisting two across two.<br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-oEsX68CUVCQ/U-5CIaoFVAI/AAAAAAAABz0/zOfNL8IcW3E/s1600/twist2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-oEsX68CUVCQ/U-5CIaoFVAI/AAAAAAAABz0/zOfNL8IcW3E/s1600/twist2.jpg" height="106" width="200" /></a></div><br /><br />We can read off the expression:<br /> $(1_B\times twist\times 1_B)(twist\times twist)(1_B\times twist \times 1_B)$.<br /><br />Another operation on wires was the duplication of a wire $\Delta:B\to B^2$. But we can also duplicate two, or $n$ wires. Let's see two:<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-BUysAHDUJng/U-5Ce0hfHuI/AAAAAAAABz8/OnAcRRvvAgk/s1600/diag2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-BUysAHDUJng/U-5Ce0hfHuI/AAAAAAAABz8/OnAcRRvvAgk/s1600/diag2.jpg" /></a></div><br /><br />We will call this operation $\Delta_2$, defined by $\Delta_2=(\Delta\times \Delta)(1_B\times twist\times 1_B)$. Its input/output behaviour is $(x,y)\mapsto (x,y,x,y)$.<br /><br />A final example before passing to circuits with feedback, namely an equation true for straight-line circuits but false for the circuits with feedback we are about to define. I will draw a picture of the equation: given any arrow $f:B\to B$ (but a similar equation is also true for and $f:B^m\to B^n$):<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-C0T-_GuD2VI/U-5CqhUmvCI/AAAAAAAAB0E/MgIh1iUrsHw/s1600/eqn.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-C0T-_GuD2VI/U-5CqhUmvCI/AAAAAAAAB0E/MgIh1iUrsHw/s1600/eqn.jpg" height="118" width="320" /></a></div><br />That is, $f\Delta=(\Delta)(f\times f)$. If you look at the input/output behaviour of these circuits you can see they are the same namely $x\mapsto (f(x),f(x))$, however the second uses more components.<br /><br />${\bf Boolean\; circuits\; with\; state\; and\; feedback}$.<br />The aim is to define a category, denoted ${\bf Circ}$, again with objects being $B^n$ but with more general arrows, with operations similar to the ones we have defined for straight-line circuits, but with also an operation of feedback.<br /><br />Today I will just describe the arrows, which often I shall call components.<br /><br />An arrow of ${\bf Circ}$ from $B^m$ to $B^n$ consists of a finite graph $G$ whose edges are labelled by pairs of elements $(x,y)$ where $x=(x_1,x_2,\cdots ,x_m)\in B^m$, and $y=(y_1,y_2,\cdots ,y_n)\in B^n$. The vertices of the graph $G$ are called the ${\it states}$ of the component and the edges are called the ${\it transitions}$ of the component. The labels tell you what happens on the left and right hand wires of the component when a transition occurs. A ${\it behaviour}$ of the component is a path in the graph $G$ which yields also a sequence of left and right labels.<br /><br />Let's look at a simple example. Notice that we separate the left and right labels by a slash.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-huP6BYtYrJI/U-5C12hRo_I/AAAAAAAAB0M/wiENDsIdiuc/s1600/delay.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-huP6BYtYrJI/U-5C12hRo_I/AAAAAAAAB0M/wiENDsIdiuc/s1600/delay.jpg" height="171" width="320" /></a></div><br /><br />This is a two state component with four transitions but what should we call it? Let's see what kind of behaviour it has. Remember a behaviour is a path in the graph. The sequence of left-labels on a path may be thought of as a signal occuring on the left as the transitions occur; similarly the sequence of right-labels is the signal on the right.<br /><br />So here is a behaviour starting in state $0$:<br /><br />$0\xrightarrow{0/0}0\xrightarrow{1/0}1\xrightarrow{0/1}0\xrightarrow{0/0}0\xrightarrow{1/0}1\xrightarrow{0/1}0\xrightarrow{0/0}0$.<br /><br />The signal on the left for this behaviour is $0,1,0,0,1,0,0$ whereas the signal on the right is $0,0,1,0,0,1,0 $. You may notice that the signal on the right is the left signal ${\it delayed}$ by one step. In fact this component is a ${\it unit\; delay\; element}$.<br /><br />Why does it act that way? The reason is that the next state is determined by the left signal (the signal is remembered as state) and the next right signal is determined by the current state (which was the last left signal).<br /><br />You may wonder why I speak of left signal, right signal instead of input and output signals. It is crucial for what we do next that left and right do not necessarily correspond to input or output respectively.<br /><div><br /></div>Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com4tag:blogger.com,1999:blog-7446594.post-66072044942664175062014-08-13T05:33:00.000-07:002014-09-03T17:49:35.255-07:00Lex total categories and Grothendieck toposes II<a href="http://rfcwalters.blogspot.it/2014/09/lex-total-categories-and-grothendieck.html">Next post in this series.</a><br /><br />I said in the<a href="http://rfcwalters.blogspot.it/2014/07/lex-total-categories-and-grothendieck.html"> first post</a> in this series that totally complete categories have a strong adjoint functor theorem.<br /><br />Here is <i>the ad</i><i>joint functor theorem</i>: if $A$ and $B$ are locally small categories, $A$ is totally cocomplete and $F: A\to B$ is a functor which preserves colimits of discrete fibrations with small fibres then $F$ has a right adjoint. <br /><br /><a name='more'></a><br /><br />Before indicating a proof of this result let us look at the<i> adjoint functor theorem for posets</i>. <br />If $F:A\to B $ is an order preserving function, $A$ is a complete poset and $F$ preserves sups then $F$ has a right adjoint $U$ with $U(b)=sup_{F(a)\leq b}(a)$. <br /><i>proof</i> Certainly $U$ so defined has the property that if $F(a)\leq b$ then $a\leq U(b)$. But also since $F$ preserves $sup$ then $FU(b)=F(sup_{F(a)\leq b}(a))=sup_{F(a)\leq b}F(a)\leq b$ and hence if $a\leq U(b)$ then $F(a)\leq FU(b)\leq b$. Hence $F(a)\leq b$ if and only if $a\leq U(b)$. Notice that we used preservation of sups only for the sups in the definition of $U$.<br /><br />There is a straightforward extension to categories of this result, namely a functor $F:A\to B$ has a right adjoint if and only if for each $b\in B$ the colimit $colimit_{Fa\to b}a$ exists and is preserved by $F$. I have been imprecise about the diagram of the colimit - we will see a definition below. Let's use this result to prove the adjoint functor theorem.<br /><br />What we need to show is if $A$, $B$ are locally small and $A$ is totally complete then $colimit_{Fa\to b}a$ is the colimit of a discrete fibration with small fibres. <br /><br />Notice that the fact that $A$ is totally complete suggest a possible adjoint to $F$, namely <br />$B\xrightarrow{yoneda_B}PB\xrightarrow{PF}PA\xrightarrow{colimit}A$ <br />where by $PA$ I mean $Sets^{A^{op}}$.<br />But $PF(yoneda_B(b))=B(F(-),b))$ so the suggested formula for $U(b)$ is the colimit of the discrete fibration $Elements(B(F(-),b))\to A$ corresponding to the functor $B(F(-),b):A^{op}\to Sets$.<br /><br />What is this discrete fibration? Over $a\in A$ the fibre is $B(Fa,b)$, that is consists of arrows $Fa\to b$. Over $\alpha:a_1\to a_2$ there are arrows $(f:Fa_1\to b)\to (g:Fa_2\to b)$ exactly when $g F(\alpha) =f$. But this is exactly the diagram I intended for $colim_{Fa\to b}(a)=U(b)$. Certainly this colimit exists and we have the theorem.<br /><br />I am busy today, so I will give examples of the use of this theorem in producing constructions in lex total categories next time.Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-75420892542516678912010-05-17T23:54:00.000-07:002014-08-17T06:46:47.706-07:00HypothesesI notice that John Baez has realized a danger of the new scientific order of blog posts, blog comments, labs, mailing lists, expository-style papers, preprints in arxiv, and traditional scientific journal articles.<br /><br />From a comment on the May 15, 2010 post of <a href="http://golem.ph.utexas.edu/category/">n-category cafe</a> (my italics)<br />"This Week’s Finds and my seminar notes are packed with hunches of varying caliber. Sometimes you need to read between the lines a bit to see them — for example, if I say something ‘should’ be true, it means I believe it’s true but haven’t proved it. And sometimes, <span style="font-style: italic;">I’ve said something is true even though I haven’t proved it</span>. By now I realize this is a bad habit… thanks to the following story.<br />Once I went to a talk where somebody said that for any ring R there’s a one-object tricategory Alg(R) consisting of R-algebras, bimodules and bimodule morphisms. I said “Really? Do you know if anyone has ever written that up?” And the speaker said “Sure! It’s in This Week’s Finds!” Which galled me, because <span style="font-style: italic;">while I knew it was true</span>, I’d never seen a proof written up — and I realized then that by claiming it was true in This Week’s Finds, I’d reduced the chances of ever seeing a proof."<br />Another remark:<br />"The last page of my slides was supposed to summarize only the ideas that will surprise and thrill the audience, so I get a standing ovation."<br /><br />I find the current state of n-category theory a confusing mixture of conjecture, unfinished definitions, unfinished proofs, buts lots of exposition.<br /><br />I am old-fashioned and believe that to maintain integrity we must insist that the science exists in the scientific journal articles. Credit should be assigned on the basis of published scientific articles. <br />I don't know what it means to have expository articles of an vaguely developed field.<br /><br />Perhaps we will end with Bogdanovs.Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-15018100474322153302012-10-01T08:01:00.003-07:002014-08-17T06:43:52.280-07:00Verba volant, scripta manentWhere do the internet, the blogs, digital photographs, the cloud and internet archives fit in?Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-81419325976500468982013-03-04T22:24:00.001-08:002014-08-17T06:43:10.299-07:0070I am seventy years old. Time to write memoirs.<br /><br />5th March 2013Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-71951879070905476892013-09-26T04:25:00.002-07:002014-08-17T06:41:53.501-07:00Ross Street's OrientalsI recently had a look at one of Jacob Lurie's expositions (in 111 pages) on<a href="http://www.math.harvard.edu/~lurie/papers/cobordism.pdf"> the clasification of topological field theories</a> - very briefly and with little comprehension. I find it difficult to read mathematics in which not even formal definitions are given: Lurie himself says "In many instances, we have not attempted to give precise definitions, let alone careful proofs".<br /><br />I have always been interested in lower category theory (up to symmetric monoidal bicategories) but only once have ventured beyond. Always we had the idea that natural transformations were like homotopies, and that one could consider homotopies between homotopies and so on, and so one would get higher categories. Thinking about axiomatizing higher categories, in particular higher associative laws lead Ross Street to considering the free n-category on an n-simplex. Mike Johnson and I also worked on this problem.<br /><br />Following this<a href="https://dl.dropboxusercontent.com/u/92056191/Archive/temporary_new_material/Orientals.html"> link</a> there is an early picture produced by Ross of an oriental.<br /><br /><br />This seems to me still an interesting problem but I don't see where it has gone in Joyal and Lurie's work.<br /><br />In any case infinity-category theory seems to be a distinct subject from category theory. Category theory should resist the attempted takeover.Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com1tag:blogger.com,1999:blog-7446594.post-88958677360042116692010-04-01T10:02:00.000-07:002014-08-15T10:46:11.030-07:00Heat on the netCommunication can become very heated on the net. I remember my first experience of it years ago when a round of emails between me, Max Kelly and Ross Street spiralled, in the course of a couple of hours, in aggression. The only way out of it was to stop writing, and start again later. (We successfully maintained a seminar, with others, which began in 1970, was still active when I left Sydney in 1998, and remains today one of the principal seminars in category theory.)<br /><br />I was reminded of this while thinking of the 20 year success of the Categories List. One needs to be conscious of the new mode of communication in order to produce a stable and productive group communication. I receive other lists which contain nothing but announcements of conferences and of jobs, whereas the categories list has managed to sustain mathematical discussion.<br /><br />I found an interesting page about <a href="http://www.aaup.org/AAUP/pubsres/academe/2007/JF/Feat/Lear.htm">moderated academic lists</a>. I quote one paragraph:<br />"One lesson I learned along the way is that the ecology of an active online community is surprisingly fragile. It can go wildly out of whack, and even self-destruct, in a very short time. I’ve seen any number of lists decline and die over the years. Some merely waste away through attrition and neglect until no one posts <br />to them anymore; others become mere notice boards for calls for papers and the like, without any real interaction among subscribers. A few flame out spectacularly, bursting with so many nasty, off-topic messages that all the “lurkers” unsubscribe, leaving the <br />disputants to fight among themselves until even they grow weary of it. Charting a middle course means achieving a high “signal-to-noise” ratio, in which the list’s content is useful enough to make it worth people’s time to stay involved." <br /><br />Another thing I learnt looking around is the meaning of "internet troll". From <a href="http://en.wikipedia.org/wiki/Internet_forum">wikipedia</a> a quote:<br />"Forum trolls are users that repeatedly and deliberately breach the netiquette of an established online community, posting inflammatory, extraneous, or off-topic messages to bait or excite users into responding or to test the forum rules and policies, and with that the patience of the forum staff. Their provocative behavior may potentially start flame wars or other disturbances. Responding to a troll's provocations is commonly known as 'feeding the troll' and is generally discouraged, as it can encourage their disruptive behavior."Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-4451816655428631272010-05-23T23:43:00.000-07:002014-08-15T10:45:35.202-07:00Probability 2 - Boy or Girl paradoxI continue to be amazed by the fact that apparently simple probability problems are often so difficult to resolve. It is particularly surprizing in view of the fact that so much science seems to depend on probability these days: the particle physicists' results are small probabilistic anomalies in incredibly expensive experiments, quantum physicists say that nature is inherently probabilistic, the medicine we take is determined by 'random' trials, evolution apparently occurs by 'random' mutation, etc, etc. (I don't necessarily concur with all this, by the way.) <br /><br />I have been thinking more about this fact since the <a href="http://cameroncounts.wordpress.com/2010/05/02/probability/">blog post of Peter Cameron</a>, which derived from another <a href="http://go2.wordpress.com/?id=725X1342&site=cameroncounts.wordpress.com&url=http%3A%2F%2Falexbellos.com%2F%3Fcat%3D1%26paged%3D2&sref=http%3A%2F%2Fcameroncounts.wordpress.com%2F2010%2F05%2F02%2Fprobability%2F">post by Alex Bellos</a>. The particular problem they consider is this: if someone tells you that they have two children at least one of whom is a boy born on Tuesday, what is the probability that the second child is a boy?<br /><br />Actually, the simpler version of this problem in which there is no mention of the day of birth (possibly introduced by <a href="http://en.wikipedia.org/wiki/Martin_Gardner">Martin Gardner</a> who died 22nd May), has been <a href="http://en.wikipedia.org/wiki/Boy_or_Girl_paradox">discussed and disputed</a> in short and in long, in circles high and low, under the name "The Boy or Girl Paradox".<br /><br />In short, my view is that the answer to this question is 1/2 (under the simplifying assumptions clearly intended; that is, that the birth rates of boys and girls are equal, etc).<br />However a closely related problem which I will explain would yield the answer 1/3, the answer preferred by mathematicians.<br /><br />I think this simple problem benefits from the distinction between states and actions, the states being the quality of being a girl or a boy, and the actions being the declarations made. In the real world problem you need to consider the probability of the action as well as the probability of being in a state.<br /><br />Let's now consider the problem in detail: the simplifying assumptions mentioned above mean that given a family with two children the following four cases are equally likely: BoyBoy, BoyGirl, GirlBoy, GirlGirl. In the case BoyBoy the likelihood of a declaration that there is a boy is 1, in the case of GirlGirl the likelihood of a declaration that there is a girl is 1, but in the other two cases there is a half chance that the declaration is 'boy', and a half chance that the declaration is 'girl'. Now let's look at the total weight of a declaration 'boy': it is 1+1/2+1/2. The weight which corresponds to the case BoyBoy is 1. Hence the proportion of 'boy' answers which correspond to the state two boys is <br />1/(1+1/2+1/2)=1/2. <br /><br />Now a slightly different problem: suppose I interview people with two children, and ask if they have a boy in the family; if they answer yes, what is the probability that the second child is a boy?<br />Again the simplifying assumptions mentioned above mean that given a family with two children the following four cases are equally likely: BoyBoy, BoyGirl, GirlBoy, GirlGirl. In the case BoyBoy the likelihood that they respond 'yes' is 1, in the case of GirlGirl the likelihood that they respond 'yes' is 0; in both the other two cases the likelihood of 'yes' is 1, not 1/2. Now let's look at the total weight of a response 'yes': it is 1+1+1. The weight which corresponds to the case BoyBoy is 1. Hence the proportion of 'yes' answers which correspond to the state two boys is <br />1/(1+1+1)=1/3. <br /><br />If there is also mention of the day of birth there are at least three interpretions:<br />1) a person declares that they have two children at least one a boy born on Tuesday;<br />2) when asked if they have a boy, the response is 'yes, and born on Tuesday';<br />3) when asked if they have a boy born on Tuesday, the response is 'yes'.<br /><br />The probability of the second child being a boy in the first case is 1/2, in the second <br />1/3 and in the third 13/27.<br /><br />In this post I have tried (exaggeratedly) to argue in as simple language as possible, because a simple problem should only require the appropriate distinctions, not a big machinery. However I have earlier proposed (with Sabadini and de Francesco Albasini) a <a href="http://arxiv4.library.cornell.edu/abs/1005.0949">mathematical context</a>, in which many of the perplexities are seen to arise from considering (normalized) probabilities, rather than weights of actions. The precise mathematical point is that normalization does not behave well with respect to sequential operations (which include abstraction). Another simple perplexing example where abstraction does not work well with normalization is Simpson's paradox, the mathematical origin of which is the fact that not always a/b+c/d=(a+c)/(b+d).<br /><br />An extreme example of Simpson's paradox is the following:<br />Consider treatments A,B and diseases X,Y.<br />Treatment A with disease X on one person cures the person (100% cure rate - best possible)<br />Treatment B with disease X on 99 people cures 98 (worse than 100%).<br />So A has a better success rate than B with disease X.<br /><br />Treatment A with disease Y on 99 people cures 1 person (this is better than 0% cure rate)<br />Treatment B with disease Y on one person fails to cure (0% cure rate - worst possible).<br />So A is better than B with disease Y.<br /><br /><br />In both diseases X and Y the treatment A is better than B.<br /><br />However treatment A saves 2 people in 100, B saves 98 in a hundred.<br />B is worse than A???Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com6tag:blogger.com,1999:blog-7446594.post-61935112413282262002010-05-06T08:49:00.000-07:002014-08-15T10:44:56.602-07:00ProbabilityI made the suggestion recently that the Kolmogorov presentation of probability was too abstract, and that this was the cause of elementary confusions like those common in the Monty Hall problem. <br /><br />I must admit to being quite unsure of the foundations of probability theory. The fact that simply stated problems are easy to make errors about hints to me that the gap between theory and practice is too wide. I make some tentative remarks below, which are made more formal in a <a href="http://arxiv.org/abs/1005.0949">small paper</a> we have just written.<br /><br />1. First, I think probability should be about explicitly described systems. (Peter Cameron in his <a href="http://cameroncounts.wordpress.com/2010/05/02/probability/">blog post</a> describes two possible systems ("protocols") which might be behind a particular problem, yielding different results.) This would imply that one needs a notion of system. In this context probabilities are weightings of actions in a particular state of a system. Such a weighting represents information about the cause of actions. It is a kind of primitive dynamical information.<br /><br />2. The Kolmogorov view is that independence is defined in terms of the probabilities of events. This is the attitude that we are observing behaviours, rather than considering systems. For systems there is a clear operation of composition in parallel. Actions may be appear to be independent behaviourally without being actually parallel.<br /><br />3. The fact that the sum of all probabilities must be 1 is another evidence of a behavioural view. A system may have big reasons for making a choice, or small reasons, in both cases, say, with a half and half probability. This doesn't affect observed behaviours. However in composing systems large reasons in one system may overwhelm small reasons in another.<br /><br />To make this more concrete: suppose I am in a situation where I am deciding to eat an apple or a pear (with equal interest), and suddenly I perceive that a car is driving straight towards me, and that with equal choice I must decide whether to run to the left or right to avoid an accident. This is a state in a composition of two systems. It is clear that the weight behind choosing an apple or a pear is overwhelmed by the choice between jumping left or right.<br /><br />At a system level weight is more fundamental than probability, which arises as a normalization of weight.<br /><br /><span style="font-weight: bold;">Update:</span> I see now that Peter Cameron has come to a conclusion (which I quote in full, but with my italics; it refers to a particular calculation which you can see at his <a href="http://cameroncounts.wordpress.com/2010/05/02/probability/">blog</a>):<br />"Mathematically the conditional probability that someone has two boys, given that one of their two children is a boy born on Tuesday, is 13/27. If we started defining the probability of some event in terms of the algorithm that led to the statement being made, all our textbooks would need to be rewritten from the ground up. <span style="font-style: italic;">I think the best way to proceed is to say</span>, we do know how to calculate probability (and how to interpret it), but this requires careful thought, and sometimes our intuition lets us down."<br /><br /><span style="font-weight: bold;">Update:</span> I made a too brief comment on Peter Cameron's blog, namely that<br />"I agree with John Faben [another commenter] that the calculation of probability requires information about the algorithm involved."<br /><br />It is somewhat difficult in blogs to follow which comments are later referred to, but it seems that Peter replied to my comment with the following:<br />"Sorry to have to disagree…<br /><br />Any calculation in probability can be done unambiguously by the rules (based on Kolmogorov’s axioms) provided we specify carefully what is the “sample space” and what is the probability measure on the sample space. If you start bringing in other factors like the algorithm used to generate a statement then all you are doing is changing the measure. That is why I said in my example that I am a covert Bayesian. I happen to think that the probability measure that applies in a given situation depends on everything I know about the situation (which may include information about the algorithm used to generate some statement)."<br /><br />He wrote more which I do not reproduce here.<br /><br />I have been trying to understand why is it difficult to apply the existing theory (Kolmogorov) to apparently simple real world problems, a fact admitted by Peter. (There is a rumour that even Erdos had difficulty with Monty Hall.)<br /><br />My suggested answer to this is that there is too great a gap between real world problems and the theory, and perhaps there could be a more detailed theory in between reducing the gap.<br /><br />The more detailed theory would be prior to the construction of the probability space.<br />It would consist in making more precise the real world problem, by describing a mathematically formal system (algorithm, or protocol). This is not beyond the capacity of mathematics to do.<br /><br />Peter seems to agree when he says "everything I know about the situation", which is another way of saying the precise system under consideration.<br /><br />There is a sleight of hand in the statement "If you start bringing in other factors like the algorithm used to generate a statement then all you are doing is changing the measure". The algorithm is needed to determine the measure; different algorithms determine different measures.Robert Waltershttps://plus.google.com/104770397900400849625noreply@blogger.com1