User françois g. dorais - MathOverflow

Answer by François G. Dorais for Non-standard model of the domination principle

2013-05-17T17:23:01Z

The simplest forcing to add a dominating function is Hechler forcing $\newcommand{\D}{\mathbb{D}}\D$. In set-theoretic circles, conditions in $\D$ are pairs $(s,f)$ where $s$ is a finite sequence of natural numbers and $\newcommand{\N}{\mathbb{N}}f:\N\to\N$, extension is defined by $(s,f) \leq_{\D} (t,g)$ if $t \supseteq s$, $g \geq f$, and $t(n) \geq f(n)$ for $|s| \leq n \lt |t|$. A $\D$-generic filter $G$ defines a function $g = \bigcup \lbrace s : (s,f) \in G\rbrace$ which eventually dominates every ground model function.

Since the statement you're trying to force is localized in the sense that you only want $g$ to dominate all total $X$-computable functions, you can get away with an index-based variant of Hechler forcing. In that case, conditions of $\D_X$ are pairs $(s,i)$ where $s$ is a (coded) finite sequence of natural numbers and $i$ is an index for a total $X$-computable function $\varphi_i^X$, extension is defined by $(s,i) \leq_{\D_X} (t,j)$ if $(s,\varphi_i^X) \leq_{\D} (t,\varphi_j^X)$ in the sense described above. A $\D_X$-generic filter defines a function $g$ as above which eventually dominates every total $X$-computable function.

Note that we cannot expect $\D_X$ conditions to form a set since "$\varphi_i^X$ is total" is a $\Pi^0_2(X)$-complete statement. This is not a major problem since generics are constructed externally and we understand what "$\varphi_i^X$ is total" means from outside the ground model. Note that if the set of conditions exists in the ground model, then $\D_X$ is just a variation on Cohen forcing. However, in general, the ground model will have a very different perception of $\D_X$ and the generic will be quite different from a plain Cohen generic set.

To see that $\D_X$ preserves $\Sigma^0_1$-induction, first show that if some extension $(t,j) \leq_{\D_X} (s,i)$ forces a $\Sigma^0_1$-statement (which may use a fixed ground model set parameter in addition to the generic function $g$) then there is another extension $(u,i) \geq (s,i)$ that also forces the same $\Sigma^0_1$-statement. It follows from this that if $A(x)$ is a $\Sigma^0_1$ statement in the forcing language, then the set $$\lbrace x \in \N : (s,i) \nVdash \lnot A(x)\rbrace$$ is actually $\Sigma^0_1$-definable over the ground model. By $\Sigma^0_1$-induction in the ground model, this set has a minimal element $x_0$ and there is an extension $(t,j) \geq (s,i)$ (even with $j = i$) such that $$(t,j) \Vdash A(x_0) \land (\forall x \lt x_0)\lnot A(x).$$ This shows that it is dense to either force $\forall x \lnot A(x)$ or to force that there is a minimal $x$ that satisfies $A(x)$. Therefore, forcing with $\D_X$ preserves $\Sigma_1$-induction.

The use of the indexed variant $\D_X$ instead of the full second-order forcing $\D$ is very useful here since $\D$ can be quite devastating to weak subsystems of second-order arithmetic. Indeed, if the ground model satisfies arithmetic comprehension, then every $\Pi^1_1$ statement becomes $\Sigma^0_2$ in the generic extension. So forcing with $\D$ will not preserve systems weaker than $\Pi^1_1$-CA₀ containing ACA₀. The index-based variant $\D_X$ is not so devastating since it is equivalent to Cohen forcing over any model of ACA₀.

Answer by François G. Dorais for If ZFC has a transitive model, does it have one of arbitrary size?

2013-05-05T12:45:15Z

No. Because the construction of the inner model $L$ is absolute for transitive models of ZFC the ordinal heights of transitive models of ZFC are precisely the ordinals $\alpha$ such that $L_\alpha$ is a model of ZFC. If $\alpha_0,\alpha_1$ are the first two ordinals such that $L_{\alpha_0}$ and $L_{\alpha_1}$ are models of ZFC, then $L_{\alpha_1}$ is a model of ZFC in which there is a transitive model of ZFC, namely $L_{\alpha_0}$, and every transitive model of ZFC has rank $\alpha_0$ and is therefore bounded in size by $|V_{\alpha_0}|$.

Answer by François G. Dorais for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T01:32:21Z

I highly recommend reading this paper by Chris Hardin and Al Taylor, A Peculiar Connection Between the Axiom of Choice and Predicting the Future, as well as this shorter piece by Mike O'Connor Set Theory and Weather Prediction.

Answer by François G. Dorais for Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples

2013-04-24T16:56:50Z

Here is a simple direct derivation of $\mathsf{WKL}$ from $\mathsf{RT}^3_3$; a similar idea ought to work for the more general principle $\mathsf{KL}$ but I haven't worked that out.

Given a (downward closed) tree $T \subseteq 2^{\lt\infty}$ define the coloring $c:[T]^3\to\lbrace-1,0,+1\rbrace$ as follows. If $t,u,v$ are not mutually incomparable, set $c(t,u,v) = 0$. If they are mutually incomparable, suppose they are listed in lexicographic order and consider the meet of $t,u$ and the meet of $u,v$. One of these is the meet of all three nodes and the other is incomparable with one of the two ends $t$ or $v$. (This is where I use that $T$ is binary.) Set $c(t,u,v) = -1$ if $t$ is incomparable with the meet of $u,v$, and set $c(t,u,v) = 1$ if $v$ is incomparable with the meet of $t,u$.

An infinite homogeneous set $H$ of color $0$ is such that all nodes of $H$ are comparable except perhaps for one loner. An infinite homogeneous set of color $+1$ is a right-handed comb where all nodes branch on the left of a common branch (the prototypical example is $\lbrace0,10,110,1110,\dots\rbrace$). Symmetrically, an infinite homogeneous set of color $-1$ is a left-handed comb. In all three cases, we can easily compute an infinite branch through $T$.

As Tanmay explained, the general case of $\mathsf{KL}$ can be done by assigning a fourth color to incomparable $t,u,v$ that branch from the same node (so the meet of $t,u$ is the same as that of $u,v$). The fact that the tree is finitely branching ensures that there can be no infinite homogeneous set for this fourth color.

Answer by François G. Dorais for A Model where Dedekind Reals and Cauchy Reals are Different

2013-04-24T17:50:06Z

Coincidentally, I am preparing to talk about some of this tomorrow. Here is some of what I will say about this. A good way to think about Dedekind vs Cauchy reals is to think about what kind of information each representation gives.

For Dedekind reals, this is pretty clear: a Dedekind cut for $r$ gives you exactly enough information to determine whether $r \leq q$ or $r \geq q$ for every rational number $q$. Using this information, it is easy to get a Cauchy sequence for $r$. First find an integer $n$ such that $n \leq r \leq n+1$. Then repeatedly bisect the interval $[n,n+1]$, comparing with the midpoint (which is always rational) to determine which half interval to use for the next step. The sequence of midpoints $a_0 = n+1/2, a_1,a_2,\dots$ is a Cauchy sequence for $r$.

For Cauchy reals, we actually get no information at all unless we know something about the rate of convergence of the Cauchy sequence for the real $r$. Since we can easily speed up to a rate of convergence, let's assume that $|a_n - a_{n+1}| \leq 2^{-n}$ for all $n$. What we are given then is a way to get, on input $\varepsilon\gt0$, a (rational) interval of length at most $\varepsilon$ that contains our real number $r$. Can we use this kind of information to get a Dedekind cut for $r$? It's not that easy...

To see that $r \leq q$ we must make sure that $a_n \leq q+2^{1-n}$ for all $n$; similarly, $r \geq q$ happens if and only if $a_n \geq q-2^{1-n}$ for all $n$. To get a Dedekind cut for $r$, we must simultaneously decide which case holds for all rationals $q$. Note that if $r = q$ then both cases hold and we must choose one. Since these decisions could require inspecting the entire Cauchy sequence, we cannot expect to do this in an easy computable manner as we did for the other way around. In fact, there is no computable process which produces a Dedekind cut from such a Cauchy sequence.

In intuitionistic systems, the dichotomy axiom $r \leq 0 \lor r \geq 0$ for Cauchy reals is equivalent to the Lesser Limited Principle of Omniscience (LLPO):

Given $f:\mathbb{N}\to\lbrace0,1\rbrace$ that takes the value $1$ at most once, either $f(2n) = 0$ for all $n$, or $f(2n+1) = 0$ for all $n$.

LLPO is nontrivial and it is not provable in some intuitionistic systems. Even in the presence of LLPO, it is not enough to simply compare $r$ with $0$, we compare the real $r$ with all rationals $q$ and comprehend all these comparisons to form a Dedekind cut for $r$. So a certain nontrivial amount of comprehension is needed on top of LLPO. Since these comparisons are not independent from each other, this is not as hard a requirement as it may seem.

Andrej gave a nice example of a sheaf topos where LLPO fails. In classical systems, LLPO is always true and a very small amount of comprehension is necessary, for example the Spartan subsystem of second-order arithmetic $\mathsf{RCA}_0$ already proves that every Cauchy real (with a known rate of convergence) is equivalent to a Dedekind real. However, the difficulties in converting one representation into another are still visible if the process is repeated infinitely often. See the discussion in Hirst, Representations of reals in reverse mathematics, Bulletin of the Polish Academy of Sciences, Mathematics 55 (2007), 303–316 PDF.

Answer by François G. Dorais for Stronger theorem not resulting from proof analysis

2013-04-19T15:00:37Z

Hindman's Theorem is a semi-example. The most common proof is the Galvin-Glazer argument that uses idempotent ultrafilters. Hindman's original proof was a phenomenally complex direct combinatorial construction. Later, other proofs came along using ideas from topological dynamics.

Blass, Hirst and Simpson have analyzed the original Hindman proof to conclude that Hindman's Theorem is provable in $\mathrm{ACA}_0^+$, a relatively weak subsystem of second-order arithmetic. On the other hand, the Galvin-Glazer proof cannot even be formulated in second-order arithmetic since idempotent ultrafilters are higher order objects. Some arguments from topological dynamics can be formulated in second-order arithmetic but none have given better bounds than Hindman's original proof.

So this is an example where you have to work much, much harder to see that the result is provable in a relatively weak system, but the hard work was not new work tailored for that purpose, it was older work that preceded the better known easier proofs.

Answer by François G. Dorais for Is there a "mathematical" definition of "simplify"?

2013-04-04T23:43:27Z

In general, probably not. However, confluence is a well studied property of rewriting systems. This is also known as the Church–Rosser property after Alonzo Church and J. Barkley Rosser who proved that the $\lambda$-calculus has this property.

Haar measure for large locally compact groups

2011-07-19T18:21:36Z

In this answer, Gerald Edgar mentions that Haar measure is naturally defined on the $\sigma$-algebra of Baire sets (the smallest $\sigma$-algebra that contains all the compact $G_\delta$ sets) of a locally compact group and that the uniqueness of Haar measure can fail for larger $\sigma$-algebras. I wonder if there is a nice example of this.

Curious, I skimmed through Halmos's classic Measure Theory, and I found that he proves the existence and uniqueness of Haar measure for the slightly larger $\sigma$-algebra generated by all compact sets. (Confusingly, Halmos defines Borel sets to be those in this $\sigma$-algebra; I will stick with the usual definition of Borel sets.)

Is there a nice example of a locally compact group where the uniqueness of Haar measure fails for the $\sigma$-algebra of Borel sets — the $\sigma$-algebra generated by open sets?

To dispell some potential confusion (see comments by Keenan Kidwell and Gerald Edgar) Haar measures are not required to be regular (for the purpose of this question).

Answer by François G. Dorais for Reverse mathematics below RCA

2013-03-30T13:39:01Z

Surprisingly, this kind of base system hasn't gotten much attention in the reverse mathematics literature. Note that the system $\mathsf{RCA}_0^*$ proposed by Simpson in §X.4 of Subsystems of Second Order Arithmetic is a weakening of $\mathsf{RCA}_0$ in precisely the opposite direction: namely $\mathsf{RCA}_0^*$ plus primitive recursion is equivalent to $\mathsf{RCA}_0$ [D. R. Hirschfeldt, R. A. Shore, Combinatorial principles weaker than Ramsey's theorem for pairs, JSL 72 (2007), 171–206; PDF].

I implicitly used a system like you want in A variant of Mathias forcing that preserves ACA₀ [AML 51 (2012), 751–780; arXiv:1110.6559]. This is a function-based system of the form $\mathfrak{N} = (\mathbb{N},\mathcal{N}_1,\mathcal{N}_2,\ldots)$ where $\mathbb{N}$ is the underlying set and each $\mathcal{N}_k$ is a set of functions $\mathbb{N}^k\to\mathbb{N}$ which together form an algebraic clone: each $\mathcal{N}_k$ contains all the constant functions, the projections $\pi_i(x_1,\dots,x_k) = x_i,$ and if $f \in \mathcal{N}_\ell$ and $g_1,\dots,g_\ell \in \mathcal{N}_k$ then the superposition $f(g_1(x_1,\dots,x_k),\dots,g_\ell(x_1,\dots,x_k))$ belongs to $\mathcal{N}_{k}$ . And this algebraic clone is closed under primitive recursion: there are distinguished $0 \in \mathbb{N}$ (zero) and $\sigma \in \mathcal{N}_{1}$ (successor) such that for any $f \in \mathcal{N}_{k-1}$ and $g \in \mathcal{N}_{k+1}$ there is a unique $h \in \mathcal{N}_k$ such that $$h(0,\bar{w}) = f(\bar{w}) \quad\text{and}\quad h(\sigma(x),\bar{w}) = g(h(x,\bar{w}),x,\bar{w})$$ for all $x, \bar{w} \in \mathbb{N}.$ Note that the uniqueness requirement on $h$ is crucial since this is the only form of induction in this system. Strangely, one needs to assume dichotomy $x \dot- y = 0 \lor y \dot- x = 0$ to avoid a few bizarre models. Over this base system, $\Delta^0_1$-comprehension boils down to what I called uniformization:

If $f \in \mathcal{N}_{k+1}$ is such that $\forall \bar{w}\,\exists x\,{f(x,\bar{w}) = 0},$ there is a $g \in \mathcal{N}_k$ such that $\forall\bar{w}\,{f(g(\bar{w}),\bar{w}) = 0}.$

And arithmetic comprehension boils down to what I called minimization:

For every $f \in \mathcal{N}_{k+1}$ there is a $g \in \mathcal{N}_k$ such that $\forall x,\bar{w}\,{f(x,\bar{w}) \geq f(g(\bar{w}),\bar{w})}.$

(The above description is semantic but it is straightforward to formalize the above as a multi-sorted system.)

Similar systems do appear in proof theory (as described in Carl's answer) but only a few are restricted to second-order types. Kohlenbach proposed similar systems in various places. The closest I've seen is what he called $\mathsf{PRA}^2$ in Things that can and things that cannot be done in PRA [APAL 102 (2000), 223–245; PDF]. He doesn't actually give a fully detailed description in that paper, but if you chase references you see that it is exactly as the system I described above except that closure under superposition and primitive recursion are ensured by type-2 functionals $\mathbf{S}^k_\ell:\mathcal{N}_k\times\mathcal{N}_\ell^k\to\mathcal{N}_\ell$ and $\mathbf{R}_k:\mathcal{N}_{k-1}\times\mathcal{N}_{k+1}\to\mathcal{N}_{k}$ . Uniformization is equivalent to the AC^0,0-qf scheme in Kohlenbach's paper. The system assumes quantifier-free induction, which is probably not stronger than the formally weaker form of induction in the system I described above.

Answer by François G. Dorais for Proof theory and primitive roots

2013-03-19T23:26:03Z

It's the Pigeonhole Principle in the final step which is not constructively valid, not Heath-Brown's main result which, after inspection, doesn't show any of the tell tale signs of non-constructiveness.

Let $P_t$ be the set of all primes for which $t$ is a primitive root. Heath-Brown shows that if $q$, $r$, $s$ are three non-zero integers which are multiplicatively independent and that $q$, $r$, $s$, $-3qr$, $-3qs$, $-3rs$ and $qrs$ are not squares, then $P_q \cup P_r \cup P_s$ is infinite (and indeed that $\left|(P_q \cup P_r \cup P_s) \cap\lbrace1,\dots,x\rbrace\right| \gg x/(\log x)^2$). It is not constructively valid to draw from this the conclusion that one of $P_q$, $P_r$, $P_s$ is infinite. However, one can draw the more negative conclusion that $P_q$, $P_r$, $P_s$ are not all three finite.

One can see this using a Brouwerian counterexample which is analogous to the above situation. Let $A$ be the set of all $n$ for which there is a string of $333$ consecutive $3$'s in the first $n$ digits of $\pi$, and let $B$ be the complement of $A$. This is legitimate since we can always compute the first $n$ digits of $\pi$ to determine whether $n \in A$ or $n \in B$. Clearly $A \cup B = \lbrace1,2,3,\dots\rbrace$ is infinite. However, we cannot assert that $A$ or $B$ is infinite without knowing whether the digits of $\pi$ do or do not contain $333$ consecutive $3$'s. In the same way that GRH allows us to say that all three sets $P_q$, $P_r$, $P_s$ are infinite, the well-known conjecture that $\pi$ is normal allows us to assert that $A$ is infinite and $B$ is finite, but we don't know yet.

I haven't gone through Heath-Brown's argument in sufficient detail to assert without doubt that it is completely constructive but if there is a non-constructive part it must be hidden somewhere in some of the results he cites and not in the paper itself. In the paper, Heath-Brown explicitly computes an asymptotic lower bound on $\left|(P_q \cup P_r \cup P_s) \cap \lbrace1,\dots,x\rbrace\right|$. The argument is not straightforward but it is not convoluted and looks completely constructive. Instead of considering all primes, he considers a smaller but still large set of well-behaved primes $p$ for which he can break down the three multiplicative subgroups mod $p$ generated by $q$, $r$, $s$ into a handful of cases. He then computes upper bounds for the number of well-behaved primes up to $x$ falling into a case where none of $q,r,s$ are primitive roots. Adding these up and subtracting the result from a lower bound on the number of well-behaved primes up to $x$ gives $\left|(P_q \cup P_r \cup P_s) \cap \lbrace1,\dots,x\rbrace\right| \geq Cx/(\log x)^2$ where $C$ is a constant that may depend on $q, r, s$. Since the multiplicative subgroups of mod $p$ generated by $q$, $r$, $s$ are finite subgroups of a finite group, the various cases are decidable and it is fine to use the law of excluded middle to break into cases that way.

Answer by François G. Dorais for Indices of r.e. sets

2013-03-16T01:02:36Z

I chased down the references to clear this up. Giusto and Simpson attribute the argument to Jockusch [Degrees of functions with no fixed points, in J. E. Fenstad et al., ed., Logic, Methodology and Philosophy of Science VIII, Elsevier Science Publishers B.V. (1989), 191–201]. That argument cannot be found in Jockush, but a very similar remark can be found that Jockusch attributes to Arslanov, Nadirov, and Solov'ev (I didn't chase that reference).

The remark in Jockusch simply defines $f$ to be such that $W_{f(e)}$ consists of the first $p(e)$ elements of $A$. Such an $f$ can easily computed from $A$ and it is necessarily fixed-point free (i.e. $W_{f(e)} \neq W_e$ for every index $e$). Proposition 1 from Jockusch's paper shows that the degrees of fixed-point free functions (FPF) and diagonally non-recursive (DNR) functions are the same. The argument for FPF → DNR proceeds as follows. Given an FPF $f$ (such as the one above) consider $g(e) = f(k(e))$ where $k$ is a recursive function such that $W_{k(e)} = W_{\varphi_e(e)}$ whenever $\phi_e(e){\downarrow}$. Then $W_{g(e)} \neq W_{k(e)} = W_{\phi_e(e)}$, which implies that $g(e) \neq \phi_e(e)$.

It appears that Giusto and Simpson attempted to combine the two arguments a little too swiftly. Indeed, the above $g$ is such that $W_{g(e)}$ consists of the first $p(k(e))$ elements of $A$ and not the first $p(\phi_e(e))$ elements of $A$.

Answer by François G. Dorais for A uniformity with a countable base is a pseudometric uniformity.

2013-02-28T00:00:15Z

First, find a fundamental system of entourages $U_0 \supseteq U_1 \supseteq \cdots$ such that

$U_0 = X \times X$
$(x_0,x_1) \in U_i$ iff $(x_1,x_0) \in U_i$.
If $(x_0,x_1),(x_1,x_2),(x_2,x_3) \in U_{i+1}$ then $(x_0,x_3) \in U_i$.

Define $e(x_0,x_1) = \inf\lbrace 2^{-i} : (x_0,x_1) \in U_i\rbrace$. This is a well-defined nonnegative number since $(x_0,x_1) \in U_0$. The function $e$ is symmetric by property 2 and, of course, $e(x,x) = 0$. However, it does not necessarily satisfy the triangle inequality just yet.

By induction on $n$, we show that $$\sum_{i=0}^{n-1} e(z_i,z_{i+1}) \geq \frac{e(z_0,z_n)}{2}$$ for all sequences $z_0,\dots,z_n$. This is clear when $n = 1$. Suppose the result is true for all $n \lt m$. Given $z_0,\dots,z_m$, set $s = \sum_{i=0}^{m-1} e(z_i,z_{i+1})$. We may assume $0 \lt s \lt \frac12$, otherwise the result is trivial. Let $n \lt m$ be such that $$\sum_{i=0}^{n-1} e(z_i,z_{i+1}) \leq \frac{s}{2} \lt \sum_{i=0}^n e(z_i,z_{i+1}).$$ By the induction hypothesis, $e(z_0,z_n) \leq s$ and also $e(z_{n+1},z_m) \leq s$ since $$\sum_{i=n+1}^{m-1} e(z_i,z_{i+1}) = s - \sum_{i=0}^{n} e(z_i,z_{i+1}) \leq \frac{s}{2}.$$ Clearly, $e(z_n,z_{n+1}) \leq s$ too. Let $k$ be such that $2^{-k-1} \leq s \lt 2^{-k}$. Then $(z_0,z_n),(z_n,z_{n+1}),(z_{n+1},z_m) \in U_{k+1}$ which implies that $(z_0,z_m) \in U_k$ and hence $e(z_0,z_m) \leq 2^{-k} \leq 2s$, as required.

If we define $$d(x,y) = \inf \sum_{i=0}^{n-1} e(z_i,z_{i+1})$$ where the infimum is taken over all finite sequences $z_0,\dots,z_n$ with $z_0 = x$ and $z_n = y$, then $d$ is a pseudometric and since we always have $$\frac{e(x,y)}{2} \leq d(x,y) \leq e(x,y),$$ this pseudometric generates the correct topology.

Answer by François G. Dorais for Cantor's diagonal argument and ZF

2013-02-25T18:26:28Z

Joel David Hamkins, Asaf Karagila and I have made some progress characterizing which sets have such a function. ~~There is still one open case left, but Joel's conjecture holds so far.~~

Let $[Y]^{X}$ denote the set of all $A \subseteq Y$ such that $A \approx X$. The question is to characterize the sets $X$ for which there is a function $d:[\mathcal{P}(X)]^{X}\to\mathcal{P}(X)$ such that $d(A) \notin A$ for all $A \in [\mathcal{P}(X)]^X$. We will instead try to answer the more general question when there is such a function $d:[Y]^X\to Y$ for arbitrary sets $X, Y$ with $X \preceq Y$. (If $X \npreceq Y$ then $[Y]^X = \varnothing$ and the question is not interesting.) An obviously necessary condition is that $\newcommand{\napprox}{\not\approx}X \napprox Y$ but this is not sufficient as Ricky illustrated. Joel conjectured that such a function exists if and only if $\aleph(X) \preceq Y$, where $\aleph(X)$ is the Hartog number of $X$, the smallest ordinal that does not inject into $X$. We will show that this conjecture is true for all Dedekind infinite sets $X$ (i.e. when $\aleph_0 \preceq X$). Since the statement is obviously true when $X \prec \aleph_0$, the only remaining case is when $X$ is infinite but Dedekind finite (i.e. when $n \prec X$ for every $n \prec \aleph_0$ but $\aleph_0 \npreceq X$).

If there is an injection $f:\aleph(X)\to Y$, then there is such a $d:[Y]^X\to Y$ can be defined as $d(A) = f(\alpha_0)$ where $\alpha_0 = \min\lbrace \alpha \lt \aleph(X) : f(\alpha) \notin A\rbrace$. This last set is always nonempty otherwise composing $f:\aleph(X)\to A$ with a bijection from $A$ onto $X$ contradicts the fact that $\aleph(X) \npreceq X$.

For the converse, the hope is to define an injection $f:\aleph(X)\to Y$ by transfinite recursion where at each stage $\alpha\lt\aleph(X)$, we choose some $f(\alpha) \notin \lbrace f(\beta) : \beta \lt \alpha \rbrace$. To make these choices we would need a function $\hat{d}:[Y]^{\prec\aleph(X)}\to Y$ such that $\hat{d}(A) \notin A$ for every $$A \in [Y]^{\prec\aleph(X)} \colon= \lbrace Z \subseteq Y : Z \prec \aleph(X)\rbrace.$$ What we are given is a function $d:[Y]^X\to Y$ with $d(A) \notin A$ for every $A \in [Y]^X$. A simple idea is to fix some $A_0 \in [Y]^X$ and define $$\hat{d}(A) = d(A \cup A_0)$$ for all $A \in [Y]^{\prec\aleph(X)}$ but this only makes sense when $A \cup A_0 \approx X$. In general, we only know that $$X \preceq A \cup A_0 \preceq A + X,$$ so this strategy will work provided that $\alpha + X \approx X$ for every $\alpha \lt \aleph(X)$. This last statement holds precisely when $X$ is empty or Dedekind infinite. Indeed, $X \approx 1+X$ already implies that $X$ is Dedekind infinite and then $X \approx \alpha + X$ follows from the fact that $\alpha + \alpha \preceq \max(\aleph_0,|\alpha|)$ for every ordinal $\alpha \lt \aleph(X)$.

Asaf Karagila and I have made a little more progress on the case where $X$ and $Y$ are both Dedekind finite. In that case $Y \approx X + Z$ and the complement in $Y$ of any element of $[Y]^X$ has size exactly $Z$ and vice versa. Therefore, the existence of a $d:[Y]^X\to Y$ such that $d(A) \notin A$ for each $A \in [Y]^X$ is precisely equivalent to the existence of a choice function $c:[Y]^Z \to X$. In particular, if $Y \approx X+1$ then there is such a $d:[Y]^X \to Y$ since there clearly is a choice function $c:[Y]^1\to Y$. This does contradict the extension of Joel's conjecture to arbitrary $Y$ but not Joel's original conjecture where $Y = \mathcal{P}(X)$. Unfortunately, we still do not know what happens when $X$ and $Y = \mathcal{P}(X)$ are both infinite but Dedekind finite.

The existence of choice functions $[Y]^Z\to Y$ is a very intricate problem. For example, it is known that the existence of a choice function $[Y]^2\to Y$ is equivalent to the existence of a choice function $[Y]^4\to Y$ but that this does not imply the existence of a choice function $[Y]^3\to Y$! These intricate implications have been examined by John Conway in the article Effective implications between the "finite" choice axioms [Cambridge Summer School in Mathematical Logic, Lecture Notes in Mathematics 337 (1973), 439–458. MR0360275, doi:10.1007/BFb0066784].

Answer by François G. Dorais for $\Sigma_1^0-COH$?

2013-02-16T21:19:40Z

I also don't recall this principle being directly adressed in the reverse math literature. However, known results can be pieced together to paint a decent picture for $\Sigma^0_1$-COH. I will add to this answer if I find something more.

The results of Jockusch and Stephan, A cohesive set which is not high [Math. Logic Quart. 39 (1993), 515–530; doi:10.1002/malq.19930390153, MR1270396] (that survive the later corrections [Math. Logic Quart. 43 (1997), 569; doi:10.1002/malq.19970430412, MR1477624]) are very relevant, at least in the context of $\omega$-models. In particular, it follows from these results that $\Sigma^0_1$-COH does not imply arithmetic comprehension. (Actually, it follows from some of my results in A variant of Mathias forcing that preserves $\text{ACA}_0$ [Arch. Math. Logic 51 (2012), 751–780; doi:10.1007/s00153-012-0297-4, arXiv:1110.6559, MR2975428] that $\Gamma$-COH does not imply arithmetic comprehension for any class of formulas $\Gamma$.)

The analysis of Jockush and Stephan actually allows us to characterize $\Sigma^0_1$-COH more precisely. Namely, $\Sigma^0_1$-COH is equivalent to the statement that:

For every set $A$, there is a set $C$ such that either $C \subseteq^* X$ or $C \subseteq^* \bar{X}$ for every $A$-computable set $X$.

Further thought shows that $\Sigma^0_1$-COH is equivalent to the conjunction of COH with:

For every set $A$, there are an infinite set $D$ and a sequence $\langle R_k \rangle$ of subsets of $D$ such that if $X$ is $A$-computable then there is a $k$ such that $X \cap D = R_k$

Or with the slight strengthening:

For every set $A$, there are an infinite set $D$ and a sequence $\langle R_k \rangle$ of subsets of $D$ such that for all $i,j$, if $W^A_i \cap W^A_j \cap D = \varnothing$, then there is a $k$ such that $W^A_i \cap D \subseteq R_k$ and $W^A_j \cap D \subseteq \bar{R}_k$.

Note that if we require $D = \omega$, this statement last is equivalent to the Weak König Lemma. Therefore COH and $\Sigma^0_1$-COH are equivalent modulo $\text{WKL}_0$ (or even $\text{RCA}_0+\text{DNR}$).

I don't know whether COH and $\Sigma^0_1$-COH are equivalent over $\text{RCA}_0$, which boils down to asking whether COH proves the bulleted statements above. There is some evidence that suggests that COH might not imply $\Sigma^0_1$-COH over $\text{RCA}_0$. Namely, COH does not imply the uniform version of the last bulleted statement (where $k$ can be effectively computed from $i,j$) by a conservation result of Hirschfeldt and Shore from Combinatorial principles weaker than Ramsey's theorem for pairs [J. Symbolic Logic 72 (2007), 171–206; doi:10.2178/jsl/1174668391, MR2298478].

Answer by François G. Dorais for Understanding Troelstra's Uniformity Principle in Constructive Mathematics

2013-02-15T22:12:00Z

The reason why your proposed example is invalid is that equality of sets is not constructively decidable and, in particular, one cannot constructively check whether a set is empty or not. Indeed, checking that $X = \varnothing$ amounts to checking that $n \notin X$ for every $n$, which is not a finite process. Restricting to computable sets does not help. For example, define $X_e$ to be the set of all $s \in \mathbb{N}$ such that the $e$-th Turing machine halts (with blank input) in at most $s$ steps. Deciding whether $X_e = \varnothing$ is equivalent to the halting problem.

That said, your formulation for Troelstra's Uniformity Principle is not correct since it is invalid when $R(X,n)$ is the statement $(0 \in X \rightarrow n = 0) \land (0 \notin X \rightarrow n = 1)$. (I understand that $X$ is a complemented subset of $\mathbb{N}$, which is the usual convention in this context.) The mantra for uniformity principles is that every total function is continuous. Thus your statement is correct if $X$ ranges over $[0,1]$ or $\mathbb{R}$ (which are connected) but not over $\mathcal{P}(\mathbb{N})$ or $\mathbb{N}^\mathbb{N}$ (which are totally disconnected). Thus all continuous functions $[0,1]\to\mathbb{N}$ are constant but there are a larger variety of continuous functions on $\mathcal{P}(\mathbb{N})$. Namely, if $f:\mathcal{P}(k)\to\mathbb{N}$ is any function where $k = \lbrace 0,\dots,k-1\rbrace$, then $F(X) = f(X \cap k)$ defines a continuous function on $\mathcal{P}(\mathbb{N})$ and every continuous function $\mathcal{P}(\mathbb{N})\to\mathbb{N}$ is of this form for some $k$. Thus a correct version of the uniformity principle for $\mathcal{P}(\mathbb{N})$ has the weaker conclusion where the $n$ satisfying $R(X,n)$ is given by such a function.

As Andrej pointed out, the above was confusing the Uniformity Principle with the Continuity Principle. Though they are similar in some ways they occur in different constructive systems and, in particular, the Uniformity Principle does not not occur in contexts where subsets of $\mathbb{N}$ are complemented.

Answer by François G. Dorais for Mathematical techniques to reduce the amount of storage memory

2013-02-05T18:14:34Z

This is one of the basic problems that led to the field of information theory. It would take a while to explain all that is known about this, but the following will get you started.

Suppose we assign each book $b$ a binary string $\sigma_b$ such that no two strings are prefixes of each other (like telephone numbers). Then a consumer's purchases can be encoded by concatenating these strings back-to-back (without separating tokens or other marks). The total number of bits used to encode all the customer's purchases is $\sum_b n_b|\sigma_b|$, where $n_b$ is the number of times book $b$ has been purchased. We now have the optimization problem of minimizing this sum subject to the constraint that no two strings are prefixes of each other. This seemingly complex constraint actually has a simple existence criterion, namely the necessary fact that $\sum_b 2^{-|\sigma_b|} \leq 1$. So the whole thing boils down to finding $$\min \sum_b n_b \ell_b \quad\text{subject to}\quad \sum_b 2^{-\ell_b} \leq 1,$$ where $\ell_b$ is the length of the binary string used to encode the book $b$.

Generalizing a bit, we can think of $p_b = 2^{-\ell_b}$ as a probability associated to the book $b$. Translating the above becomes the problem of finding $$\max \sum_b n_b \log p_b \quad\text{subject to}\quad \sum_b p_b = 1,$$ where $p_b \in [0,1]$ are no longer restricted to being powers of $\frac12$. This continuous optimization problem has solution $p_b = n_b/n$, where $n = \sum_b n_b$ is the total number of books sold. Assuming that this solution happens to be such that the probabilities $p_b$ are all powers of $\frac12$, the total number of bits used is $$n \log_2 n - \sum_b n_b\log_2 n_b.$$ Dividing by $n$ to get the average number of bits used per book sold we get $$\log_2 n - \sum_b \frac{n_b}{n} \log_2 n_b = - \sum_b p_b \log_2 p_b.$$ This is the Shannon entropy of the distribution $p_b = n_b/n$ and this is an absolute lower bound for lossless encoding of this kind of data. Even if the probabilities are not powers of $\frac12$ encodings arbitrarily close to this bound can be achieved through arithmetic coding. In the situation you describe, it seems likely that the distribution $p_b$ is not known in advance, which is the main difficulty with achieving this optimal bound in practice.

Answer by François G. Dorais for Finite axiom of choice: how do you prove it from just ZF?

2010-07-19T21:51:20Z

There are two finite choice theorems, the internal one and the external one, both are true in ZF.

As Charles Staats pointed out, the external version is a tautology (modulo some finite combinatorics): if $a_1,\dots,a_n$ are all nonempty, then there are $z_1 \in a_1$,...,$z_n \in a_n$ and then $\lbrace (a_1,z_1),\ldots,(a_n,z_n)\rbrace$ is the desired choice function for the family $X = \lbrace a_1,\dots,a_n \rbrace$ of nonempty sets.

The internal version "every finite family of nonempty sets has a choice function" is stronger since a model of ZF may have nonstandard finite cardinals. The proof in this case is by induction on the cardinality of the family.

The empty family has a trivial choice function — the empty function. Suppose we know the theorem to be true for families of size $n$. Let $X$ be a family of nonempty sets with size $n+1$. Let $g:n+1\to X$ be a bijection. Let $X' = g[n]$ and $a = g(n)$. Then $X'$ is a family of nonempty sets of size $n$, which therefore has a choice function $f':X' \to \bigcup X'$. Since $a$ is nonempty, we can find $z \in a$ and hence $f = f' \cup \lbrace (a,z) \rbrace$ is a choice function for the original family $X$.

Answer by François G. Dorais for Ensuring nonempty lightface Borel sets have elements via theories of second-order arithmetic

2013-01-17T15:04:34Z

Given a tree $T \subseteq \omega^{\lt\omega}$, the statement "$B$ is an infinite path through $T$" is $\Pi^0_2$. Therefore, if $\mathcal{M}$ is such that every nonempty $\Pi^0_2$-class coded in $\mathcal{M}$ has a point in $\mathcal{M}$, then $\mathcal{M}$ is necessarily a $\beta$-model. So the models you want are precisely the $\beta$-models of $\Pi^1_1$-$\mathsf{CA}_0$.

Answer by François G. Dorais for From the product lemma to to a result about powersets

2013-01-08T14:54:56Z

When doing this in a set theory without replacement, the issue is really in the definition of $(\leq \lambda)$-closed. Here is a concrete example to illustrate.

Work in $V_{\omega+\omega}$, which is a model of ZC. Obvious failure of replacement in this model is that $\omega+\omega \notin V_{\omega+\omega}$ and yet there is an easy bijection between $\omega$ and $\omega+\omega$. For $\mathbb{Q}$, use the set of all finite partial functions $p:\lbrace\omega,\omega+1,\omega+2,\ldots\rbrace\to\lbrace0,1\rbrace$. Note that $\mathbb{Q}$ is isomorphic to standard Cohen forcing, except that $\mathbb{Q}$ is a proper class. Interestingly, $\mathbb{Q}$ is $(\leq\omega)$-closed for the trivial reason that $\mathbb{Q}$ has no infinite sub-set! Nevertheless, forcing with $\mathbb{Q}$ is the same as standard Cohen forcing and therefore adds a new subset of $\omega$.

For class forcing in models without replacement, the appropriate definition of $(\leq\lambda)$-closed is that every sub-class of $\mathbb{Q}$ which is a chain of size at most $\lambda$ has a lower bound in $\mathbb{Q}$. With this definition, the argument that Joel gave works perfectly.

Answer by François G. Dorais for How would set theory research be affected by using ETCS instead of ZFC?

2013-01-04T01:14:35Z

In principle, nothing would be lost by working in ETCS+R instead of ZFC since the two theories are very nicely interpretable in each other. However, after talking it through with Mike Shulman (whom I thank very much) here, I came to the conclusion that much would be lost in practice.

The problem lies with the notion of wellfoundedness. Recall that a binary relation $R$ on a set $A$ is wellfounded if every nonempty subset $B$ of $A$ has an $R$-minimal element (an $x \in B$ such that $y \not\mathrel{R} x$ for all $y \in B$); this is a $\Pi_1$ statement in the Lévy hierarchy. In ZFC, an equivalent statement is that there is an ordinal valued rank function for $R$ on $A$ (a function $r:A \to \mathrm{Ord}$ such that $x \mathrel{R} y \Rightarrow f(x) \lt f(y)$ for all $x,y\in A$). This is a $\Sigma_1$ statement in the Lévy hierarchy due to the fact that being an ordinal is $\Delta_0$. In ETCS+R, there is no suitable equivalent to ordinals: two wellorderings of the same type are indistinguishable from each other. Because of this, in ETCS+R, the equivalent rank function statement is much more complex since one must explicitly say that the codomain of the rank function is a wellordering (for which we must use the $\Pi_1$ definition).

Since wellfoundedness is $\Delta_1$ in ZFC, it is absolute for transitive models (of a small fragment) of ZFC. In other words, transitive embeddings between models of ZFC preserve wellfoundedness. (An embedding $f:M \to N$ is transitive if $f$ maps the elements of $x$ in $M$ onto the elements of $f(x)$ in $N$ for every $x \in M$; so the range of $f$ is a transitive substructure of $N$ isomorphic to $M$.) For models of ETCS+R, there is no natural equivalent to transitive embeddings so if one wants to preserve wellfoundedness then one must explicitly require that. In practice, it is very difficult to check that an embedding preserves wellfoundedness, especially when compared to checking that an embedding is transitive.

Therefore, ETCS+R does not have a very good grasp of wellfoundedness compared to ZFC. Since the study of wellfoundedness is so central to modern set theory, the framework of ZFC is much more appropriate than ETCS+R for set theorists to work with. To rephrase an analogy I used elsewhere, asking a set theorist to work in ETCS+R instead of ZFC is like asking a ring theorist to work with ternary relations $A(x,y,z)$ for addition $x+y = z$ and $M(x,y,z)$ for multiplication $x \cdot y = z$: it's essentially the same, in principle, but it's simply not the right thing to do!

The origin of sets?

2012-12-22T21:32:43Z

The history of set theory from Cantor to modern times is well documented. However, the origin of the idea of sets is not so clear. A few years ago, I taught a set theory course and I did some digging to find the earliest definition of sets. My notes are a little scattered but it appears that the one of the earliest definition that I found was due to Bolzano in Paradoxien des Unendlichen:

There are wholes which, although they contain the same parts $A$, $B$, $C$, $D$,..., nevertheless present themselves as different when seen from our point of view or conception (this kind of difference we call 'essential'), e.g. a complete and a broken glass viewed as a drinking vessel. [...] A whole whose basic conception renders the arrangement of its parts a matter of indifference (and whose rearrangement therefore changes nothing essential from our point of view, if only that changes), I call a set.

(The original German text is here, §4; I don't remember where I got the translation.)

According to my notes, Bolzano wrote this in 1847. Since Boole's An Investigation of the Laws of Thought was published a just few years later in 1854, it seems that the idea of sets was already well known at that time.

What was the earliest definition of 'set' in the mathematical literature?

Historical queries of this type are hopelessly vague, so let me give some more specific criteria for what I am looking for. The object doesn't have to be called "set" but it must be an independent container object where the arrangement of the parts doesn't matter.

It should also be fairly general in what the set can contain. A general set of points in the plane is probably not enough in terms of generality but if the same concept is also used for collections of lines then we're talking.
It shouldn't have implicit or explicit structure. Line segments, intervals, planes and such are too structured even if the arrangement of the parts technically doesn't matter.
It should be an independent object intended to be used and manipulated for its own sake. For example, the first time a collection of points in general position was considered in the literature doesn't make the cut since there was no intent to manipulate the collection for its own sake.
It should be a definition. Formal definitions as we see them today are a relatively new phenomenon but it should be fairly clear that this is the intent, such as when Bolzano says "I call a set" at the end of the quote above.
It should be mathematical concept. The strict divisions we have today are very recent but it should be clear that the sets in question are intended for mathematical purposes. Paradoxien des Unendlichen is perhaps more of a philosophical treatise than a mathematical one, but it is clear that Bolzano is considering sets in a mathematical way.

That said, any input that doesn't quite meet all of these criteria is welcome since the ultimate goal is to understand how the modern idea of set came to be.

Answer by François G. Dorais for Can we weaken GCH in this class forcing?

2012-12-21T13:38:35Z

It's impossible to accurately answer this since you don't say what forcing you have in mind. However, in the "typical" case, the answer is yes.

The "typical" case is when the forcing poset $P$ comes from a "typical" iteration of set forcings. These are "typically" arranged so that for unboundedly many $\kappa$, the partial iteration $P_\kappa$ up to $\kappa$ consists of well-behaved $\kappa^+$-cc forcings (often enough these are small so that $|P_\kappa| \leq \kappa$), and the remaining posets in the iteration after $\kappa$ are $\kappa$-closed. The $\Delta$-System Lemma (or even $|P_\kappa| \leq \kappa$ in nice cases) can "typically" be used to show that $P_\kappa$ is $\kappa^+$-cc; the "typical" $\Delta$-System Lemma application (or counting argument) here requires $\kappa^{\lt\kappa} = \kappa$. Then a standard variation of the theorem you state shows that $P$ preserves ZFC.

This is the "typical" case but it is only "typical" because it is fairly straightforward to show that such $P$ are tame. Note that the theorem you state deals with a very special case where $P$ splits as a product at $\kappa$. This is not uncommon but in general $P$ will only split as an iteration, but the general idea of the argument "typically" still applies to the more general case.

Answer by François G. Dorais for What is the status of Cantor-Schroder-Bernstein in Reverse Math?

2012-12-19T19:53:35Z

I will show that variants of the following proof work in extremely weak set theories but perhaps not in $\mathsf{B}_0^{\mathrm{set}}$.

We can always reduce to the case where one of the two injections is an inclusion. Suppose that $B \subseteq A$ and $f:A \to B$ is an injection. Say that $x \in B$ is a $B$-stopper if there is a finite sequence $\langle x_0,\dots,x_n \rangle$ with $x_0 = x$, $x_n \in B - f[A]$, and $f(x_{i+1}) = x_i$ for each $i \lt n$. The function $g:A \to B$ defined by $g(x) = x$ if $x$ is a $B$-stopper and $g(x) = f(x)$ if $x$ is not a $B$-stopper is a bijection.

The verification that $g$ is a bijection is a straightforward feat of plain logic provided that the base theory can handle the formation of arbitrary finite sequences. (I won't consider systems that can't handle arbitrary finite sequences.) So it is enough to make sure that $g$ exists. Assuming $\Delta_0$-comprehension, this is equivalent to the existence of the set of $B$-stoppers. If $B^{\lt\omega}$ exists, then the set of $B$-stoppers can be formed by $\Delta_0$-comprehension.

Sadly, Simpson's system $\mathsf{B}_0^{\mathrm{set}}$ does satisfy $\Delta_0$-comprehension, but it does not prove that $X^{\lt\omega}$ exists for every set $X$. In fact, I don't think it is known whether this system proves that $X^n$ exists for every set $X$ and every $n \lt \omega$. (See A. R. D. Mathias, Weak systems of Gandy, Jensen and Devlin, where this system is known as $\mathsf{GJI}_0$, modulo the fact that Simpson's formulation of the axiom of infinity is a little unusual. I think Simpson's axiom of infinity prevents Gandy's model but not the general problem it illustrates.)

If $B^{\lt\omega}$ does not exist, then the definition of $B$-stopper given above requires $\Sigma_1$-comprehension. However, the precise set of $B$-stoppers is not needed. If $C \subseteq B$ is such that $B-f[A] \subseteq C$ and both $C$ and $A-C$ are closed under $f$, then the map $h:A\to B$ defined by $h(x) = x$ if $x \in C$ and $h(x) = f(x)$ if $x \in A-C$ is a bijection. Over $\mathsf{B}_0^{\mathrm{set}}$ (even without infinity), the existence of such a set $C$ is easily established using the compactness theorem for propositional logic, which is known to be weaker than $\Sigma_1$-comprehension. This is the weakest system that I know which proves CSB.

Remark. The language of propositional logic is difficult to work with in set theories that do not prove that $X^{\lt\omega}$ exists for every set $X$. However, the theory in question consists of $p_x \leftrightarrow p_{f(x)}$ for $x \in A$, $p_x$ for $x \in B-f[A]$, $\lnot p_x$ for $x \in A-B$. Since these formulas are all short, we can get by with standard finite powers of sets.

In any case, I strongly advise against working in set theories that cannot prove that $X^{\lt\omega}$ exists for every set $X$.

Answer by François G. Dorais for papers archives? (especially not indexed by google)

2012-12-15T18:11:34Z

The EuDML is an interesting project that makes mathematics published in Europe available online.

Answer by François G. Dorais for How should one look at the set of compatible ring structures on a given group?

2012-12-12T15:32:18Z

Being a logician, I would look at this from the model theoretic point of view and think about spaces of types, which are all rather nice Stone spaces.

Here is the setup for your case for $0$-types. Let $\mathcal{L}_G$ be the language of rings augmented with a constant for each element of the additive group $G$. Let $A_G$ be the set of purely additive (have no mention of multiplication or the multiplicative identity) sentences of $\mathcal{L}_G$ that are true in $G$. This is a partial $0$-type and the space $\mathcal{T}_G^0$ of all (complete) $0$-types extending $A_G$ is a lot like what you describe. Indeed, if $a,b,c \in G$ then $a\times b = c$ is a sentence of $\mathcal{L}_G$ which determines a basic clopen set $\lbrace p \in \mathcal{T}_G^0 : a \times b = c \in p\rbrace$. This is a little finer than the space $\mathcal{R}_G$ you describe since elements of $\mathcal{R}_G$ only encode the truth for quantifier-free sentences of $\mathcal{L}_G$. The advantage of using spaces of types is that they have been extensively studied in model theory. Beyond $0$-types, you can consider the spaces of $k$-types, which instead of sentences use the broader class of formulas of $\mathcal{L}_G$ with free variables among $v_1,\dots,v_k$. Together, these spaces of types give a very nice understanding of the situation you're looking at.

Note that there are some types that are not necessarily compatible with the underlying additive group being precisely $G$. For example, the $1$-types that extend $\lbrace v_1 \neq a : a \in G \rbrace$ are incompatible with such rings. Nevertheless, if $R$ is a ring with underlying additive group $G$, then $R$ corresponds to the $0$-type $\lbrace \phi : R \vDash \phi\rbrace$, every element $a \in R$ corresponds to the $1$-type $\lbrace \phi(v_1) : R \vDash \phi(a)\rbrace$, and so on. The Omitting Types Theorem lets you know which types can correspond to rings whose underlying groups are precisely $G$.

A few more details regarding the last sentence. If $G$ is a countable group and $\tau \in \mathcal{T}^0_G$ is a complete extension of $A_G$, then $\tau$ corresponds to a ring with underlying additive group $G$ if and only if there is no single formula $\phi(v_1)$ such that $\tau \vdash \phi(v_1) \to v_1 \neq a$ for every $a \in G$. Of course, this happens exactly when $(\forall v_1 \lnot\phi(v_1)) \in \tau$ or $\phi(a) \in \tau$ for some $a \in G$. So the points of $\mathcal{T}^0_G$ that correspond to types that contain one of these for each formula $\phi(v_1)$. Since $G$ is countable, this is always a $G_\delta$ subset of $\mathcal{T}^0_G$ and therefore it is always a nice Polish subspace of $\mathcal{T}^0_G$.

Since you're interested in the action of $\mathrm{Aut}(G)$, let me add that $\mathrm{Aut}(G)$ acts on $\mathcal{T}^0_G$ in a natural way and that the $G_\delta$ subset described above is invariant under this action. However, since $\mathcal{T}^0_G$ is compact, there may be much to gain in considering the action on the whole space.

Answer by François G. Dorais for Does $\Pi^1_{\infty}$ comprehension imply ATR$_0$?

2012-12-04T03:43:25Z

Yes, in fact $\Pi^1_1$-CA₀ suffices to prove ATR₀. The simplest way to see this is that ATR₀ is equivalent to $\Sigma^1_1$-separation: if $\phi(n)$ and $\psi(n)$ are $\Sigma^1_1$ formulas then $$\forall n (\lnot \phi(n) \lor \lnot\psi(n)) \rightarrow \exists C \forall n ((\phi(n) \rightarrow n \in C) \land (\psi(n) \rightarrow n \notin C)).$$ Assuming $\Pi^1_1$-CA₀ one can simply take $C = \lbrace n : \lnot\psi(n)\rbrace$, for example, to satisfy the conclusion. Details can be found in Simpson's Subsystems of Second-Order Arithmetic.

Answer by François G. Dorais for Suslin algebras

2012-12-03T05:58:17Z

Jensen constructed a Suslin algebra of size $2^{\aleph_1}$ ($= \aleph_2$ in that model) to prove the consistency of the Suslin Hypothesis with the Continuum Hypothesis. You can find a detailed account of his intricate construction in The Souslin Problem (Lecture Notes in Mathematics 405) by Devlin and Johnsbraten. This is essentilally the only construction I am aware of.

Answer by François G. Dorais for Permission to use Online Notes

2012-11-28T07:12:31Z

The Stanford Copyright & Fair Use Overview is pretty clear about what constitutes fair use in the classroom and what doesn't:

Rules for Reproducing Text Materials for Use in Class

The guidelines permit a teacher to make one copy of any of the following: a chapter from a book; an article from a periodical or newspaper; a short story, short essay, or short poem; a chart, graph, diagram, drawing, cartoon, or picture from a book, periodical, or newspaper.

Teachers may photocopy articles to hand out in class, but the guidelines impose restrictions. Classroom copying cannot be used to replace texts or workbooks used in the classroom. Pupils cannot be charged more than the actual cost of photocopying. The number of copies cannot exceed more than one copy per pupil. And a notice of copyright must be affixed to each copy.

Examples of what can be copied and distributed in class include:

a complete poem if less than 250 words or an excerpt of not more than 250 words from a longer poem

a complete article, story, or essay if less than 2,500 words or an excerpt from any prose work of not more than 1,000 words or 10% of the work, whichever is less; or one chart, graph, diagram, drawing, cartoon, or picture per book or per periodical issue.

Not more than one short poem, article, story, essay, or two excerpts may be copied from the same author, nor more than three from the same collective work or periodical volume (for example, a magazine or newspaper) during one class term. As a general rule, a teacher has more freedom to copy from newspapers or other periodicals if the copying is related to current events.

The idea to make the copies must come from the teacher, not from school administrators or other higher authority. Only nine instances of such copying for one course during one school term are permitted. In addition, the idea to make copies and their actual classroom use must be so close together in time that it would be unreasonable to expect a timely reply to a permission request. For example, the instructor finds a newsweekly article on capital punishment two days before presenting a lecture on the subject.

Teachers may not photocopy workbooks, texts, standardized tests, or other materials that were created for educational use. The guidelines were not intended to allow teachers to usurp the profits of educational publishers. In other words, educational publishers do not consider it a fair use if the copying provides replacements or substitutes for the purchase of books, reprints, periodicals, tests, workbooks, anthologies, compilations, or collective works.

Note that this does not apply if the work is licensed appropriately. For example, the Stanford Copyright & Fair Use Overview quoted above is licensed CC BY-NC and this answer is licensed CC BY-SA. For course notes, it makes sense to use such a license since that is probably the intended use of the work. Contact the author(s) and recommend that they license their work in a manner they find appropriate.

The Stanford Copyright & Fair Use Overview also has a clear notice regarding online material:

If You Want to Use Material on the Internet

Each day, people post vast quantities of creative material on the Internet -- material that is available for downloading by anyone who has the right computer equipment. Because the information is stored somewhere on an Internet server, it is fixed in a tangible medium and potentially qualifies for copyright protection. Whether it does, in fact, qualify depends on other factors that you would have no way of knowing about, such as when the work was first published (which affects the need for a copyright notice), whether the copyright in the work has been renewed (for works published before 1978), whether the work is a work made for hire (which affects the length of the copyright) and whether the copyright owner intends to dedicate the work to the public domain. If you want to download the material for use in your own work, you should be cautious. It's best to track down the author of the material and ask for permission. Generally, you can claim a fair use right for using a very small portion of text for commentary, scholarship or smilar purposes.

The thing to take away from this is that there is no substitute for proper licensing. If you intend for something to be used in some way or another: make that clear!

Answer by François G. Dorais for Name for this generalized pigeonhole principle?

2012-11-26T00:10:54Z

This is equivalent to the Weak Partition Principle (a close relative of the Partition Principle mentioned by Goldstern). The Weak Partition Principle is form 100 in Consequences of the Axiom of Choice by Howard and Rubin (the Partition Principle is form 101).

The Weak Partition Principle asserts that if there is a surjection from $X$ onto $Y$ then it is not the case that $X$ has strictly smaller cardinality than $Y$ (i.e. $X \prec Y$). In contrapositive form, if $X \prec Y$ then there is no surjection from $X$ onto $Y$.

To see that the Weak Partition Principle implies your statement, note that if $P$ contains no block which intersects two distinct blocks of $Q$ then each block of $P$ is contained in a unique block of $Q$ and the map $P \to Q$ thus defined is necessarily a surjection. By the Weak Partition Principle, this cannot hold at the same time as the hypothesis $P \prec Q$.

For the converse, suppose that the Weak Partition Principle fails as witnessed by sets $X \prec Y$ and a surjection $p:X \to Y$. Let $Q = \lbrace p^{-1}(y) : y \in Y \rbrace$ and $P = \lbrace \lbrace x \rbrace : x \in X\rbrace$. These are two partitions of $X$ with $P \prec Q$ and every block of $P$ is clearly contained in a unique block of $Q$.

Answer by François G. Dorais for How many well orderings of $\aleph_0$ are there?

2012-11-17T14:06:06Z

This is an aside that I mentioned elsewhere long ago but deserves mention here since it homes in on the counterintuition that probably led Colin to doubt the answer.

As Colin pointed out, every $R \subset \omega$ can be interpreted as a binary relation on $\omega$ through a pairing function. This leads to a partition $\mathcal{B}$ of $\mathcal{P}(\omega)$ into isomorphism classes of binary relational structures $(\omega,R)$. Every countable infinite ordinal $\alpha$ has its own isomorphism class $B_\alpha \in \mathcal{B}$ and therefore $\aleph_1 \preceq \mathcal{B}$. We can also see that $2^{\aleph_0} \preceq \mathcal{B}$ in a multitude of ways. For example, we can map each $X \subseteq \omega$ to the isomorphism class of the directed graph consisting of one directed cycle of length $n+1$ for each $n \in X$ and infinitely many isolated points to fill space. In fact, we see that $\aleph_1 + 2^{\aleph_0} \preceq \mathcal{B}$ since the ranges of these two maps are disjoint. This is all provable without the axiom of choice.

There are models of ZF in which $2^{\aleph_0}$ and $\aleph_1$ are incomparable cardinals. Solovay's model where all sets of reals are Lebesgue measurable is such an example. In such models, $\mathcal{B}$ must have cardinality strictly greater than $2^{\aleph_0}$... Yes, that's right: $\mathcal{B}$ is a partition of $\mathcal{P}(\omega)$ that has more pieces than there are elements in $\mathcal{P}(\omega)$!

Comment by François G. Dorais

2013-05-18T19:22:59Z

Garrett Birkhoff's undergraduate thesis was on "Axiomatic Definitions of Perfectly Separable Metric Spaces" ams.org/journals/bull/1933-39-08/…

Comment by François G. Dorais

2013-05-18T19:16:40Z

Apparently, perfectly separable and completely separable are synonyms of 2nd-countable.

Comment by François G. Dorais

2013-05-18T19:06:58Z

This 1935 reference also uses this convention: ncbi.nlm.nih.gov/pmc/articles/PMC1076540/pdf/…

Comment by François G. Dorais

2013-05-18T19:03:54Z

Hm. I deleted my comment before I saw yours.

Comment by François G. Dorais

2013-05-18T11:37:20Z

By $g \geq f$, I mean $g(x) \geq f(x)$ for all $x$. I never assumed that the universe was standard, so this works as is in non-standard universes. In particular, this shows that the domination principle does not imply $\Sigma^0_2$-bounding.

Comment by François G. Dorais

2013-05-12T22:05:40Z

This question is now continuing on Terry Tao's blog - terrytao.wordpress.com/2013/05/08/…

Comment by François G. Dorais

2013-05-10T16:17:25Z

Stefan, it's not a good idea to claim an "error in a classical paper" in the title of the question, so I removed that.

Comment by François G. Dorais

2013-05-09T02:00:46Z

OK, I see. (I fixed the link to Miller's book which got mangled after the edit.)

Comment by François G. Dorais

2013-05-09T01:10:18Z

Wait, what is the issue? It seems that Miller's definitions match the OP's, modulo the synonyms 'field of sets' and 'algebra of sets'.

Comment by François G. Dorais

2013-05-08T17:10:00Z

Thanks! This is an excellent answer!

Comment by François G. Dorais

2013-05-08T16:43:36Z

Are you sure about replacing $\mathbb{R}$ by any formally real field, not just Arhimedean ones?

Comment by François G. Dorais

2013-05-06T15:06:13Z

We don't know yet whether the Diophantine theory of $\mathbb{Q}$ is decidable, but if it is that would definitely be a concrete example.

Comment by François G. Dorais

2013-05-01T03:54:46Z

What is $L$? $\quad$

Comment by François G. Dorais

2013-05-01T00:39:13Z

There has been a closing war on this question. The war is now over. meta.mathoverflow.net/discussion/1579/…

Comment by François G. Dorais

2013-04-30T19:14:48Z

Nash-Williams's proof probably does use AC. Since ZFC is conservative over ZF for $\Pi^1_1$ statements, this does no harm and the result is still provable without AC. The key is that if $r$ codes a counterexample in $V$, then that must be a counterexample in $L[r]$ too, but AC is true in $L[r]$ so the Nash-Williams proof works in there. Furthermore, in this analysis, the definition of wqo being used is immaterial.