Relations between reducibilities of table type (Q796521)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Relations between reducibilities of table type |
scientific article |
Statements
Relations between reducibilities of table type (English)
0 references
1983
0 references
It is proved that the elementary theories of the upper semilattices of the recursively enumerable p- and d-degrees are not equal. Let \(P_ r\) be a family of r-complete sets. It is noticed that \((i) (P_{btt}\cap P_ l\cap P_ c)\backslash P_{bl}\neq \text{ΓΈ}\); (ii) \((P{}_{btt}\cap P_ l)\backslash(P_ c\cup P_{bl})\neq \emptyset\).
0 references
recursively enumerable degrees
0 references
reducibilities of table type
0 references
elementary theories
0 references
upper semilattices
0 references