𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A splitting theorem for the Medvedev and Muchnik lattices

✍ Scribed by Stephen Binns

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
174 KB
Volume
49
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This is a contribution to the study of the Muchnik and Medvedev lattices of non‐empty Π^0^~1~ subsets of 2^ω^. In both these lattices, any non‐minimum element can be split, i. e. it is the non‐trivial join of two other elements. In fact, in the Medvedev case, if__P__ > ~M~ Q, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible ∃‐theories.

📜 SIMILAR VOLUMES

The Strong Independence Theorem for Auto
The Strong Independence Theorem for Automorphism Groups and Congruence Lattices of Arbitrary Lattices
✍ G. Grätzer; F. Wehrung 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 330 KB

97᎐108 proved a much stronger result, the strong independence of the automorphism group and the congruence lattice in the finite case. In this paper, we provide a full affirmative solution of the above problem. In fact, we prove much stronger results, verifying strong independence for general lattic

A Kruskal–Katona Type Theorem for the Li
A Kruskal–Katona Type Theorem for the Linear Lattice
✍ S Bezrukov; A Blokhuis 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 154 KB

We present an analog of the well-known Kruskal-Katona theorem for the poset of subspaces of PG(n, 2) ordered by inclusion. For given k, (k < ) and m the problem is to find a family of size m in the set of -subspaces of PG(n, 2), containing the minimal number of k-subspaces. We introduce two lexicogr