LOGIC SEMINAR

Spring 2012

Previous seminars at:

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

Campus map

http://www.gwu.edu/staticfile/GW/Admissions-Undergraduate/2010-foggy-bottom-map.pdf

Thursday, April 26, 2012

4:30–5:30 p.m.

Speaker: Joe Mourad, Georgetown University

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

Title: Applications of Fixed Point Behavior in “Ecological” Computability, III, the case N ≥3

Abstract: Finally, I would like to consider the case when N = 3. In mathematics, in general, we usually see that 3 or more does not work the same way as 2 does for reflection principles. When there are N representational systems, and we consider self-reflection and directed reflective subsystems, we obtain N² different systems. Up to isomorphism there are really just two main types. So the interesting case occurs when two or more of the N agents are somehow unique so that they are not interchangeable. We will apply this mathematical framework to the Enneagram model for personality and look at empirical evidence to support our models.

Thursday, April 19, 2012

4:30–5:30 p.m.

Speaker: Joe Mourad, Georgetown University

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

Title: Applications of Fixed Point Behavior in “Ecological” Computability, II, the case N =2

Abstract: The second in a series of three talks will look at the case of two independent computing agents or representational systems. The corresponding result in computabilty theory will be the Double Recursion Theorem due to Raymond Smullyan. We will also look at the versions of the fixed point images on R² that pertain to this case. We will discuss potential applications outside of mathematics.

Thursday, April 12, 2012

4:30–5:30 p.m.

Speaker: Joe Mourad, Georgetown University

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

Title: Applications of Fixed Point Behavior in “Ecological” Computability, I, the case N =1

Abstract: This will be the first in a series of three talks, which will build on themes that we touched on in the Fall 2011 series. There we used the fixed point theorems to talk about self-identifying machines, which needed to locate themselves given a changing (evolving) environment. We used a map of North Carolina to identify the fixed point of that particular map (it went through Rock Springs North Carolina and, if you recall, lies somewhere southeast of Durham.) We will review these results and explore applications of such ideas to philosophy of mind/cognitive science. In doing so we will explore metatheoretic issues dealing with the application of rigorous formal methods to both mainstream experimental science and “folk science”. We will make the transition to the case of N =2. Although familiarity with the fixed point theorems in both logic and analysis is helpful, no prior knowledge will be needed.

Distinguished Logic Seminar

Friday, March 16, 2012

11:00 a.m.–12:00 noon

Speaker: Doug Cenzer, University of Florida

http://www.math.ufl.edu/~cenzer/

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

Title: Effective Categoricity of Injection  Structures

Abstract: An injection structure A consists of a set A together with a one-to-one function f mapping A to A. These are among the most fundamental structures in mathematics. The orbit of an element a of A is the set of images f ⁿ(a) and also the preimages f ^-n(a) of a. Orbits are of three types. They may be finite, where f ⁿ(a) = a for some n. They may have type w and consist of an element a not in the range of f, together with its images f ⁿ(a) for every natural number n. Finally, they may have type Z and consist of an element a together with an infinite sequence of images f ⁿ(a) and also an infinite sequence of preimages f ^-n(a). By an effective structure we will mean that f is computable and that A is either computable, c.e. or co-c.e. set of natural numbers. A computable injection structure A is said to be computably categorical if for any computable structure B isomorphic to A, there is a computable isomorphism. We show that A is computably categorical if and only if it has only finitely many infinite orbits. Any c.e. injection structure A is isomorphic to some computable structure B and, furthermore, there is a computable isomorphism from B onto A. We also consider Delta-2 and Delta-3 isomorphisms.

Friday, March 16, 2012

(jointly with Knots in Washington)

Time: TBA

Speaker: Wesley Calvert, Western Illinois University

http://www.math.siu.edu/calvert/index2.html

Place: Rome Hall (801 22^nd Street), Room 459

Title: Computing Distances in Graphs

Abstract: How can we compute the distance between vertices in a graph, given only data on adjacency? If there are infinitely many vertices, this problem may be unsolvable, but it can still be approximated in an interesting way. It turns out that distances in graphs capture this sort of approximation exactly, in that any function that can be approximated can be approximated by a graph. I'll give examples that aren't obviously graph-like. This is joint work with Jennifer Chubb Reimann and Russell Miller.

Thursday, March 8, 2012

4:30–5:30 p.m.

Speaker: Kai Maeda, GWU

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

Title: Non-Associative Structures and Their Turing Degrees

Abstract: We investigate Turing degrees of non-associative structures and their isomorphism types. These structures include racks, quandles and crossed sets. We will first review their definitions and establish basic properties.

Thursday, February 23, 2012

4:30–5:30 p.m.

Speaker: Kai Maeda, GWU

Place: Monroe Hall (2115 G Street), Room 253 (Math Lab)

Title: Enumeration Reducibility and Application to Structure Theory

Abstract: I will establish several results about enumeration reducibility in computability theory. I will then show how they can be used in computable model theory to produce a countable structure the isomorphism type of which does not have a Turing degree.

Thursday, February 16, 2012

4:30–5:30 p.m.

Speaker: Kai Maeda, GWU

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

Title: Turing Degrees of Isomorphism Types of Structures

Abstract: I will introduce one of Richter’s theorems, which uses enumeration reducibility to show that a structure does not have the degree of its isomorphism class.  I will then apply this result to structures not previously studied in computability theory.

LOGIC SEMINAR

Fall 2011

Thursday, December 1, 2011

4:00–5:00 p.m.

Speaker: Kai Maeda, GWU

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

Title: Anti-Chains and Richer’s Degrees of Algebraic Structures

Abstract: Richter’s degree of a countable algebraic structure is a Turing degree theoretic measure of complexity of its isomorphism class.  It has been shown that some classes, such as abelian groups or partially ordered sets, have arbitrary degrees, by showing that these classes contain infinite anti-chains of structures with certain algebraic and computability theoretic properties.  I will further extend these results to structures not previously studied in logic.

Thursday, November 10, 2011

4:00–5:00 p.m.

Speaker: Valentina Harizanov, GWU

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

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

Title: Co-Computably Enumerable Equivalence Structures

Abstract: We investigate co-computably enumerable equivalence structures and their isomorphisms. We prove that for every computable, relatively limit computably categorical equivalence structure, which is not computably categorical, there is an isomorphic co-computably enumerable structure that is not limit computably isomorphic to any computable, even computably enumerable structure. This is joint work with D. Cenzer (U. of Florida) and J. Remmel (U. California, San Diego).

Thursday, November 3, 2011

4:00–5:00 p.m.

Speaker: Valentina Harizanov, GWU

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

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

Title: Computably Enumerable Equivalence Structures

Abstract: We investigate computably enumerable equivalence structures and their isomorphisms. While every computably enumerable equivalence structure with infinitely many infinite classes is isomorphic to a computable structure, there are computably enumerable equivalence structures that are not isomorphic to computable ones. We show that if computably enumerable equivalence structures A and B are isomorphic to a computable structure that is relatively limit computably categorical, then A and B are limit computably isomorphic. This is joint work with D. Cenzer (U. of Florida) and J. Remmel (U. California, San Diego).

Thursday, October 27, 2011

4:00–5:00 p.m.

Speaker: Fredrick Nelson, Howard University

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

Title: Effective p-adic Filtration of Rank-1 Holm Curves

Abstract: The Holm curve H is given by an equation of the form ky(y+r+s)(y-r+s) = lx(x+r+s)(x-r+s), where r and s are relatively prime integers with r > |s|, and k and l are distinct square-free relatively prime positive integers. H is an elliptic curve passing through each the nine points (-r-s,-r-s), (-r-s,0), (-r-s,r-s), (0,-r-s), (0,0), (0,r-s), (r-s,-r-s), (r-s,0), and (r-s,r-s).  The other rational points on H are associated in a precise (but  possibly non-effective) manner with pairs (M,N) of q-congruent numbers where cos(q) = s/r and M/N = k/l. Conjecturally, the group of rational points on every Holm curve is torsion-free so its rank is at least 1.  It is natural to ask whether rank-1 Holm curves exist.  We answer this question in the affirmative and discuss an effective characterization of the p-adic filtration on the Weierstrass curve E corresponding to H, which yields infinitely many pairs of q-congruent numbers with ratio k/l.

Thursday, October 13, 2011

4:00–5:00 p.m.

Speaker: Joe Mourad, Georgetown University

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

Title: Paradox, Fixed Points, and Computability

Abstract: This will be an entirely self-contained talk at an elementary level, focusing on some aesthetically and philosophically interesting aspects of computability theory. One of the hallmark features of computability is its universality. This gives rise to a phenomenon that is reflexive or in some sense self-referential. In applications this results in computation procedures that model both paradoxical and equilibrium, or fixed point, behavior. In the computable setting these mysterious phenomena turn out to be much more understandable. Indeed one of the features that is elucidated is the dichotomy between local and global action. We will explore these themes and look at some of the common paradoxes and Kleene Fixed Point Theorem (Recursion Theorem) and give applications.

Thursday, September 29, 2011

4:00–5:00 p.m.

Speaker: Joe Mourad, Georgetown University

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

Title: “Ecological” Computing, part II

Abstract: The questions of fixed points and stability arise very naturally in the context of Oracle Turing Machines presented last time. The proof of the Kleene fixed point theorem and applications will be presented in a natural way. Furthermore, I will show that this schema not only gives the Turing computable functions but the whole hyperarithmetic hierarchy. Further generalizations will also be explored.

Thursday, September 22, 2011

4:00–5:00 p.m.

Speaker: Joe Mourad, Georgetown University

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

Title: “Ecological” Computing, part I: Fixed Points

Abstract: This is an elementary presentation of Oracle Turing Machines with an added twist. The twist is that we view the oracle as the complete computing environment. This environment not only contains functions already computed, but even contains (a version of) the function currently being computed. This is meant to simulate the way computing actually occurs in the real world where self-reference and even irreconcilable conflict can occur (Is so., Is not., Is so!, Is not!, IS SO!!, IS NOT!!! ...). The questions of fixed points and stability arise very naturally in this context.

Logic-Topology Seminar

Tuesday, September 20, 2011

11:10a.m.–12:10p.m.

Speaker: Jozef Przytycki, GWU

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

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

Title: Homology of Distributive Lattices

Abstract: While homology theory of associative structures, such as groups and rings, was extensively studied in the past, beginning with the work of Hopf, Eilenberg, and Hochschild, homology of non-associative distributive structures, such as quandles, has been neglected until recently. Distributive structures have been studied for a long time. In 1880, C.S. ~Peirce emphasized the importance of (right-) self-distributivity in algebraic structures. However, homology for these universal algebras was introduced only sixteen years ago by Fenn, Rourke, and Sanderson. We develop this theory in the historical context and propose a general framework to study homology of distributive structures. We illustrate the theory by computing some examples of 1-term and 2-term homology, and then by discussing 4-term homology for Boolean algebras and distributive lattices. We will start with a gentle introduction to distributive lattices and Boolean algebras (and their generalizations) for topologists, and with homology theory of distributive structures for logicians. We will end by outlining potential relations to Khovanov homology, via the Yang-Baxter operator.

Graduate Student Seminar

Thursday, October 27, 2011

11:00a.m.–12:00 noon

Speaker: Kai Maeda, GWU

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

Title: Turing Degrees of the Isomorphism Types of Structures

Abstract: Richter’s degree of a countable algebraic structure is a computability theoretic measure of complexity of its isomorphism class. It has been shown that some classes, such as abelian groups or partially ordered sets, have arbitrary degrees, while other structures, such as linear orderings or trees, can only have degree 0. In this presentation, I will explain how we measure this degree of complexity of isomorphism types and will survey some known results. Finally, I will further extend these results to structures not previously studied in logic.