User nate ackerman - MathOverflow

Answer by Nate Ackerman for Fixed point theorems

2013-04-10T06:12:30Z

Kleene's Second Recursion Theorem If $F$ is a total computable function then there is an index $e$ such that $\{e\} \simeq \{F(e)\}$.

This has many applications such as effective transfinite recursion.

Answer by Nate Ackerman for Fixed point theorems

2013-04-10T06:04:00Z

Knaster-Tarski's fixed point theorem: If $L$ is a complete lattice and $f:L \rightarrow L$ is order preserving, then the set of fixed points of $f$ form a (non-empty) complete lattice.

Answer by Nate Ackerman for Barwise compactness theorem

2013-03-30T01:02:34Z

This is a good question. The issue though is you have made several assumptions on your model $\mathcal{M}$ which cannot all hold simultaneously. To be precise lets enumerate the assumptions you have made:

(1) $\mathcal{M}$ is a model whose underlying set consists of urelements

(2) There is a relation $\lt$ in the language of $\mathcal{M}$ where $(\mathcal{M},<^{\mathcal{M}})$ is isomorphic to $(\omega, \in)$.

(3) There is an admissible set $A$ such that $\mathcal{M} \in A$ and $o(A) = \omega$.

To see that these three things can't all happen simultaneously suppose $A$ is any admissible set containing an $\mathcal{M}$ that satisfies (1) and (2) and let

$\varphi :=(\exists m \in \mathcal{M})(\exists x$ an ordinal $) [m'\in M:m' < m] \cong x$

This is a $\Sigma_1$ formula which holds in $A$ and hence by reflection there is a set $a \in A$ such that

$\varphi^a :=(\exists m \in \mathcal{M})(\exists x\in a$ an ordinal $) [m'\in M:m' < m] \cong x$

which also holds in $A$.

But then by assumption every finite ordinal is in $a$ and so by $\Delta_1$ separation we have $\omega \in A$ and $o(A) > \omega$, thus contradicting (3).

Effect of large cardinals on the value of $\omega_1^L$ in $L$

2012-10-28T05:47:52Z

I have three three questions, the first two of which probably have the same answer and the third of which is more vague.

For a set $A$ let $L_\alpha(A)$ be the constructible universe up to $\alpha$, built from $A$ as a set (and not a predicate). Further let $X = (B, f)$ where $B$ is a transitive set and $f$ is a bijection from $\omega$ to $B$.

Also assume that the background universe has whatever large cardinals you would like (or that would be helpful). In particular though there is at least one inaccessible cardinal in $L$.

(1) Suppose $L_\alpha\models ZFC$. Is it the case that $\omega_1^L = \omega_1^{L_\alpha}$?

(2) Suppose $L_\alpha(X)\models ZFC$. Is it the case that $\omega_1^{L(X)} = \omega_1^{L_\alpha(X)}$?

(3) If the answer to (1), (2) is yes, is there any simpler way for $L_\alpha$ to know that $\omega_1^{L_\alpha} = \omega_1^L$ (other than $L_\alpha\models ZFC$)?

Finally I will just make one observation to highlight why this question isn't trivial. If you replace $ZFC$ with $KP$ then there are many countable admissible sets $L_\alpha\models KP$ with countable (in $L$) ordinals $\beta\in L_\alpha$ such that $L_\alpha \models \omega_1 = \beta$.

Thanks

Answer by Nate Ackerman for Proper class forcing vs forcing with a set of conditions bigger than one's model

2012-10-22T07:53:48Z

To pin down terms lets say "large set forcing" is what you described above where you assume there is an inaccessible $\kappa$, apply a forcing $P$ of size at least $\kappa$ (i.e. a large set forcing) and then look at $V[G]_{\kappa}$ where $G$ is generic for $P$ over $V$.

Lets then call "class forcing" what is done when you force with a carefully defined class as in, for example, the book "Fine Structure and Class Forcing" by Sy D. Friedman.

There are two issues (as I see them) with large set forcing which class forcing attempts to address.

First, in general it is not the case that with a large set forcing $V[G]_\kappa$ will be a model of ZFC. For example, unless you choose your partial order very carefully, there is no reason to believe that in $V[G]$ that $\kappa$ is even inaccessible. Class forcing gets around this issue by adding conditions on the definable forcing to ensure that when all is said and done the result is still a model of ZFC

The second issue is that in large set forcing you are, by assumption, not dealing with all of the sets. Specifically you can't both assume that there is an inaccessible, use that fact to construct a partial order which wouldn't exist without one, and then say "a ha" there really wasn't an inaccessible.

That being said you are right that very often, especial in category theory, people act as if the universe is really just a set and assume they won't get into trouble. And in fact there are good mathematical reasons for why you can do this (if you are interested I would recommend Feferman's "Set-theoretical foundations of category theory").

Very roughly speaking, there are systems equi-consistent with ZFC which have a class/set distinction where the classes aren't just subclasses of the universe of sets (but rather some not specified combination of subclasses, subsubclasses, etc.) These systems are then able to stay equiconsistent with ZFC because their collection of non-set classes is only required to satisfy a minimal amount of separate/replacement (at least with non-set parameters). A good example of a set theory which does this (in addition to Feferman's mentioned above) is Ackermann's set theory.

What helped me internalize why this collection of non-set classes can't be forced to satisfy many of the separation/replacement axioms which we would like, was the realization that Morse-Kelly Set theory, which differs from Godel-Berney's set theory only in that comprehension is allowed to have set variables, has strictly greater consistency strength.

Anyhow, getting back to class forcing. In some sense one of the main things class forcing is really doing is making sense of how one forces when one does not necessarily have the closure properties which are satisfied by sets (but not by classes).

Answer by Nate Ackerman for Higher categorical analogue of concreteness

2012-10-19T02:36:51Z

If you require you category to be actually small (and not just locally small) then the answer is yes.

Suppose $C$ is a small category. We can then define the category $C'$ as follows:

Objects($C'$) = ${ C/t: t \in$ Object(C)$}$
Morphisms($C'$) are functors between the corresponding categories

There is then a functor $F:C \rightarrow C'$ where

$F(t) = C/t$ for any object $t$ of $C$
For any map $\alpha:s \rightarrow t$ in $C$, $F(\alpha):C/s \rightarrow C/t$ is the functor where:
- When $\beta:p \rightarrow s$ is an object of $C/s$ then $F(\alpha)(\beta) = \alpha \circ \beta:p \rightarrow t$ is the corresponding object of $C/t$.
- Suppose $P:p\rightarrow s$ and $Q:q\rightarrow s$ are objects of $C/s$ and $g: P \rightarrow Q$ is a morphism in $C/s$ (i.e. a map $g:p \rightarrow q$ such that $q \circ g = p$).
  
  Then $F(\alpha)(\gamma) = g$ (as a map from $F(\alpha)(P) \rightarrow F(\alpha)(Q)$)

When dealing with locally small (but not necessarily small) categories however you have to be careful about set theoretic size issues.

Answer by Nate Ackerman for Topological spaces determined by generalized metric spaces

2012-08-14T00:08:12Z

This isn't an answer to exactly your question, but it has been proved that all topological spaces come from suitably generalized metric spaces. Specifically in ''All Topologies Come From Generalized Metric Spaces'' by Ralph Kopperman in The American Mathematical Monthly he shows that any topological space can be obtained from a generalized metric space where you weaken the axioms and replace $\mathbb{R}$ by a suitable semi-group with certain properties.

It also was shown in ''Quantales and continuity spaces'' by R. C. Flagg in Algebra Universalis that all topological spaces can be obtained by suitable weakenings of the axioms of a metric space and replacing $\mathbb{R}$ by quantales. This is, to my mind, particularly nice as the resulting generalized objects are essentially just categories enriched in the quantale.

Answer by Nate Ackerman for What are the most attractive Turing undecidable problems in mathematics?

2012-07-28T23:59:15Z

Given a finite relational language with at least one binary relation, the question of which formulas are finitely satisfiable (i.e. realized in at least one finite structure) is $\Sigma^0_1$ but not computably enumerable (by Trakhtenbrot's Theorem)

Answer by Nate Ackerman for Proofs that require fundamentally new ways of thinking

2012-01-02T20:33:34Z

Barwise compactness and $\alpha$-recursion theory. The idea many properties of the following are captured by thinking of how to define analogs in $V_\omega$:

(1) Finite sets are elements of $V_{\omega}$.

(2) Computable sets can are $\Delta_1$ definable over $V_{\omega}$.

(3) Computable enumerable sets can are $\Sigma_1$ definable over $V_{\omega}$.

(4) First order logic is $L_{\infty, \omega} \cap V_\omega$.

Then, if we replace $V_\omega$ by a different countable admissible set $A$, many of the results relating these classes have analogs. E.g. Barwise compactness, completeness, the existence of an $A$-Turing jump, ...

Measure on $\omega_1$

2011-11-17T05:29:30Z

Let $\mathcal{O}$ be the $\sigma$-algebra on $\omega_1$ generated by its countable subsets. Is there a ($\sigma$-additive) probability measure on $\mathcal{O}$ that is not concentrated on a countable set? (I am trying to construct a real random variable whose support has size $\aleph_1$.)

Computable distribution on [0,1] with C-infinity distribution function

2011-01-07T16:02:38Z

Does anyone know of an easily-describable distribution on $[0,1]$ with a density $p$ (with respect to Lebesgue measure) that satisfies the following properties:

$p$ is $C^\infty$
$p(0) = a$, $p(1) = b$ (for fixed real numbers $a$, $b$)
every derivative of $p$ at 0 and 1 is 0
p is computable (informally, we can compute $p$ at any point to arbitrary accuracy)

Comment by Nate Ackerman

2013-01-24T23:24:03Z

What would you write for $|x-y|\geq \epsilon$?

Comment by Nate Ackerman

2012-10-28T13:17:33Z

@ Goldstern: I changed $L_\kappa$ to $L_\alpha$. Thanks

Comment by Nate Ackerman

2012-10-19T00:08:47Z

If you are interested here is a link to the slides of the talk I gave at the joint meetings a couple of years ago [Sheaf Induction](math.harvard.edu/~nate/talks/Berkeley/2009/…) As for the paper, I am in the process of putting the final touches on it and hope to post it soon.

Comment by Nate Ackerman

2012-10-19T00:08:44Z

@O a: Thanks for the clarification. With regards to the connection between sheaves and trees, part of my thesis actually is dedicated to that connection and how one can generalize transfinite recursion to "well-founded" sheaves which aren't trees. While I had to discover the connection by myself, and while I haven't seen it anywhere else, it wouldn't surprise me of someone else had noticed it before me.

Comment by Nate Ackerman

2012-10-15T21:01:00Z

@O a: Also, could you please highlight exactly where your question is in the post. I read through it and couldn't identify it. Thanks.

Comment by Nate Ackerman

2012-10-15T21:00:24Z

But if $F^*$ is the corresponding tree then $|F^*(\omega)| = |2^{\omega}|$

Comment by Nate Ackerman

2012-10-15T21:00:04Z

@O a: I agree with Joel that your definition of a sheaf on $\kappa$ is guaranteed to be a $\kappa$-tree only if $\kappa$ is inaccessible. Further, for non-inaccessible cardinals, if $F$ is the sheaf corresponding to $T$, then it may be the case that $T$ is a $\kappa$-tree but there is some $\alpha < \kappa$ with $|F(\alpha)| \geq \kappa$. For example consider the tree $T^*$ consisting of all maps from $n\rightarrow \{0,1\}$ for $n \in \omega$ along with all constant maps $f_\alpha:\alpha \rightarrow\{0\}$ for $\alpha \leq \omega_1$. $T^*$ is clearly an $\omega_1$ tree.

Comment by Nate Ackerman

2012-10-15T18:52:08Z

3) Generally $\cup X$ means take the union over all element in the set $X$ where as $\cup_{P} X(x)$ means take the union over the set $\{X(x): P(x)$ holds $\}$. So I believe it would be clearer to write $\cup_{\beta < \alpha} F(\beta)$ and not $\cup \beta < \alpha F(\beta)$ And finally to anyone who isn't o a who is reading this. I apologize if it isn't correct etiquette to put so many corrections in the comments, but I don't have enough reputation points to edit the post myself (and I would welcome being told of any other way to pass along the info if there is one)

Comment by Nate Ackerman

2012-10-15T18:44:13Z

(although the correct answer can be inferred from the context we have to read the rest of the sentence to understand what the object is, or even that it is a single object and not two). As an example, writing $\{f_i:\alpha⟶2,i<\kappa\}$ takes care of this issue. 2) I would suggest never writing a quantifier after the thing it is quantified. Specifically I would write $F(j+1)=\{g:(\forall i \leq j)g|\alpha\neq f_i\}$ instead of $F(j+1)=\{g:g|\alpha\neq f_i \forall i \leq j\}$

Comment by Nate Ackerman

2012-10-15T18:35:15Z

Lastly, there are a couple of presentation issues which I think will make the post much cleaner (although obviously these are my personal preference). 1) When defining a sequence it is helpful to have some form of delimiter joining the description of the sequence as well as the conditions on the indexes. Specifically: $f_i:\alpha⟶2,i<\kappa$ it is unclear if you are defining a sequence here, or are defining a unique function with an index $i$ that you are requiring to be less than $\kappa$

Comment by Nate Ackerman

2012-10-15T18:33:09Z

The second reason this proof doesn't work (or is at least incomplete) is that you haven't shown that $\kappa$ is regular. So, for example this proof doesn't show that $\beth_\omega$ doesn't have (WC).

Comment by Nate Ackerman

2012-10-15T18:33:06Z

Third, I don't believe your argument that (WC) implies inaccessibility is correct for two reasons. First you are making fundamental use of the assumption that $\kappa = |2^\alpha|$. However it is possible to have $\kappa$ not be inaccessible and yet for this still not to hold. For example consider the case $|2^{\omega}| = \omega_2$. In this situation $\omega_1$ is not equal to $|2^{\alpha}|$ for any $\alpha$.

Comment by Nate Ackerman

2012-10-15T18:32:39Z

While I am not trying to do self-promoting here you might want to check out my slides [Sheaf Recursion](math.harvard.edu/~nate/talks/Berkeley/2009/…) to see an explanation in the case of $\kappa=\omega$.

Comment by Nate Ackerman

2012-10-15T18:32:29Z

Second, according to your definition $F(1) \subseteq F(\omega \cdot \alpha)$ for any $\alpha$. If $y \in F(1)$ then what is $y|_{\omega, 2}$ (the restriction of $y$ as an element of $F(\omega)$ to an element of $F(2)$? I think what you want to do is use the fact that every $\kappa$-branching tree can be viewed as a subtree of $\kappa^{<\kappa}$ and then use the fact that $\kappa^{<\kappa}$ is a collection of functions to define your sheaf.

Comment by Nate Ackerman

2012-10-15T18:32:12Z

@o a: Thanks for the updated version. It is much clearer what is going on. However I still do have several points. First, your definition of a Grothendieck topology isn't quite right as the covers aren't sieves (see [Grothendieck topology](en.wikipedia.org/wiki/Grothendieck_topology)). What you have is a Grothendieck pretopology. The difference is, approximately, the difference between a topology and a basis for a topology.