# LOGIC SEMINAR

http://home.gwu.edu/~harizanv/Logic%20Seminar%20F09.html

# Friday, April 22, 2016

3:004:00p.m.

Speaker: Jacob Learned, GWU

Place: Corcoran Hall (725 21st Street), Room 106

Title: Quantum neural networks

# Wednesday, April 20, 2016

2:30330p.m.

Speaker: Mariel Supina, GWU

Place: Bell Hall (2029 G Street), Room 108

Title: GroverÕs search algorithm: quantum speed-up

# Wednesday, April 13, 2016

5:306:30p.m.

Speaker: Valentina Harizanov, GWU

Place: Corcoran Hall (725 21st Street), Room 101

Title: Transforming structures

Abstract: Often, interesting computability-theoretic phenomena are first obtained on structures of special kind, which result from specific complicated constructions and may not come from natural classes. It is often desirable to find such phenomena on structures in other, well-known classes. We will present algorithmic ways of transforming certain countable structures and their isomorphisms into other types of algebraic structures and their isomorphisms in such a way that relevant computability-theoretic properties are transferred.

# Wednesday, March 30, 2016

5:306:30p.m.

Speaker: Johanna Franklin, Hofstra University, NY

Place: Funger Hall (2201 G Street), Room 108

Title: Category and lowness for isomorphism

Abstract: A Turing degree d is said to be low for isomorphism if, whenever two structures are d-isomorphic, they are already computably isomorphic. Solomon and I proved that every 2-generic Turing degree was low for isomorphism and hypothesized that no weaker level of genericity would suffice. However, Turetsky and I constructed a properly 1-generic real that is low for isomorphism. In this talk, I will present proofs of both of these results.

Wednesday, February 3, 2016

5:306:30p.m.

Speaker: Valentina Harizanov, GWU

Place: Phillips Hall (801 22nd Street), Room 110

Title: The tree method in priority arguments

# Wednesday, January 20, 2016

5:306:30p.m.

Speaker: Russell Miller, City University of New York

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

Place: Phillips Hall (801 22nd Street), Room 110

Title: Computable functors and effective interpretations

Abstract:  We draw connections between two related notions. An effective interpretation of a countable structure A in another countable structure B uses exactly the notion of interpretation from model theory, except that now the domain of the interpretation is allowed to use tuples from B of arbitrary finite length, and that the formulas to be used must be computable infinitary Sigma_1 formulas, rather than finitary formulas of arbitrary complexity. A computable functor, from the category Iso(B) of all structures with domain omega isomorphic to B to the corresponding category Iso(A), is given by two Turing functionals, one mapping objects from Iso(B) to objects in Iso(A) and the other mapping isomorphisms between objects in Iso(B) to isomorphisms between the corresponding objects in Iso(A). Recent work by Harrison-Trainor, Melnikov, Montalb‡n and the speaker has shown these two concepts to very tightly related. An effective interpretation of A in B clearly yields a computable functor from Iso(B) to Iso(A). We will describe the converse and consider how these notions may be extended to continuous functors and interpretations by L_omega_1,omega formulas in general.

# Wednesday, December 2, 2015

5:306:30p.m.

Speaker: Tslil Clingman, GWU

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

Title: An exploration of the category of relations

Abstract:  The category of relations, Rel, has a rich structure and serves as an important example of many concepts in the general theory. We will begin by understanding morphisms, limits and self-duality in this category, observing that one may take the external axiom of choice (as this is not always possible), before moving to understand any of the several important structural notions present in Rel. Depending on audience interest, we will see how Rel is a (closed) monoidal category, an enriched category (in two important ways) and even a strict 2-category. Finally, time permitting, we will explore a very important generalisation of Rel which leads to the general theory of weak 2-categories. Only elementary knowledge of category theory will be assumed.

# Thursday, November 12, 2015

6:007:00p.m.

Speaker: Valentina Harizanov, GWU

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

Title: Coding sets into orders

# Wednesday, November 4, 2015

5:306:30p.m.

Speaker: Ajit Iqbal Singh, Indian National Science Academy

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

Title: Roping more by ringing less in topology

# Thursday, October 29, 2015

6:007:00p.m.

Speaker: Rumen Dimitrov, Western Illinois University

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

# Wednesday, October 14, 2015

5:306:30p.m.

Speaker: Tslil Clingman, GWU

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

Title: A gentle introduction to monoidal categories

Abstract: While general categories provide a rich and deep theory, more focused inquiry may be achieved by requiring of the categories a certain additional structure. Perhaps one of simplest starting points is requiring the objects of the category to form a monoid in an appropriate sense. We shall work our way up from elementary definitions in the general theory to such Òmonoidal categoriesÓ, examine their natural manifestations, explore what Ògeneralised elementsÓ of such categories may be and, time allowing, further directions and motivations. No prior understanding of category theory will be assumed.

Wednesday, October 7, 2015

5:306:30p.m.

Speaker: Dr. Fredrick Nelson

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

Title: The group of rational points on the Holm curve is torsion-free

Abstract: The Holm curve is the elliptic curve given by the equation k,,y-^3.y. = l,,x^-3.x. where k and l are distinct, relatively prime, square-free, positive integers. It is isomorphic to the elliptic curve in Weierstrass form. By MordellÕs theorem, the group of rational points on the Holm curve is a finitely-generated abelian group. I will prove that this group is torsion-free, thus establishing a previous conjecture. The proof uses McKeeÕs algorithm for computing division polynomials of elliptic curves.

# Wednesday, September 30, 2015

5:306:30p.m.

Speaker: Hakim Walker, GWU

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

Title: Computable isomorphisms between (2,1):1 structures

Abstract: A (2,1):1 structure consists of a countable set A (usually the natural numbers) and a function f that maps, to each element of A, either exactly one element of A or exactly two elements of A. Similar structures have been studied recently by Harizanov, Cenzer, Remmel, and Marshall, particularly the complexity of isomorphisms between such structures. In this talk, we will begin by presenting some of the basic properties of these structures, particularly the types of orbits under f, which can be interpreted as directed graphs. Then we will discuss some computability-theoretic results, including two classes of (2,1):1 structures that are computably categorical, i.e., every two computable copies of the structure have a computable isomorphism between them. Finally, we will conclude with an application to the Collatz conjecture.

# Wednesday, September 23, 2015

5:306:30p.m.

Speaker: Jozef Przytycki, GWU

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

### Title: Curtain homology and logic

Abstract: We show a simple visualization that allows us to construct homology theory for a Yang-Baxter operator. The linear map $R: V\otimes V \to V\otimes V$ is called by Fadeev school of theoretical physics the Yang-Baxter operator if it is invertible and satisfies the following equation:
$(R\otimes Id) (Id \otimes R)(R\otimes Id) = (Id \otimes R)(R\otimes Id)(Id \otimes R)$.
We show that the quandle homology, in its cubic form, can be presented graphically using a diagram (curtain diagram). This in turn gives rise to homology of Yang-Baxter operator. We speculate that this homology is related to Khovanov homology of links and gives a deep connection between Knot Theory and Statistical Physics.