User henry towsner - MathOverflow

Answer by Henry Towsner for Stronger theorem not resulting from proof analysis

2013-04-19T12:42:34Z

Probably the most famous example in reverse math is Ramsey's Theorem for pairs. The usual proof goes through in $ACA_0$, and iterates to give Ramsey's Theorem for n-tuples. But Seetapun gave a very different proof of Ramsey's Theorem for pairs shows that the statement is weaker than $ACA_0$. (And Seetapun's argument only works for pairs.)

Answer by Henry Towsner for AC and Euclidean Geometry

2013-01-15T19:34:10Z

Tarski gave a first-order formulation of Euclidean geometry and proved it complete (without using the axiom of choice). In particular, that means that Euclidean geometry is the same in every model of ZF, with or without choice. One might question whether Tarski's formulation actually captures all of Euclidean geometry, but it certainly includes everything in Euclid.

Answer by Henry Towsner for Understanding the nature and structure of proofs; Reverse Mathematics and Proof Theory. Prerequisites? Good introductory texts?

2013-01-12T16:34:48Z

Historically, reverse math is very closely tied to ideas in proof theory, but as Andreas points out, over the last decade or so, the connection to recursion theory has been very strong. For the foundational ideas in the area (in Simpson's book, for instance, or many of Friedman's writings) proof theory is very relevant.

Probably the two main introductions to proof theory right now are:

Proofs and Types by Girard (available online)
Basic Proof Theory, by Troelstra and Schwichtenberg

(A note on the Troelstra and Schwichtenberg book: the book is harder than most textbooks to get through solo, because it's very detailed; looking through it solo requires more than the usual amount of work identifying for oneself what the big picture is.)

Finally, in regards to your question about whether a statement has only finitely many proofs: proof theory is definitely the right place to look for questions like that. As Andreas points out, it turns out that it's very hard to phrase questions like that coherently, because it's easy to modify a proof in a trivial way, but hard to define precisely what should constitute a trivial modification.

Answer by Henry Towsner for What ordinals are definable relations in Peano Arithmetic?

2012-11-01T17:22:44Z

The computable ordinals---that is, the ordinals below $\omega_1^{CK}$---are, by definition, represented by computable relations, all of which can be represented by formulas in PA, and indeed, even by fairly simple formulas. As Andreas points out, allowing arithmetic formulas instead of computable ones does not change the class of ordinals.

Answer by Henry Towsner for How do quantifiers limit scope?

2012-10-14T20:53:36Z

Bounded quantifiers of various kinds, like $\forall x<t$ or $\exists y\in\mathbb{N}$, are a commonly used notational convention. The convention for such notations is exactly what you expect: \[\forall x<t\ P(x)\equiv \forall x(x<t\rightarrow P(x))\] while \[\exists x<t\ P(x)\equiv \exists x(x<t\wedge P(x)).\] The different choice of connective is necessary and appropriate, since it preserves duality: \[\forall x<t \ P(x)\Leftrightarrow \neg\exists x<t\ \neg P(x).\]

Your students are using bounded quantifiers of this kind, with the correct interpretation. However that particular syntax isn't generally used, for the reasons Peter Smith notes. People who want quantifiers bounded by predicates generally introduce some other notation; the one I'm most familiar with is \[\forall x\in P (Q(x)),\] but there are other variants (for instance, introducing $\in$ in a high school class would presumably require at least some discussion of sets, which might be undesirable).

There's no canonical set of abbreviations, so you ultimately have to make a call about which syntax is permitted. (Having a textbook that casually uses non-standard abbreviations is a further complication; I know I'd be quite frustrated to be told that formulas had to be built using certain rules when my own textbook couldn't be bothered to follow them.)

Small Configurations in Random Hypergraphs

2012-04-04T14:59:57Z

I have a somewhat technical question regarding the distribution of small hypergraphs in randomly chosen hypergraphs. (My hope is that this is something that can be done using standard ideas about random hypergraphs, and that I'm just not comfortable enough with the area to see how.)

I begin with some large vertex set $G$, $|G|=n$, and choose a random $k$-uniform hypergraph $\Gamma$ by independently placing each edge from ${G\choose k}$ in $\Gamma$ with probability $p$. (I expect the relevant case to be of the form $p\approx n^{-1/c}$ for some $c$.) I fix some $d$.

Now I fix some small $k$-uniform hypergraph $H$ on $n'$ vertices with at most $d$ edges, and I'm interested in those tuples $\vec x\in G^{n'}$ such that $H$ is a sub-hypergraph (not necessarily induced) of the restriction of $\Gamma$ to $\vec x$. (I think of $H$ as defining which edges I care about, and then I'm interested in those tuples in which all the edges mandated by $H$ are actually present in $\Gamma$.) I'll write $\Gamma_H\subseteq G^{n'}$ for the set of such tuples.

Now suppose I have some set $A\subseteq G^{n'}$, and I want to estimate its probability as a fraction of $\Gamma_H$. One way to do so would be to define $$\mu_H(A)=\frac{|A\cap\Gamma_H|}{|\Gamma_H|}.$$

But another way to do so would be to partition $H$ into two sub-hypergraphs, $H_0,H_1$, and ask about $$\mu'_H(A)=\frac{1}{|\Gamma_{H_0}|}\sum_{\vec x\in \Gamma_{H_0}}\frac{|\{\vec y\mid (\vec x,\vec y)\in A\cap\Gamma_H\}|}{|\{\vec y\mid (\vec x,\vec y)\in\Gamma_H\}|}.$$

Let's say $\Gamma$ is $\delta$-good if for every set $A$, $$|\mu_H(A)-\mu'_H(A)|<\delta.$$ It seems like to show that this holds, one could show that for "most" choices of $\vec x\in\Gamma_{H_0}$, $|\{\vec y\mid(\vec x,\vec y)\in\Gamma_H\}|$ is close to the value it ought to have.

I would like to show that for an appropriate choice of $p$, and with fixed values $k,d,n',\delta$, the probability that $\Gamma$ is $\delta$-good approaches $1$ as $n\rightarrow\infty$. (I'd be particularly happy to 1) know what good choices of $p$ would be, or 2) show that this follows from an established notion of pseudo-randomness.)

(I actually need a more complicated case in which one partitions $H$ into three pieces $H_0,H_1,H_2$, and looks at the measures $\mu_H$ and $\mu'_H$ relative to "almost every" fixed tuple $\vec z\in\Gamma_{H_2}$, but perhaps I'll be able to derive that easily from an answer, or perhaps I'll end up asking a follow-up question.)

Answer by Henry Towsner for Applications of idempotent ultrafilters

2012-09-17T15:38:05Z

There are applications of idempotent ultrafilters (often under the name "idempotent member of the enveloping semigroup") to finding and classifying the structure of topological dynamical systems. Auslander's book "Minimal Flows and Their Extensions" includes some of them.

(p,q) versus Glivenko-Cantelli

2012-06-14T19:56:38Z

Say a collection of sets $\mathcal{F}$ satisfies the (p,q) property if whenever $\mathcal{G}\subseteq\mathcal{F}$ with $|\mathcal{G}|\geq p$, there is a $\mathcal{H}\subseteq\mathcal{G}$ with $|\mathcal{H}|\geq q$ and $\bigcap\mathcal{H}\neq\emptyset$. A (p,q) theorem for some class of sets $\mathcal{C}$ gives a bound $T_{p,q}$ so that whenever $\mathcal{F}\subseteq\mathcal{C}$ has the (p,q) property, there is a set $S$ such that $|S|\leq T_{p,q}$ and whenever $F\in\mathcal{F}$, $F\cap S\neq\emptyset$.

The main classes I know of for which a (p,q) theorem has been proven are the convex sets in $\mathbb{R}^d$ and the sets of bounded VC dimension. But both of these are Glivenko-Cantelli classes, which means that if we select a sufficiently large finite set $S$ at random then, with probability $1$, every set in the class intersects with $S$ with fraction close to its measure. In particular, by choosing $S$ large enough, this means every set in the class of measure $\geq\epsilon$ contains a fraction of $S$ of size, say $(\epsilon/2)|S|$. (Technically $S$ is a multiset, but when the base set is large enough, this doesn't make a difference.)

Unless I'm misunderstanding something, the conclusion of Glivenko-Cantelli is much stronger than the conclusion of the (p,q) theorem: the claim holds for almost every choice of $S$, for all large sets in the class simultaneously, and each set has "large" intersection with $S$ instead of just one point. Also, Glivenko-Cantelli-type theorems seem to be easier to prove.

The only catch is that Glivenko-Cantelli only covers the large sets in the class, while the (p,q) theorem covers every single set in the class satisfying the (p,q) property.

This brings me to the problem: the main example of a collection $\mathcal{F}$ with the (p,q) property seems to be a collection of sets with measure $\geq\epsilon$ for some fixed $\epsilon$. In other words, exactly the collections already covered by Glivenko-Cantelli.

My question is, roughly, what more the (p,q) theorem does for us. Am I missing something about the statements, so that the (p,q) theorem provides more? Or are there interesting collections with the (p,q) property which aren't already covered by being a Glivenko-Cantelli class?

Answer by Henry Towsner for Admissible ordinal beyond $\omega_{1}^{ck} .$

2012-06-09T21:43:20Z

The admissible ordinals are unbounded in $\omega_1$, so there are uncountably many countable admissible ordinals. Barwise's book, "Admissible Sets and Structures" is the standard reference on all things admissible. Beyond that, the proof theoretic literature contains some investigation of extensions of Kripke-Platek by "large cardinal" assumptions, beginning with KP+"there exists an admissible ordinal", and these theories are satisfied precisely by various larger admissible ordinals (and in all cases, there are countable ordinals which satisfy them). Various papers by Jäger, Pohlers, and Rathjen contain these theories.

Answer by Henry Towsner for higher fourier analysis: splitting periodic parts and 'nilsequence' noise ?

2012-05-19T17:13:32Z

(I agree with the comment that there isn't exactly a question here, but I'll try to make some useful comments.)

First, a key idea in this area is that there can be different notions of structure corresponding to different questions, and for each notion of structure, a corresponding notion of randomness. If one's notion of structure is given by Fourier analysis, periodic, or nearly periodic, functions are structured, and functions which are completely non-periodic, like $n\mapsto e(n^2)$, are random.

(Note the connection to your other question---a characteristic factor is a notion of structure, and generally the two are exactly equivalent.)

But for some purposes we want to consider other notions of structure. $n\mapsto e(n^2)$ is an example of a function which looks random relative to the periodic functions, but is actually quite structured. (That it looks random is really quite misleading, and I think somewhat sensitive to the way you plotted it, since I recall looking at plots of related functions which make clear that they have a structure, just not a periodic one.)

The randomness Tao is talking about in the structure/randomness dichotomy is what's left over after you've approximated a function as well as possible using some family of functions (the most common example being functions given by nilsystems with certain parameters).

Answer by Henry Towsner for eigenfunctions -> characteristic factors

2012-05-19T17:03:16Z

The first important thing to note about a characteristic factor is that it's not uniquely defined. In particular, if you expand a characteristic factor to a larger factor, you still have a characteristic factor. So the interesting question is to find a characteristic function which is small enough that its elements are easy to work with. One of the natural ways of looking at a characteristic factor is as the factor generated by certain canonical functions.

The classic case (and the one which motivated the more recent work) is where the eigenfunctions are the canonical functions, the factor is the collection of functions with pre-compact orbit, and the factor is characteristic for the average you describe in your question.

Eigenfunctions can be viewed as coming from nilsystems where the group is abelian (that is, the step is 1), so a generalization is to work with functions coming from nilsystems of higher step. These functions generalize the eigenfunctions, and are characteristic for more complicated averages. In that sense these particular characteristic factors generalize the eigenfunctions.

More generally, the notion of a characteristic factor captures, relative to arbitrary averages, what the factor generated by the eigenfunctions captures relative to a particular average.

Answer by Henry Towsner for Applications of nonconstructive mathematics

2012-05-14T16:07:26Z

The mean and pointwise ergodic theorems are non-constructive, and I understand they were originally developed for applications to thermodynamics.

Answer by Henry Towsner for Question of combinatorics in the lower part of the Borel hierarchy.

2012-01-11T19:50:05Z

(As Andreas has pointed out, this answer is not correct---it concerns a slightly different class of functions.)

The answer to your first question is yes. For any nice function $f$, consider the tree $T_f$ of finite sequences $(x_0,\ldots,x_k)$ such that there is some proper extension $(x_0,\ldots,x_k,\ldots,x_{k+r})$ with $$g_f((x_0,\ldots,x_k))\neq g_f((x_0,\ldots,x_k,\ldots,x_{k+r})).$$ (In other contexts, this is called the "tree of unsecured sequences".)

Then it is easy to see that $f$ being nice implies that this tree is well-founded. The function $h_f$ can be defined, with ordinal $ht(T_f)$, by setting the ordinal value $\alpha((x_0,\ldots,x_k))$ to be the height of $(x_0,\ldots,x_k)$ in $T_f$ if this sequence is unsecured, and $0$ if the sequence is secured.

In the $2^\omega$ case, this means the supremum of ranks of nice functions is $\omega$: by Konig's lemma, a well-founded binary tree is finite.

In the $\omega^\omega$ case, I believe the supremum of ranks should be $\omega_1$ (in plain ZFC), though the proof doesn't appear to be entirely obvious. (One could to take a tree of sequences of height $\alpha$, which induces a function $h_f$, and then take the corresponding $f$, but some additional work is needed to ensure that there is no other representation of $f$ giving it a lower rank.)

Functions like your $g_f$, but with range $\omega$ instead of ${0,1}$, have been called "asymptotically stable". I believe this terminology was introduced by Tao in a blog post; Kohlenbach and Gaspar have a paper ("On Tao’s “ﬁnitary” inﬁnite pigeonhole principle") discussing an application, and I have a paper with Beiglbock ("Transfinite Approximation of Hindman's Theorem") which deals with the tree $T_f$.

Answer by Henry Towsner for Best way to present (or avoid) a tedious epsilon argument in a paper

2011-09-29T14:20:38Z

Sometimes fiddly $\epsilon$ bounds can be eliminated by carrying out the proof using nonstandard analysis. (You probably don't want to learn about nonstandard analysis just to rewrite one proof, but if you find yourself in this situation repeatedly, it might become a worthwhile investment.)

Jump Inversion of Arithmetic

2011-05-16T01:32:10Z

I seem to recall once hearing a result to the effect that $\emptyset^{(\omega)}$ was the double jump of some other degree, but could not be the triple jump of any degree. However I'm unable to find the exact result. Does anyone know what I might be thinking of (or what is actually known about jump inversion on $\emptyset^{(\omega)}$, if I'm remembering this completely wrong)?

Answer by Henry Towsner for Are the Millennium Prize Problems all decidable?

2011-04-18T16:12:52Z

Most of the Millennium Prize Problems are individual problems, with a single yes or no answer. Decidability as a question only really makes sense in the context of a countably infinite family questions, where you can ask whether it's decidable which of those questions should be answered yes.

Answer by Henry Towsner for Is it possible for P(N) to be larger than Aleph_omega?

2011-03-10T01:50:41Z

Yes. In fact, the only requirement on $2^{\aleph_0}$ is that $cf(2^{\aleph_0})>\aleph_0$. (Cohen's argument can make the power set any regular cardinal, and I think it requires at most small modifications to handle the general case.)

Answer by Henry Towsner for What notions are used but not clearly defined in modern mathematics?

2011-02-26T04:06:12Z

In proof theory, the notion of a "natural well-ordering" comes up, but isn't (perhaps can't be) defined formally.

In a similar vein, I'm told that inner model theorists were proving results about "the core model" for decades without having a precise definition of what it was.

Compactness of the Unit Ball in a Superreflexive Space

2011-02-20T01:39:18Z

The unit ball is compact in the weak topology iff the space is reflexive. Is there an analogous topology under which the unit ball is compact iff the space is super-reflexive?

(I know a space is super-reflexive iff the unit ball is super weakly compact, but I'm not aware of a topology which makes super weak compactness equivalent to compactness in that topology.)

Answer by Henry Towsner for Why is "P vs. NP" necessarily relevant?

2011-02-03T22:18:10Z

To respond to the question in your title, I think it's based on a false premise. I don't think anyone serious claims that "P vs NP" is "necessarily relevant", in the sense you seem to mean "relevant"---that is, I don't think anyone claims that a solution "P vs NP" will automatically have significant impact on the way computing is used. There are, however, good reasons to think that the question is of substantial theoretical interest.

As for your question at the very end, if P=NP then, for any problem, the algorithm which diagonalizes through all possible P-time algorithms is guaranteed to be a P-time algorithm for the problem. (Of course, this algorithm would be very slow.) So in some sense there can't be a non-effective proof that P=NP.

Dual of the Ultraproduct of a Banach Space

2011-01-25T18:46:03Z

Suppose we have a Banach space ultraproduct $(E_i)_U$. I can think of three natural objects which are "dual-like":

$(E_i^*)_U$, the ultraproduct of the duals of the ground spaces.
The space made up of objects $(f_i)_U$ such that:

a) Each $f_i:E_i\rightarrow\mathbb{R}$

b) There is a $B$ such that for every $i$ and every $x$, $|f_i(x)|\leq B||x||$

c) For any $(x_i)_U, (y_i)_U\in (E_i)_U$, $\lim_U||f_i(x_i+y_i)-f_i(x_i)-f_i(y_i)||=0$

d) For any $(x_i)_U\in (E_i)_U$ and any real $\alpha$, $\lim_U ||f_i(\alpha x_i)-\alpha f_i(x_i)||=0$
The ordinary dual $(E_i)_U^*$.

It's easy to see that the space in (1) is contained in the space in (2) which is contained in the space in (3). Furthermore, I think it's well known that (1) is, in general, strictly smaller than (3).

My question is what is known about (2). Does it have a name? I expect that it can be strictly smaller than (3), but are any examples known?

Edit: A little bit of motivation for why I'm thinking about (2). It has some nice properties that (3) doesn't, since its elements can be described: given $f$ in (2), for each $i$ we have a function $f_i$ on $E_i$, and by choosing $i$ large enough, we can ensure that $f_i$ "resembles" an element of the dual of $E_i$.

But (2) should still act a great deal like the true dual. (Formally, suppose $M$ is some model---say, of $ZFC$---where for every Banach space $X$, $\phi(X,X^*)$ holds, and which contains every element of our sequence $(E_i)$. Then in $(M)_U$, $(E_i)_U$ is a Banach space, and $M$ believes that (2) is the dual of $(E_i)_U$, so $M$ will satisfy $\phi((E_i)_U,(2))$. This may be enough for some purposes, or it may even imply that $\phi((E_i)_U,(2))$ holds in "the real world".)

Measurability of sets of pairs

2011-01-11T23:35:05Z

Suppose $(X,\mathcal{B},\mu)$ is a measure space, and let $B\subseteq X^2$ be an arbitrary set.

1) Is there a nice characterization of the circumstances under which there is a $\sigma$-algebra $\mathcal{C}\supseteq\mathcal{B}$ and a measure $\nu$ on $\mathcal{C}$ extending $\mu$ such that $B$ is measurable with respect to $\mathcal{C}\times\mathcal{C}$?

2) Is it possible for there to be distinct extensions $\mathcal{C}_1,\nu_1$ and $\mathcal{C}_2,\nu_2$ such that $B$ is measurable with respect to $\mathcal{C}_1\times\mathcal{C}_1$ and $\mathcal{C}_2\times\mathcal{C}_2$, but $\nu_1^2(B)\neq \nu_2^2(B)$?

3) If the answer to 2 is yes, is there a nice characterization of the circumstances under which extensions of $\mathcal{B}$ assign a unique value to the measure of $B$?

(If it helps, $\mathcal{B}$ can be assumed to have or not have nice properties like separability or being a regular Borel measure.)

Answer by Henry Towsner for Winning strategy at chomp (a chocolate bar game)?

2011-01-05T18:47:58Z

The non-constructive proof you refer to is proving a $\Pi_2$ statement, and therefore can be unwound to give an explicit proof. (This was pointed out to me by Mints, in the context of the game Hex, for which the same situation occurs.)

If the argument is what I expect it to be The strategy is to simply produce the tree of all possible moves and then label them as winning or losing (for player 1) by induction: and end-state is winning if player 2 takes the poison, a node where player 1 moves is winning if any of its children are winning, and a node where player 2 moves is winning if all of its children are winning. Roughly the same argument as in the non-constructive proof shows that the root node is winning, and so player 1's strategy is just to always move so they end up on a winning node.

(Of course, this isn't an elegant strategy, so there's still a reasonable open question there, but it is a known winning strategy in any formal sense of the term.)

Answer by Henry Towsner for Compactness theorem with preserved substructure

2010-12-22T16:06:43Z

No. Suppose the signature of T contains a distinguished symbol $\omega$, and $T$ contains the statements $R(\omega)$ and the infinitely many statements $1+\cdots+1<\omega$. Then any finite subset of $T$ has a model where $R$ is isomorphic to the reals and $\omega$ is interpreted as some large enough real. But in any model of the entire theory $T$, $\omega$ has to be interpreted as something larger than any real number.

Answer by Henry Towsner for logics restricted in arithmetic hierarchy

2010-11-24T01:25:53Z

There are some theories which, in essence, have only $\Pi^0_2$ formulas, in a way which I think captures what you're trying to capture. These theories are actually entirely quantifier free, but they allow free variables. A proof of some statement like $\phi(x,t)$ where $t$ is a term containing $x$ free is then viewed as a proof that $\forall x\exists y\phi(x,y)$. This only makes sense if you expect your witness $y$ to be given explicitly by a term, but that's often true, and will certainly be true if the kinds of things you're thinking about are Turing machines and discrete math.

Primitive recursive arithmetic is sometimes presented like this, and Godel's theory T (a theory of functionals) has this form as well. T is very similar to the $\lambda$-calculus, and I believe some theories of $\lambda$-calculus are also presented in the same way.

Answer by Henry Towsner for Strength of Transfinite Induction on the Difference Hierarchy

2010-11-27T19:25:49Z

I hope it's not too tacky to answer my own question now that I've had a few days and train rides to think about it.

The answer is that the proof theoretic ordinal of $\Delta-TI_0$ is the Howard-Bachmann ordinal (the ordinal of $\Pi^1_1-CA_0^-$, $\Pi^1_\infty-TI_0$, $ID_1$, and $KP\omega$).

The upper bound is easy to see ($\Delta-TI_0$ is a subtheory of $\Pi^1_\infty-TI_0$). (In fact, each instance of $\Delta-TI_0$ is provable in $\Pi^1_1-CA_0^-$, modulo some work to handle parameters in the formulas in $\Delta$.)

For the lower bound, consider the easy embedding of $ID_1$ into the language of second order arithmetic, in which arithmetic formulas map to arithmetic formulas and the least fixed point in $ID_1$ is mapped to a $\Pi^1_1$ formula. Then all formulas of $ID_1$ map to $\Delta$ formulas, so every axiom of $ID_1$ becomes a theorem of $\Delta-TI_0$ (the point here is that the only instances of induction axioms appearing in $ID_1$ are induction on $\Delta$ formulas). In particular, the proof of well-foundedness below the Howard-Bachmann ordinal can be carried out, unchanged, in $\Delta-TI_0$.

Strength of Transfinite Induction on the Difference Hierarchy

2010-11-23T19:13:15Z

I'm wondering if a particular theory of second order arithmetic has been studied or is known to be equivalent to some other theory.

Consider the formulas generated by $\Pi^1_1$ and $\Sigma^1_1$ formulas by propositional combinations (the title refers to this, rather informally, as the difference hierarchy, since these formulas are essentially the difference between two $\Pi^1_1$ formulas, the difference between two such, and so on). Let's call this class of formulas $\Delta$, for convenience.

My question is what the strength (either reverse mathematical or proof theoretic) of $\Delta-TI_0$, the theory which allows transfinite induction along any well-ordering for $\Delta$ formulas, is. This has proof theoretic strength strictly greater than $\Pi^1_2-TI_0$ (Rathjen and Weierman's proof that $\Pi^1_2-TI_0$ implies well-foundedness of $\psi\Omega^{\Omega^n}$ goes through, and furthermore this theory can carry out the key induction internally), and strictly less than $\Pi^1_1-CA_0$ (the standard argument that $\Pi^1_1-CA_0$ proves the existence of a $\beta$-model of $\Pi^1_\infty-TI_0$ suffices).

Answer by Henry Towsner for Examples of transformations which are weak-mixing but not strong-mixing

2010-11-23T18:07:18Z

Oddly, I was just looking for such a transformation last week, and ran across various "cutting-and-stacking" constructions, of which this paper by Chacon is a short, self-contained example. (This probably meets your first two conditions, but isn't a continuous transformation.)

Answer by Henry Towsner for Modal logic - satisfiability

2010-11-13T18:03:34Z

Your question is quite underspecified; it's not clear what language you're talking about (my guess is propositional logic plus box and diamond, which is the most common modal logic, but by no means the only one). Even then, there are many different proposed semantics, corresponding to different interpretations of diamond. Even if, by "satisfiable", you mean satisfiable in a possible world semantics (which later parts of your question imply), there are still questions to be decided about the kinds of relationships between the possible worlds allowed. However I think the statement is untrue in just about any system.

To see this, let $X$ be any propositional formula which is neither a tautology nor the negation of a tautology, and let $Y$ be $\neg X$. Take a model with just two worlds, interpret $\diamond$ as meaning "true in either world", and make $X$ true in one and false in the other. Then $\diamond X$ and $\diamond Y=\diamond \neg X$ are both true in every world of this model, but clearly $X\wedge Y=X\wedge\neg X$ is unsatisfiable.

Symmetric Proof that Product is Well-Founded

2010-10-06T21:15:00Z

This is a fairly minor, technical question, but I'll toss it out in case someone has a good idea on it.

Suppose $(X,<_X)$ and $(Y,<_Y)$ are well-founded orderings (not necessarily linearly ordered, though I don't think it matters). Consider the ordering ${<}$ on $X\times Y$ given by $(x',y') < (x,y)$ if $x'\leq x$ and $y'\leq y$, and either $x' < x$ or $y' < y$. Note that this is not the lexicographic ordering; indeed, it's symmetric.

Obviously $X\times Y$ is well-founded. Suppose I want to prove this carefully (by which I really mean "in the formal theory $ID_1$"); more precisely, let's take $X$ to be a set with two properties: $$Cl_X:\forall x(\forall x'<_X x. x'\in X)\rightarrow x\in X$$ and $$Ind_X: \forall Z[\forall x(\forall x'<_X x. x'\in Z)\rightarrow x\in Z)\rightarrow X\subseteq Z]$$ and similarly for $Y$. (These just characterize that $X$ is its own well-founded part.) I want to prove that for all $(x,y)\in X\times Y$, $(x,y)$ are in the well-founded part of $X\times Y$ under ${<}$; call the well-founded part of $X\times Y$ $Acc(X\times Y)$.

I know one way to prove this: for each $x\in X$, define $Y_x=\{y\in Y\mid (x,y)\in Acc(X\times Y)\}$ . Let $X'$ be the set of $x\in X$ such that $Y\subseteq Y_x$. Then it would be good enough to show that $X'$ satisfies the closure property, so I can apply $Ind_X$. To do this, in turn, I show that, if $Y\subseteq Y_{x'}$ for all $x'<_X x$ then $Y_x$ satisfies the closure property, so I can apply $Ind_Y$.

Of course, that means I know I second way: I could swap $X$ and $Y$ in the above proof. Moreover, when one works through the details, it's clear that I'm really proving that the lexicographic ordering is well-founded, and using the fact that ${<}$ is a subrelation of the lexicographic ordering.

Which brings me to my question: is there a proof that $Acc(X\times Y)=X\times Y$ which is symmetric?

Comment by Henry Towsner

2012-12-26T15:46:56Z

In answer to your question from Oct 23 (which I hadn't seen, and missed the notification for), the statement I made in my last comment doesn't need anything special about $A$. Both methods I described for finding the density of $A$ involve $A$; one of them additionally involves $\Gamma$. As for the regularity lemma, I'm afraid I don't see the similarity beyond the fact that both mention partitions.

Comment by Henry Towsner

2012-10-23T15:12:12Z

@vzn: The graph analog is the following: suppose $A$ is a subgraph of the random graph $\Gamma$, and I want to know the density of $A$. One way to find this is to divide the number of edges in $A$ by the number of edges in $\Gamma$. Another way is to look at each vertex $x$, and calculate $N_A(x)/N_\Gamma(x)$, and then take the average value of this to be the density of $A$. If $\Gamma$ is complete, these obviously give the same value. If $\Gamma$ is random then these should give roughly the same value because $N_\Gamma(x)$ is close to constant. (By $N_\Gamma(x)$, I mean the neighborhood.)

Comment by Henry Towsner

2012-10-19T12:23:16Z

@vzn: I need the situation where n' is fixed and n is arbitrarily large relative to that, so $n>>n'$ is really the only condition on $n'$.

Comment by Henry Towsner

2012-10-03T14:50:27Z

@vzn: No. I corrected a typo: it should say that H is a graph on n' vertices. I expect to find many copies of H in $(G,\Gamma)$.

Comment by Henry Towsner

2012-09-17T16:07:54Z

It's my understanding that the application to combinatorics actually came by this route: Galvin had noted that the equivalence between the existence of an idempotent ultrafilter and Hindman's Theorem, but it was a while before someone familiar with the work on enveloping semigroups (Glazer, specifically) pointed out that the proof of existence had actually been known for some time under a different name.

Comment by Henry Towsner

2012-06-30T00:18:31Z

Don't the existing notions of large cardinals already do this? Let $M_1$ is a model of ZFC+"there is an inaccessible", and let $M_0$ consist of those sets of size hereditarily smaller than the least inaccessible of $M_1$. This seems to be precisely the situation you describe. The "small" (sub-measurable) large cardinal notions are then the sorts of chains of increasing models of ZFC you describe.

Comment by Henry Towsner

2012-06-19T21:53:19Z

Whether or not the convex sets form a GC class depends on the measure (I was basing the statement on "Glivenko-Cantelli Theorems for Classes of Convex Sets", which shows that they are for various measures). I guess one way to apply the (p,q) theorem would be to choose a measure for which the convex sets fail to satisfy Glivenko-Cantelli, and use that measure to construct a (p,q) family, but if that's the only way to generate (p,q) families, it doesn't address the VC dimension case, since VC sets will satisfy Glivenko-Cantelli for any measure.

Comment by Henry Towsner

2012-05-17T14:58:34Z

"In computer science, there's a systematic way to check if your code is buggy or not as you write code". Surely the unsolvability of the halting problem tells us this isn't true.

Comment by Henry Towsner

2012-05-14T17:46:52Z

I'm not sure Kruskal's tree theorem is nonconstructive. I recall seeing several approaches to constructive proofs, though the only one I can find quickly is Wim Veldman's "An intuitionistic proof of Kruskal's Theorem".

Comment by Henry Towsner

2012-05-08T12:56:22Z

As stated, the answer is no: take $\phi(S)$ to be $\{0\}$ if $S=\{0\}$ and $S\setminus\{0\}$ otherwise. The, no matter what ultrafilter you use, the only way to have 0 present in almost every $\phi(S_i)$ is to have them all be $\{0\}$, in which case no other number can be. One can make $\alpha$ smaller and still have a counterexample by only removing anything from sufficiently large sets; if the size of the $S_i$ is bounded almost everywhere, only a few $F_s$ can be large, and if the $S_i$ grow to be unbounded, 0 is almost always removed.

Comment by Henry Towsner

2012-05-06T14:25:30Z

This isn't the first time you've made assertions to the effect that set theorists are unaware that most elements of an uncountable set don't have finite representations. In actuality, this is a well-known fact routinely taught to undergraduates.

Comment by Henry Towsner

2012-04-12T22:05:52Z

I've found Tao's notes (the ones Ben Green is referring to above), terrytao.wordpress.com/2009/04/14/…, to be very useful.

Comment by Henry Towsner

2012-04-12T18:57:51Z

The wikipedia article pretty clearly points out that the actual normal form is $U(\mu y. R(x_1,\ldots,x_n,y))$, where $U$ and $R$ are both primitive recursive. So $h(x,y)$ may require the application of another primitive recursive function to $\mu z. R(x,y,z)$.

Comment by Henry Towsner

2012-04-08T21:34:07Z

Derivation tree with what axioms and rules? There isn't a canonical answer for second-order logic; "full" second order logic, where the range of quantification is understood to be all sets and predicates fails compactness, and therefore doesn't have any conventional proof system. The usual alternative is a first-order formulation where functions and predicates are just objects of a different sort, together with comprehension principles (as in reverse math or ZFC); but this is actually first-order logic.

Comment by Henry Towsner

2012-04-07T23:22:08Z

I didn't say we can't prove that the reduction is guaranteed to work, I said we can't prove it in the same system we want to apply it to. I'm only guessing what you mean by "a natural example where this reduction is not working" (for instance, I still don't know what "this reduction" is), but why do you think there are any such examples at all? You can't prove, in Peano arithmetic, that every proof has a corresponding cut-free proof, but you won't find a counter-example, because every proof does have a cut-free version, and this can be proven...but in a stronger system.