LOGIC SEMINAR

 

Spring 2014

 

Logic Seminar

(senior thesis defense)

Thursday, April 24, 2014

5:156:15p.m.

Speaker: James Clark, GWU

Place: Monroe Hall (2115 G Street), Room 267

Title: Complexity of Orders on Computable Groups

Abstract: A left order on a group is a linear ordering of its elements, which is left-invariant under the group operation. If a left order is also right-invariant, it is called a bi-order. Orders on groups are often identified with their positive cones. Certain algebraic conditions determine such cones.  For an orderable group (even magma), there is a natural topology on the set of its orders. For computable groups, we also investigate computability theoretic complexity of their orders.

 

 

 

Logic Seminar

(senior thesis defense)

Thursday, April 17, 2014

5:156:15p.m.

Speaker: Milica Taskovic, GWU

Place: Monroe Hall (2115 G Street), Room 267

Title: Axiom of Choice across Mathematical Disciplines

Abstract: Ever since its establishment, the axiom of choice (AC) has been one of the most controversial axioms in set theory. The main criticism of AC is that it claims the existence of an object without explicitly defining the object in the language of set theory. Even so, AC has been used in proofs of many known theorems across all mathematical disciplines. However, its use is often disguised since it is equivalent to hundreds of other mathematical statements. In this talk we will discuss the use of AC in undergraduate mathematics courses, and some counterintuitive examples it creates. 

 

 

Logic/Algebra Seminar

Thursday, April 10, 2014

6:157:15p.m.

Speaker: Alexandra Shlapentokh, East Carolina University

http://personal.ecu.edu/shlapentokha/

Place: Monroe Hall (2115 G Street), Room 267

Title: Easy as Q: HilbertÕs Tenth Problem for subrings of Q and number fields

Abstract: We show that there are subrings of Q, ÒcloseÓ to Q,  where HilbertÕs Tenth Problem is Turing equivalent to HilbertÕs Tenth Problem over the rational numbers.  These results complement results of Poonen and others showing that there are subrings ÒcloseÓ to Q, where HilbertÕs Tenth Problem is equivalent to the problem over Z.

 

 

Logic Seminar

Thursday, April 10, 2014

5:156:15p.m.

Speaker: Wesley Calvert, Southern Illinois University

http://lagrange.math.siu.edu/Calvert/

Place: Monroe Hall (2115 G Street), Room 267

Title: Optimal characterization of learnability

Abstract: In the Probably Approximately Correct (PAC) notion of machine learning, a computer has the task of finding some concept which, with high probability, will be very close to a pre-specified target. We would like to characterize when this is possible, and to do so in an optimal way.  In the present talk, we compute exactly the degree of unsolvability of the problem of determining whether a concept class is PAC learnable. The model of concept class used, a uniform set of Pi-0-1 classes, is a natural one, frequently used in computability, and is rich enough to include most natural examples.

 

 

Thursday, March 27, 2014

5:156:15p.m.

Speaker: Rumen Dimitrov, Western Illinois University

http://www.wiu.edu/users/rdd104/home.htm

Place: Monroe Hall (2115 G Street), Room 267

Title: Algorithms in computable vector spaces

Abstract: The notions of both computable and computably enumerable vector space have been introduced by Metakides and Nerode in 1977. From the lattice-theoretic point of view neither of these notions is the vector space analog of the notion of a computable set.  We need the existence of a dependence algorithm. In this talk we will discuss the connections between dependence and convexity algorithms in vector spaces and their importance for other algebraic constructions.

 

 

Thursday, February 27, 2014

5:156:15p.m.

Speaker: Leah Marshall, GWU

Place: Monroe Hall (2115 G Street), Room 267

Title: Computable categoricity of computable partial injection structures

Abstract: We will review and continue our discussion from the December seminar.  A computable structure A is computably categorical if for every isomorphic computable structure B, there is a computable isomorphism from A to B.  A computable injection structure is a structure consisting of a computable set and a computable injective (11) function.  We will present some recent results generalizing the notion of computable injection structures to include partial computable functions.  We will also present recent results regarding computable categoricity of computable partial injection structures.

 

 

Thursday, February 20, 2014

5:156:15p.m.

Speaker: Valentina Harizanov, GWU

http://home.gwu.edu/~harizanv/

Place: Monroe Hall (2115 G Street), Room 267

Title: Orderable groups

Abstract: We investigate properties of orders on groups that respect the algebraic structure. There is a natural topology on the set of such orders, and this space is compact even for magmas. For some groups, this space is homeomorphic to the Cantor set. For familiar computable groups, we investigate the structure and complexity of orders and their connection with computable trees. Many questions remain open.

 

 

Friday, January 24, 2014

4:005:00p.m.

Speaker: Russell Miller, City University of New York

http://qcpages.qc.cuny.edu/~rmiller/

Place: Monroe Hall (2115 G Street), Room 267

Title: The theory of fields is complete for isomorphisms

Abstract: We give a highly effective coding of countable graphs into countable fields.  For each countable graph G, we build a countable field F(G), uniformly effectively from an arbitrary presentation of G.  There is a uniform effective method of recovering the graph G from the field F(G).  Moreover, each isomorphism g from G onto any G' may be turned into an isomorphism F(g) from F(G) onto F(G'), again by a uniform effective method so that F(g) is computable from g. Likewise, an isomorphism f from F(G) onto any F(G') may be turned back into an isomorphism g with F(g)=f.  Not every field F isomorphic to F(G) is actually of the form F(G'), but for every such F,  there is a graph G' isomorphic to G and an isomorphism f from F onto F(G'), both computable in F.

 

It follows that many computable-model-theoretic properties which hold of some graph G will carry over to the field F(G), including spectra, categoricity spectra, automorphism spectra, computable dimension, and spectra of relations on the graph.  By previous work of Hirschfeldt, Khoussainov, Shore, and Slinko, all of these properties can be transferred from any other countable, automorphically nontrivial structure to a graph (and then to various other standard classes of structures), so our result may be viewed as saying that, like these other classes, fields are complete for such properties.

 

This work is joint with Jennifer Park, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh.

 

 

Logic-Topology Seminar

Tuesday, January 21, 2014

5:006:00p.m.

Speaker: Victoria Lebed, Advanced Mathematical Institute, Osaka City University, Japan

http://www.math.jussieu.fr/~lebed/index_ENG.html

Place: Monroe Hall (2115 G Street), Room 267

Title:  Towards topological applications of Laver tables

Abstract: Laver tables are certain finite shelves (i.e., sets endowed with a binary operation which is distributive with respect to itself). They originate from set theory and have a profound combinatorial structure. In this talk I will discuss our dreams regarding potential braid and knot invariant constructions using Laver tables, and also present some real results in this direction, such as a detailed description of 2- and 3-cocycles for Laver tables. The rich structure of the latter promises interesting topological applications.

(Joint work with Patrick Dehornoy)

 

Logic in Baltimore

 

2014 Joint Math Meetings, Baltimore Convention Center: January 15–18, 2014

http://jointmathematicsmeetings.org/meetings/national/jmm2014/2160_intro

 

AMS-ASL Special Session on Logic and Probability

 

AMS Special Session on Computability in Geometry and Topology

 

Association for Symbolic Logic Winter Meeting:  January 17–18, 2014

 

 

Fall 2013

 

Tuesday, December 17, 2013

3:455:00p.m.

Speaker: Rumen Dimitrov, Western Illinois University

http://www.wiu.edu/users/rdd104/home.htm

Place: Monroe Hall (2115 G Street), Room 267

Title: The open problem regarding the automorphisms of L*(Q_inf)

Abstract: Guichard proved in 1984 that there are countably many automorphisms of the lattice L(Q_inf) of computably enumerable subspaces of Q_inf by proving that the automorphisms are generated  by computable semilinear transformations. The question about the number of automorphisms of the factor-lattice L*(Q_inf) is still open. We will discuss AshÕs conjecture regarding this question and how some of our recent results corroborate this conjecture.

 

 

Thursday, December 12, 2013

4:005:00p.m.

Speaker: Leah Marshall, GWU

Place: Monroe Hall (2115 G Street), Room 267

Title: Computable categoricity

Abstract: A computable structure A is computably categorical if for every isomorphic computable structure B there is a computable isomorphism from A to B. We will present some recent results regarding computable isomorphism including an example of a computable structure that is not computably categorical.

 

 

Thursday, November 21, 2013

5:30–6:30 p.m.

Speaker: Valentina Harizanov, GWU

http://home.gwu.edu/~harizanv/

Place:  Monroe Hall (2115 G Street), Room 267

Title: C.e. and co-c.e. structures and their isomorphisms

Abstract: Computable structures and their isomorphisms have been studied extensively in computable structure theory. Here, we investigate the complexity of isomorphisms of computably enumerable (c.e.) and co-computably enumerable (co-c.e.) structures with a single equivalence relation and structures with a single injective function. This is joint work with Doug Cenzer and Jeff Remmel.

 

 

Friday, October 11, 2013

4:30–5:30 p.m.

Speaker: Mietek Dabkowski, University of Texas at Dallas

http://www.utdallas.edu/math/faculty/dabkowski.html

Place:  Monroe Hall (2115 G Street), Room 267

Title: Orderable groups and their spaces of orders

Abstract: A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. We investigate computability theoretic and topological properties of spaces of left orders on computable orderable groups. Topological properties of spaces of orders on groups were first studied by A. Sikora who showed that for free abelian groups of finite rank n >1 the space of orders is homeomorphic to the Cantor set. We study groups for which the spaces of left orders contain the Cantor set and we establish that a countable free group of rank n ³2 and fundamental groups of oriented surfaces have a bi-order in every Turing degree.

 

 

Thursday, September 19, 2013

5:30–6:30 p.m.

Speaker:  Jennifer Chubb, University of San Francisco

http://cs.usfca.edu/~jcchubb/

Place:  Monroe Hall (2115 G Street), Room 267

Title: Orderings of algebraic structures

Abstract: A partial left ordering or bi-ordering of an algebraic structure is a partial ordering of the elements of the structure, which is invariant under the structure acting on itself on the left or, respectively, both on the left and on the right. I will discuss algorithmic properties of the orderings admitted by a computable structure, and consider some general questions.

 

 

Logic-Topology Seminar

Thursday, September 5, 2013

5:306:30p.m.

Speaker: Jozef Przytycki, GWU

http://home.gwu.edu/~przytyck/

Place: Monroe Hall (2115 G Street), Room 267

Title:  Quandles and codimension two embeddings

Abstract: Distributivity has been an integral part of logic for a long time. An attempt to decouple them in linear logic applied to quantum mechanics was not successful. Distributivity in topology is a more recent development and can be dated to the PhD dissertation of Joyce in 1979, in which quandles were applied to knot theory. The next push came with construction of homology theory for quandles by Fenn, Rourke, and Sanderson (between 1990 and 1995). In 1998, Carter, Kamada, and Saito
discovered how to use homology of quandles to study classical and higher-dimensional knots. From that time we observe an exponential growth of the topic, and it is my pleasure to report that it was achieved partly by work of our students. In this I talk will offer a gentle introduction to this unusually successful use of distributivity in
knot theory.
References
1. J.S. Carter, S. Kamada, and M. Saito, Surfaces in 4-space, Encyclopaedia Mathematical Sciences, Low-Dimensional Topology III, Gamkrelidze,
and Vassiliev, editors, 2004, 213pp.
2. D. Joyce, An Algebraic Approach to Symmetry with Applications to Knot Theory, Ph.D. dissertation, University of Pennsylvania, 1979.
3. J.H. Przytycki, Distributivity versus associativity in the homology theory of algebraic structures, Demonstratio Math., 44 (2011), pp. 823–869;
 e-print: http://front.math.ucdavis.edu/1109.4850