Date/Time : 10 May 2023 17:00
Venue : S17 #04-05 (SR2)
Speaker : Jan Baars,

For a Tychonov space X we define Cp(X) to be the linear subspace of R^X consisting of all real-valued continuous functions on X. Let βX be the ˇCech-Stone compactifaction of X and let X^* = βX \ X be the remainder of X. For u ∈ X^*, we denote Xu = X ∪ {u} ⊆ βX.

For the countable discrete space ω, elements of ω^* can be identified with free ultrafilters on ω. In 1990 Gul’ko proved in [3] for u, v ∈ ω^* that Cp(ωu) and Cp(ωu) are linearly home- omorphic if and only if ωu and ωv are homeomorphic. In [1] this result was generalized for finite sums of spaces ωu as follows: For n, m ≥ 1 and {u1,…,un, v1,…,vm} ⊆ ω∗, let X and Y be the direct sums of all ω_ui and ω_vi, respectively.

Then the spaces Cp(X) and Cp(Y) are linearly homeomorphic if and only X and Y are homeomorphic, in particular n = m. Gul’ko’s result does not hold for all spaces X. For example in [2] it was shown that for each ordinal space α, where ω < α < ω1 is a limit ordinal, there are u, v ∈ α^* such that Cp(αu) and Cp(αv) are linearly homeomorphic but αu and αv are not homeomorphic.

Here the references are as follows:

[1] J. Baars, On the lp-equivalence of ultrafilters, Bull. Pol. Acad. Sci. Math. Vol 70 No 1. (2022), 63–82.

[2] J. Baars and J. van Mill, Function spaces and points in ˇCech-Stone remainders, To appear in Topology Appl.

[3] S.P. Gul’ko, Spaces of continuous functions on ordinals and ultrafilters, Math. Notes, Vol. 47,4 (1990), 329–334.

Add to calendar :

Date/Time : 12 Apr 2023 17:00
Venue : via Zoom
Speaker : Daniel Max Hoffmann, University of Warsaw

Add to calendar :

Date/Time : 05 Apr 2023 17:00
Venue : S17 #05-11 (SR5)
Speaker : Frank Stephan, National University of Singapore

Languages over the unary alphabet have been studied in computer science for a long time. The present work investigates regular languages over the unary alphabet and one investigates the various forms of representing them by finite automata. Here three types of automata are studied:

(a) Deterministic finite automata where the finite automaton has exactly one run per word which is accepting iff the word is in the given language.

(b) Nondeterministic finite automata where there are choices in the states on how to procede with a run on various symbols, a word is in the language iff there is some run which is accepting.

(c) Unambiguous finite automata which are a special case of nondeterministic finite automata and which either reject a word or which have exactly one accepting run for a word.

The results presented are from the following two areas:

(1) This paper improves the upper bound of the equality problem of unary nondeterministic automata from an exponential in the second root to an exponential in the third root of the number of states. This almost matches a known lower bound based on the exponential time hypothesis by Fernau and Krebs.

(2) It is established that the standard regular operations of union, intersection, complementation and Kleene star cause either only a polynomial or a quasipolynomial blow-up.
Concatenation of two n-state ufas, in worst case, causes a blow-up from n to a function with an exponent of sixth root of n. Decision problems of finite formulas using regular operations and comparing languages given by n-state unambiguous automata, in worst case, require an exponential-type of time under the Exponential Time hypothesis and this complexity goes down to quasipolynomial time in the case that the concatenation of languages is not used in the formula. Merely comparing two languages given by n-state ufas in Chrobak Normal Form is in LOGSPACE.

This talk is joint work with Gordon Hoi, Sanjay Jain and Christopher Tan.

Add to calendar :

Date/Time : 29 Mar 2023 17:00
Venue : S17 #05-12 (SR4)
Speaker : Ruofei Xie,

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

In the article “Highness Properties Close to PA-Completeness”, Greenberg, Miller, and Nies left the following questions:

–Is there a finite collection of functionals {Gamma_i:i<N} such that for every martingale M majorizing the optimal c.e. supermartingale m, Gamma_i(M) is a DNC_k function for some i<N?

–Is there a uniform way to compute a DNC_k function from a martingale M majorizing m whose initial capital is bounded by 1?

In the talk, I will try to answer these questions.

Add to calendar :

Date/Time : 22 Mar 2023 17:00
Venue : S17 #05-11 (SR5)
Speaker : Kihara Takayuki,

In this talk, we examine the topos-theoretic aspect of the degrees of (computable) unsolvability. One of the main interpretations of constructive mathematics is Kleene’s realizability interpretation, which, as is well known, can be relativized by an oracle. In this sense, an oracle can be a factor that causes a change in a model of constructive mathematics.

Let us review this observation from another point of view: there is a topos, called the effective topos, based on Kleene’s realizability interpretation. And relativizing the realizability interpretation to an oracle yields a subtopos of the effective topos. Thus, the structure of oracles, i.e., the structure of the degrees of unsolvability, is expected to be closely related to the structure of the subtoposes of the effective topos.

In this talk, we give a complete correspondence, in a strict sense, between the structure of the degrees of unsolvability and the structure of subtoposes of the effective topos (or its relatives).

Add to calendar :

Date/Time : 15 Mar 2023 17:00
Venue : S17 #05-11 (SR5)
Speaker : Liu Shixiao ,

In the first half of the talk I shall be proving the properness of Mathias forcing with lower density requirement. In the second half of the talk I shall demonstrate the difficulty in applying this method (and some other commonly used methods) to Silver forcing with lower density requirement.

Add to calendar :

Date/Time : 08 Mar 2023 17:00
Venue : S17 #05-11 (SR5)
Speaker : Chong Chitat, National University of Singapore

Let T be the full infinite binary tree (i.e. the Cantor space). An infinite subtree S of T is a strong subtree if (i) S is isomorphic to T, (ii) if sigma is a node in S, and sigma_0, sigma_1 are its immediate successors in S, then sigma_0 and sigma_1 have the same length in T and furthermore (iii) the intersection of sigma_0 and sigma_1 is sigma.

The Halpern-Lauchli Theorem is a theorem in combinatorial mathematics which states that for any finite number of infinite full binary trees T_1,T_2,…, T_d, and any finite coloring of the d-row vectors in T_1 x
T_2 x … x T_d, there exist strong subtrees S_1 subseteq T_1, S_2 subseteq T_2, …, S_d subseteq T_d for which all d-row vectors in S_1 x S_2 x … x S_d have the same color.

This Ramsey type theorem is yet another striking demonstration of the existence of order within chaotic disorder. There is no known simple proof of this theorem in the published literature.

In this talk we discuss the proof-theoretic strength of the Halpern-Lauchli theorem from the reverse mathematics point of view. In particular, we give a characterisation of the inductive strength of this theorem as well as its conservation strength over a base theory weaker than Sigma_2-induction.

This is joint work with Li Wei and Yang Yue.

Add to calendar :

Date/Time : 01 Mar 2023 17:00
Venue : via Zoom
Speaker : Linus Richter, Victoria University of Wellington

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

A recent “point-to-set principle” of Jack Lutz and Neil Lutz characterises the Hausdorff dimension of any subset of Euclidean space in terms of the Kolmogorov complexity of its individual points.
Sets with particular fractal properties can now be constructed point-by-point, by coding “enough” information into each point, bit-by-bit.

After introducing the point-to-set principle, I will present a new result in fractal geometry: under V=L (the axiom of constructiblity), I will outline the construction of co-analytic sets of Euclidean space which fail Marstrand’s Projection Theorem, a classical result in fractal geometry concerning the dimension of orthogonal projections of analytic plane sets onto lines.

Add to calendar :

Date/Time : 15 Feb 2023 17:00
Venue : S17 #05-11 (SR5)
Speaker : David Belanger, National University of Singapore

We present a system of functionals that can serve as Skolem functions, so that any arithmetical formula can be rewritten in terms of them, in a model of BSigma_n + not ISigma_n. A distinguishing feature of our construction is that each functional is coded as a natural number within the model, and there is an upper bound on the codes. The method has a number of interesting applications.

This is joint work with Chong, Li, Wong and Yang.

Add to calendar :