Logic Seminar in Semester II AY 2008/2009

• 15:30 hrs: first hour tutorial;
• 16:45 hrs: second hour scientific talk.

1. 14/01/2009, Week 1
   15:30 hrs: Organizational meeting.
   
   
2. 21/01/2009, Week 2
   15:30 hrs: Frank Stephan. Tutorial Inductive inference.
   16:45 hrs: John Case. Talk Three Computability Topics: 1. Characterization for self-reference in numberings; 2. Complementation for self-reference in numberings; 3. Learning Ershov grammars.
   Abstract: I will present three conference talks I believe will be of interest to my Singapore Math and other colleagues. Rogers' effective numberings are essentially programming systems for the partial computable functions where the programs have numerical names. Kleene's (Second) Recursion Theorem (krt) in such an effective programming system (eps) essentially says that, for any program p in the eps, there is a program e in the eps which creates a self-copy and subsequently runs p on the self-copy (and on p's externally given input). krt in an eps provides for arbitrarily algorithmically usable program self-knowledge in that eps. Some epses have krt, some do not. Topic 1. examines attempts at characterizing epses with krt. Topic 2. concerns properties of epes complementary to krt.
   A machine learns a set (or language) iff the machine, fed any listing of the set, after some trial and error, eventually outputs a definition or definitions of the set. The definitions considered under Topic 3 are what might be called Ershov Grammars: they describe iterated (including transfinitely iterated) differences of r.e. sets. The motivation comes from Burgin who pointed out that people edit their outputs and, in effect, posited that humans may be employing (low level) such grammars. Topic 3 provides some corresponding learning power hierarchy results re learning Ershov Grammars for r.e. sets.
   
   
3. 28/01/2009, Week 3
   No tutorial, no talk.
   
   
4. 04/02/2009, Week 4
   15:30 hrs: Frank Stephan. Tutorial Inductive inference.
   16:45 hrs: Yang Yue. Talk PART and Sigma_2 collection principle.
   Abstract: PART is a statement saying two descriptions (to be specified in the talk) characterizing the order type of omega + omega* are equivalent. The problem whether PART is equivalent to Sigma_2 collection was raised from Reverse Mathematics. I will talk about the background of the problem and prove their equivalence. This is a joint work with Chong Chitat and Steffen Lempp.
   
   
5. 11/02/2009, Week 5
   15:30 hrs: Frank Stephan. Tutorial Inductive inference.
   16:45 hrs: Johanna Franklin. Talk Subclasses of the Kurtz random reals.
   Abstract: Kurtz randomness is such a weak notion that it can reasonably be considered a genericity notion as well. I will present some results concerning the relationships some of its subclasses have to each other.
   
   
6. 18/02/2009, Week 6
   15:30 hrs: Frank Stephan. Tutorial Inductive inference.
   16:45 hrs: Sy Friedman. Talk The Effective Theory of Borel Equivalence Relations.
   Abstract: Striking results have been obtained by Silver, Harrington-Kechris-Louveau and others regarding the structure of Borel equivalence relations under Borel reducibility. In this talk I'll discuss what happens to this theory when "Borel" is replaced by "Hyp" (i.e., "Lightface Borel" or "Delta-1-1"). The Silver and Harrington-Kechris-Louveau dichotomies do not hold effectively, and the effective theory even when restricted to equivalence relations with only *finitely* many equivalence classes is complicated!
   This is joint work with two of my postdocs, Katia Fokina and Asger Toernquist.
   
   
7. 04/03/2009, Week 7
   15:30 hrs: Yu Liang. Tutorial On countable admissible ordinals.
   16:45 hrs: Zhu Huiling. Talk Compact Cardinals.
   Abstract: The notion of compactness came from topology and is widely used to describe certain properties in first order logic and large cardinals. In this talk, I'll go through with the development of large cardinal hierarchy, focusing on the equivalent definitions and consistent strength of weakly compact, measurable, strongly compact and supercompact cardinals.
   
   
8. 11/03/2009, Week 8
   15:30 hrs: Yu Liang. Tutorial On countable admissible ordinals.
   16:45 hrs: Li Yanfang. Talk Countable Borel equivalence relations.
   Abstract: Countable Borel equivalence relations is an important subspecies of Borel equivalence relations. This family of Borel equivalence relations is closely related to countable group actions. I will first talk about the hierarchy of countable equivalence relations and then according to this hierarchy, present some related results such as characterization of hyperfinite Borel equivalence relations and existence of universal countable Borel equivalence relation which is not hyperfinite.
   
   
9. 18/03/2009, Week 9
   15:30 hrs: Yu Liang. Tutorial On countable admissible ordinals.
   16:45 hrs: Shao Dongxu. Talk Analytic determinacy
   Abstract: Martin proved that analytic determinacy holds under the assumption that the measurable cardinal exists in 1970. From his original proof, he developed the homogeneous tree argument, which can be used to show the projective determinacy.
   
   
10. 25/03/2009, Week 10
    15:30 hrs: Makoto Tatsuta. Talk Types for Hereditary Permutators.
    Abstract: This talk answers the TLCA open problem 20 of finding a type system that characterizes hereditary permutators. First this talk shows that there does not exist such a type system by showing that the set of hereditary permutators is not recursively enumerable. The set of positive primitive recursive functions is used to prove it. Secondly this talk gives a best-possible solution by providing a countably infinite set of types such that a term has every type in the set if and only if the term is a hereditary permutator. (This talk was presented at LICS 2008.)
    16:45 hrs: Liu Jiang. Talk The constructions of minimal r.e. truth-table degrees.
    Abstract: Marchenkov, independently, Fejer and Shore proved the existence of non-recursive r.e. minimal truth table degree. Those are two interesting constructions. Marchenkov's construction is based on Degtev's method to build minimal r.e. tt-degree in r.e. degrees. On the other side, Fejer and Shore make use of a special tree method. However, the set constructed by either of methods is semirecursive. We shall exhibit these two methods, and investigate their virtues.
    
    
11. 01/04/2009, Week 11
    15:30 hrs: Wu Guohua. Tutorial REA Operators.
    16:45 hrs: Zhu Yizheng. Talk The covering lemma.
    Abstract: The covering lemma for L, discovered by Jensen, states that if 0^# does not exist, then L is the maximum inner model, in the sense that every uncountable set of ordinals can be covered by a set of ordinals in L of the same size. It is the first result that establishes a deep connection between large cardinals and inner models. Later, generalizations of the covering argument to larger core models were found to be an integral part of core model theory. There comes a dichotomy: If a certain large cardinal does not exist in the universe, then the corresponding core model below that large cardinal is maximum with a covering property.
    Jensen's covering lemma is then a special case of the dichotomy between 0^# and L.
    In this talk I will present a partial proof to Jensen's covering lemma for L, and give some hints on how the covering argument generalizes to larger core models.
    
    
12. 08/04/2009, Week 12
    15:30 hrs: Dieter Spreen. Talk An intrinisic characterization of effective topologies.
    Abstract: An effective topological space is a two-level structure consisting of two indexed sets: points and basic opens, as well as two enumerable relations between the two levels: membership and convergence.
    Numbered sets possess a variety of intrinsic topologies defined by their computability structure. We characterize those of them that are compatible with the given topology.
    As a consequence characterizations for two important types of topologies are obtained.
    16:45 hrs: Peng Yinhe. Talk Reals in iterable premice.
    Abstract: In Mitchell-Steel's construction of iterable premice, there are some good properties for reals, such as, reals in different iterable premice are the same in the same hierarchy. And by using the tool of iteration, we can see these properties clearly.
    
    
13. 15/04/2009, Week 13
    15:30 hrs: Wu Guohua. Tutorial REA Operators.
    16:45 hrs: Lee Yung Hei. Talk Fuzzifying game theory.
    Abstract: I will provide a brief introduction to fuzzy logic and game theory. Then I will show how fuzzy logic can be applied to game theory, using the Prisoner's Dilemma as an example.
    
    
14. 29/05/2009, Friday, Colloquium Room A
    16:00 hrs: Cristian Calude. Talk Can Peano Arithmetic Prove Randomness?
    Abstract: We prove that every computably enumerable (c.e.) random real is provable in Peano Arithmetic (PA) to be c.e. random. A major step in the proof is to show that the theorem stating that ``a real is c.e. and random iff it is the halting probability of a universal prefix-free Turing machine'' can be proven in PA. Our proof, which is simpler than the standard one, can also be used for the original theorem.
    Our positive result can be contrasted with the case of computable functions, where not every computable function is provably computable in PA, or even more interestingly, with the fact that almost all random finite strings are not provably random in PA.
    We also prove two negative results: (a) there exists a universal machine whose universality cannot be proved in PA; (b) there exists a universal machine U such that, based on U, PA cannot prove the randomness of its halting probability.