Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.
The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.
We study arithmetic and hyperarithmetic degrees of categoricity. We extend a result of E. Fokina, I. Kalimullin, and R. Miller to show that for every computable ordinal $\alpha$, $\mathbf{0}^{(\alpha)}$ is the degree of categoricity of some computable structure $\mathcal{A}$. We show additionally that for $\alpha$ a computable successor ordinal, every degree $2$-c.e. in and above $\mathbf{0}^{(\alpha)}$ is a degree of categoricity. We further prove that every degree of categoricity is hyperarithmetic and show that the index set of structures with degrees (...) of categoricity is $\Pi_{1}^{1}$-complete. (shrink)
We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.
We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...) disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)
There is a family of questions in relativized complexity theory--weak analogs of the Friedberg Jump-Inversion Theorem--that are resolved by 1-generic sets but which cannot be resolved by essentially any weaker notion of genericity. This paper defines aw2-generic sets. i.e., sets which meet every dense set of strings that is r.e. in some incomplete r.e. set. Aw2-generic sets are very close to 1-generic sets in strength, but are too weak to resolve these questions. In particular, it is shown that for any (...) set X there is an aw2-generic set G such that $\mathbf{NP}^G \cap co-\mathbf{NP}^G \nsubseteq \mathbf{P}^{G \oplus X}$ . (On the other hand, if G is 1-generic, then $\mathbf{NP}^G \cap co-\mathbf{NP}^G \subseteq \mathbf{P}^{G \oplus \mathrm{SAT}}$ . where SAT is the NP-complete satisfiability problem [6].) This result runs counter to the fact that most finite extension constructions in complexity theory can be made effective. These results imply that any finite extension construction that ensures any of the Friedberg analogs must be noneffective, even relative to an arbitrary incomplete r.e. set. It is then shown that the recursion theoretic properties of aw2-generic sets differ radically from those of 1-generic sets: every degree above O' contains an aw2-generic set: no aw2-generic set exists below any incomplete r.e. set; there is an aw2-generic set which is the join of two Turing equivalent aw2-generic sets. Finally, a result of Shore is presented [30] which states that every degree above 0' is the jump of an aw2-generic degree. (shrink)
Humans hunt and kill many different species of animals, but whales are our biggest prey. In the North Atlantic, a male long-fi nned pilot whale (Globiceph- ala melaena), a large relative of the dolphins, can grow as large as 6.5 meters and weigh as much as 2.5 tons. As whales go, these are not particularly large, but there are more than 750,000 pilot whales in the North Atlantic, traveling in groups, “pods,” that range from just a few individuals to a (...) thousand or more. Each pod is led by an individual known as the “pilot,” who appears to set the course of travel for the rest of the group. This pilot is both an asset and a weakness to the pod. The average pilot whale will yield about a half ton of meat and blubber, and North Atlantic societies including Ireland, Iceland, and the Shetlands used to manipulate the pilot to drive the entire pod ashore. In the Faroe Islands, a group of 18 grassy rocks due north of Scotland, pilot whale hunts have continued for the last 1200 years, at least. The permanent residents of these islands, the Faroese, previously killed an average of 900 whales each year, yielding about 500 tons of meat and fat that was consumed by local residents. Hunts have declined in recent years. From 2001 to 2005, about 3400 whales were killed, yielding about 890 metric tons of blubber and 990 metric tons of meat. The whale kill, or grindadráp in the Faroese language, begins when a fi shing boat spots a pod close enough to a suitable shore, on a suitably clear day. A single boat, or even a small group of fi shermen, is not suffi cient to trap a.. (shrink)
Ethics researchers have scrutinized ethical business problems, which have been demonstrated through the actions of managers at Enron, WorldCom, and Arthur Andersen, among others. In response to these business transgressions, the US government has implemented the Sarbanes–Oxley Act to shore up businesses’ ethics infrastructures. However, universities, too, struggle with ethics problems. These include NCAA (National Collegiate Athletic Association) violations, discrimination issues, sexual harassment, endowment admits, plagiarism, and research funding manipulation. Despite these problems, we have little knowledge regarding universities’ ethics (...) infrastructures and codes of conduct, and insignificant empirical research on academic ethics issues (Kelley & Chang, Journal of Higher Education, under review, 2006; Morgan & Korschgen, College Student Journal, Sept., 2001). This lack of knowledge exists despite the critical role universities play in shaping the moral behavior of future generations (Langlais, The Chronicle of Higher Education, January 13:B11, 2006; Woo, BizEd, May/June:22–27, 2003). In this paper, we conduct exploratory research to identify the elements of universities ethics’ infrastructures. From our research, we develop an understanding of the ethics policies and infrastructure elements in place at a representative group of universities. We compare these infrastructures to those in business as well as across Carnegie Classifications. We then conclude with recommendations for developing university ethics infrastructures and suggestions for future research. (shrink)
