Files.

About: This page contains links to and descriptions of files I have available for downloading.

Files

• My thesis (pdf file) | : Cofinitary Groups and Other Almost Disjoint Families (written under supervision of Andreas Blass and Yi Zhang).

  Abstract: We study two different types of (maximal) almost disjoint families: very mad families and (maximal) cofinitary groups. For the very mad families we prove the basic existence results. We prove that MA implies there exist many pairwise orthogonal families, and that CH implies that for any very mad family there is one orthogonal to it. Finally we prove that the axiom of constructibility implies that there exists a coanalytic very mad family.
  Cofinitary groups have a natural action on the natural numbers. We prove that a maximal cofinitary group cannot have infinitely many orbits under this action, but can have any combination of any finite number of finite orbits and any finite (but nonzero) number of infinite orbits.
  We also prove that there exists a maximal cofinitary group into which each countable group embeds. This gives an example of a maximal cofinitary group that is not a free group. We start the investigation into which groups have cofinitary actions. The main result there is that it is consistent that the direct sum of א₁ many copies of Z₂ has a cofinitary action.
  Concerning the complexity of maximal cofinitary groups we prove that they cannot be K_σ, but that the axiom of constructibility implies that there exists a coanalytic maximal cofinitary group. We prove that the least cardinality a_g of a maximal cofinitary group can consistently be less than the cofinality of the symmetric group.
  Finally we prove that a_g can consistently be bigger than all cardinals in Cichon's diagram.

• Cardinal Invariants Related to Permutation Groups, with Yi Zhang pdf file. (published in Ann. Pure Appl. Logic 143 (2006), pp. 139--146i.

  Abstract: We consider the possible cardinalities of the following three cardinal invariants which are related to the permutation group on the set of natural numbers:
  a_g := the least cardinal number of maximal cofinitary permutation groups;
  a_p := the least cardinal number of maximal almost disjoint permutation families;
  c(Sym(N)) := the cofinality of the permutation group on the set of natural num- bers.
  We show that it is consistent with ZFC that a_p = a_g < c(Sym(N)) = 2 ; in fact we show that in the Miller model a_p = a_g = א₁ < א₂= c(Sym(N)).

• Very Mad Families pdf file. (published in Contemporary Mathematics 425, Advances in Logic, The North Texas Logic Conference, October 8-10, 2004, University of North Texas, Denton, Texas, edited by Su Gao, Steve Jackson, and Yi Zhang,, pp. 105--112)

  Abstract: The notion of very mad family is a strengthening of the notion of mad family of functions. Here we show existence of very mad families in different contexts.

• Analytic and Coanalytic Families of Almost Disjoint Functions, with Juris Steprans and Yi Zhang, pdf file. The Journal Symbolic Logic, Volume 73 (2008), no. 4, 1158--1172.

  Abstract: If F ⊆ ^NN is an analytic family of pairwise eventually different functions then the following strong maximality condition fails: For any countable H ⊆ ^NN, no member of which is covered by finitely many functions from F, there is f ∈ F such that for all h ∈ H there are infinitely many integers k such that f(k) = h(k). However if V = L then there exists a coanalytic family of pairwise eventually different functions satisfying this strong maximality condition.

• The Complexity of Maximal Cofinitary Groups, pdf file. Proceeding American Mathematical Society, Vol. 137 (2009), no. 1, 307--316.

  Abstract: A cofinitary group is a subgroup of the infinite symmetric group in which each element of the subgroup has at most finitely many fixed points. A maximal cofinitary group is a cofinitary group that is maximal with respect to inclusion. We investigate the possible complexities of maximal cofinitary groups, in particular we show that (1) under the axiom of constructibility there exists a coanalytic maximal cofinitary group, and (2) there does not exist an eventually bounded maximal cofinitary group. We also suggest some further directions for investigation.

• Comparing Notions of Randomness, with Steffen Lempp. pdf file Accepted in Theoretical Computer Science, and available on their website.

  Abstract: It is an open problem in the area of effective (algorithmic) randomness whether Kolmogorov-Loveland randomness coincides with Martin-Löf randomness. Joe Miller and André Nies suggested some variations of Kolmogorov-Loveland randomness to approach this problem and to provide a partial solution. We show that their proposed notion of injective randomness is still weaker than Martin-Löf randomness. Since in its proof some of the ideas we use are clearer, we also show the weaker theorem that permutation randomness is weaker than Martin-Löf randomness.

• Stability and Posets, Carl G. Jockusch, Jr., Bart Kastermans, Steffen Lempp, Manuel Lerman, and Reed Solomon. pdf file. Journal of Symbolic Logic, 74 (2009), no. 2, pp 693--711.

  Abstract: Hirschfeldt and Shore have introduced a notion of stability for infinite posets. We define an arguably more natural notion called weak stability, and we study the existence of infinite computable or low chains or antichains, and of infinite Π⁰₁-chains and antichains, in infinite computable stable and weakly stable posets. For example, we extend a result of Hirschfeldt and Shore to show that every infinite computable weakly stable poset contains either an infinite low chain or an infinite computable antichain. Our hardest result is that there is an infinite computable weakly stable poset with no infinite Π⁰₁-chains or antichains. On the other hand, it is easily seen that every infinite computable stable poset contains an infinite computable chain or an infinite Π⁰₁-antichain. In Reverse Mathematics, we show that SCAC, the principle that every infinite stable poset contains an infinite chain or antichain, is equivalent over RCA₀ to WSCAC, the corresponding principle for weakly stable posets.

• On Computable Self-Embeddings of Computable Linear Orderings, Rodney G. Downey, Bart Kastermans, and Steffen Lempp. pdf file | project euclid. Journal of Symbolic Logic, Volume 74, Issue 4 (2009), pp. 1352--1366.

  Abstract: We make progress toward solving a long-standing open problem in the area of computable linear orderings by showing that every computable η-like linear ordering without an infinite strongly η-like interval has a computable copy without nontrivial computable self-embedding.

  The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

• Isomorphism Types of Maximal Cofinitary Groups, Bulletin of Symbolic Logic, September 2009, Volume 15, pp. 300-319. pdf file

  Abstract: A cofinitary group is a subgroup of Sym(N) where all nonidentity elements have finitely many fixed points. A maximal cofinitary group is a cofinitary group, maximal with respect to inclusion. We show that a maximal cofinitary group cannot have infinitely many orbits. We also show, using Martin's Axiom, that no further restrictions on the number of orbits can be obtained. We show that Martin's Axiom implies there exist locally finite maximal cofinitary groups. Finally we show that there exists a uniformly computable sequence of permutations generating a cofinitary group whose isomorphism type is not computable.

• An Example of a Cofinitary Group in Isabelle/HOL. pdf file. In: G. Klein, T. Nipkow, and L. Paulson (ed), The Archive of Formal Proofs, http://afp.sourceforge.net/entries/CofGroups.shtml, August 2009, Formal proof development.

  Abstract: We formalize the usual proof that the group generated by the function k -> k+1 on the integers gives rise to a cofinitary group.

• Questions on Cofinitary Groups pdf file. (submitted)

  Abstract: A cofinitary group is a subgroup of the symmetric group on the natural numbers in which all non-identity members have finitely many fixed points. In this note we describe some questions about these groups that interest us; questions on related cardinal invariants and isomorphism types.

slides for talks.

• 2009 August: New Mexico State University. pdf files of slides for the talk ``A formalization of a simple example of a cofinitary group'' given at BLAST09.
• 2009 January: University of Colorado at Boulder. pdf file of slides for the talk ``Separating Notions of Randomness'' given in the logic seminar.
• 2009 January: University of Colorado at Boulder. pdf file of slides for the talk ``Maximal Cofinitary Groups''.
• 2008 March: Boise State University. pdf file of slides for the talk ``Maximal Cofinitary Groups''.
• 2008 February: Penn State, Pennsylvania: The Center for Dynamics and Geometry Seminar. pdf files of slides for the talk "Generating Sets of Cofinitary Groups".
• 2008 February: Penn State, Pennsylvania: logic seminar. pdf files of slides for the talk "Separating Notions of Randomness".
• 2007 October: Rutgers University, New Brunswick: special session on Set Theory of the Reals of the AMS sectional meeting, and MAMLS meeting. pdf files of slides for the talk "A Locally Finite Maximal Cofinitary Group".
• 2007 July: Bedlewo, Poland: First European Set Theory Meeting. pdf file of slide for the talk "A Locally Finite Maximal Cofinitary Group".
• 2007 March: Miami University, Oxford, Ohio. pdf file of slides for the talk "Orthogonal MAD Families".
• 2007 February: University of Wisconsin -- Madison, Department Colloquium, pdf file of slides for the talk "Concreteness of Cofinitary Subgroups of the Infinite Symmetric Group".
• 2006 June: Methods of Logic in Mathematics III. A talk on the construction of a coanalytic maximal cofinitary group under the axiom of constructibiity pdf file.
• 2006 May: ASL annual meeting in Montreal. A talk on maximal cofinitary groups and questions influenced by its group structure pdf file of slides.
• 2006 May: Southern Wisconsin Logic Colloquium. A talk on the existence of a coanalytic maximal cofinitary group under the axiom of constructability pdf file of slides.
• 2006 April: Graduate Student Conference, Wisconsin. A talk on orthogonal very mad families pdf file of slides.
• 2005 December: pdf file of slides of a survey type talk about maximal cofinitary groups for a conference in Zhuhai, China.
• 2005 September: Millican Lecture, University of North Texas, Denton, Texas, pdf file of slides for the talk "The Question of Concreteness of Cofinitary Subgroups of the Infinite Symmetric Group".
• 2005 September: Logic Seminar, University of North Texas, Denton, Texas, pdf file of slides for the talk "A Π¹₁ Maximal Cofinitary Group" (note these slides were used in combination with the blackboard)
• 2005 July: Methods of Logic in Mathematics II, Cardinal Invariants Related to Permutation Groups, pdf file of slides.
• 2005 April: Sun Yat Sen University, Mathematics Colloquium, April 1 2005, Cofinitary Permutation Groups pdf file of slides.
• 2004 December: University of Michigan Logic Seminar, December 2, slides of my talk on Maximal Cofinitary groups and how to construct them pdf file.
• 2004 November: New York Graduate Student Logic Conference, slides of my talk on the axiom of constructability and Π¹₁ families of reals pdf file.
• 2004 November: North Texas Logic Conference 2004: slides of my talk on Orbits of Maximal Cofinitary Groups (pdf file).
• 2003 August: Logic Colloquium 2003 Helsinki, abstract of my talk on Very Mad Families (ps file) (pdf file).
• 2003 August: Logic Colloquium 2003 Helsinki, slides of my talk on Very Mad Families (pdf file).