User noah s - MathOverflow

Answer by Noah S for List of Whitehead-like Problems

2013-06-14T17:16:33Z

One that - to the best of my knowledge - is still a huge open problem is about non-standard models of $PA$ and Scott systems. A Scott system $S$ is a set of reals such that $(\omega, S)\models WKL_0$; that is, $S$ is closed under Turing reducibility and has paths through all of its trees. Now, given a non-standard model of arithmetic $M\models PA$, we say a real $X$ is coded in $M$ if $$ \exists a\in M\forall b\in M\cap\omega(M\models b\vert a\iff b\in X). $$ (It's a slight abuse of notation to write "$M\cap \omega$" for the standard part of $M$, but this is common.) The set of reals coded in $M$ is called the standard system of $M$ and is denoted by "$SSy(M)$."

A beautiful short argument shows that $SSy(M)$ is always a Scott set: infinite binary trees in $SSy(M)$ come from binary trees of nonstandard height in $M$, by an overspill argument, which must have paths of internally-finite but externally-infinite length; and these long paths corresond to infinite paths in $SSy(M)$. Conversely, it is easy to prove that every countable Scott set is the standard system of some model of $PA$.

The major open question is whether the stronger statement, "Every Scott set is the standard system of a model of $PA$," is true.

(Actually, we can do a bit better than "countable": by a union of chains argument, every Scott set of size $\le\aleph_1$ is a standard system, so in the presence of $CH$ the problem is solved. However, I still think this fits the question, because what's really going on is that countable=easy and $\aleph_1$ is "close enough" to countable to still be tractable.)

Answer by Noah S for Random infinite sequence : Can machines generate truly random sequences.

2013-06-11T15:58:50Z

(I'm really not sure this is appropriate for MO - mathstackexchange might be better - but this does lead into some quite interesting subjects, so I'll give a go at answering.)

So first, let me make a few obvious comments. Certainly a truly random source cannot be distinguished from a nonrandom source in a finite amount of time: if I have an agent who correctly identifies a sequence $S$ as random after the first $n$ bits, then that same agent will guess that a sequence $T$ agreeing with $S$ on the first $n$ bits is random; but there are many such computable $T$.

So the "right" way to ask this question might be: given a binary sequence $S$, is there some sort of effective test which at each moment $n$ makes a guess "random/nonrandom" (really: "noncomputable/computable," but I think this is what the OP means by "random?") and $S$ is in fact random iff there are infinitely many $n$ at which the test guesses "random"? In particular, the test cannot refuse to guess (although at a given $n$, it may take an arbitrarily long time). (There are other ways we could modify the question, but let's take this one to start with.)

Now the answer is "no," there is no such test. For suppose $\mathfrak{t}$ were such a test. Then we could build a computable sequence $S$, a finite initial segment at a time, by always searching for some way to extend $S$ so that $\mathfrak{t}$ says "random" at least once more than it already has. Either this process becomes impossible at some point - in which case $\mathfrak{t}$ is terrible, since it won't recognize as random any random sequence which begins with the finite initial segment of $S$ built so far - or this process defines a computable sequence $S$ which $\mathfrak{t}$ infinitely often thinks is random. So every specific effective randomness test fails, somehow.

On the other hand, there is no "pseudorandom" computable real: if $S$ is a computable sequence, there is a test for randomness that guesses "nonrandom" iff the string it's presented with agrees with $S$. This test is absolutely terrible, but it does successfully identify all random strings as random, and $S$ as nonrandom. Another way of phrasing it: in your words, there will always be the possibility of a "judge" who happens to know just the index for the computable sequence, and bases his decisions entirely on that.

You might object that this treats "computable sequences" in a broad way. An interesting question we can ask is the following: let's say I'm presented, one bit at a time, with a sequence I am told is computable. Can I find an index for it? This is the beginning of computability-theoretic learning theory; Jain and Stephan's paper "A tour of robust learning" might be interesting to you. (I'll add a couple other sources, which I vaguely remember but can't find right now, as I track them down.)

Answer by Noah S for The paradox with the first uncountable ordinal

2013-06-07T00:05:15Z

The answers already given amount to, "With probability 1, a probability-zero event will happen when you do something randomly." This is absolutely correct, but let me give a slightly different take on the OP's argument that is more specifically about well-orderings.

Let's simplify matters, and just do the following: select $\alpha,\beta\in\omega_1$ randomly. What is the probability that $\alpha<\beta$ (in the usual ordering on $\omega_1$)? Naive arguments show that the probability is 1. But by those same arguments, the probability that $\beta<\alpha$ is 1.

In the reals context, the paradox is: if I select a real $r=\langle s_0, s_1\rangle$, what is the probability that $r\in X$, where $$ X=\lbrace u=\langle v_0, v_1\rangle: f^{-1}(v_0) < f^{-1}(v_1)\rbrace,$$ and in turn $$ f: \omega_1\rightarrow\mathbb{R} $$ is a bijection? (Note that this argument is really about well-orderings, and not just about the inevitability of probability-zero events.)

This is just Freiling's argument against $CH$ (see http://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry). This argument was discussed on MO here: http://mathoverflow.net/questions/49721/axiom-of-symmetry-aka-freilings-argument-against-ch. Briefly, the reason it isn't generally found convincing as an argument against $CH$ is that it tacitly assumes that the reals are well-orderable if and only if they are well-orderable in a measurable way. So if you believe that there are non-measurable sets, this argument really shouldn't be very convincing.

(On the other hand, if you find this argument intuitively appealing, maybe $L(\mathbb{R})$ is right for you!)

Answer by Noah S for Ontological status of some "sets" in ZFC

2013-06-04T21:43:43Z

Consider the following descriptions of sets:

(1) $X=\lbrace i\in\omega: i=0\rbrace=\lbrace0\rbrace$,

(2) $Y=\lbrace i\in\omega: i=0\iff CH, i=1\iff \neg CH\rbrace=\lbrace 0\rbrace$ or $\lbrace 1\rbrace$, and

(3) $Z=\lbrace i\in\omega: \text{ the $i$th Diophantine equation (in some natural listing) has an integral solution}\rbrace$.

Now, the short version is: $ZFC$ (actually, much less than $ZFC$) proves that $X$, $Y$, and $Z$ exist.

A slightly longer version, which might help you understand what's going on here: really, what I have is not three sets $X$, $Y$, and $Z$, but rather three first-order formulas $\phi_1(x), \phi_2(x)$, and $\phi_3(x)$ with a single free variable. Now, for every such formula $\phi(x)$, $ZFC$ proves that $$ \lbrace i\in\omega: \phi(i)\rbrace$$ exists; this is just Separation + Infinity.

There are really three potential issues here, and none of them have to do with the "ontological status" of (2).

First, there's the issue of Infinity: whether we believe that infinite sets exist. It's perfectly reasonable to discard infinite sets, but (a) most mathematicians don't, and (b) if you do, then presumably you aren't very interested in $ZFC$.
Second, there's the issue of incompleteness: among the three formulas "$\phi_2(x)$" (defining the set $Y$), "$x=0$," and "$x=1$," $ZFC$ can prove that two of those formulas are actually equivalent; but $ZFC$ cannot prove any specific equivalence. This is an issue with the underlying logic, not the sets: classical logic can (and does: Excluded Middle) prove $\theta\vee\psi$ without proving $\theta$ or $\psi$. This is one reason some people prefer intuitionistic logic, but it's not really an issue with sets (in my opinion). Certainly it's not really a paradox, just something which newcomers to logic might find surprising at first. EDIT: To explain a bit more why this isn't a set issue, but a logic issue, note that for any sets $A$ and $B$ and any formula $\phi$, $ZFC$ proves $$\exists C[(C=A\iff \phi)\wedge(C=B\iff \neg\phi)]. $$ So this really has nothing to do with the sets themselves.
Finally, there's the real set-theoretic issue: the third set, $Z$, has no finite description! (This is the solution to Hilbert's Tenth Problem by Davis, Matiyasevitch, Putnam, and Robinson.) Note that this is not a property of the description of $Z$, but rather a property of the set $Z$ itself. To my mind, this begins to get into the real ontological weirdness of set theories: the extent to which they demand the existence of "undescribable" (which can range anywhere from "not efficiently computable" to "incomputable" to "undefinable") sets. Is the powerset of $\omega$ describable? Is a well-ordering of the reals describable? Set theory is full of instances where sets are describable only in a very indirect sort of way, and this is interesting; but it's very much not an issue with (2), which is just a logical curiosity, and it's also not a paradox, but a necessary feature of taking mathematics beyond the finitary, which I think is a good thing.

Answer by Noah S for Order-independent properties arising naturally in mathematics

2013-05-30T21:44:43Z

An example and a counterexample at the same time: Dowker's Theorem. (See, for example, this question: http://mathoverflow.net/questions/108310/what-are-the-applications-of-dowkers-theorem.)

Dowker's theorem asserts that (the geometric realizations of) two simplicial complexes, $K$ and $L$, associated to a binary relation $R\subseteq X\times Y$ are homotopy equivalent. As I understand it, the proof of this equivalence requires a choice of ordering of the simplices; but the particular ordering used is not relevant, i.e., any total order can be used. (Please correct me if I'm wrong here!)

This is either an example, or a counterexample, depending how one looks at it. On the one hand, the equivalence of homotopy type between $K$ and $L$, as a proposition which is true, does not depend on the choice of ordering; on the other hand, in order to get a particular homotopy equivalence between $K$ and $L$, a choice of ordering is necessary: the equivalence provided by Dowker's theorem is not natural.

Answer by Noah S for Computability complexity of the first-order theory of arithmetic?

2013-05-29T02:29:14Z

If I understand the question you're asking, the theory of arithmetic in the language of PA is of degree $$0^{(\omega)}=\lbrace \langle x, y\rangle: x\in 0^{(y)}\rbrace,$$ the $\omega$th jump of the emptyset. To see why, just covince yourself that we can use one jump to tell whether a $\Sigma^0_1$ statement is true; two jumps to tell whether a $\Sigma^0_2$ statement is true; etc. (Actually, this just shows that the true theory of arithmetic is computable in $0^{(\omega)}$; this is, though, enough for your question. The other direction can be proved by coding Turing machines into the language of arithmetic, via Kleene's T predicate. That's definitely one of those "do-it-once-and-then-never-again" type of proofs.)

This is considerably smaller than the degree of Kleene's $\mathcal{O}$. To get an idea of just how much smaller it is, note that we can continue taking jumps past $\omega$: in fact, as long as $\alpha$ is a computable well-ordering, then $0^{(\alpha)}$ makes sense. Now, there are lots of computable ordinals: basically, any countable ordinal you can think of is computable (including the quite large proof-theoretic ordinals). Certainly, $\omega$ is very very small compared to $\omega_1^{CK}$, the first noncomputable ordinal. But each of these sets $0^{(\alpha)}$ for $\alpha$ computable is $\Delta^1_1$, that is, both $\Pi^1_1$ and $\Sigma^1_1$, and hence Kleene's $\mathcal{O}$ is much larger. See Sacks' book, "Higher Recursion Theory," for details on this and more.

As to who proved it, I believe that Kleene's paper which introduced the arithmetical hierarchy proved that the set of (Goedel numbers of) true $\Sigma^0_n$ sentences had degree $0^{(n)}$; I don't know whether he then explicitly observed the fact that the whole theory has degree $0^{(\omega)}$, but that follows immediately.

EDIT: Actually, the question of attribution might be a bit more subtle than that. The paper by Kleene which introduces the arithmetical hierarchy, "Recursive predicates and quantifiers" (http://www.jstor.org/stable/1990131?seq=1), was written in 1943; but I don't believe arbitrary Turing degrees (including the higher jumps) were treated explicitly until later (certainly no earlier than 1944, when Emil Post first posed his Problem, and no later than Kleene-Post 1954). By that time, though, the proof would certainly have been considered trivial from Kleene's work. The upshot is, I'm not sure when the statement "the true theory of $\mathbb{N}$ in the language of PA has degree $0^{(\omega)}$" was first explicitly stated.

FURTHER EDIT: Technically, my answer requires a bit of hyperarithmetic theory, which is maybe undesirable. Here's another way to show that the true theory of arithmetic is strictly weaker than Kleene's $\mathcal{O}$; this approach concludes that the theory is $\Delta^1_1$, which is still a bad upper bound, but enough to conclude that it's weaker than $\mathcal{O}$.

Given an arithmetic formula $\phi$, we can computably-in-$\phi$ come up with a game, $G_\phi$, in which player I tries to show $\phi$ is false and player II tries to show $\phi$ is true. This is described more in detail and generality in Vaananen's "Games and Models" (http://www.maths.manchester.ac.uk/logic/mathlogaps/workshop/ManchesterVaananen.pdf; it's what Vaananen calls the "semantic game"), where he calls it the "semantic game," and in other sources, where it's generally called "game semantics" for first-order logic. Basically, we first put $\phi$ into prenex normal form (which you should convince yourself we can do computably), and strip away the quantifiers one by one, with player I choosing values for each universally-quantified variable, and player II choosing values for each existentially-quantified variable. At the end of the game, a quantifier-free expression with no free variables is left; and player I wins iff that expression is false.

Now, player I has a winning strategy iff $\phi$ is false, and player II has a winning strategy iff $\phi$ is true. But saying that one player or another has a winning strategy is $\Sigma^1_1$: "there is a strategy (=real) such that no finite play (=finite sequence of natruals=natural) defeats it." So the set of Goedel numbers of true arithmetic statements is $\Sigma^1_1$, and the set of Goedel numbers of false arithmetic statements is also $\Sigma^1_1$. That's it!

[Note that the conclusion that "X wins the game" is $\Sigma^1_1$ relied on the fact that the game in question was clopen, i.e., guaranteed to end in finitely many moves; in particular, the semantic game has only as many moves as there are quantifiers in $\phi$. For a more complicated game, this would fail, and in fact open games - the simplest kind of game which can go on indefinitely - in which player II/Closed/Defender wins do not necessarily have winning strategies for II which are $\Delta^1_1$ in the game itself.]

Answer by Noah S for Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?

2013-05-26T18:25:10Z

EDIT: The other answers show that my intuition was wrong, and that in fact there is such a linear order in $ZFC$, so this answer (except the bit about determinacy) is superfluous.

Although it seems likely that $ZFC$ proves there is no such order, choice will certainly be necesary for such a proof: it is consistent with $ZF$ that $\mathbb{R}$ has infinite, Dedekind-finite subsets, which is exactly what you're asking for. (I'm looking for a reference . . . EDIT: Asaf gives a good reference in a comment, below.)

There can be no countable example of such an order, however; such an order can't embed $\mathbb{Q}$, and hence is scattered, and a result (I believe) of Jullien then lets us write it as a finite sum of indecomposable orders; it is then easy to see that the whole order embeds into a proper subset of itself.

If we assume the Axiom of Determinacy, then every uncountable set of reals has a perfect subset; this means there is no uncountable example of such an order, and hence by the above fact the answer to your question is no.

Under choice, things look a bit more complicated, but I suspect the answer is no; I'll post more if I can figure it out.

Answer by Noah S for Avoiding reflexive paradox in set theory

2013-05-24T00:44:47Z

As The User says in the comments, you still have a problem, aesthetically at least - in order to prevent the existence of "silly" models, you need some axiom asserting that $\in^*$ isn't too big. As is, a model in which $\in^*$ always holds between any $x$ and $y$ satisfies your axioms; this means that your separation axiom just asserts the existence of the empty set, and so any collection of sets containing the empty set can form a model of your axioms. In particular, your theory is now certainly consistent, since the structure consisting of a single object, interpreted as the emptyset, is a model.

This is the primary difficulty in creating a useful set theory - not avoiding the paradoxes, but avoiding them in such a way that the resulting theory has some semantic power, so that models of the theory all share some intuitive properties. Also, we want the theory to be powerful, in the sense that any of its models interpret the rest of mathematics. These two demands are actually tied together, since one of the semantic properties we tend to demand of a set theory is that its models function well as universes for mathematics. In this case, avoiding paradoxes too easily is actually in some sense a bad thing - having too many models can get in the way of interpretive power. For example, one theorem showing that ZFC is a powerful theory - the Reflection Theorem, that asserts that for each finite fragment F of ZFC, ZFC proves the consistency of F - can also be thought of as a near-inconsistency result: ZFC is "as close as possible" to inconsistency, in terms of what it says about its own finite fragments.

(This is not to argue that you should stop thinking about these things! I think coming up with alternate set theories is one of the best things a logician can do with their time; or at least that's how I justify it to my advisor! But it is a good idea to keep all of these things in one's mind. In particular, I recommend at the outset setting down a list of requirements you want your set theory to satisfy: is consistent relative to PA? interprets ZFC? is formulated in seven-valued infinitary logic?* since this will guide your process.)

* Nobody said those demands had to be reasonable, after all!

Answer by Noah S for Is deciding whether a Turing machine provably runs forever equivalent to the halting problem?

2013-05-22T02:53:14Z

It's late, so I might be making a mistake or several, but I think this works:

Assuming $ZF$ is consistent (I don't think soundness is necessary for this part), I'll show PROVELOOP can compute the set of $\Pi^0_1$ theorems of $ZF$.

Given a $\Pi^0_1$ sentence in the language of set theory $\varphi$, build in the usual way a machine $M$ which runs until it finds a counterexample to $\varphi$; $M$ provably loops iff $ZF$ proves $\varphi$. In one direction, if $ZF$ proves $\varphi$, then $M$ has to loop forever since $ZF$ is consistent; and what's more, as long as the construction of $M$ was sufficiently transparent, $ZF$ can prove this, so $\ulcorner M\urcorner\in PROVELOOP$. In the other direction, if $ZF$ proves $\neg\varphi$, then $ZF$ proves that $M$ halts; if $ZF$ is consistent, then that means $ZF$ does not prove that $M$ does not halt, so $\ulcorner M\urcorner\not\in PROVELOOP$.

Now, all I need to do is show that the set of $\Pi^0_1$ theorems of $ZF$ is equivalent to the halting problem, $H$. For some reason I'm having trouble doing this at the moment, but I think this is straightforward (can someone fill this gap?). I think it's in this second step that Soundness (or $\Sigma_1$-Soundness) will be necessary.

Lawvere's fixed point theorem and the Recursion Theorem

2013-05-19T22:52:33Z

Building off of Qiaochu's comment on my answer to a previous mathoverflow question, I would like to know: can the Recursion Theorem, $$\forall e\exists k[\Phi_e\text{ is total }\implies \Phi_{\Phi_e(k)}\cong\Phi_k],$$ be gotten as a corollary of Lawvere's Fixed Point Theorem: $$ \text{If $\mathcal{C}$ is Cartesian closed and }f: A\rightarrow B^A\text{ is an epimorphism, then every $g: B\rightarrow B$ has a fixed point.}$$

I tried to work this out myself, but I couldn't seem to come up with the right category to live in; I feel like the proof should be fairly simple, and quite illuminating. Alternatively, if it can't be done (at least in a reasonable way), I'd like to know what the obstacle is.

(I apologize if this question is too low-level for MO; my own background in category theorem is somewhat limited, so I don't know how whether this is actually a research-level question. As partial justification, I would like to point out that from a computability theory perspective, this doesn't seem entirely trivial.)

"Inverse problem" for Brauer groups

2013-05-16T00:18:59Z

This question is just a curiosity, but I'm really interested in the answer. It was originally posted on math.stackexchange (http://math.stackexchange.com/questions/368897/inverse-problem-for-brauer-groups), but hasn't received any responses despite some upvotes, so I'm posting it here.

Given a field $K$, we can form the set$^*$ $Br(K)$ consisting of equivalence classes of finite-dimensional central simple $K$-algebras which split over some Galois extension of $K$, modulo "are Morita-equivalent" (I hope I have that right, it's been a while). This set is actually a group, in a natural way: the tensor product over $K$ is well-defined on the equivalence classes, and has identity (the equivalence class of $K$ as an algebra over itself) and inverses (given by $R\mapsto R^{op}$). Actually $Br(K)$ turns out to be a second cohomology group, in a natural and useful way, but I don't really have a good understanding of that part.

My main question is, what groups are the Brauer group of some field? I know a couple trivial bits of the answer to this: $Br(K)$ is always abelian, and of cardinality at most $\aleph_0\times\vert K\vert$, and $Br(K)$ is always torsion. Within those constraints, I only know of one specific nontrivial Brauer group: $Br(\mathbb{R})=\mathbb{Z}/2\mathbb{Z}$ by Frobenius' Theorem on division algebras over $\mathbb{R}$. (I've seen the Brauer group of $\mathbb{Q}$ described by a short exact sequence, but I wasn't able to get an explicit description from that; is it known?) EDIT: As Emerton points out in a comment below, the Brauer group of $\mathbb{Q}$ (and much more) is known: it is $Br(\mathbb{Q})=\mathbb{Z}/2\mathbb{Z}\oplus\bigoplus_1^\infty\mathbb{Q}/\mathbb{Z}.$

My main question is: is there a known list of properties which are necessary and sufficient for a group to be $\cong Br(K)$ for some $K$?

There are many possible variations/elaborations of this question, which may not have deep significance but seem kind of interesting. For example, leaving the context of fields for a moment, there is an analogous notion of Brauer group for groups, and we can ask (although I'm not sure why we would ask): is there a group which is its own Brauer group? My second question is just: is there a good resource for this type of question, that is, for constructing Brauer groups of various objects to specification? I imagine the opposite direction (finding Brauer groups of fields we already care about) is much more useful, but I'm personally interested in this direction.

(As an aside, I'm not sure whether the "group theory" tag is appropriate here; if it is not, feel free to delete it, or let me know and I will delete it.)

$^*$ As a very minor aside, note that size issues don't arise here: since we specify "finite-dimensional," there are at most $\aleph_0\times\vert K\vert$ many such algebras up to isomorphism; using Scott's trick then lets us represent these equivalence classes in perfectly fine way.

Answer by Noah S for Is there any proof that you feel you do not "understand"?

2013-05-17T03:25:20Z

It took me a very long time to understand the Recursion Theorem. The proof is ridiculously simple: one clear observation about computability (there is a computable total $f$ such that if $\Phi_e(e)\downarrow$ then $\Phi_{f(e)}\cong\Phi_{\Phi_e(e)}$), followed by one line of mysterious symbol-pushing. It only became meaningful to me when I was told to think of it as a diagonal argument that failed (which was also the way it was discovered, if I recall correctly).

Actually, that piece of explanation really changed the way I think about mathematics: it drove home the value of the heuristic principle that if an informal argument doesn't actually work, then there has to be some thing - which will be mathematically interesting - which is actively blocking it. Not always true, but extremely often useful for understanding why math is the way it is (at least for me).

Answer by Noah S for Basic results with three or more hypotheses

2013-05-16T06:36:53Z

Lindstrom's theorem: if $L$ is a regular logic which is compact, has the Lowenheim-Skolem property, and extends first-order logic, then $L$ is (equivalent to) first-order logic. Compactness and the Lowenheim-Skolem property are both very important notions, which are (in abstract model theory) often studied independently of each other; regularity and extending first-order logic are slightly more minor, but I still think they are substantial enough to count as individual hypotheses. ("Regular" means that given a formula $\phi$ and a predicate symbol $U$, there is a single formula $\phi^U$ such that for all structures $M$ in a language containing $U$ and all symbols used in $\phi$, we have $M\models\phi^U\iff M^U\models\phi$.)

Answer by Noah S for Are the two meanings of "undecidable" related?

2013-05-16T06:08:24Z

My opinion is that the answer to your question is "no;" these are fundamentally different concepts, and should be called by different names.

The first kind of undecidability you mention is absolute: it doesn't depend on an ambient theory. Of course, the second kind of undecidability is relative to a specific theory, and given any proposition $p$ there is some true axiomatizable theory $T$ which decides it (e.g., either $PA\cup\lbrace p\rbrace$ or $PA\cup\lbrace\neg p\rbrace$). The absolute version is much stronger, in the following sense: if $P(x)$ is a formula which is undecidable in the first sense, then for any axiomatizable true theory $T$, there must be some $m$ such that $P(m)$ is undecidable (in the second sense) in $T$.

I think the only sense in which these two notions are closely related is that historically they come out of the same machinery: Goedel's 1931 paper for the second sense of undecidability and Turing's 1936 paper for the first sense both use the same idea of representing computational systems inside the language of arithmetic. Besides this, though, the substance of the two notions is completely different (at least, that's my perspective; I'd be interested if anyone disagrees).

(One last thought: really, the first sense of undecidability is a special case of the more broad notion of "non-computable function." Proving the existence of a non-computable function just takes a counting argument; getting a definable non-computable function, which is what your first notion of undecidability is essentially talking about, takes more work.)

Answer by Noah S for A Model where Dedekind Reals and Cauchy Reals are Different

2013-04-24T07:34:38Z

In Andrej's answer, a "background theory" of something like ZF formulated in intuitionistic logic is assumed. Let me give a slightly different approach.

(EDIT: I did not mean that Andrej's answer used the full power of ZF; I just meant that it seemed to take place in an informal setting with the flavor of ZF. I just wanted to bring up the distinction between the ways in which these separations can happen - for me, the intuitionistic set theory/topos version "feels different" than the reverse math version (I have a very coarse picture of things, here: for me, e.g., ZFC+large cardinals and ETCS give the same, extremely broadly speaking, "picture of the world," which $RCA_0$ does not). I definitely didn't mean to say that Andrej used such-and-such axioms.)

Instead of looking at a set theory, we can approach the question from the perspective of computability theory and reverse mathematics. The theory $RCA_0$ basically consists of "computable" reasoning about natural numbers and sets of natural numbers; for details, see Simpson's book, the first chapter of which is an excellent introduction and motivation for the subject, and is available from his website: http://www.math.psu.edu/simpson/sosoa/chapter1.pdf. $RCA_0$ is the natural base theory to look at if we are interested in the computability side of things, but also want to use classical logic (one might argue that if we care about computability, we shouldn't use classical logic; I don't hold this opinion, but I'm sympathetic to it).

Now, computability theoretically, there are two reasonable notions of "computable Cauchy sequence of rationals": a computable sequence of rational numbers which happens to be a Cauchy sequence classically, or a computable sequence of rational numbers together with a computable function $f$ (a modulus) such that for all rational $\epsilon$, any terms in the sequence after the $f(\epsilon)$th term are $<\epsilon$ apart. These latter sequences can be called "effectively Cauchy," and the statement that every Cauchy sequence has a modulus is equivalent over $RCA_0$ to the much stronger system $ACA_0$.

On the other side of things, there are three reasonable notions of "computable Dedekind cut of rationals": a nonempty computable set of rational numbers which is closed upwards, together with a nonempty computable set of rational numbers which is closed downwards, the two of which are disjoint and omit at most one rational number; a nonempty c.e. set of rational numbers which is closed upwards; or a nonempty c.e. set of rational numbers which is closed downwards. The latter correspond to reals which are "semicomputable from above/below"; see for example http://arxiv.org/pdf/1110.5028.pdf. Again, I believe the equivalence of all these notions is equivalent over $RCA_0$ to $ACA_0$.

Now versions of all of these definitions can be made within $RCA_0$, and appropriate questions about equality can be asked (although one does have to be careful when formalizing these sorts of things). My recollection is that at least one possible version results in $RCA_0$ not proving their equivalence; I'll add the details when I'm more awake.

What can the degrees of constructibility be?

2013-02-22T01:06:44Z

If $r, s\in\mathbb{R}$, we say $r$ is constructible relative to $s$ - and write $r\le_cs$ - if $r\in L[s]$. Modding out by the induced equivalence relation $\equiv_c$, we get a partial order, the degrees of constructibility $\mathcal{C}$. This poset is extremely dependent on the ambient set theory. If $V=L$, the poset is trivial, whereas the existence of a Cohen real automatically leads to a very complicated structure (see, e.g., the paper "The degrees of constructibility of Cohen reals" by Abraham and Shore).

My question is basically, what is known about the possible posets which $\mathcal{C}$ could be? I am especially interested in properties of $\mathcal{C}$ which follow from large cardinals. For example, if $0^\sharp$ exists, then we can deduce that $\mathcal{C}$ has size $2^{\aleph_0}$, which is the maximum possible; presumably this actually gives us a lot more.

As a sub-question, what is a good source for learning about techniques for building a model of $ZFC$ in which $\mathcal{C}$ has some prescribed properties?

ADDED: I'm most interested in what can be said when the size of $\mathcal{C}$ is assumed to be $2^{\aleph_0}$. As a particular example, the paper "Hinges and automorphisms of the degrees of non-constructibility" by P. Farrington (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.3272) has, as Lemma 2.5, the following (CAVEAT: Farrington's paper actually gives the wrong definition of "hinge," which was corrected in Lubarsky's review in the JSL in 1989):

Suppose that $\omega_2^L<\omega_1$. Then there is no nontrivial automorphism of $\mathcal{C}$.

(Now $\omega_2^L<\omega_1$ (and much more!) is a consequence of the existence of $0^\sharp$, so this is a very weak hypothesis.) Results like this are exactly what I'm looking for: properties $\mathcal{C}$ which follow from large cardinals, and in particular can hold under the assumption $\vert\mathcal{C}\vert=2^{\aleph_0}$.

Answer by Noah S for Countable open subgroup

2013-04-11T02:54:42Z

I believe the question the poster is trying to ask is, "Why is theorem 3.6 of the article http://link.springer.com/article/10.1023%2FA%3A1010466924961#page-1 true?" Certainly this seems to be something the OP cares about, so I'll address it. (I think this question is borderline for MO, since the answer seems to be rather trivial - feel free to downvote this answer if you think the question is definitely inappropriate, although please say that's why you're downvoting.)

Definition (1.1 in the cited paper): If $G$ is a group, a $T$-sequence $\alpha=\langle a_n\rangle_{n\in\omega}$ is a sequence of elements of $G$ which converges to 0 (the authors say "vanishes;" I presume that's what this means) in some non-discrete topology on $G$. A topology $\tau$ on $G$ is determined by $\alpha$ if $\tau$ is a maximal topology in which $\alpha$ converges to 0.

The theorem the OP is asking about is:

Theorem (3.6): If $\tau_1$ is a topology on an infinite group $G$ determined by some $T$-sequence,then $\tau_1$ is complemented by some topology $\tau_2$ also determined by a $T$-sequence.

The proof of this theorem, in its entirety, is:

Note that $(G, \tau_1)$ has a countable open subgroup. Now, apply Theorems 1.6 and 3.5 and Lemma 2.3.

The part the OP seems to be asking about is the first sentence. The key is that in the theorem's hypothesis the topological group $(G, \tau_1)$ is assumed to be generated by some $T$-sequence $\alpha$. The reason this matters is that if $(G, \tau_1)$ is determined by $\alpha$, then clearly $A\cup\lbrace 0\rbrace$, where $A$ is the underlying set of $\alpha$, must be open - since $\tau_1$ is maximal among the topologies in which $\alpha$ converges to 0. Now the desired countable open subgroup is just the group generated by $A$.

Answer by Noah S for Anick resolution

2013-03-31T05:26:06Z

The first paragraph of David Anick's paper, "On the Homology of Associative Algebras" (http://www.jstor.org/stable/2000383):

Let $k$ be a field and let $G$ be an associative augmented $k$-algebra. For many purposes one wishes to have a projective resolution of $k$ as a $G$-module. The bar resolution is always easy to define, but it is often too large to use in practice. At the other extreme, minimal resolutions may exist, but they are often hard to write down in a way that is amenable to calculations. The main theorem of this paper presents a compromise resolution. Though rarely minimal, it is small enough to offer some bounds but explicit enough to facilitate calculations. As it relies heavily upon combinatorial constructions, it is best suited for analyzing otherwise tricky algebras given via generators and relations.

Reverse mathematics below RCA

2013-03-29T06:36:00Z

I'm sure this is a fairly basic question, but I can't seem to find a solid answer:

My primary question is: Is there a reasonably nice subsystem of second-order arithmetic corresponding essentially to "primitive recursive comprehension?" I'm interested only in $\omega$-models - that is, I don't care about how much induction the system allows. In fact, I'd prefer it to have full induction, so that I know the weakness of the system lies squarely in its comprehension axioms. I do mean "comprehension" here: I'd like this system to be a two-sorted system, like $RCA$ itself, so e.g. $PRA$ is not what I'm looking for - although maybe it can be tweaked into a satisfactory system in an easy way?

My secondary question is: assuming a positive answer to the first question, what are some natural statements which are equivalent (over this base system) to $RCA$ (or $RCA_0$)?

(I'm almost certain this is written up nicely somewhere easily accessible, and my google-fu is simply failing me; if this is the case, and this question is therefore inappropriate for mathoverflow, please feel free to close it.)

Self-containing structures

2013-03-24T02:03:02Z

(This question is partly inspired by http://mathoverflow.net/questions/852/what-is-inter-universal-geometry.)

I have absolutely no background in Teichmuller theory or any related subject, but what I can follow of Mochizuki's description of inter-universal Teichmuller theory fascinates me. In particular, I'm very interested in what I perceive as his general claim* that an ill-founded set theory would represent certain mathematical objects more intuitively, and I'd like to get a handle on this, independently of his specific work.

I'm looking for reasonably natural mathematical structures which, in some sense, "contain themselves" as an element (or element of some element, or etc.). (This is obviously a fairly soft question, and I apologize in advance if it is inappropriate for MO.)

To clarify what I mean, I know of basically two specific examples. The first is the universal set in the set theory $NF$; the second is the set of (isometry types of) compact metric spaces of diameter $\le 1$, which under the Gromov-Hausdorff metric forms a compact metric space of diameter $\le 1$. Both of these, I imagine, can be expanded: the former could be replaced with any other consistent notion of universal set, or universal category; and my understanding is that there are a number of moduli spaces which are also naturally elements of themselves. This is the sort of thing I'm looking for: well-defined mathematical structures which can naturally be thought of as containing themselves as "elements," or "points," etc.

EDIT: what I say here about the Gromov-Hausdorff metric appears to be very wrong: see Nicola Gigli's answer below. Can this would-be example be fixed?

I'm especially interested in whether there are natural examples of the form $a_0"\in" . . . "\in" a_n"\in" a_0$ for $n>0$, since I know of no natural such example.

ADDED: An interesting observation is that - uniquely out of all examples and near-examples that I know - the Gromov-Hausdorff example above is not naturally "maximal" among its own elements. That is, there is no sense (that I'm aware of, at least) in which the space of all compact metric spaces of diameter $\le 1$ is the largest such metric space. This is obviously not the case for the universal set (in set theories which allow such objects), or the set of computable partial functions, or any variants of these. So a sub-question: does anyone have an example of a self-containing structure which is not somehow "maximal" amongst its elements?

*On, e.g., page 55 of Inter-universal Teichmuller Theory IV (http://www.kurims.kyoto-u.ac.jp/~motizuki/Inter-universal%20Teichmuller%20Theory%20IV.pdf).

Answer by Noah S for Self-containing structures

2013-03-24T05:16:07Z

Building off of Steve Huntsman's comment comparing self-containment with Cantor's diagonal argument, the set of partial computable functions can be viewed as containing itself (infinitely many times, in fact, in infinitely many ways) via the concept of a universal computable function. (By contrast, the standard diagonalization shows that the set of total computable functions does not contain itself in this way.) This actually works on the level of computable functionals: there is a single $e\in\omega$ such that for all $X\subseteq\omega$, $$ \Phi_e^X(\langle x, y\rangle)\cong \Phi_x^X(y)$$ (where $a\cong b$ means that either both $a$ and $b$ are defined and equal, or both $a$ and $b$ are undefined).

[Now as a side remark, consider the recursion theorem, which says that there is a single computable (partial) function $f$ such that for all total $\Phi_e$, $$\Phi_{\Phi_e(f(e))}= \Phi_{f(e)}.$$ The key technical step in proving this theorem is the construction of a total function $t$ such that $\Phi_e(e)\downarrow\implies \Phi_{\Phi_e(e)}=\Phi_{t(e)}$, and this in turn crucially uses the existence of universal computable functions. Moreover, the intuition behind the proof of the recursion theorem is that it is a failed attempt at diagonalization. At least to me, this reinforces the notion that self-containment can be thought of as a kind of anti-diagonalizability.]

Answer by Noah S for Question on Godel completeness theorem

2013-03-26T17:38:59Z

(For simplicity, I assume all languages and theories are countable.)

I'm not sure what "really exists" means; Godel's theorem says that a model of $T$ exists whenever $T$ is consistent.

If by "really exists" you mean "exists in some constructive sense," then the answer is: sort of. There are consistent, computable theories with no computable model (e.g., PA + a nonstandard integer - see Tennenbaum's Theorem; or $ZF$ (and, I suspect, every natural set theory) - see http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc), but every consistent theory $T$ does have a model which is low with respect to $T$; in particular, such a model is computable from $T'$, the Turing jump of $T$, which is nicely definable. If you accept operations as complicated as Separation and Replacement, then you should certainly accept the existence of models of consistent theories (unless your underlying logic is not classical, in which case I have nothing useful to say, although Andrej Bauer probably does).

Let me elaborate a bit on why having computationally simple models is relevant. It's not just that such models are "less complicated" than standard set-theoretic constructions, as I state above; it's that we don't even need to talk about set theory, at all, to get them! The models in question are uniformly computable in the jump of $T$; that is, there is a single $e\in\omega$ such that for all theories $T$, either $\Phi_e^{T'}$ codes a model of $T$, or $\Phi_e^{T'}$ codes a proof of $\exists x(x\not=x)$ from $T$. So if we believe that jumps of arbitrary sets of natural numbers "really exist" - that is, if we believe that statements of the form $\exists n\phi(n)$ are meaningful whenever $\phi$ is meaningful - then we have to believe that consistent theories have models. It is definitely possible to be skeptical of the meaningfulness of arbitrary arithmetic statements, but at that level of skepticism it seems like classical logic is the "wrong" tool, so all the questions/theorems look different anyways. I'm pushing this point because I suspect your question is coming from a skepticism towards set theory - which I consider entirely healthy! - and I want to argue that no set theory is needed to believe in models.

Please let me know if this addresses your question. I would suggest, though, that you explain a bit what you mean.

Answer by Noah S for A (seem to be) elementary logic question

2013-03-26T16:48:34Z

http://en.wikipedia.org/wiki/Beth_definability

Godel on recursion-theoretic hierarchies

2013-03-26T04:52:51Z

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes:

"Another mathematical eternal return: Toward the end of his life, Godel regarded the question of whether there is a linear hierarchy for the recursive sets as one of the big open problems of mathematical logic. Intuitively, given two decision procedures, one can often be seen to be simpler than the other. Now a set of integers is recursive iff both it and its complement are recursively enumerable. The pivotal result of classical descriptive set theory is Suslin's that a set is Borel iff both it and its complement are analytic. But before that, a hierarchy for the Borel sets was in place. In an ultimate inversion, as we look back into the recursive sets, there is no known hierarchy."

I have two questions regarding this.

1) Can anyone provide a citation for this? I was unaware that Godel turned to this question at any point, and I'd be curious reading anything he had to say about it.

2) What work has been done on this question? In particular, is there any reason to believe there is such a hierarchy, beyond the (in my opinion, unconvincing) analogy with the Borel sets Kanamori gives?

Some observations around the second question: there are known, natural linear hierarchies for proper subsets of the recursive sets; for example, the Grzegorczyk hierarchy (http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy) gives a hierarchy of the primitive recursive sets with order type $\omega$. However, it's not clear to me that any of these hierarchies have a chance of being extendible to all of the recursive sets in any nice way. In particular, one barrier faced would be that the naturally-occurring hierarchies enumerate those computable functions which are provably total in some corresponding recursive theory of arithmetic (or set theory), and no such theory can prove the totality of all total recursive functions. But maybe I'm wrong about some of this?

ADDED: I want to clarify that the connection between hierarchies and provable totality - which here is an obstacle - is usually incredibly useful (and if I have my history right, many of these hierarchies were developed precisely to understand what functions were provably total in certain systems).

Answer by Noah S for Similarities between Post's Problem and Cohen's Forcing

2013-03-08T21:30:46Z

The primary difference between forcing arguments in set theory and priority constructions is that the latter care about the complexity of the generic filter in a way the former do not. In particular, forcing in set theory involves hitting every dense set in a given model, and so the generic cannot possibly be a member of that model (unless the poset is trivial), whereas if you frame priority constructions as forcing arguments the goal is to hit a fixed countable set of dense sets with a generic which is computable (or close to that) as a set of conditions (the set coded by the generic, on the other hand, won't be computable).

(Let me write this out explicitly, in the case of Friedberg-Muchnik: the poset in question is the set of pairs $(p, \rho)$, where $p$ is the set built so far (i.e., $p\in 2^{<\omega}$) and $\rho$ is the collection of restraints imposed so far (so $\rho$ is a finite subset of $\omega\times(\omega\cup\lbrace -1\rbrace$) with each element of $\omega$ occurring as the left component of at most one element of $\rho$). The poset is ordered in the following way: $(p, \rho)\le(q, \pi)$ if

$\vert p\vert\ge\vert q\vert$ and $\forall n<\vert q\vert, q(n)\le p(n)$ (this is the c.e. condition - we're not allowed to remove elements from the set we're building);
for all $(n, m)\in\pi$ with $m>-1$, either $p\upharpoonright m+1=q\upharpoonright m+1$ or for some $k-1$ we have $(k, j)\in \rho-\pi$ (this is the missing condition Francois pointed out, which stipulates that restraints can only be violated by the actions of higher-priority requirements); and
$$ \forall n\in dom(\rho), \rho(n)\not=\pi(n)\implies \exists m < n[(\rho(m)=-1\vee m\not\in dom(\rho))\wedge \pi(m)\downarrow>-1).$$ (This just says that $\rho$ "could occur from $\pi$ by injury.")

Note that conditions in this poset can be coded by natural numbers, so it makes sense to talk about a set of conditions - i.e., a filter - being computable. Now the requirements in the Friedberg-Muchnik argument can be represented by dense sets (which are not computable) in this poset, two for each $\Phi_e$, and the theorem turns into "there is a computable filter through this poset generic for this collection of dense sets." In fact, I believe the poset described above is "universal" for finite injury arguments, in the sense that each finite injury argument can be dealt with by coming up with an appropriate list of dense subsets of this poset and then arguing that there is a computable filter which is generic for that collection of sets, but I'm not sure about that.)

A possible stronger analogy: priority arguments are like forcing axioms. Forcing axioms say "for such-and-such a poset and collection of dense sets, there is a generic filter already in the model." For example, Martin's Axiom says that for any poset $\mathbb{P}$ with the c.c.c. and any collection $\mathcal{D}$ of $< 2^{\aleph_0}$-many dense sets, there is already a $\mathcal{D}$-generic filter. By analogy, the punchline of a priority argument is often "for this particular poset and these dense sets, there is a computable generic filter." In both cases, we start with the Rasiowa-Sikorski Theorem ("we can hit countably many dense sets") and try to strengthen it: in the set-theoretic case, by enlarging the class of dense sets, and in the computability-theoretic case, by restricting the collection of filters we consider. In fact, this is an analogy I've spent a lot of time thinking about over the course of the last year; it hasn't helped me understand priority arguments, but it has helped me understand forcing axioms.

That said, I do think of priority constructions as a type of forcing; I just realize that this isn't necessarily convincing.

Now let me briefly address the question of what role, if any, Friedberg/Muchnik (or related earlier work by Kleene/Post) played in Cohen's development of forcing. On the one hand, in his paper "The Discovery of Forcing" (which you cite), Cohen describes his process as mostly self-contained, but at one key juncture bolstered by reading Goedel's monograph on $L$. No reference is made to computability theory, and indeed the words "Friedberg," "Muchnik," "Post," "priority," and "recursion" appear nowhere in the article. ("Kleene" appears once, but only in reference to the fact that Kleene's tome on mathematical logic did not include anything especially relevant to Cohen's project.) On the other hand, I seem to recall an article in which Cohen described his picture of forcing as involving an adapting oracle, which he connected to computability theory - which would suggest a real influence. But I can't track down that citation at present; all I can find is a comment by Chad Groft on Terry Tao's blogpost http://terrytao.wordpress.com/2010/03/19/a-computational-perspective-on-set-theory/ that says Cohen explained forcing in this way in his later years. But Cohen may have changed his intuition about forcing over time, so that it is quite possible that Cohen came to view his forcing arguments as related in spirit to recursion theory, while not actually having drawn any inspiration from the subject originally.

Versions of large cardinals with target model in a generic extension

2013-03-10T00:12:23Z

(I ran into this question while thinking about the (Strong) Inner Model Hypothesis: see http://www.jstor.org/stable/4093051 or http://arxiv.org/abs/0711.0680.)

A measurable cardinal is a cardinal $\kappa$ such that there is an elementary embedding $j: V\rightarrow M\subseteq V$ with $M$ an inner model of $V$ and $crit(j):=\min\lbrace \alpha\in ON: j(\alpha)\not=\alpha\rbrace=\kappa$.

Now we can allow the target model of $j$ to live, not inside $V$, but inside some set-generic extension of $V$ as follows. Say that $\kappa$ is outer-measurable if there is some poset $\mathbb{P}\in V$, some $G$ which is $\mathbb{P}$-generic over $V$, and some transitive inner model $M$ of $V[G]$ such that there is an elementary embedding $$ j: V\rightarrow M\subseteq V[G]$$ with $crit(j)=\kappa$.

In general, given any large cardinal property $(*)$ defined in terms of elementary embeddings, we can define outer-$(*)$-ness to be the property $(*)$ where the target model $M$ is allowed to be an inner model of some set-forcing extension of $V$, rather than $V$ itself. My questions, then, are:

Is there a large cardinal property $(*)$ such that we can have an outer-$(*)$ cardinal which is not $(*)$?
Is there a large cardinal property $(*)$ such that the consistency strength of an outer-$(*)$ cardinal is weaker than the consistency strength of a $(*)$-cardinal?

I suspect that the answer to the second question is "no;" I have no idea about the first question.

[EDIT: Thanks to Joel for pointing out that my now-removed claim that "measurable=outer-measurable" is wrong.]

Answer by Noah S for A question about Universal sets.

2013-02-22T20:14:05Z

I believe that not much is known about NF itself and large cardinals - keep in mind that NF disproves the axiom of choice (Specker, 1953), and many large cardinal notions are not robustly defined in the absence of choice, in the sense that definitions equivalent over ZFC become non-equivalent without AC.

The system NFU (=NF + urelements), however, is much better behaved. It is known to be consistent - in fact, consistent relative to PA - and NFU does not disprove choice. (Although, having urelements, a universal set, and choice leads to the interesting situation in which the powerset of the universe is strictly smaller than the universe itself.) Over NFU+AC, we can attempt to define at least the smaller large cardinals in much the usual way.

That said, I don't' know anything about large cardinals in NFU, but I'd look at work of Ali Enayat (for example, http://academic2.american.edu/~enayat/Slides%20of%20Talks/Cambridge%20Slides.pdf) for starters.

Answer by Noah S for Set theory question

2013-02-21T01:24:58Z

I'm assuming you're asking about the theory $ZF+\neg AC+CH$. The answer is yes - but you have to be clear about what you mean by "$CH$."

First, a trivial example: we can start with a model of $ZFC+CH$, and force a failure of $AC$ via a (symmetric submodel of) a $2^{\aleph_0}$-closed forcing extension. Since our forcing extension is sufficiently closed, it adds no new sets of reals, so $CH$ remains true; essentially, what's going on is that we're adding a failure of $AC$ to our model, but we're doing so at such a high level in the cumulative hierarchy that it doesn't affect the reals.

A more refined version of your question: can we have $ZF+\neg AC(\mathbb{R})+CH$? That is, a model of $ZF$ in which $CH$ holds but the reals are not well-ordered.

This is where we need to be precise about what $CH$ means. The useful version of $CH$ is "every set of reals is either at most countable, or can be bijected onto $\mathbb{R}$." Under this phrasing, we do indeed have the consistency of $ZF+\neg AC(\mathbb{R})+CH$!

To get $AC(\mathbb{R})$ to fail, we just need a model in which there is no injection from $\omega_1$ (which is defined to be the least uncountable ordinal) to $\mathbb{R}$: if $AC(\mathbb{R})$ held, we could send each countable ordinal $\alpha$ to the "least" real which codes a well-order of order type $\alpha$. To force the continuum hypothesis to hold requires a bit more subtlety. My favorite model of $ZF+\neg AC(\mathbb{R})+CH$ is $L(\mathbb{R})$ under the assumption of large cardinals: large cardinals imply that $L(\mathbb{R})\models AD$, the axiom of determinacy, which in turn implies that every set of reals has the perfect set property (so $CH$ holds) and also that there is no injection from $\omega_1$ to $\mathbb{R}$ (so $AC(\mathbb{R})$ fails). However, this model does involve a massive jump in consistency strength, past that of $ZF$, which is not necessary: Truss has a construction, which is a variation of a construction of Solovay (which does require large cardinals, albeit just one small one!), which does not require any more consistency strength than $ZF$ itself and satisfies $ZF+\neg AC(\mathbb{R})+CH$.

Methods to tell if a magma has idempotents

2013-02-18T02:15:21Z

(Disclaimer: below, when I say "compact" I mean "compact Hausdorff.")

I asked a version of this question on math stackexchange (http://math.stackexchange.com/questions/305186/left-continuous-magmas-with-no-fixed-points) a couple days ago, but received no answer; I apologize if this question is too low-level for this site.

Background: Mostly for fun, I'm looking at a particular binary operation on the set of ultrafilters on the natural numbers, $\beta\mathbb{N}$ - this was inspired by reading the proof via idempotent ultrafilters of Hindman's theorem. The key component of this proof is the easy result that any left continuous compact semigroup (that is, any compact topological space $X$ together with a binary operation $*: X^2\rightarrow X$ such that for all $s\in X$ the map $t\mapsto t*s$ is continuous) has an idempotent element. A while ago, I naively concluded that this meant that my operation had idempotents; however, this turned out to be very unjustified, since the operation I'm looking at turned out to be non-associative (which surprised me), and associativity is crucial to the proof of the existence of idempotents: there are plenty of left continuous compact magmas without idempotents (consider the set $\lbrace a, b\rbrace$ in the discrete topology with the operation $x*y=z\iff z\not=y$).

I still have no idea whether the magma I'm studying has any idempotents. But more to the point, I realized that I have no idea in general how to go about trying to tell whether a given magma has idempotents.

My question is twofold: first, what are some necessary/sufficient conditions for a (let's say left continuous and compact) magma to have idempotents? Second, what are some instructive examples of such magmas without idempotents? I don't think the two-element example is particularly instructive, since - despite being very simple! - it doesn't really resemble anything I can think of encountering in practice. As far as examples go, I'm particularly interested in ones of large cardinality - a naturally occuring left continuous compact magma of size $2^{2^{\aleph_0}}$ without idempotents would be fantastic!

Lattice of differences between ultrafilters

2012-08-28T05:51:07Z

Consider two ultrafilters, $U$ and $V$, on the same cardinal $\kappa$. Let $D(U, V)=\lbrace X\subseteq \kappa: X\in U-V\rbrace$; clearly $D(U, V)$ is a lattice under $\subseteq, \cap, \cup $ since the intersection of two $U$- or $V$-large sets is $U$- or $V$-large, and the union of two $U$- or $V$-small sets is $U$- or $V$-small; by the same reasoning, $D(U, V)$ is a $\lambda$-complete lattice, where $\lambda$ is the minimum of the completeness of $U$ and the completeness of $V$.

My general question is, does this lattice have any interesting properties?

In particular, I'm interested in the following: let $M\models ZFC^-$, let $U\in M$ be a countably complete ultrafilter on some $M$-measurable cardinal $\kappa$, and let $j: M\rightarrow \prod M/U$ be the elementary embedding of $M$ into the ultrapower via $U$. Let $V=\lbrace X\in\wp^M(\kappa): \kappa\in j(X)\rbrace$; then $V\in M$ and $V$ is a normal ultrafilter on $\kappa$. In particular, if $U$ is not normal, then $U\not=V$. Intuitively, however, the difference between $U$ and $V$ is "small" (to be fair, this "intuition" may just be a figment of my not understanding inner model theory); is this somehow reflected by the lattice $D(U, V)$? In general, can anything about the relationship between $U$ and $V$ be read off of the lattice $D(U, V)$?

(Also, is this notion studied somewhere? I've googled around, unsuccessfully.)

EDIT: to clarify, I'm most interested in properties which can be determined from the isomorphism type of the lattice $D(U, V)$ alone.

Thanks in advance; hopefully this isn't too open-ended.

Comment by Noah S

2013-06-16T15:04:09Z

To make this more explicit for the OP, take e.g. $A=271^3$ and $B=2^33^573^3$. Then $AB(A+B)=271^32^33^573^3(919^3)$, and no exponent below 3 appears.

Comment by Noah S

2013-06-15T23:15:49Z

Is this a homework question?

Comment by Noah S

2013-06-14T17:06:09Z

If I understand correctly, you're asking what is the probability - for a randomly chosen function $f: a\rightarrow b$ - that $\vert ran(f)\vert=k$ for given $a, b, k$. This is certainly not research level. (If this isn't what you're asking, what are you asking?)

Comment by Noah S

2013-06-14T02:15:45Z

(I just want to reiterate that the reason this question will be closed is that it's not appropriate for this site - this is an awesome question, and exactly what you should be asking after/while learning calculus!)

Comment by Noah S

2013-06-14T02:13:11Z

@Garabed, I added some paragraph breaks to the question - I hope you don't mind.

Comment by Noah S

2013-06-14T02:10:21Z

This is a great question, but it's more appropriate for mathstackexchange. (I think it's probably been asked there already, actually, so I'd check.)

Comment by Noah S

2013-06-14T00:46:07Z

I think this might be more appropriate for mathstackexchange or csstackexchange?

Comment by Noah S

2013-06-12T12:49:23Z

Looking at your other questions as well, I think you should put in more effort to make precise what you are asking for. I have no idea what an answer to this question, for example, would consist of.

Comment by Noah S

2013-06-10T17:06:51Z

So wait, your argument goes from "If a list contains . . . then it contains pi", through "there is no decimal representation of pi," and somehow declares victory? Okay, yeah, I'm done here.

Comment by Noah S

2013-06-10T16:59:28Z

I'm sure I'll regret this, but: "If a list contains every finite initial sequence of pi, then it contains pi." What about the list $\langle 3, 3.1, 3.14, . . .\rangle$. Where is $\pi$ on that list? You are using either the word "list," or the word "contains," in a radically different fashion from its actual mathematical meaning.

Comment by Noah S

2013-06-08T21:32:46Z

Leaving aside other issues, a question ought to be direct and clear: "contains many questions" is not necessarily a good thing. Also, I'm far from knowledgeable (or even literate!) in the area of subfactors, but it is very unclear from your question what is proved, what is guessed, what is informal, etc.

Comment by Noah S

2013-06-07T04:06:23Z

For that matter, what does "small $d$" mean? $d<10$? $d<10^{10}$?

Comment by Noah S

2013-06-07T03:55:23Z

How did this arise? How do you know it's true?

Comment by Noah S

2013-06-05T06:02:40Z

Not totally related, since this is about many-sorted first-order logic, and not higher-type first-order logic, but: for an example of themany-sorted framework not just being syntactic sugar, consider the "$\mathcal{M}^{eq}$" construction defined e.g. on page 28 of Marker's book on model theory: given a single-sorted structure $\mathcal{M}$, the many-sorted structure $\mathcal{M}^{eq}$ has one sort per parameter-free definable equivalence class on some finite power of $\mathcal{M}$. Since there are always infinitely many sorts, this construction cannot be made first-order in a nice way.

Comment by Noah S

2013-06-05T04:58:08Z

If this answers your question, you can accept by clicking the check mark to the left of the answer.

User noah s - MathOverflow

Answer by Noah S for List of Whitehead-like Problems

Answer by Noah S for Random infinite sequence : Can machines generate truly random sequences.

Answer by Noah S for The paradox with the first uncountable ordinal

Answer by Noah S for Ontological status of some "sets" in ZFC

Answer by Noah S for Order-independent properties arising naturally in mathematics

Answer by Noah S for Computability complexity of the first-order theory of arithmetic?

Answer by Noah S for Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?

Answer by Noah S for Avoiding reflexive paradox in set theory

Answer by Noah S for Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?

Lawvere's fixed point theorem and the Recursion Theorem

"Inverse problem" for Brauer groups

Answer by Noah S for Is there any proof that you feel you do not "understand"?

Answer by Noah S for Basic results with three or more hypotheses

Answer by Noah S for Are the two meanings of "undecidable" related?

Answer by Noah S for A Model where Dedekind Reals and Cauchy Reals are Different

What can the degrees of constructibility be?

Answer by Noah S for Countable open subgroup

Answer by Noah S for Anick resolution

Reverse mathematics below RCA

Self-containing structures

Answer by Noah S for Self-containing structures

Answer by Noah S for Question on Godel completeness theorem

Answer by Noah S for A (seem to be) elementary logic question

Godel on recursion-theoretic hierarchies

Answer by Noah S for Similarities between Post's Problem and Cohen's Forcing

Versions of large cardinals with target model in a generic extension

Answer by Noah S for A question about Universal sets.

Answer by Noah S for Set theory question

Methods to tell if a magma has idempotents

Lattice of differences between ultrafilters

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Comment by Noah S

Answer by Noah S for Is deciding whether a Turing machine provably runs forever equivalent to the halting problem?