Logic Seminar in Semester II AY 2017/2018
Talks are Wednesday afternoon in Seminar Room S17#04-06
and start at 17:00 hrs. Here an overview over the topics.
Talks from the
- Wednesday 17/01/2018, 17:00 hrs, Week 1,
Learnability and Positive Equivalence Relations.
A positive equivalence relation is an r.e. equivalence relation on
the natural numbers which has infinitely many equivalence classes.
The present work studies for various positive equivalence relations
which learning criteria can be separated by r.e. one-one families
of sets closed under the equivalence relation. The learning criteria
considered are finite, confident, explanatory, vacillatory and
behaviourally correct learning from positive data. The general results
are the following:
Note that the implications finitely learnable ⇒ confidently learnable
⇒ explanatorily learnable ⇒ vacillatorily learnable ⇒
behaviourally correctly learnable hold, independently of the chosen
positive equivalence relation, as these implications follow directly
from the definitions.
- There is always an r.e. one-one family which cannot be behaviourally
- There is always a behaviourally correctly learnable r.e. one-one
family which cannot be learnt vacillatorily;
- For some positive equivalence relation, every vacillatorily learnable
r.e. one-one family is explanatorily learnable;
- There is always an explanatorily learnable r.e. one-one family
which cannot be learnt confidently;
- Some positive equivalence relations do not admit r.e. one-one families
which can be learnt confidently; however, when such a family exisits,
then there is also such a family which cannot be learnt finitely.
- Wednesday 24/01/2018, 17:00 hrs, Week 2,
Dilip Raghavan. An application of PCF theory
to cardinal invariants above the continuum.
It will be proved in ZFC that if κ is any regular
cardinal greater than בω,
then d(κ) ≤ r(κ).
Here d(κ) is the smallest size of
dominating family of functions from κ to κ and
r(κ) is the smallest size of a family of subsets of
κ which decide every other subset of κ.
This result partially dualizes an earlier result of myself and Shelah.
The proof uses the revised GCH, which is an application of PCF theory.
This is joint work with Saharon Shelah.
- Wednesday 31/01/2018, 17:00 hrs, Week 3,
Ben Blumson. Relevance and Verification.
According to A. J. Ayers' (1936) first empiricist criterion of meaning,
"... we may say that it is the mark of a genuine factual proposition ...
that some experiential propositions can be deduced from it in conjunction
with certain other premises without being deducible from those other
premises alone." Ayer's criterion was supposed to distinguish
scientifically verifiable statements from unverifiable nonsense, but it's
well known to be trivial: if S is an arbitrary statement and O any
observation statement, then S entails O in combination with "if S then O"
even if "if S then O" does not entail O by itself (alternatively, if "if S
then O" does entail O on its own, S is a tautology). In this talk, I will
argue that Ayer's criterion can be defended from triviality by the
adoption of the relevant logic R, a non-classical logic in which the
antecedent of a conditional is supposed to be relevant to its consequent
(I won't presuppose knowledge of Ayer or relevant logic).
- Wednesday 07/02/2018, 17:00 hrs, Week 4,
Randomness versus induction.
We look at some recent work towards finding the axiomatic strength of the
statement: There is a Martin-Löf random set of natural numbers.
- Wednesday 14/02/2018, 17:00 hrs, Week 5,
Combinatorics and Probability in First and Second Order Arithmetic.
Recent years see emergence of connections between the reverse mathematics
of Ramsey theory and computable measure theory or algorithmic randomness.
Here we consider two simple propositions in measure theory which have
interesting connections to the reverse mathematics of Ramsey theory. The
first is that every set X in Cantor space of positive Lebesgue measure
is non-empty. If X is assumed to be effectively closed then this is the
well-known WWKL0. However, if X is allowed to be a
little wilder and the proposition is twisted a bit, then it could help in
understanding the first order theory of some Ramseyan theorems. The second
is that every set X in Cantor space of positive measure has a perfect
subset. This proposition is somehow related to a tree version of Ramsey's
theorem. But unlike the first one, it is not familiar to people either in
algorithmic randomness or reverse mathematics.
- Wednesday 21/02/2018, 17:00 hrs, Week 6,
Many-valued logic, automata and languages.
In 1960, Büchi, Elgot, Trakhtenbrot discovered a correspondence
between finite automata and monadic second order logic on words:
A language of nonempty words is regular if and only if it is MSO-definable.
Many-valued logics with truth values from MV-algebras and weighted
automata with weights from semirings are generalizations of classical
two-valued logics and finite automata, respectively.
In this talk, I give some examples of corresponding MV-algebras and
semirings and present translations between many-valued MSO-formulae and
weighted automata that define the same language.
- Wednesday 07/03/2018, 17:00 hrs, Week 7,
Wong Tin Lok
- Wednesday 14/03/2018, 17:00 hrs, Week 8,
- Wednesday 21/03/2018, 17:00 hrs, Week 9,
- Wednesday 28/03/2018, 17:00 hrs, Week 10,
- Wednesday 04/04/2018, 17:00 hrs, Week 11,
- Wednesday 11/04/2018, 17:00 hrs, Week 12,
- Wednesday 18/04/2018, 17:00 hrs, Week 13,