User alex lupsasca - MathOverflow

Surreal Numbers and Set Theory

2011-07-21T20:52:19Z

Hello,

I looked through MathOverflow's existing entries but couldn't find a satisfactory answer to the following question:

What is the relationship between No, Conway's class of surreal numbers, and V, the Von Neumann set-theoretical universe?

In particular, does V contain all the surreal numbers? If so, then is there a characterization of the surreal numbers as sets in V? And does No contain large cardinals?

I came across surreal numbers recently, but was surprised by the seeming lack of discussion of their relationship to traditional set theory. If they are a subclass of V, then I suppose that could explain why so few people are studying them.

Thank you, Alex

Logically independent but true sentences

2010-08-08T18:36:14Z

My question is of a logical nature and concerns what I perceive to be two different types of mathematical independence.

Suppose we have a (sufficiently strong) axiomatic theory $T$. Gödel's Incompleteness Theorems state that:

$T$ is not a complete theory. That is, there is a sentence (expressible in the language of the theory) which is true, but not provable in the theory. In what follows, I will refer to such a sentence as a Gödel sentence and denote it by $G$.
$T$ cannot prove its own consistency. That is, assuming that $T$ is consistent, $\not\vdash_T\mathrm{Con}(T)$.

For my question to make sense, I must lay out the following principle, which I take to be "self-evident" (by which I mean that I believe most people would endorse it):

'If one is committed to a theory $T$, then one is also committed to $\mathrm{Con}(T)$.'

In other words, suppose that I accept the axioms of $PA$ (for instance). That means that I am committed to $PA$, in the sense that I believe it to be true, and therefore consistent. As such, it would be incoherent for me to disbelieve $\mathrm{Con}(PA)$.

This situation gives rise to the following state of affairs:

On the one hand, there are statements which are independent from a theory $T$, but whose truth is nevertheless implied by $T$, even though $T$ cannot prove them. This is the paradigm of the First Gödel Theorem (cited above) applied to arithmetic: in the context of $PA$, it says that there is a Gödel sentence $G$ which is not provable in $PA$, but that if $PA$ is consistent, then $G$ must nevertheless be true. Thus, if one is committed to $PA$, one is committed to $\mathrm{Con}(PA)$ (by the above principle) and therefore one is committed to the truth of $G$.
On the other hand, there are statements which are independent from a theory $T$, and in addition, no judgment regarding their truth value may be inferred from $T$. This is the paradigm of Set Theory ($T=ZFC$) and the Continuum Hypothesis ($CH$). One's commitment to $ZFC$ does not imply anything about the truth of $CH$, since both $ZFC+CH$ and $ZFC+\neg CH$ are consistent. Note that this is different from the first case, in which $PA+\neg G$ is inconsistent.

In essence, I see a dichotomy between statements which are independent from a theory $T$ and also from $\mathrm{Con}(T)$, and those which are independent from $T$ but nevertheless implied by $\mathrm{Con}(T)$. I am tempted to say that there are two types of logical independence; is such a division valid, or would anyone care to contest it?

In case this is a very well-known issue, are there any other examples (aside from Gödel sentences) of statements which are independent from a theory but provable if one assumes consistency? In particular, I am wondering if there are any "natural" such questions. (Of course, the statement $\mathrm{Con}(T)$ is itself an example, albeit a trivial one.)

Thank you!

Answer by Alex Lupsasca for (Non?)-linearity of the consistency strength ordering in ZF

2011-03-28T00:32:35Z

My understanding is that the large cardinals are indeed linearly ordered, which is a remarkable fact. Of course, it is not a theorem (nor could it ever be?), but merely an empirical fact; still, there is no known explanation for this completely surprising coincidence.

On the other hand, there are sentences $\sigma$ such that $T+\sigma>T$ and $T+\neg\sigma>T$. These are called "Double jump sentences" and though they are rare, a number of them exist. Thus, $\le_{cons}$ is not linear, though the counterexamples are quite contrived (none of the known ones would be called "natural" by a mathematician).

You can read more about Double jump sentences (and find references) here:

http://plato.stanford.edu/entries/independence-large-cardinals/#IntHie

I hope this answers your question to your satisfaction!

Completion of ZFC

2010-11-22T05:23:55Z

I attended a talk given by W. Hugh Woodin regarding the Ultimate L axiom and I wanted to verify my current understanding of what the search for this axiom means. I find it to be a fascinating topic but the details are so far beyond my grasp.

Given the language of set theory, one can write down a multitude of first-order sentences. By Godel's Incompleteness Theorem, it is known that from the ZFC axioms one can only derive the truth-values of a (small) fragment of these sentences.

In the past, it was hoped (by Godel, among others) that the Large Cardinal Axiom hierarchy would provide an infinite ladder of axioms of increasing strength such that any first-order sentence in the language of set theory would be either provable or refutable from ZFC + LCA for some suitable LCA.

However, it is now known (?) that the LCA hierarchy (pictorially represented as the vertical spine of the set-theoretic universe V) is not enough to settle all such questions. In particular, there is an additional horizontal "degree of freedom" due to Cohen forcing: for instance, when it comes to CH, it is known (or merely believed?) that both CH and ~CH are consistent with the LCA hierarchy.

Now, let a "completion of ZFC" be an assignment of truth-values to every first-order sentence in the language of set theory, such that a sentence is true whenever ZFC proves that sentence; moreover, for the other sentences (i.e. those which are undecidable in ZFC) the assignment of truth-values must be consistent.

My understanding of Ultimate L is that it picks out a unique completion of ZFC as being the "correct" one; that is, even though Cohen forcing allows us to have models (and therefore completions) of both ZFC + CH and also of ZFC + ~CH, Ultimate L eliminates the horizontal ambiguity and provides us with a unique completion of ZFC in which the truth-values of first-order sentences only depend on the vertical LCA hierarchy.

Is my understanding correct? And how do we know that there are (infinitely) many different completions of ZFC in the first place? Could it be that there is no way to consistently assign truth-values to all first-order sentences, i.e. that no completion exists?

Also, how would we know that Ultimate L + LCA picks out a unique completion (as opposed to a class of completions)? And would it be a valid completion (does consistency of ZFC + Ultimate L follow from Con ZFC)?

I would appreciate answers to any of the above questions, as I can't find anything on this topic in the literature. Thank you!

Difficult Infinite Sum

2010-09-29T05:49:58Z

Does anyone know of a way to simplify this sum?

$$S(n)=\sum_{j=1}^{\rho(n)}\sum_{k=1}^\infty\frac{\sin[2\pi k n 2^{-j}]-\sin[2\pi k (n-1) 2^{-j}]}{k}$$

where $\rho(n)=[\log_2(n)]$ (and $[x]$ denotes the greatest integer less than $x$).

Note: This question is a follow-up to a previous question I asked: http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer

EDIT: After following all the given suggestions, I found that for integer $n$,

$$\frac{S(n)}{\pi}=2^{-\rho(n)}-1+\frac{1}{1+(-1)^n}\sum_{j=1}^{\rho(n)}\left[\frac{n}{2^j}\right]-\left[\frac{n-1}{2^j}\right].$$

This is pretty much what I started with in my previous post, so if anyone knows of a way to take this sum, please let me know. Anyway, I will leave this result here in case anyone ever comes across $S(n)$ in some other context. Thanks to everyone who helped.

Greatest power of two dividing an integer

2010-06-28T20:16:40Z

Does anyone know of a closed form for the function on $\mathbb{N}$ which returns the greatest power of two which divides a given integer?

To be more precise, any positive integer $n\in\mathbb{N}$ can be uniquely expressed as $n=2^pq$ where $p,q\in\mathbb{N}$ and furthermore $q\equiv1\mod2$. I am looking for a closed form of the resulting function $f:\mathbb{N}\to\mathbb{N}$ which is such that $f:n\mapsto p$, as defined e.g. on Wikipedia.

As a starting point, I constructed a summation which does the job: $$f(n)=\sum_{j=1}^{\rho(n)}\left(\prod_{i=1}^{j}\cos\left[\frac{\pi n}{2^i}\right]\right)^2$$ where $\rho(n)=\lfloor\log_2n\rfloor$. Sadly, this expression is not very useful, and I would prefer a closed form expression. Using Morrie's Law, the product can be converted to a limit as follows: $$f(n)=\lim_{\epsilon\to0}t[\pi(n+\epsilon),\rho(n)]$$ where $$t[x,m]=\sum_{j=1}^{m}\left(\frac{2^{-j}\sin[x]\cos[x]}{\sin[2^{-j}x]}\right)^2$$ However, I cannot find a closed form for this summation...

So in summary, I'd be grateful if anyone could give me an expression for $t(x,m)$ which would make my version of $f$ usable, or if anyone could tell me another such $f$.

Thanks!

EDIT: I followed Gerry's answer and derived the following Fourier series for $f$:

$$f(n)=(1+\cos[\pi n])\left(1-2^{-\rho(n)}+\sum_{j=1}^{\rho(n)}\sum_{k=1}^\infty\frac{\sin[2\pi k n 2^{-j}]-\sin[2\pi k (n-1) 2^{-j}]}{k}\right)$$

I will try to further simplify this...

Principal Minors of Matrix Product

2010-09-12T01:21:08Z

Suppose $A$ is a positive definite matrix and $B$ is a non-symmetric matrix with all positive principal minors.

Is their product $AB$ a matrix with all positive principal minors?

I believe the answer is yes, and I have been trying to find a proof but got stuck along the way. The wiki page for minor gives a corollary to the Cauchy-Binet formula which I think may be of use: http://en.wikipedia.org/wiki/Minor_%28linear_algebra%29#Applications

Thank you, Alex

Set theoretical realizations of the hidden variables program in quantum mechanics

2010-06-30T16:42:15Z

The hidden variables program in quantum mechanics has been largely discredited by two powerful theorems, namely those of Bell and Kochen/Specker. Nonetheless, this program retains a certain philosophical appeal ("God does not play dice" and all that jazz) so I won't bother to motivate my interest in the topic.

More specifically, I am investigating recent efforts to construct alternative frameworks for QM in which hidden variables are possible, thereby making the theory deterministic/realistic, etc. In particular, there are two very intriguing papers, one by William Boos and the other by Robert Van Wesep, which make use of set theoretical tools to create (plausible?) hidden variable theories:

William Boos (1996) claims that random ultrafilters can provide a realization of the hidden variable program: http://www.springerlink.com/content/n3gr194551472536/
Robert Van Wesep (2006) argues that the hidden variable program is entirely characterized by generic filters and uses forcing techniques on the algebra of quantum propositions: http://arxiv.org/abs/quant-ph/0506040

Interestingly, both authors use related techniques (ultrafilters & forcing) which perhaps indicates that they are on to something... However, the papers are very technical and I do not fully understand their results; sadly, I could not locate any reviews of either paper online (which is surprising to me, considering how intriguing these papers are).

So my question is the following: has anyone read these papers, and if so, could you please comment on them?

(Although the question ultimately relates to physics, I feel that the highly mathematical nature of the methods used in these papers (and their beauty!) should appeal to the audience of Math Overflow, and indeed, I hope that someone here has already perused them...)

Thank you!

PS: Boos' paper is not freely available from the publisher, but a copy exists online: http://uploading.com/files/37m88a11/boos%2Bultrafilters.pdf/

Comment by Alex Lupsasca

2011-07-23T08:34:34Z

Thank you for your answer! So $V$ also contains $\omega/2$, $\omega-1$, $\sqrt{\omega}$, etc. but these numbers don't appear as stages in the cumulative hierarchy $V_\alpha$?

Comment by Alex Lupsasca

2011-03-30T19:39:30Z

You are entirely right; I stand corrected.

Comment by Alex Lupsasca

2010-11-23T14:41:59Z

Thank you for your answer :) As for your first paragraph: Ultimate L does not pick a unique completion of ZFC because of Godel incompleteness; but assuming that the LCA hierarchy is indeed linearly ordered, then doesn't Ultimate L + LCA pick out a unique completion? That is, I thought that the two together remove both the horizontal and vertical ambiguity.

Comment by Alex Lupsasca

2010-11-23T14:38:07Z

Thank you for bringing my attention to Lindenbaum's lemma; that does indeed answer one of my questions. Thank you :)

Comment by Alex Lupsasca

2010-11-23T05:34:20Z

Thank you for this long and thoughtful answer! I am more intrigued than ever!

Comment by Alex Lupsasca

2010-11-23T04:18:47Z

Well, using the solution in terms of logarithms and then in terms of arguments (given by Stopple) below, one can obtain (by using arctan(y/x) as argument) a sum with terms of the form arccot(tan x) which finally simplifies to the expression given in the above edit.

Comment by Alex Lupsasca

2010-11-22T06:54:16Z

@sleepless: I think I was too hasty; there was a mistake in what I computed :(

Comment by Alex Lupsasca

2010-11-22T05:29:24Z

I believe that Poisson summation eventually leads back to $[n/2]-[(n-1)/2]+[n/4]-[(n-1)/4]+[n/8]-[(n-1)/8]+\dots$ which is what I started with in the first place and is of little use to me... Thank you for the help nevertheless; this was an instructive experience :)

Comment by Alex Lupsasca

2010-10-02T20:40:15Z

I seem to be getting the same expression that I started with (in my previous post) and was trying to simplify...

Comment by Alex Lupsasca

2010-09-30T00:15:30Z

I tried to apply the Poisson summation but got a function which doesn't match the sum... I must be making a mistake somewhere. One more thing: I thought that sinc(0) is usually defined to be 1?

Comment by Alex Lupsasca

2010-09-29T21:42:42Z

This expression is indeterminate for integer n... Can you think of a way around that?

Comment by Alex Lupsasca

2010-09-29T05:38:14Z

Thanks! Did you derive this yourself, or could you point me to a reference?

Comment by Alex Lupsasca

2010-09-12T03:43:27Z

Thank you. This is probably why I couldn't finish my proof :)

Comment by Alex Lupsasca

2010-08-11T17:50:04Z

Thank you for this great answer! Francois's reply, which mentions the Paris-Harrington Theorem, directly answers my question and so I was compelled to choose it over yours. Nonetheless, I find your contribution much more informative: assuming the principle that " is provable implies " (which I am certainly inclined to believe) allows one to prove all the arithmetical truths! If I understand correctly, this is a very satisfying state of affairs :)

Comment by Alex Lupsasca

2010-08-11T17:45:02Z

Thank you for your prompt answer! The Paris-Harrington Theorem really does seem like the example I was looking for.