The Cichon Diagram for Degrees of Relative Constructibility

I just submitted my first paper: The Cichon Diagram for Degrees of Constructibility, on the ArXiv here, and I wanted to take the opportunity to write something about it here.

Abstract: Following a line of research initiated by Brendle, Brooke-Taylor, Ng and Nies, I describe a general framework for turning reduction concepts of relative computability into diagrams forming an analogy with the Cichon diagram for cardinal characteristics of the continuum. I show that working from relatively modest assumptions about a notion of reduction, one can construct a robust version of such a diagram. As an application, I define and investigate the Cichon Diagram for degrees of constructibility relative to a fixed inner model W. Many analogies hold with the classical theory as well as some surprising differences. Along the way I introduce a new axiom stating, roughly, that the constructibility diagram is as complex as possible.

In this paper I consider generalizations of the Cichon Diagram for reduction concepts. A reduction concept is a triple (X, \sqsubseteq, 0) where X is a non-empty set, \sqsubseteq is a partial preorder on X and 0 \in X is a distinguished element. An element x \in X is called basic if x \sqsubseteq 0. Common examples include Turing reducibility with the basic elements being the computable sets, arithmetic reducibility with the basic elements being the \emptyset-definable subsets of \mathbb N and degrees of constructibility with the basic elements being the constructible reals (in all these cases the underlying set is the reals). I show for a wide variety of reduction concepts on the reals, one can develop a generalization of the ideas underlying the study of the cardinal characteristics of the continuum by considering sets \mathcal B_\sqsubseteq (R) and \mathcal D_\sqsubseteq (R) for various relations R, where \mathcal B_\sqsubseteq (R) is the set of elements which \sqsubseteq-build a witness to the fact that the basic reals are small with respect to R and \mathcal D_\sqsubseteq (R) is the set of elements which \sqsubseteq-build a witness to the fact that the basic reals are not big with respect to R. I show that for such reduction concepts one can always construct an analogue of the Cichon diagram. For example, below is the Cichon diagram for degrees of constructibility relative to a fixed inner model W. Recall that x \leq_W y if and only if x \in W[y].


Screen Shot 2018-01-23 at 3.00.32 PM


In the second part of the paper I focus on the case of \leq_W and show that all of the arrows pictured above are consistently strict.

Theorem: The Cichon diagram for \leq_W as shown above is complete in the sense that if A and B are two nodes in the diagram and there is not an arrow from A to B in the \leq_W-diagram then there is a forcing extension of W where A is not a subset of B.

The proof of this theorem involves studying how the diagram is affected by familiar forcing notions to add reals. Accompanying my arguments are versions of the diagram as affected by these forcing notions. For example, here are the versions for Sacks, Cohen and Hechler forcing.

In the end I show that there is one proper forcing over W which simultaneously realizes all possible separations. This is the last main theorem proved in the paper. It’s formalized in GBC.

Theorem: Given any transitive inner model W of ZFC, there is a proper forcing notion \mathbb P, such that in W^\mathbb P all the nodes in the \leq_W-Cicho\’n diagram are distinct and every possibile separation is simultaneously realized.

Screen Shot 2018-01-23 at 3.17.11 PM

For more information check out the paper! Also, you can see a blog post about it on the page of my advisor, Joel David Hamkins, to whom I am incredibly grateful, here.


Final Study Guide

As I mentioned in class, I have compiled a list of questions as a Final Study Guide to help you study for the final which will be on Tuesday, January 23rd. On Monday we will have a review day. To get full credit for participation you will be required to

  1. Ask a question
  2. Help answer a problem either from this list or from the midterm, which we will also be reviewing.

I have also typed up solutions for the midterm. Note however that in some cases there are more than one correct response so if you have something slightly different than what I have written, this does not mean it’s necessarily wrong.

To also help you study here are some Lecture Notes on sets that I typed up (essentially the first lecture).

Homework # 3

The following problems are for HW #3, which is due this Thursday, January 18th.

For the first three problems use \epsilon - \delta to show the following limits are true.

  1. \lim_{x \to 1} 2x - 3 = -1
  2. \lim_{x \to 2} \frac{x^2 - 4}{x-2} = 4
  3. \lim_{x \to a} 3x + 2 = 3a + 2 for all a \in \mathbb R.
  4. Prove for contradiction that the following limit does not exist: \lim_{x \to 0} \frac{1}{x} + x^2.

The rest of the problems are from the textbook.

Chapter 4: 17

Chapter 5: B. 14, 15

Chapter 6: A. 6, 14

EXTRA CREDIT: Following the problem with the last homework, let me be clear that (in this class) 0 counts as a natural number! For extra credit, give an example of a property of natural numbers n that is true for all n > 0 but false for n = 0.

Please let me know if you have any questions.

Homework #2

The following problems are all from Chapter 2 of our textbook. This homework is due on Wednesday, January 10th.

Section 2.2: Problems 1, 2, 3, 4

Section 2.5: Problems 1,2, 3, 10

Section 2.7: Problems 4, 5, 6

Section 2.9: Problems 7, 8, 9

Verify de Morgan’s Second Law using a Truth Table: \neg(p \lor q) \Leftrightarrow (\neg p) \land (\neg q)

Homework #1

The first homework is due on Thursday, January 4th. All exercises are taken from our textbook, The Book of Proof by Richard Hammock.

Chapter 1

Section 1.2: Part A, Number 1 a), c), e)

Section 1.3 Part B, Numbers 9, 10, 11, 12

Section 1.4 Part A, Numbers 7, 8, 9, 10

Section 1.5 Number 4 a), b), c), f), g), h)


Welcome to Math 156 at Hunter College City University of New York. Here is the syllabus for the course, also available as a pdf here: Math 156 Syllabus.

MATH 156.W02 Introduction to Mathematical Proof Workshop, 2 hrs, 1 cr, Winter 2018

Meets: Monday, Tuesday, Wednesday, Thursday, 9:00am-11:05am, Room 604HW

Instructor: Corey Switzer

Office Hours:  Thursdays from 11:30-12:30 in Room 924 HE, other times by appointment

Email: cswitzer[“at” sign]gradcenter[dot]cuny[dot]edu (Please include Math 156 in the subject line)

Textbook: Book of Proof, Second Edition, by Richard Hammack © 2013, Richard Hammack (publisher). ISBN 978-0-9894721-0-4, (313 pages). Download the ebook for free from the author’s website here, and/or purchase the print edition on Amazon or Barnes & Noble for around $15.

Notes: Other notes will be passed out in class and available at the course website here.

Course Learning Outcomes:

  • Construct direct and indirect proofs and proofs by induction and determine the appropriateness of each type in a particular setting. Analyze and critique proofs with respect to logic and correctness, and prove conjectures
  • Learn to construct proofs that are not only mathematically correct but also clearly written, convincing, readable, notationally consistent, and grammatically correct,
  • Apply the logical structure of various proof techniques, proof types, and counterexamples and work symbolically with connectives and quantifiers,
  • Perform set operations on finite and infinite collections of sets and be familiar with properties of set operations and different cardinalities for infinite sets,
  • Work with relations and functions, including surjections, injections, inverses, and bijections, equivalence relations, and equivalence classes,
  • Learn to work with εδ definitions and proofs involving limits at a point for polynomials, rational functions, as well as transcendental functions that do not have a limit at a point,

Course Content to be Covered

Syllabus: As a rough guide, we will cover most Chapters from the following:

  • Chapter 1: Sets
  • Chapter 2: Logic
  • Chapter 4: Direct Proof
  • Chapter 5: Contrapositive Proof
  • Chapter 6: Proof by Contradiction
  • Chapter 7: Proving Non-Conditional Statements
  • Chapter 8: Proofs Involving Sets
  • Chapter 9: Disproof
  • Chapter 10: Mathematical Induction
  • Chapter 11: Relations
  • Chapter 12: Functions
  • Chapter 13: Cardinality of Sets
  • Epsilon-Delta Proofs

General: A typical class will begin with some problems for the previous class to test comprehension. Students will be expected to work with one another on these problems and, on occasion, present solutions. Then, I will introduce topics and examples of proof techniques from the text. It is important to understand what goes on in class each day. This means being present and being prepared for every class, first by reading the textbook and second by making a serious effort to do the homework.

It is encouraged that you work together both on reviewing the material and doing the homework. However, this is not an excuse for copying some one else’s work. Every student is expected to turn in their own, original work.

Last Day to Withdraw with a Grade of W:     1/16/17

Grading/Test Dates:
Class participation (including attendance), 25%; Homework (Due roughly twice a week), 25%; Midterm (Take Home, Due 1/15), 25%; Final Exam (In Class, January 23rd), 25%

Academic Integrity:

Hunter College regards acts of academic dishonesty (e.g., plagiarism, cheating on examinations, obtaining unfair advantage, and falsification of records and official documents) as serious offenses against the values of intellectual honesty. The College is committed to enforcing the CUNY Policy on Academic Integrity and will pursue cases of academic dishonesty according to the Hunter College Academic Integrity Procedures.

Disabilities: If you have a disability that you believe requires special accommodations: In compliance with the American Disability Act of 1990 (ADA) and with Section 504 of the Rehabilitation Act of 1973, Hunter College is committed to ensuring educational parity and accommodations for all students with documented disabilities and/or medical conditions. It is recommended that all students with documented disabilities (Emotional, Medical, Physical and/or Learning) consult the Office of AccessABILITY located in Room E1124 to secure necessary academic accommodations. For further information and assistance please call (212-772-4857)/TTY(212-650-3230).