User jason - MathOverflow

Answer by Jason for Awfully sophisticated proof for simple facts

2010-12-09T04:54:47Z

Theorem (ZFC + "There exists a supercompact cardinal."): There is no largest cardinal.

Proof: Let $\kappa$ be a supercompact cardinal, and suppose that there were a largest cardinal $\lambda$. Since $\kappa$ is a cardinal, $\lambda \geq \kappa$. By the $\lambda$-supercompactness of $\kappa$, let $j: V \rightarrow M$ be an elementary embedding into an inner model $M$ with critical point $\kappa$ such that $M^{\lambda} \subseteq M$ and $j(\kappa) > \lambda$. By elementarity, $M$ thinks that $j(\lambda) \geq j(\kappa) > \lambda$ is a cardinal. Then since $\lambda$ is the largest cardinal, $j(\lambda)$ must have size $\lambda$ in $V$. But then since $M$ is closed under $\lambda$ sequences, it also thinks that $j(\lambda)$ has size $\lambda$. This contradicts the fact that $M$ thinks that $j(\lambda)$, which is strictly greater than $\lambda$, is a cardinal.

Answer by Jason for Half Cantor-Bernstein Without Choice

2011-05-19T05:59:21Z

To your original question, it seems worth mentioning the point that your hypothesis implies the following:

If $|A| = |A \times 2|$ and there is a surjection from $A$ onto $B$, then $B$ injects into $A$.

This really just generalizes the example given by Ricky, but to see this:

Suppose we have a bijection $b: A \rightarrow A \times \{0, 1\}$ and a surjection $g: A \rightarrow B$. $A$ injects into $A \cup B$ by the inclusion map, and we can get a surjection from $A$ onto $A \cup B$ by mapping an $a \in A$ to itself if the second coordinate of $b(a)$ is $0$ or to $g(a)$ if the second coordinate of $b(a)$ is $1$. In other words, we split $A$ into two copies of itself, mapping the first copy surjectively (bijectively) onto itself via the identity and the second copy surjectively onto $B$ via $g$. By your stated principle, this would then mean that we have a bijection $h$ from $A$ onto $A \cup B$ whereby $h^{-1} \upharpoonright B$ would be an injection from $B$ into $A$.

From this observation, I think it becomes intuitively clear how your principle is a form of choice in disguise. In particular, your principle would imply that $\alpha^+$ injects into $\mathcal{P}(\alpha)$ for every infinite ordinal $\alpha$ since we have a surjection from $\mathcal{P}(\alpha)$ onto $\alpha^+$ (even without choice by virtue of the fact that every ordinal of size $|\alpha|$ is encoded by a subset of $\alpha$). But as I'm sure you're already aware, models of ZF have been constructed where this will not be the case.

Answer by Jason for How much larger is the powerset of a transfinite set?

2011-05-08T06:29:08Z

As Stefan mentions, the Cantor diagonal argument is completely general to larger cardinals. The difference merely is that the indices of your list range over infinite ordinals rather than just the finite ones. However, if I correctly understand the difference you are trying to point out, it's this:

Given a countable list of infinite decimal expansions of Real numbers between 0 and 1, one can easily produce infinitely many such numbers not in this list by the Cantor diagonal argument because when selecting the $n^{th}$ digit, we have $9$ choices that won't match the given digit. On the other hand, for our constructed subset of $\aleph_{\alpha}$, our choice is uniquely determined using the Cantor diagonal argument across the main diagonal, mainly we include a given $\beta < \aleph_{\alpha}$ if and only if it is not in the $\beta^{th}$ subset in our list.

However, as you are probably aware, $2^{\aleph_0}$ represents the cardinality of the set of functions from $\mathbb{N}$ into $\{0, 1\}$ or the number of subsets of $\mathbb{N}$ by viewing the binary functions as characteristic functions determining membership (i.e., $n \in S_f \Leftrightarrow f(n) = 1$). The fact that $10^{\aleph_0}$ (cardinality of set of functions from $\aleph_0$ into $\{0, 1, \ldots, 9\}$) can be put into one to one correspondence with $2^{\aleph_0}$ is not unique to $\aleph_0$. Specifically, $10^{\aleph_{\alpha}}$ can be put in one-to-one correspondence with $2^{\aleph_{\alpha}}$ for any $\aleph_{\alpha}$, and this goes along the lines of what Nate was saying about certain operations not affecting cardinality. In fact, since $2^{\aleph_{\alpha}} = (2^{\aleph_{\alpha}})^{\aleph_{\alpha}}$, we actually have $2^{\aleph_{\alpha}}$ many choices for $f(\beta)$ for each $\beta < \aleph_{\alpha}$ using the Cantor diagonal argument when constructing our $f$. Therefore, if anything, the Cantor diagonal argument shows even wider gaps between $\aleph_{\alpha}$ and $2^{\aleph_{\alpha}}$ for increasingly large $\alpha$ when viewed in this light.

A way to emphasize how much larger $2^{\aleph_0}$ is than $\aleph_0$ is without appealing to set operations or ordinals is to ask your students which they think is larger:

(a) The number of possible books that can be written in any language

(b) The number of Real numbers between $1/10^{1001}$ and $1/10^{1000}$

The first answer would of course be only countably many since there are countably (or finitely) many possible alphabet symbols, and each book has only finitely many characters. You can then ask variations of (a) by making it sound larger. For example, you can ask what would happen if there were actually countably infinite many possible languages. At a more advanced level, you could replace (b) with the nowhere dense Cantor set.

The rest of this answer is most likely not suitable below the college level, but I'll mention it anyway just in case:

If you are extremely ambitious (going along the large countable ordinal route that Todd mentions), you could consider various reflection/Löwenheim-Skolem arguments. For example, for any fixed finite fragment of the theory of ZFC, ZFC proves that we have a countable transitive model $M$ of this fragment of set theory. In this case, $2^{\aleph_0} > \aleph_0 = |M|$, but assuming we chose a sufficiently large finite fragment, $M$ will contain a fairly rich array of definable countable ordinals. You can then point out that such a model will have all of the "natural" functions $f: \mathbb{N} \rightarrow \mathbb{N}$ so it will still know that ordinals such as $\epsilon_0$ are countable. But $M$ has many ordinals beyond what it can put into one to one correspondence with $\aleph_0$, mainly all of the actual countable ordinals that it thinks are uncountable. Similarly, there will be many ordinals that $M$ can put into one-to-one correspondence with $\aleph_{\alpha}^M$ for every ordinal $\alpha \in M$. But again, all of these ordinals are actually countable.

Answer by Jason for some arguments concerning forcing over V

2011-05-01T08:39:32Z

No, if $A$ holds in a forcing extension $V[G]$, it need not be forced by $1$ in general. But this is not what is done. Instead, the argument can proceed as follows: In order to show that $1$ forces a statement to be true, we may show it is true in all forcing extensions. Consider an arbitrary forcing extension $V[G]$. If $V[G] \nvDash A$, then $V[G] \models A \rightarrow B$. Consequently, it suffices to restrict our attention to forcing extensions $V[G]$ for which $A$ is true and then show that $B$ will also be true in $V[G]$.
I'm still not sure which part of the proof you find problematic, but let me try to break it down step by step.

First note that $\lnot A \vee B$ is tautologically equivalent to $A \rightarrow B$ so: $1 \Vdash A \rightarrow B$ $\Leftrightarrow$ $1 \Vdash \lnot A \vee B$. Specifically, $A \rightarrow B$ will be true in every forcing extension if and only if $\lnot A \vee B$ is true in every forcing extension.

But to show $1 \Vdash \lnot A \vee B$, it is sufficient to show that the set $D$ of conditions from $P$ forcing $\lnot A \vee B$ is dense in $P$. This is because if $G$ is a $V$-generic filter for $P$, then it must meet every dense set. Consequently, if $D$ is dense, then there will be a condition $p$ in $G \cap D$. In this case, $p \in G$ and $p \Vdash \lnot A \lor B$ so $V[G] \models \lnot A \lor B$, or equivalently, $V[G] \models A \rightarrow B$.

Fix a $q$ in $P$. If any $p \lt q$ forces $\lnot A$, then it will also force $\lnot A \lor B$ because $\lnot A \vee B$ is a tautological consequence of $\lnot A$. Specifically, if every forcing extension $V[G]$ such that $p \in G$ models $\lnot A$, then every such extension will also model $\lnot A \vee B$.

We may therefore assume that all $p \lt q$ do not force $\lnot A$ so that $q \Vdash A$. Notice that if $q$ did not force $A$, then we'd have $V[G] \models \lnot A$ for some $G$ where $q \in G$. In this case, we would have some condition $r \in G$ forcing $\lnot A$. Now notice that if $r \Vdash \lnot A$ and $s < r$, then also $s \Vdash \lnot A$ since every filter containing $s$ will contain $r$ by the upward closure of filters. But also if $q \in G$ and $r \in G$, then we may find such a condition $s$ in $G$ below both $q$ and $r$ by virtue of $G$ being a filter. This $s$ will then be below $q$ and will force $\lnot A$ by virtue of being less than $r$, contrary to assumption.

It therefore suffices to show that we have a condition $p$ below $q$ forcing $B$. If we let $q \in G$, and $V[G] \models B$, then we will have a condition $r \Vdash B$ such that $r \in G$. As in 4., we may then find an $s \in G$ below $q$ that forces $B$ (and hence also $\lnot A \lor B$), and so we are done.

As a technical point, it is implicitly assumed throughout this argument that there is no minimal condition in $P$. Otherwise, replace $\lt$ with $\leq$.

Answer by Jason for Normal measures on $P_{\kappa }(\lambda )$ extend the club filter

2011-04-08T22:47:56Z

Suppose $\kappa$ is $\lambda$-supercompact for some $\lambda \geq \kappa$, and let $j: V \rightarrow M$ be an elementary embedding with critical point $\kappa$ such that $j(\kappa) > \lambda$ and $M^{\lambda} \subseteq M$ for some inner model $M$. First, observe that $V$ and $M$ agree on $P_{\kappa}\lambda$ because $M$ is closed under ${<}\kappa$ sequences. In particular, this means that $\lambda^{{<}\kappa} \leq (\lambda^{{<}\kappa})^M$ since $M \subseteq V$. But this then means that $j(\kappa) > (\lambda^{{<}\kappa})^M \geq \lambda^{{<}\kappa}$ because $j(\kappa)$ is inaccessible in $M$ and $j(\kappa)$ is greater than both $\lambda$ and $\kappa$. Next, note that any $x \in P_{\kappa}\lambda$ will be a subset of $\lambda$ having size less than the critical point $\kappa$ so that $j(x) = j''x \subseteq j''\lambda$.

[Specifically, if for some $\alpha < \kappa$, we have a bijection $f: \alpha \rightarrow x$, then $j(f)$ will be a bijection between $j(\alpha) = \alpha$ and $j(x)$. So every element of $j(x)$ is of the form $j(f)(\beta)$ for some $\beta < \alpha$, but $j(f)(\beta) = j(f(\beta)) \in j''x$ since $\beta$ is also below the critical point.]

Also, $M$ will contain $h = j \upharpoonright \lambda$ by its closure under $\lambda$ sequences. Therefore, $M$ will have $j''P_{\kappa}\lambda = \{j(x)| x \in P_{\kappa}\lambda\} = \{j''x| x \in P_{\kappa}\lambda\} = \{h''x| x \in P_{\kappa}\lambda\}$. Now letting $g: P_{\kappa}\lambda \rightarrow \lambda^{{<}\kappa}$ be a bijection in $V$, we will have a bijection $j(g) \upharpoonright j''P_{\kappa}\lambda: j''P_{\kappa}\lambda \rightarrow j''\lambda^{{<}\kappa}$ in $M$. Therefore, $M$ will have the range of $j(g)$, which is exactly $j''\lambda^{{<}\kappa}$. Now, since $C$ has size at most $\lambda^{{<}\kappa}$ (in $V$), we may let $e: \lambda^{{<}\kappa} \rightarrow C$ be a surjection. Then $j(e) \upharpoonright j''\lambda^{{<}\kappa}: j''\lambda^{{<}\kappa} \rightarrow j''C$ is a surjection in $M$ so similarly, its range, $D = j''C$, will be in $M$. But $M$ will also know that $j''\lambda^{{<}\kappa}$ has size $\lambda^{{<}\kappa} < j(\kappa)$ because $M$ can construct $j \upharpoonright \lambda^{{<}\kappa}$ from $j''\lambda^{{<}\kappa}$ by virtue of $j$ being order-preserving. Therefore $\bigcup D \in j(C)$ by the ${<}j(\kappa)$-directed closure of $j(C)$ in $M$, as you mention.

Also, if $x \in C$, then $|x| < \kappa$ and $x \subseteq \lambda$ so $j(x) = j''x \subseteq j''\lambda$. Therefore, $\bigcup D = \bigcup j''C \subseteq j''\lambda$.

Answer by Jason for Is modern computability theory "really" about algorithms?

2011-04-07T02:03:28Z

A somewhat analogous question can be asked about large cardinals. Specifically, why should we study large cardinals when (a) ZFC cannot prove their consistency and (b) we don't generally appeal to the existence of such large infinities when working in the rest of mathematics. However, when Vitali shows that (when assuming choice) we cannot extend the Lebesgue measure to a countably additive translation-invariant measure that measures all subsets of the Real numbers, it is natural to ask for a weakening of this property. Specifically, can we extend the Lebesgue measure in such a way if we remove the translation-invariance condition? But upon the exploration of this question, we begin to reveal this beautiful large cardinal hierarchy that provides insight on the structure of our universe of set theory. The large cardinal hierarchy then becomes an abstract object to study in its own right.

Similarly, after Church and Turing prove the existence of noncomputable sets building on the work of Gödel, one may be inclined to ask about relative computability. What if I had access to the membership in that halting set; what functions wouldn't be computable then? Alternatively, one may ask, as Post did, whether it is possible to have access to an "intermediate" noncomputable set $A$ that does not make the halting set relatively computable using $A$ as an oracle. Questions such as these help prompt the beginnings of the study of Turing degrees, and the pursuit of their answers lead to a better understanding of the arithmetical hierarchy, as you mention. This helps to make the study of computability theory self-perpetuating: not only is it of intrinsic interest, but it also helps us better understand ideas from related fields using different approaches. For a more specific example, at the very low level of the Turing degree lattice, the question of whether a function is computable has produced unifying theories of randomness, e.g., Kolmogorov Complexity and Martin-Löf randomness tests.

But let me conclude by mentioning that questions regarding oracle-assisted computations are not necessarily hypothetical. There have been theoretical physical models proposed for supertask computations that would allow us to prove all theorems of arithmetic or solve the halting problem.

Answer by Jason for Unwritten Rule Of Writing Own Name

2011-03-31T00:32:05Z

I would avoid referring to your theorems by your own name unless they have become completely standardized as such. This is especially true when you submit a paper establishing a supposed new result since it will likely be considered presumptuous to assume that no one has already proven something similar. However, it would be awkward not to refer to your name in a theorem if it has become standard terminology. For instance, when Woodin proves results about Woodin cardinals, what else would he call them? To answer your second question then, I'd say you should do so when it is pretty much unavoidable not to.

On the other hand, it is perfectly acceptable to cite your own work, and you should certainly do this. When doing so however, I would avoid referring to yourself if possible. Generally, you can do this by saying "as shown in [n]" where n is the (alpha)-number for the article in your list of references.

As for referring to others' work, I think it is generally considered a compliment to name a property or a theorem after the person who introduced it. However, you need to do your homework first on this, making sure you attribute correctly. Also, you certainly can say "Name introduced such and such a concept in [citation number]," and this happens very often.

Answer by Jason for Mathematics seminar for "non-mathematicians"

2011-03-26T00:03:58Z

I highly recommend teaching arithmetic in different bases and base conversion because it aids in the conceptual understanding of our ordinary base ten arithmetic and representations of numbers. If these students are going to become elementary school teachers, they're primarily going to be teaching kids how to add, subtract, multiply, and divide so it is really important for them to have a firm grasp on why these procedures actually work.

For a related "magic" trick, you can ask them why the telephone number trick works.

In general, a variety of discrete math topics including propositional logic and basic number theory would also seem suitable.

Answer by Jason for Proofs of Gödel's theorem

2011-03-21T23:50:14Z

For Goedel's first incompleteness theorem, you can appeal to the existence of any computably (recursively) enumerable set $A$ that's not computable (recursive). Specifically, suppose $T$ is an $\omega$-consistent, computable theory powerful enough to represent all computable functions. Let $f$ be a total computable function listing all Natural numbers in $A$, and let $F$ represent $f$ in the theory $T$. Then there must exist $n \in \mathbb{N}$ for which:

(1) $T \nvdash \exists m F(m, n)$ nor (2) $T \nvdash \lnot\exists m F(m, n)$

Otherwise we could determine whether or not any given $n$ is in $A$ by effectively listing all theorems of $T$ until we received one of these statements, contradicting the fact that $A$ is not computable. Specifically, (1) would tell us that $n \in A$ by the $\omega$-consistency of $T$ (i.e., there exists a true Natural number $m$ so $f(m) = n$) while (2) would tell us that $n \notin A$ because it is never listed by $f$.

If I recall correctly, a proof along these lines is mentioned in An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi.

Impact of discrepancy between Kunen's and Jech's definition of iterated forcing on full support iterations

2011-02-14T06:07:15Z

One of the first things we usually learn when we study iterated forcing is that we can force over a model of ZFC + GCH to make the continuum function ($\lambda \mapsto 2^{\lambda}$) restricted to some set $S$ of regular cardinals follow any nondecreasing pattern satisfying König's Theorem ($\text{cof}(2^{\lambda}) > \lambda$). This is accomplished by an Easton product of adding the desired number of Cohen subsets to each cardinal in $S$. For example, assuming that the GCH holds in $V$, we can force $2^{\aleph_n} = \aleph_{n+2}$ for all Natural numbers $n$ with the full support $\omega$-iteration where we force with the ground model poset adding $\aleph_{n+2}$ many Cohen subsets of $\aleph_n$ at every stage $n$.

However, if we instead force with the posets adding $\aleph_{n+2}$ Cohen subsets of $\aleph_n$ from the successive extensions, then the iteration will preserve the GCH. Such a phenomenon is easily explained away by the fact that after forcing to add Cohen subsets of $\aleph_n$, we have necessarily changed the definition of the forcing adding Cohen subsets of $\aleph_{n+1}$ in the extension.

Now consider a full support $\omega$-iteration $\mathbb{P}$ where at every stage $n$, we force to add a Cohen real. Since the poset adding a Cohen real is the set of finite partial binary sequences with domain $\omega$, all transitive models of ZFC agree on its definition. Therefore, the aforementioned concern disappears in this context. Because the forcing to add a Cohen real satisfies the countable chain condition (c.c.c.), it is proper. Then since proper forcing is closed under countable support iterations using Jech's definition of a forcing iteration, $\mathbb{P}$ will be proper and hence $\omega_1$-preserving. However, using Kunen's definition, the iteration can collapse $\omega_1$. For example, from Chapter VIII, Exercise (E4):

Let $\mathbb{P}_{\omega}$ be defined by countable supports, and let each $\pi_n$ be $(\text{Fn}(\omega, 2)){}^{\check{}}$). Show that $\mathbb{P}_{\omega}$ collapses $\omega_1$.

Kunen then notes that this problem goes away when full names are used. On the other hand, Jech seems to circumvent the problem altogether by defining $\mathbb{P}_n * \dot{\mathbb{Q}}_n$ to be the set of pairs $\langle p, \dot{q}\rangle \in \mathbb{P} \times \text{dom}(\dot{\mathbb{Q}}_n)$ such that all conditions from $\mathbb{P}_n$ force $\dot{q}$ to be in $\dot{\mathbb{Q}}_n$ rather than just requiring that the condition $p$ forces this as Kunen does.

What I would like to see then is an elaboration of the explanation of why these forcing iterations are different including the intuition behind these differences. Specifically, my question is as follows:

Why does the full support $\omega$-iteration forcing with $(\text{Fn}(\omega, 2)){}^{\check{}}$ (forcing to add a Cohen real) at every stage collapse $\omega_1$ under Kunen's definition but not under Jech's? For example, how is it that every binary $\omega$-sequence from the ground model is coded in the generic filter using Kunen's definition but not Jech's?

As a side request related to how this question came up, can you provide an example of a full support $\omega$-iteration that must have size at least $\aleph_2$, but each individual stage of forcing is necessarily proper and of size at most $\aleph_1$?

Answer by Jason for Restricted Versions of Hechler Forcing

2011-03-09T08:51:53Z

In case you aren't already aware of this, Jech uses a slightly different poset for Hechler forcing. Specifically, he fixes a family $\mathcal{F} \subseteq \omega^{\omega}$ and lets conditions be of the form $(s, E)$ where $s$ is a finite sequence of Natural numbers and $E$ is a finite subset of $\mathcal{F}$. The conditions are ordered by $(t, F) \leq (s, E)$ exactly when $t$ is an end extension of $s$ and $F \supseteq E$ such that $t(n) > e(n)$ whenever $e \in E$ and $n \in \text{dom}(t) \setminus \text{dom}(s)$ (Jech might have defined it a little differently, not sure). Of course, if we define$\;$$f_E: \omega \rightarrow \omega$ by:

$f_E(n) = \sup\{e(n) \mid e \in E\}$

then the map sending $(s, E)$ to $(s, f_E)$ should bear witness to the forcing equivalence of Jech's characterization of Hechler forcing for $\mathcal{F}$ and your proposed $\mathbb{D}(\mathcal{F})$ when $\mathcal{F}$ is closed under finite suprema.

Now to question (1), you already observed that if you have a function dominating all members of $\mathcal{F}$, then $\mathbb{D}(\mathcal{F})$ cannot add an (eventually) dominating real because for any $n$, it is dense that we stay at or below the dominating function at some later value. When $\mathcal{F}$ is countable, we can easily find such a function by diagonalizing against all of its members. When MA is true, the existence of such a dominating function is extended to families of any size less than $2^{\omega}$. Therefore, as an easy observation for ensuring that $\mathbb{D}(\mathcal{F})$ adds a dominating real, $\mathcal{F}$ must have size at least $\omega_1$ in all cases, and we cannot hope to make any nontrivial blanket characterizations about bounding $\mathcal{F}$'s maximum necessary size in general. Jech actually assumes that $\mathcal{F}$ has size less than $2^{\omega}$ so that he can make the ZFC + MA theorem that the ground model already has a real dominating all functions in $\mathcal{F}$.

Answer by Jason for Kunen's use of Countable Transitive Models

2011-03-03T20:36:24Z

Here are some examples that might help in understanding. If ZFC is consistent, then it follows we have a set model $M$ of the theory. Consider a nonprincipal ultrafilter $U$ on $\omega$ and let $M^{\omega}/U$ be the induced ultrapower. $M^{\omega}/U$ is a model of ZFC, but it cannot be well-founded because its $\omega$ has nonstandard elements. Specifically, for any strictly increasing function $g: \mathbb{N} \rightarrow \mathbb{N}$ and $n \in \mathbb{N}$, we have $M^{\omega}/U \models \omega > (g)_{U} > n$ where the $\omega$ here is of course the nonstandard one.

Also, if you don't want to work with ultrapowers directly, you can simply appeal to the Compactness theorem. Introduce a set of constants $\{c_n| n \in \mathbb{N}\}$ into your language and for each $n \in \mathbb{N}$, define $\varphi_n := c_0 \ni c_1 \ni \ldots \ni c_n$. If ZFC is consistent, then every finite fragment of $ZFC + \{\varphi_n| n \in \mathbb{N}\}$ is consistent so the entire theory is by the Compactness theorem. This then gives us a model $N$ of ZFC that externally can be seen to have an infinite descending chain:

$c_0 \quad \ni_N \quad c_1 \quad \ni_N \quad c_2 \quad \ni_N \quad \ldots \quad \ni_N \quad c_n \ldots$.

Note this is not an actual infinite $\in$-descending chain as Stefan points out, but merely a binary relation on the set $N$. For example, if $N = M^{\omega}/U$ is the ultrapower induced by a nonprincipal ultrafilter $U$ on $\omega$, then $\in_N$ would be defined by $(g)_U \quad\in_N\quad(h)_U$ exactly when $\{n \in \mathbb{N}| g(n) \in h(n)\} \in U$.

Answer by Jason for Consistent hierarchy of axiomatic systems

2011-02-24T01:47:26Z

There is a generalization of the compactness theorem to infinitary logics that sounds somewhat close to what you want. Specifically, the compactness theorem tells us that every finitely satisfiable theory of the usual formulas from a first-order language $L$ is satisfiable. For any uncountable cardinal $\kappa$, we can extend $L = L_{\omega, \omega}$ to the infinitary language $L_{\kappa, \kappa}$ by closing the usual formulas under $\bigwedge_{\xi < \lambda}\varphi_{\xi}$, $\bigvee_{\xi < \lambda}\varphi_{\xi}$, $\exists \langle x_{\xi}| \xi < \lambda\rangle$, and $\forall \langle x_{\xi}| \xi < \lambda\rangle$ for all $\lambda < \kappa$. We then define $\kappa$ to be strongly compact if an analogous theorem holds for arbitrary $L_{\kappa, \kappa}$, mainly that if every collection of fewer than $\kappa$ many statements from a theory in $L_{\kappa, \kappa}$ is satisfiable, then the theory is satisfiable.

Now let me emphasize that while ZF + AD may sound natural, it does much much more than prove the consistency of ZF. In fact, ZF + AD proves the consistency of ZFC + "There exists a Woodin cardinal", and Woodin cardinals are quite high up in the large cardinal hierarchy (i.e., a sufficiently stronger theory than ZF that is more likely to be inconsistent than ZF alone). Also, since set theorists tend to like having choice, the usual assumption is not that AD holds in our universe. Instead, we assume that it holds in the minimal transitive ZF model containing all of the ordinals and all of the reals, i.e., $L(\mathbb{R})$.

Now from ZFC + "There exists a strongly compact cardinal", we can prove that ZF + AD holds in $L(\mathbb{R})$. Moreover, we can prove that for every $\alpha$, there exists $\beta > \alpha$ such that AD holds in the set $L_{\beta}(\mathbb{R})$. In particular, ZFC + "There exists a strongly compact cardinal" proves CON(ZF + AD), CON(ZF + AD + CON(ZF + AD)), CON(ZF + AD + CON(ZF + AD + CON(ZF + AD))), etc.

The above result illustrates how assuming a strongly compact cardinal is also a very strong large cardinal hypothesis, but it is only one (admittedly significant) jump higher in our large cardinal hierarchy.

Answer by Jason for Sum of three bijections

2011-02-24T00:12:52Z

One key observation is that with $3$ functions, we are free to have one of them assume any rational value at any Natural number. This is not possible when we only have $2$ functions where after we select the value for $q_1(n)$, we have $q_2(n)$ completely determined by $f(n) - q_1(n)$ and visa versa. The other key observation is that we can split $\mathbb{N}$ into the $3$ disjoint infinite subsets $A_1, A_2, A_3$ with each subset consisting of the set of indices where we make the $q_i$ assume the "next" rational value it has not already assumed according to some bijective enumeration. Specifically:

Fix an arbitrary function $f: \mathbb{N} \rightarrow \mathbb{Q}$ and an arbitrary bijection $e: \mathbb{N} \rightarrow \mathbb{Q}$. The function $e$ induces a well-order, $<_e$ on the set of rational numbers defined by $r\text{ }<_e\text{ }s$ exactly when $e^{-1}(r) < e^{-1}(s)$ (i.e., $r$ is listed before $s$). It also induces a well-order $<_e^*$ on pairs of rationals defined by $\langle r, s\rangle <_e^* \langle t, u\rangle$ exactly when $r\text{ }<_e\text{ }t$ or both $r = t$ and $s\text{ }<_e\text{ }u$ (so-called lexicographical ordering).

We can then define each of the $q_i$ by induction as follows:

If $n \equiv i \pmod 3$, define $q_i(n)$ to be the $<_e$-least rational value not already assumed by $q_i(m)$ for $m < n$.

Then for the $j$ and $k$ such that $n \not\equiv j \pmod 3$ and $n \not\equiv k \pmod 3$, let $\langle r_j, r_k\rangle$ be the $<_e^*$-least pair such that $r_j$ was not assumed by any of the $q_j(m)$ and $r_k$ was not assumed by any of the $q_k(m)$ for $m < n$ and $r_j + r_k = f(n) - q_i(n)$. Note that there is such a pair since there are infinitely many pairs $\langle r_j, r_k\rangle$ satisfying the equality and only finitely many pairs excluded from consideration. Then define $q_j(n) = r_j$ and $q_k(n) = r_k$.

Answer by Jason for Are there uncountably many essentially inequivalent versions of Mathematics?

2011-02-17T10:30:00Z

Main Question:

(1) Yes, let $A_j: 2^{\aleph_j} \neq \aleph_{j+1}$ (i.e., GCH does not hold at $\aleph_j$). We can do this by simultaneously forcing (via a countable product of posets adding Cohen subsets) $2^{\aleph_j} = \aleph_{j+1+s_j}$ where $s_j$ represents the truth value at $j$.

Edited Additions: You can also let $A_j$ be the statement "$\aleph_{j}^{L}$ is a cardinal (in $V$)" (i.e., the $j^{th}$ uncountable cardinal of the constructible universe is a cardinal in the actual universe). In this case, you could simultaneously force over $L$ (via a countable product of posets from $L$ collapsing cardinals) to add a surjection from $\aleph_{j-1}^L$ to $\aleph_{j}^L$ exactly when $s_j = 0$ so that the cardinal $\aleph_{j}^L$ becomes an ordinary ordinal of size $|\aleph_{j-1}^L|$ in the forcing extension. In the case that all of the $s_j$'s are $0$, the first $\aleph_0$ many cardinals of $L$ all become countable ordinals from the perspective of the forcing extension whereas if they're all $1$'s, then we have done trivial forcing and so the forcing extension is $L$.

Now after showing the desired relative consistency results as above, you can note (for your If so part) that you are only considering countable ordinals here from the perspective of most universes. For example, if a certain type of Real exists in your universe, mainly $0^{\sharp}$, then the true $\aleph_1$ will be inaccessible in $L$ and more so all of the $\aleph_j^L$'s for $j \in \mathbb{N}$ will be very puny countable ordinals in the said universe. Of course, this is probably cheating, but I thought I'd mention it anyway.

Also to your subquestion, $2^{\aleph_0} = \aleph_1$ and $2^{\aleph_0} = \aleph_2$ are very meaningful distinctions. But also under ZFC, $2^{\aleph_0}$ needs to be quite large in order to extend the Lebesgue measure to a countably additive measure on the full powerset of $\mathbb{R}$.

François already gave a very nice general answer to your main question so I think I'll leave my answer at that.

Answer by Jason for Intended interpretations of set theories

2011-02-14T09:41:58Z

If you assume that ZFC is consistent, then it follows from Gödel's completeness theorem that there is a set model of ZFC. You can then argue from a Platonistic point of view by taking the viewpoint of that set model. Note that Kunen also proves relative consistency results by moving to models that are not sets with respect to the viewpoint of your model. For example, he proves the relative consistency of the GCH with ZFC by moving to the inner model L. The reason he talks about fragments of ZFC for relative consistency results obtained via forcing is because CON(ZFC) does not guarantee the existence of a countable transitive model of ZFC.

Edit: Let me now put forth a more complete answer tying together philosophical and mathematical considerations. A strict finitist doesn't believe in the existence of the set of Natural numbers but that in itself does not prevent the individual from talking about properties shared by all of its elements. Even if you don't believe that it is a static collection of elements that can be put together into a single set, you can still syntactically prove theorems about Natural numbers (as discussed in more detail by Carl with reference to ZFC). But since $\mathbb{N}$ does not exist in this platonistic frame of thinking, your intuitive objection about quantifying over all well-founded sets is analogous to this problem where we try to quantify over all Natural numbers. Ultimately, some finitists will adopt a compromise where they accept the existence of infinite sets but only ones that can be constructed from the Natural numbers in a finitistic manner (e.g., expressible in a relatively weak theory such as primitive recursive arithmetic or PRA). A somewhat analogous resolution to your philosophical objection is to allow for the existence of definable classes as Kunen does by considering them as "abbreviations for expressions not involving them" or to treat classes as separate formal objects in a conservative extension of ZFC such as NBG. Of course, if you assume the existence of an inaccessible cardinal $\kappa$, then you have a nice set model of NBG, mainly the collection of $\Delta_0$-definable subsets of $V_{\kappa}$.

You can also take a semantic point of view but with a syntactic twist. Specifically, you can pretend that you live in a model of ZFC, but you don't know which one. You therefore can assert the existence of sets provable from the axioms of ZFC while acknowledging that there are sets out of reach. Similarly, you can assert ZFC-provable properties of all of the sets in your unspecified universe while realizing that you are unaware of the boolean truth value of statements independent of ZFC. This line of thinking is indeed present with boolean-valued models of ZFC where you talk about the probabilities of certain statements being true or certain sets given by names coming to fruition in forcing extensions.

Finally, you can throw yourself in a constructed set model $M$ guaranteed by ZFC's believed consistency and restrict to some subclass of $M$. Specifically, you can externally take a sufficient cut of its universe $V_{\alpha}^M$ (which may be all of $M$) as you alluded to or restrict yourself to its parameter-free definable sets if it happens to be a model of $V = OD$ as François mentions to get a model of ZFC. However, in both cases, you will potentially be sacrificing some of the richness exhibited by the universe $M$.

Answer by Jason for A question about imaginary Turing machines.

2011-02-09T23:35:08Z

The Turing Machine you describe here can actually be constructed (from a practical standpoint also), but it would be tedious and not of much practical use.

First note that the finite set of symbols $\{ \in, \forall, \exists, x, \prime, \land, \lor, \lnot, \rightarrow, \leftrightarrow \}$ would be more than sufficient to represent all statements expressible in the language of set theory (prime used to differentiate the countably infinite set of variables: $x, x^{\prime}, x^{\prime\prime},\ldots$). We can have the scrap work occur to the left of the place where we list out all of our ZFC theorems. The (highly inefficient) process can be described as follows:

(1) Copy the tape counter, which can represent $n$ by $n$ successive primes written from right to left.

(2) Run a Turing Machine that on an input of $n$ primes, writes the first $n$ ZFC axioms (separated by spaces only working left on the tape) according to some recursive (computable) numbering.

(3) Run a Turing Machine that on an input of $n$ formulas, applies the first $n$ rules of inference in first-order logic (in the sense that there are an infinite number of substitution rules, each applying a specific change of variable) on each of the formulas already on the working part of the tape and writes them all to the left.

(4) Iterate through each formula on the left, determining whether it's the same as one already in your actual list or a negation of one. If not, add the formula to your list. If it's a negation of one, add the formula, reset your pointer to the beginning of the actual list, and HALT.

(5) Add a prime to the original counter, reset the pointer to the beginning of the prime list, and go to step (1).

In a nutshell, this procedure at every stage $n$, lists all ZFC theorems provable in $n$ steps (not already listed) by limiting oneself to the first $n$ rules of inference and the first $n$ axioms according to some recursive (computable) enumeration. Note that the the number of states required for such a Turing Machine is sensitive to ZFC only in the listing of the axioms (i.e., the number of states for the Turing machine carrying out step (2)).

The problem with such a Turing machine is that it exhibits no effective intelligence in its procedure. Its running time for producing theorems would be exponential as a function of the length of their shortest proofs and emulating it in a programming language such as C++ would not change this fact. Even if there were an obvious contradiction in ZFC with a proof requiring $1000$ lines (considering all of the formal manipulations, this isn't very long), it would most likely take somewhere on the order of $2^{1000}$ years to find. Therefore, the issue is not with the size of the Turing machine, but its running time. Indeed, there is an ongoing research program in automated theorem proving to only choose "smart" paths of deduction rather than mindlessly trying them all.

Finally let me address an issue with the number of symbols and coding. Anything that can be done with a Turing machine having a countable alphabet can be carried out by a Turing Machine having a binary alphabet (with a likely introduction of new states) under suitable coding. This is because there are only finitely many states and hence finitely many possible transitions. Specifically, given a finite collection of subsets $\{S_1, \ldots, S_n\}$ of a countable alphabet of symbols representing the possible transitions from one state to another, we can assign each symbol a Natural number so that each of the $S_n$ are finite unions of recursive sets (assigning first the $n$-intersection to a computable infinite coinfinite set of Natural numbers; then doing the same for each of the $(n-1)$-intersections with the remaining unassigned symbols and Natural numbers, down to the individual $S_i$) and hence recursive.

Also, with coding, your question admits an annoying answer. This is similar to a question I asked in Asymptotic density of provable statements in ZFC.

Specifically, if ZFC is inconsistent, then a Turing machine printing two contradictory statements and then halting would get the job done. Otherwise, we can bijectively associate the set of Natural numbers with the set of all binary strings. By taking any computable infinite and coinfinite subset $A$ of the Natural numbers, we can code the statements in the language of set theory so that the ZFC theorems are precisely the Natural numbers (binary strings) from $A$. This means that a Turing Machine could require an arbitrarily large number of states if $A$ is suitably complex or very few if $A$ were something simple.

Answer by Jason for Singular Cardinals, and A Strange Question.

2011-02-07T02:59:24Z

Theorem If $0^{\sharp}$ does not exist and $\lambda$ is a singular cardinal, then any forcing adding subsets to $\lambda$ necessarily adds subsets to a cardinal below $\lambda$.

Proof: Let $\mathbb{P}$ be a partial order in the ground model and $G \subseteq \mathbb{P}$ be $V$-generic. Without loss of generality, we may assume that $\mathbb{P}$ is a partial order on a cardinal so that its elements are all ordinals. Also let $\vec{s} = \langle s_{\alpha}| \alpha < \text{cof}(\lambda)\rangle$ be a cofinal sequence in $\lambda$ in the ground model and $\dot{A}$ a $\mathbb{P}$-name for a subset of $\lambda$ in $V[G]$. Now suppose that $V$ and $V[G]$ agree on the bounded subsets of $\lambda$. Then for all $\alpha$, we have $a_{\alpha} = s_{\alpha} \cap \dot{A}_G \in \mathcal{P}(\lambda)^{V}$ so for every $\alpha < \text{cof}(\lambda)$, there will be:

$p_{\alpha} \in G$ such that $p_{\alpha} \Vdash \dot{A} \cap \check{s_{\alpha}} = \check{a_{\alpha}}$

Because $V$ is a definable class in $V[G]$, the forcing relation for $V$ is definable in $V[G]$, and we may therefore choose such a $\text{cof}(\lambda)$-sequence of conditions $p_{\alpha}$ below a condition forcing that $\dot{A}$ is a name for a subset of $\lambda$. Let $S_A = \{p_{\alpha}| \alpha < \text{cof}(\lambda)\} \in V[G]$ be such a set of ordinals. Now $S_A$ is a set of ordinals having size $\text{cof}(\lambda)$ in $V[G]$ so by the nonexistence of $0^{\sharp}$, it follows from Jensen's covering lemma that there is a constructible set $C$ of size $\theta = \max\{\omega_1, \textrm{cof}(\lambda)\}$ in $V[G]$ covering $S_A$. Then since $\lambda$ is singular, $\theta < \lambda$ whereby $C \in L \subseteq V$ will also have size $\theta$ in $V$ by virtue of the fact that a poset adding no new subsets to $\theta$ cannot collapse any cardinals below $\theta^{++}$. But now $S_{A} \subseteq C$ must also be in $V$ because otherwise $V[G]$ would be adding a subset of $\theta$ induced by $f''S_{A}$ where $f: C \rightarrow \theta$ is a bijection in the ground model. However, then $V$ can construct $A$ from $S_A$ in the ground model since

$A = \bigcup\{a \in \mathcal{P}(\lambda)| p \in S_{A} \land s_{\alpha} \in \text{range}(\vec{s}) \land p \Vdash \dot{A} \cap \check{s_{\alpha}} = \check{a}\}$. $\Box$

In particular, this shows that if $V$ is a forcing extension of $L$, then we cannot add a subset to a singular cardinal without adding a subset to a cardinal below it. I don't have an answer for what happens when $0^{\sharp}$ does exist, but at least this shows that your very interesting question is closely tied to the existence of certain large cardinals.

Answer by Jason for Why do we teach calculus students the derivative as a limit?

2011-01-31T04:43:52Z

There was a recent article in the American Math Monthly, Analysis with Ultrasmall Numbers, that might be of interest. For a summary of its implementation in a high school classroom, see http://maths.york.ac.uk/www/sites/default/files/odonovan-slides.pdf.

A quick skim of its implementation seems to suggest that it provides a groundwork for some of the informal manipulations used in calculus-based physics classes.

Zero-knowledge proof that 0 = 1

2010-12-10T05:13:46Z

Suppose one day I came up with a proof that 0 = 1 in some formal system such as PA or ZFC that cannot prove its own consistency (unless it is inconsistent). Would it be possible to have a zero-knowledge proof of this? In other words, would it be possible for me to convince you with high probability that I had derived such a proof without (feasibly) revealing the proof of the contradiction? (I haven't by the way...found such a contradiction.)

Answer by Jason for Ultrapowers, and Models of Set theory.

2011-01-23T04:46:27Z

(1) Even in the absence of a large cardinal hypothesis, Łoś's theorem still applies so we still have $V \models \varphi(x_1, \ldots, x_n)$ if and only if $V^{\kappa}/U \models \varphi(c_{x_1}, \ldots, c_{x_n})$ where $c_{x_i}$ is the constant function assuming $x_i$ on every value in $\kappa$. In particular, we still will have an elementary embedding between the two structures. However, the problem with working with this structure directly is that if the ultrapower is nonprincipal, then there will even be nonstandard elements of $\omega^{V_{\kappa}/U}$ so none of the usual absoluteness arguments will carry over. Therefore, we really want $\in_U$ to be a well-founded relation on V_{\kappa}/U so we could compose the map with the transitive collapse to get an elementary embedding $j: V \rightarrow N$ for some proper inner model $N$ (i.e., transitive and containing all ordinals).

As I was typing up this response, I see that Andres already replied with basically everything I was going to say about (2). Let me just add that part of the strength of having a nontrivial embedding $j: V \rightarrow N$ with critical point $\kappa$ ($\kappa$ is the least ordinal such that $j(\kappa) > \kappa$) is that we could always use such an embedding to get another elementary embedding $j: V \rightarrow N^{*}$ with critical point $\kappa$ where $N^*$ is transitive and contains all of its $\kappa$ sequences. We cannot even get $\omega$ closure for $M$ when $M$ contains a nonstandard $\omega$.

Answer by Jason for Consistent r.e. extensions of non r.e. theories.

2011-01-18T08:21:58Z

Let $A = T \cup R$ where $R$ is any set of refutable statements from $T$ (i.e., $T \vdash \lnot \varphi$ for all $\varphi$ in $R$). A simple necessary condition for such a $T^{\prime}$ to exist is that $A$ is not recursively (computably) enumerable. If it were, then given a r.e. (c.e.) $T^{\prime} \supseteq T$, we could recursively enumerate all statements of $T$ by listing only the ones in $T^{\prime}$ that also appear in $A$ (i.e., $T = T^{\prime} \cap A$). The reason for this equality is that $T^{\prime}$ is an extension of $T$ so it must contain all the statements in $T$ but then it cannot include any in $R$ by its consistency.

Now let $I$ be the set of all statements that are independent of $T$ (i.e. all $\varphi$ such that $T \nvdash \varphi$ and $T \nvdash \lnot \varphi$). In the case that $T$ is deductively closed meaning $T \vdash \varphi$ implies that $\varphi \in T$, a corollary of the above result is that $I$ cannot be the complement of a recursively enumerable set. This is the instance of letting $R$ be the set of all statements refutable from $T$.

Answer by Jason for Simple example of a sequence without computable modulus of convergence

2011-01-13T05:09:51Z

The answer to your more restrictive question is still yes with a reasonable definition of computable sequence (and I'll use your Busy Beaver example in the proof). Specifically, I will provide you with a computable $f: \mathbb{N} \rightarrow \mathbb{N}$ such that $\vec{a} = \langle a_m| m \in \mathbb{N}\rangle$ defined by:

$a_m = \begin{cases} 1/f(m) & \text{if } f(m) \neq 0 \\ 0 & \text{otherwise.} \end{cases}$

converges to $0$, but its modulus of convergence is noncomputable.

Fix a computable Cantor pairing function $\langle \cdot, \cdot\rangle$ where $\langle e, n\rangle \geq n$ for all $n$ and some computable enumeration of Turing machines $\langle T_e| e \in \mathbb{N}\rangle$ with $T_0$ some trivial Turing machine halting in $0$ steps on every input. Then define $f$ as follows:

$f(\langle e, n\rangle) = \begin{cases} e & \text{if } T_e \text{ halts in exactly } n \text{ steps on input } 0 \\ 0 & \text{otherwise.} \end{cases}$

$f$ is clearly computable because we can use an appropriate Universal Turing machine to run program $e$ on input $0$ for $n$ steps to determine whether it halts in exactly $n$ steps or not. Furthermore, each positive Natural number $e$ is assumed at most once by $f$, mainly at $\langle e, n\rangle$ if $T_e$ halts in exactly $n$ steps on input $0$. Consequently, for any positive Natural number $e$, we'll have $|a_m - 0| < 1/e$ beyond the at most $e$ many places where $f$ assumes a value from {$1, 2, \ldots, e$}. Therefore, $\vec{a}$ converges to $0$.

But if the modulus of convergence $M$ for $\vec{a}$ were computable, where $M(k)$ is understood to satisfy $|a_m - 0| < 1/k$ for all $m > M(k)$, then the Busy Beaver problem would also be computable. To see this, first note that if the program with positive index $e$ halts on input $0$ in exactly $n$ steps and $e \leq k$, then we have $a_s = 1/f(s) = 1/e \geq 1/k$ where $s = \langle e, n\rangle \geq n$, so that $M(k) \geq n$. Consequently, $M(k)$ will give us an upper bound on the number of steps it takes for all programs halting on input $0$ with index at most $k$ to do so. Therefore, by taking the maximum code $e_s$ of all of the $s$-state Turing machines, $M(e_s)$ will in particular provide us with an upper bound on the number of steps that it takes for all $s$-state Turing Machines halting on input 0 to do so. Then we simply run all of the $s$-state programs for this many steps and take the maximum output to compute $BB(s)$.

If on the other hand, you wanted $\langle a_s| s < \mathbb{N}\rangle$ to be a convergent computable sequence of Natural numbers, then $a_s$ must be constant beyond some fixed Natural number $N$, and so we will always have a simple computable modulus of convergence given by the constant function assuming $N$ at every value.

Nonstandard models of PA of large cardinal size

2010-12-20T03:57:46Z

It is easy to overlook the fact that the existence of a given large cardinal provides us with a true arithmetical statement that would otherwise be false if the large cardinal notion were not consistent with ZFC (See On statements independent of ZFC + V=L ). The arithmetical statement that I'm referring to here is CON(ZFC + large cardinal notion). This is an example of where we use a fact that is external to the set of Natural numbers, the existence of the large cardinal, to prove a result that's internal to $\mathbb{N}$. If we want a less esoteric statement of looking externally (not using a large cardinal notion) to prove an internal result about the Natural numbers, we can consider Goodstein's Theorem. Goodstein's Theorem states that a certain infinite collection of sequences, almost all of which grow very quickly on some initial segment, eventually descend to 0. The amazing result is that while this fact is not provable in Peano arithmetic, we can give a very simple proof of it in ZFC. In this case, we consider sequences of infinite ordinals to prove a true arithmetical statement representable in PA.

Let me now switch gears a little to say something about large cardinals. Assuming increasingly strong large cardinal axioms opens up the possibility for increasingly complex transitive set models of ZFC and then increasingly complex definable inner models of ZFC. Nevertheless, even if we assume a sufficiently strong large cardinal hypothesis, say the existence of a weakly compact cardinal $\kappa$, the elementary embeddings that arise fix all "small" elements (hereditary size less than $\kappa$ in the domain). I would therefore like to consider nonstandard models of PA that will not be fixed by such embeddings in an effort to make use of the large cardinal assumptions in a meaningful way for revealing internal truth by external examination. In order to avoid asking a rather vague question, let me pose it as follows:

Has anyone considered models of PA of large cardinal size?

As an example of what I have in mind, assume that we have a nonstandard model $M$ of PA of size $\kappa$ containing an unbounded well-order ( See Uncountable nonstandard models of PA ) for $\kappa$ supercompact. Can we use the fact that $\kappa$ is supercompact to reveal any interesting number-theoretic properties true in $M$?

Clearing misconceptions: Defining "is a model of ZFC" in ZFC

2011-01-11T12:10:47Z

There is often a lot of confusion surrounding the differences between relativizing individual formulas to models and the expression of "is a model of" through coding the satisfaction relation with Gödel operations. I think part of this can be attributed to the common preference for using formulas over codings. For example, a standard proof showing that $V_{\kappa} \models ZFC$ for $\kappa$ inaccessible will appeal to the fact that all of the ZFC axioms relativized to $V_{\kappa}$ are true. But then one learns about the Lévy Reflection Theorem scheme which allows every (finite) conjunction of formulas to be reflected to some $V_{\alpha}$. Perhaps this knowledge is followed by a question of whether the Compactness theorem can be used to contradict Gödel's Second Incompleteness Theorem.

Specifically, consider the following erroneous proof that ZFC + CON(ZFC) proves its own consistency:

Introduce a new constant $M$ into the language of set theory and add to the axioms of ZFC all of its axioms $\varphi_n$ relativized to $M$, denoted $\varphi_n^M$. Provided that ZFC is consistent, every finite collection of this theory is consistent by the Lévy Reflection Theorem whereby the Compactness Theorem tells us that the entire theory ZFC + "$M \models ZFC$" will be consistent. Consequently, this theory has a (ZFC) model $N$ so in this model, there exists a model $M$ of ZFC. To summarize then, arguing in ZFC + CON(ZFC), we've seemingly proven that we have a ZFC model $N$ modeling the consistency of ZFC by virtue of it having the model $M$ (i.e., seemingly $N \models ZFC + CON(ZFC)$ so we would have a proof of CON(ZFC + CON(ZFC)).

The misstep in this proof is of course a misuse of the conclusion of the Compactness theorem, mainly the assumption that such an $N$ will think that $M$ is a ZFC model. With some enumeration of the formulas of the axioms $\{\varphi_n| n \in \mathbb{N}\}$ of ZFC, it is clear that $N$ will certainly think that $M \models \varphi_n$ for any particular $n \in \mathbb{N}$ analogous to how a nonstandard model of Peano arithmetic has an element $c$ satisfying $c > n$ for any particular $n \in \mathbb{N}$. The problem of course in the case of $N$ is that there may be formulas with nonstandard indices not accounted for just as there will definitely be nonstandard numbers greater than $c$ in the PA example.

If one were to carry out the same proof with the more tedious arithmetization of syntax, then this link may be more apparent.

To a lesser extent, there may also be confusion with the fact that $0^{\sharp}$ provides us with a proper class of $L(\alpha) \preceq L$. This may lead to the question of whether $L$ has its own truth predicate, contradicting Tarski's Theorem. But of course $L$ will only realize that each of these $\varphi^{L(\alpha)}$ is true for any ZFC axiom $\varphi$, and if one attempts to appeal to the arithmetization of syntax, one can begin to see the problem that these $\alpha$ may not (and of course will not) be definable (without parameters) in the constructible universe L.

Since these types of misconceptions can be common among logicians and non-logicians alike, I thought I would ask the highly intelligent mathematicians who have worked through such problems or helped illuminate them to others if they would do so here as well. I think compiling a collection of tidbits of wisdom in this area from the collective perspectives of the MO Community can be illuminating to all. As such, my question is as follows:

What insights can you share regarding the questions of formalizing "is a model of ZFC" in ZFC and the various "paradoxes" that arise?

For example, maybe you can show a related seemingly paradoxical problem and resolve it, or simply share your thoughts on how to avoid such traps of logic.

Answer by Jason for Theorems that are 'obvious' but hard to prove

2011-01-10T03:50:08Z

I think this answers your question in a perverse way: All statements in the theory of Natural Numbers provable from the ZFC axioms of set theory. They are obviously true by definition.

EDIT: Looking at this objectively, it probably sounds like I'm saying if a statement is true, then it's obviously true. However, that was not my intent, and I apologize for what may have sounded like a thoughtless response. This is how I see it:

All statements expressible in the language of arithmetic can be represented by formulas in the language of set theory that are only $\Delta_1$ in the Levy hierarchy. In particular, all transitive models will agree on whether they are true. If we further restrict ourselves to only consider the true statements in $\mathbb{N}$ that are ZFC theorems, then all ZFC models will agree that these statements must be true so they are about as obvious to ZFC models as possible. Now if you are an oracle having knowledge of all such true statements, then you will probably develop an intuition that makes them all seem "intuitively obvious." This reflects the answers suggesting that a theorem is obvious after you prove it.

To add one more related point here, when addressing G$\ddot{\textrm{o}}$del's Incompleteness Theorem, one can naively ask about completing PA in the "obvious" way, i.e., by extending it to be the theory consisting of all true statements in $\mathbb{N}$. But of course such a completion is not computable.

Answer by Jason for Inconsistency and workaday independence.

2011-01-10T11:33:31Z

I really like this question, and I think it gets to the heart of the study of large cardinals in set theory. To add to Andres's excellent answer, let me talk a little more about inner models and forcing extensions in the context of large cardinals. A number of set theorists like to assume the existence of large cardinals with the greatest consistency strength that is still believably relatively consistent with ZFC with the purpose of studying the "richest" set-theoretic universe possible. Such large cardinal notions are relatively consistent with statements such CH or $\lnot$CH, but are never relatively consistent with $\lnot CON(ZFC)$. Furthermore, while a large cardinal can be destroyed by moving to a forcing extension, ZFC models and their truth predicates will persist in all outer models including forcing extensions. On the flip side, moving to even the smallest inner model of G$\ddot{\textrm{o}}$del's Constructible Universe $L$ may very well dispose of truth predicates for some set models $M \in L$ of ZFC present in the original universe, but as Andres's post points out, there still must be some such $M$ with constructible truth predicates.

Now even under the assumption of large cardinals, you can of course move to set models of ZFC + $\lnot$CON(ZFC). But the point is that in the presence of sufficiently strong large cardinal hypotheses, these are not the reliable models from a philosophical point of view as they lack any of the richness of the ambient model. Since Andres mentioned Harvey Friedman, I'll mention that his brother Sy-David Friedman, has a stronger notion of consistency in the case that sufficiently powerful large cardinals exist called internal consistency (See e.g., Internal Consistency and the Inner Model Hypothesis ). In the presence of inner models with sufficiently strong large cardinals, a formula is internally consistent provided that it holds in an inner model. In this situation, it is never possible for $\lnot CON(ZFC)$ to be internally consistent, but it is possible that $\lnot CH$ is.

Let me now also provide another related link between large cardinals and your question. While we may not presently consider models of ZFC + $\lnot$CON(ZFC), we certainly do consider models of ZFC + $\lnot$LC for some large cardinal notion LC, and these give rise to very nice results (e.g., Covering lemmas).

Implication of Polignac's conjecture on prime distribution in models of PA

2011-01-07T10:07:52Z

Polignac's conjecture (PC) is that there exists infinitely many pairs of consecutive prime numbers that are a distance $d$ apart for some natural number $d$. The twin prime conjecture is the particular instance of this conjecture for $d = 2$. The fact that this conjecture remains open has some interesting implications on nonstandard models of Peano Arithmetic (PA). Specifically, it is a standard exercise to show that every model of PA has order type $\mathbb{N} + \mathbb{Z} \cdot A$ for some dense linear order without endpoints. Thus every nonstandard model has an initial segment of Natural numbers followed by nonstandard numbers all appearing in an unbounded dense linearly ordered collection of what are called integer blocks or $\mathbb{Z}$-blocks. What I realized (someone else must've realized this too so please mention references if you know of any) is that if Polignac's conjecture turned out to be false, then we'd have the following strong limitation on the number of primes appearing in $\mathbb{Z}$-blocks.

($\mathbb{N} \vDash \lnot PC$) If $M$ is a model of PA and is $\Sigma^0_1$-equivalent to the theory of $\mathbb{N}$, then $M$ can have at most one prime appearing in any $\mathbb{Z}$-block: If not, then for some $d \in \mathbb{N}$, there would be a pair of nonstandard numbers that $M$ would view as two consecutive primes a distance $d$ apart. Since this occurs in a $\mathbb{Z}$-block, for any true Natural number $n$, the model $M$ thinks that there is a pair of consecutive primes greater than $n$ a distance $d$ apart. Then by $\Sigma^0_1$-elementarity, $\mathbb{N}$ would think the same thing so $\mathbb{N}$ would have unboundedly many pairs of consecutive primes a distance $d$ apart, making Polignac's conjecture true (in the standard model).

My question concerns the other models of PA:

Can we prove that there is a nonstandard model of PA having a $\mathbb{Z}$-block with at least two primes? Even better, can we prove that there is a model of PA with unboundedly many $\mathbb{Z}$-blocks having at least two primes?

Answer by Jason for Forcing over an arbitrary model of ZFC

2010-12-07T05:17:07Z

This is a great question that every set theorist first learning about the beautiful area of forcing should ask. As Andres described, there are a number of ways to understand forcing, but I want to elaborate on the boolean-valued model method since I believe that this is the most intuitive way to understand what it means to "force over $V$."

First, let me briefly introduce the method for which you are familiar. Cohen's forcing construction over an arbitrary partial order $\mathbb{P}$ involves the usage of what are called $\mathbb{P}$-names. If we are working with a countable transitive model $M$, then we should have $\mathbb{P} \in M$, and we are restricting our attention to the class of $\mathbb{P}$-names in $M$, denoted $M^{\mathbb{P}}$. Since $M$ is countable, we can use standard diagonalization techniques to construct an actual $M$-generic filter $G \subseteq \mathbb{P}$ in $V$. Our choice of filter $G$ will determine the values of each of the $\mathbb{P}$-names that become the elements of $M[G]$. But an amazing fact about forcing is that we actually have a definable "forcing relation" $\Vdash$ in $M$ such that $p \Vdash \varphi(\tau_1, \ldots, \tau_n)$ exactly when $M[G] \vDash \varphi(\tau_1^G, \ldots, \tau_n^G)$ for all $M$-generic filters $G$ with $p \in G$ where $\tau_1, \ldots, \tau_n \in M^{\mathbb{P}}$ is any collection of $\mathbb{P}$-names in $M$ and $\tau_i^G$ is the interpretation of the $\tau_i$ by $G$. Another amazing fact about this forcing relation is that if $M[G] \vDash \varphi(\tau_1^G, \ldots, \tau_n^G)$, then there will be $p \in G$ such that $p \Vdash \varphi(\tau_1, \ldots, \tau_n)$. Combining these facts, $M$ can assert "I may not know whether $\varphi$ will be true in extensions that are (possibly) fictitious to me, but I do know that $\varphi$ must be true exactly when the (imaginary) $M$-generic filter $G$ contains an element in $S_{\varphi}$ where $S_{\varphi}$ is the subcollection of conditions from $\mathbb{P}$ that force $\varphi$ to be true." You can easily verify using these facts about forcing that statements $\varphi$ that are true in all forcing extensions have $S_{\varphi} = \mathbb{P}$ and those that are false have $S_{\varphi} = \emptyset$.

With this background, I can now talk about "forcing over" $V$ using the Boolean-valued model method. In $V$, we can construct the proper class boolean-valued model $V^{\mathcal{B}}$ consisting of all $\mathcal{B}$-names from $V$ (same thing as $\mathbb{P}$-names but your poset is a complete boolean algebra $\mathcal{B}$). This model will not have a $1-0$ (true-false) truth value predicate per-say but will instead have a truth value predicate that ranges among all values in the boolean algebra. We denote the truth value of any statement $\varphi(\tau_1, \dots, \tau_n)$ by $\|\varphi(\tau_1,\ldots,\tau_n)\|$ for any collection of $\mathcal{B}$-names $\tau_1, \ldots, \tau_n \in V^{\mathbb{B}}$. Now let's compare this to the former construction.

First, the forcing relation that was said to be in $M$ was just a relativized version of the one in $V$. Mainly, if we pretend our $V$ is this countable model $M$ and set $\mathbb{P} = \mathcal{B} \setminus \{0\}$, the same things will be true. So $V$ can assert "I may not know whether $\varphi$ will be true in extensions that are (possibly) fictitious to me, but I do know that $\varphi$ must be true exactly when the (imaginary) $V$-generic filter $G$ contains an element in $S_{\varphi}$ where $S_{\varphi}$ is the subcollection of conditions from $\mathcal{B} \setminus \{0\}$ that force $\varphi$ to be true." Note that as was the case with $M$, these generic filters are fictitious to $V$ (unless $\mathcal{B} \setminus \{0\}$ is trivial), but $V$ still can talk about the name for these hypothetical objects. Also, the nice thing about complete boolean algebras is that all subcollections are closed under supremums. Consequently these $S_{\varphi}$ will each have a supremum and the supremum will be the boolean value that will wind up being assigned to $\|\varphi\|$. Note then that the statements that are always true in every forcing extension (such as the axioms of ZFC) will have $S_{\varphi} = \mathcal{B} \setminus \{0\}$ so that such $\varphi$ will be assigned boolean value $1$ while the statements that are always false in every forcing extension will have $S_{\varphi} = \emptyset$ so that these statements will all be assigned boolean value $0$. More generally, you can use the properties of the forcing relation to verify that the conditions forcing $\varphi$ to be true in the extension are precisely those at or below $\|\varphi\|$ in the boolean algebra under the prescribed assignment. This is why we commonly refer to these values from the boolean algebra as "probabilities" (though they aren't in general members of $[0, 1]$). If the boolean value is 1, it's necessarily true in the extension; if it's $0$, it's necessarily false in the extension and if it's some other value, then it will be true in a wider range of extensions if it's closer to $1$ in the boolean algebra lattice.

Finally in regards to forcing over $V$, you may object that forcing over complete boolean algebras is not completely general, but in fact every partial order $\mathbb{P}$ can be associated with a complete boolean algebra $\mathcal{B}(\mathbb{P})$ such that any forcing extension that can arise over $\mathbb{P}$ is equivalent to one that can arise over $\mathcal{B}(\mathbb{P}) \setminus \{0\}$.

And to address your question about utility, we are often concerned not only about relative consistency results but where these results will be true. For example, it is often more difficult to show that we can find a forcing extension of an inner model (transitive proper class model containing all of the ordinals) where $\varphi$ is true rather than a set where $\varphi$ is true. Since inner models are ubiquitous in the study of large cardinals, this is why it is especially important that we distinguish between the two types of philosophical forcing methods.

Answer by Jason for What is the generic poset used in forcing, really?

2011-01-05T11:05:18Z

First, a point of clarification: you're not adding the poset but rather forcing with it, and the poset itself remains unchanged after the forcing. The generic object that you're adding is actually a filter on this set meeting every dense subset (or maximal antichain) of the partial order.

The elements of the partial order, often called conditions in the context of forcing, form the possible components and the generic filter is responsible for collecting them in such a way to add an object of the desired form. In this way, the poset is highly correlated with the object you want to add because if you don't have the correct building blocks, there is no way to filter out the ones you want to use to construct an object of the desired form. The key property of the generic filter is that it consists of a compatible collection of conditions simultaneously meeting every dense subset. You can think of these dense subsets as the individual properties that we are going to want this filter to have. This is all better illustrated with examples:

Forcing To Add $\kappa$ many Cohen Reals: Here your forcing poset consists of finite partial functions from $\omega \times \kappa$ into {0, 1} ordered by reverse inclusion (longer is stronger). The conditions are the finite pieces of the $\kappa$ many Reals (subsets of $\omega$) that you're adding. By virtue of consisting of a compatible set of conditions meeting all dense subsets, a generic filter $G$ will pick them out in such a way that $\bigcup G: \omega \times \kappa \rightarrow \{0, 1\}$ is a total function with all of its $\kappa$ columns representing a newly added distinct Real. Specifically, the filter part insures that these conditions can be put together to form a partial function while the generic part makes sure that we've met all of the conditions imposed by the dense subsets, which include making sure the function is total, and that every column defines a distinct Real that's different from every one in the ground model. Because of the simplicity of the forcing poset, the cardinals between the ground model and the forcing extension are the same so if $\kappa = \omega_2$, then you've really forced $\lnot$CH to hold in the extension.

Forcing to Collapse a Cardinal $\lambda$ to have size $\kappa$: Here we force with the partial order consisting of partial functions from $\kappa$ into $\lambda$, each having size strictly less than $\kappa$. Again the partial order is ordered by reverse inclusion so the more the domain is filled in, the stronger the condition (lower in the partial order). A generic filter $G$ will again select these partial functions in such a way that $\bigcup G: \kappa \rightarrow \lambda$ is a total function. By virtue of meeting all dense subsets, $\bigcup G$ will have all elements from $\lambda$ in its range so it will be a newly added surjection. Consequently, if $\lambda > \kappa$ for $\kappa$ and $\lambda$ cardinals in the ground model (pre-forcing), then $\lambda$ will have been collapsed to be a $\kappa$-sized ordinal in the forcing extension. Because of the poset's closure, we didn't add any ${<} \kappa$-sized subsets of objects from the ground model or collapse any cardinals at or below $\kappa$, and we sometimes use these facts or even stronger properties to argue about truth in the ground model by virtue of truth in the forcing extension.

Sacks forcing: Here we add a "minimal Real" by forcing with the partial order consisting of perfect trees of finite binary sequences ordered by inclusion. A generic filter $G$ will thus consist of a collection of trees with larger and larger stalks so that $\bigcap G$ is a new branch through the tree ${}^{\omega}2$ that can be associated with a new Real.

Prikry forcing: If we have a nonprincipal normal $\kappa$-complete measure on a cardinal $\kappa$, then we can force with the collection of conditions of the form $\langle s, A\rangle$ where $s$ is a finite sequence of ordinals from $\kappa$ and $A$ is a subset of $\kappa$ from the normal measure. $\langle t, B\rangle \leq \langle s, A\rangle$ if $B \subseteq A$ and $t$ is an end extension of $s$ only adding ordinals from $A$ to the range of $t$. Here we won't take the union or the intersection of the generic filter $G$ but only the union of the finite sequences of ordinals in $\kappa$ from the first coordinates of the conditions in $G$. Again, the filter will make sure that this constructed object is a function, and by virtue of meeting all dense subsets, this union will form a countable unbounded sequence in $\kappa$. The importance of using a normal measure was making sure that no cardinals collapse, which is used for showing the relative consistency of the negation of the Singular Cardinal Hypothesis with a measurable cardinal. In this case, we winded up getting rid of unnecessary parts of the conditions, but they were used to guide the construction. Specifically, they were used to make sure our functions reached up high but did so without collapsing cardinals.

However, despite the fact that all of these forcing posets (notions) guide what our construction will look like, we can have much less intuitive posets accomplishing the same things. Mainly, we can associate each of these partial orders with some strange ordering on the elements of a cardinal and still accomplish the same result. Specifically, all of these forcing extensions would be equivalent to forcing extensions adding a subset of some cardinal.

There are obviously a number of other known forcing notions, but since this post is already long enough and maybe a little too technical for your question, let me just conclude with the main point. Mainly, we choose our posets looking ahead to the properties we want our generic object to have. The more complex the generic object that we want to add, the more complex the dense subsets we're going to need to have to make sure that the filter meeting them has all of the desired characteristics. This greater complexity often comes in terms of some combination of larger possible antichain sizes, more dense subsets, less closure, etc. While we can always define a descending sequence of conditions so that we meet any countable collection of dense subsets or maximal antichains, the genericity of the filter magically does this in a way to simultaneously meet all of them in a compatible way.

Comment by Jason

2011-05-19T06:09:35Z

I should mention that I may be abusing notation slightly, mainly $|A| = |A \times 2|$ is meant as there exists a bijection between $A$ and $A \times 2$ (or that the class of sets in bijective correspondence with $A$ is equal to the class of sets in bijective correspondence with $A \times \{0, 1\}$. I do not mean to imply that we can assign arbitrary sets $A$ an ordinal number for which there is a bijective correspondence (without choice).

Comment by Jason

2011-05-08T06:34:33Z

If you mention countable ordinals to your students, I would highly recommend pointing out the difference between ordinal exponentiation and cardinal exponentiation as it is often a source of confusion that $2^{\omega} = \omega$ (under ordinal exponentiation), but $2^{\aleph_0} \geq \aleph_1$ (under cardinal exponentiation).

Comment by Jason

2011-05-06T06:35:57Z

@tylern: Large cardinals are cardinals whose relative consistency with ZFC cannot be established from ZFC alone (assuming of course that ZFC is consistent). ZFC easily proves outright the existence of successor and limit cardinals. On the other hand, what you ask to prove is true for all regular cardinals. ZFC proves that all successor cardinals are regular, and a limit cardinal can be regular if we accept the existence of what is called a weakly inaccessible cardinal, which is a large cardinal notion. But in general, this is not a large cardinal question so I'm removing the tag.

Comment by Jason

2011-05-02T05:14:46Z

Glad I could help. It looks like I missed your comment before I typed up my answer to 2, but maybe it'll still be useful to you or someone else.

Comment by Jason

2011-04-30T03:11:11Z

@Amit: OK, so it's what I've seen as $\text{Coll}(\aleph_1, {<}\kappa)$. Thanks.

Comment by Jason

2011-04-29T07:01:45Z

By $\text{Coll}(\kappa, \aleph_2)$, you don't mean the set of partial functions from $\aleph_2$ into $\kappa$ having size at most $\aleph_1$, do you? In this case, $U$ will not contain any subsets of $(P_{\omega_2}(\lambda))^{V[G]}$ because $j''\lambda$ will be too big. Since I would refer to that poset as $\text{Coll}(\aleph_2, \kappa)$, I'm thinking maybe you mean an Easton product $\prod_{\alpha < \kappa} \text{Coll}(\aleph_1, \alpha)$. Is this interpretation correct?

Comment by Jason

2011-04-23T09:40:26Z

Actually, we do know that it exists because large cardinals exist. :) Also, if such an $\alpha$ does exist, then every element of $L_{\alpha}$ is definable without parameters. (See e.g., mathoverflow.net/questions/55392/…).

Comment by Jason

2011-04-09T06:31:10Z

Small omission: should say range of $j(g)$ restricted to $j''P_{\kappa}\lambda$, which is exactly $j''\lambda^{{<}\kappa}$.

Comment by Jason

2011-04-01T20:48:50Z

If you're not even willing to accept any fundamental logical axioms, then you are probably skeptical of the logical rules of inference as well. But without accepting any rules of inference, your theorems are exactly the axioms! As it's been said, "If you assume nothing, you can prove nothing." But even this comment is usually put in the context of at least assuming certain logical axioms and rules of inference.

Comment by Jason

2011-03-31T20:31:51Z

What I expressed here is my interpretation of the "unwritten" rules. Every "you should/need" was meant as "in my opinion, this is a good guideline to follow". As others have mentioned or alluded to, there are no universal rules. Separately, citing one's own work increases its exposure while citing others' work attaches proper credit and helps to make your research sound more informed.

Comment by Jason

2011-03-22T19:33:19Z

Asked/accepted answer here: stackoverflow.com/questions/5394003/tn-tn-sqrtn.

Comment by Jason

2011-03-17T01:10:21Z

@Oliver: You probably meant *CON*(ZF + AD) implies CON(ZFC + "There exist infinitely many Woodin cardinals"). ZF + AD cannot prove this (assuming ZF + AD is consistent) or it would prove its own consistency since CON(ZFC + "There exist infinitely many Woodin cardinals") implies CON(ZF + AD). In a model where ZF + AD holds, its inner model $\text{HOD}^{L(\mathbb{R})}$ will model ZFC + "There exists infinitely many Woodin cardinals", but this is a proper class. You can for any $n \in \mathbb{N}$ prove the consistency of ZFC + "There exists $n$ Woodin cardinals" from ZF + AD b/c it holds in cuts.

Comment by Jason

2011-03-11T20:06:31Z

I still want to think through some stuff, but this is very helpful. Thank you very much.

Comment by Jason

2011-03-10T07:06:25Z

To second David's comment, it may be unclear without more motivation why the Wikipedia article on this topic is unsatisfactory: "NC is contained in PolyL = DSPACE((log n)O(1))), which is strictly contained in PSPACE by the space hierarchy theorem." (en.wikipedia.org/wiki/PSPACE-complete)

Comment by Jason

2011-03-10T02:51:45Z

@Andreas: Yes, that's an important observation here because for more complex posets we can surreptitiously code a dominating real in the generic one; @Justin: Yeah, I've only seen Hechler forcing mentioned (almost as an aside) in the context of applications of MA and as an exercise in Jech. He seems to use such a family only to limit its size; we obviously cannot find a real in a ZFC + MA model dominating all of its own reals. But he also could've just done without the condition and talked about only dominating fewer than $2^{\omega}$ many so maybe he was just making the forcing more general.