Combinatorics and Card Shuffling
Prof Sami Assaf, University of Southern California, USA
Friday, 11 May 2012, 12h00, M 200
Variations on a Theme by Ishihara
Dr Hannes Diener, University of Siegen, Germany
Thursday, 22 March 2012, 16h00, M 111 (Seminar Room)
After a gentle, short introduction to constructive analysis we will present results by Hajime Ishihara of 1991, which became known as "Ishihara's tricks". These results are about decisions that, on first and maybe even second glance, seem algorithmically impossible to make. We will present new results, which extend Ishihara's ideas, and apply these extensions to three problems. Lastly, we will show how Ishihara's tricks can be used to give an axiomatic, concise, and clear proof of the well known phenomenon that in many constructive settings every real-valued function on the unit interval is continuos ("computability implies continuity").
A Direct Proof of Wiener's 1/f Theorem
Matthew Hendtlass, University of Leeds, UK
Thursday, 15 March 2012, 16h00, M 111 (Seminar Room)
In functional analysis it is not uncommon for a proof to proceed by contradiction coupled with an invocation of Zorn's lemma. Since any ideal object produced by such an application of Zorn's lemma is in fact nonexistent, proofs of this form can often be simplified, both in form and in logical complexity, by rewriting as a direct proof using the principle of Open Induction isolated by Raoult. If the theorem under consideration is sufficiently concrete, then a far weaker instance of induction suffices for the proof and, with some massaging, one may obtain a fully constructive proof. We apply this method to Gelfand's proof of Wiener's 1/f theorem, producing first a simple direct proof of Wiener's theorem which, while being as elegant as Gelfand's, is completely elementary modulo open induction; and then an even simpler constructive proof.