User sridhar ramesh - MathOverflow

Answer by Sridhar Ramesh for Proof without words for surface area of a sphere

2012-11-19T01:29:40Z

I will describe in words a proof which might as well be illustrated without words (I would provide it in such visual form instead had I only the skills to make diagrams any nicer than MS Paint scrawls):

Imagine a sphere as the Earth, oriented in the usual way with the North pole on top. [This makes no difference except to my linguistic convenience, of course]

Consider an infinitesimal "square" patch of the Earth's surface, whose sides are oriented along lattitudinal and longitudinal lines, and the distortion this square undergoes when projected horizontally outward to the cylinder circumscribing the Earth (with the polar axis as its axis).

The ratio of the square's horizontal distance from the polar axis to the radius of the Earth is equal to the ratio of the square's vertical span to the length of its longitudinally oriented sides. (These are both the cosine of the angle between the square's position and the equator (equivalently, the angle between the square's orientation and vertical)).

Accordingly, the factor by which the square's lattitudinally oriented sides are stretched in our cylindrical projection is equal to the factor by which its longitudinally oriented sides are squashed.

Thus, our cylindrical projection is area-preserving, from which we have that the area of the entire sphere is the same as the side area of its circumscribing cylinder.

This, it seems to me, is a perfectly "directly geometric" account of the desired fact.

Answer by Sridhar Ramesh for Tarski's Theorem and Gödel's Second Incompleteness Theorem

2012-11-17T05:08:01Z

Tarski's theorem is on the unDEFINability of truth, but yes, Goedel's results follow (and in some sense are the same thing): provability (in some particular system of interest) is definable, therefore truth cannot match provability, therefore (supposing the system of interest is consistent, and therefore sound for the relevant sentences) there is a sentence which is true but not provable. This is the first completeness theorem.

What would it mean for a predicate T to actually define truth? Just that T(s) and s are equivalent for each sentence s. Thus, Tarski's undefinability theorem tells us more specifically that, for any definable T, there is some sentence G such that T(G) and G are equivalent to each other's negation. The above is just what happens when we take T to define provability; we thus see more specifically that incompleteness arises from a sentence G equivalent to the negation of its provability, which is therefore (supposing the system of interest is consistent) true but not provable.

One can then argue, in the usual way, that our proof of the first incompleteness theorem, suitably internalized in the system of interest, yields the second incompleteness theorem. [Our argument shows that the consistency of the system of interest entails the non-provability of G. But this conclusion is just what it means for G to be true! Thus, if the system of interest proves its own consistency, it proves G, contra its own consistency.]

Properly "transfinitely" Euclidean domains

2012-10-21T01:52:59Z

Are there integral domains which admit ordinal-valued Euclidean functions but not $\mathbb{N}$-valued Euclidean functions?

Answer by Sridhar Ramesh for wellfounded sets and predecessors

2012-10-04T18:57:46Z

Sure. Just take the natural numbers with the usual ordering, and slap on a new maximum element. This is well-founded (it is the ordinal $\omega + 1$), but the maximum element has no predecessor, despite not being minimal either.

Intuitionistic consistency of surjection from naturals to reals

2012-08-31T06:11:27Z

Is it consistent intuitionistically (in the sense of topos theory) for there to be a surjection from the natural numbers to the (Dedekind, let us say) real numbers? [I've managed to convince myself this happens in the effective topos, but not so convincingly as I'd like; I suspect others will be able to answer more confidently and cleanly...]

Answer by Sridhar Ramesh for Are all the theorems true?

2012-08-01T19:17:20Z

"goodness" appears to be your attempt to describe the property of having existential witnesses (that whenever $T$ proves there exists an $x$ such that $P(x)$, there is also a specific numeral n such that $T$ proves $P(n)$). There are also other related ideas such as $\omega$-consistency. But "goodness" doesn't quite match any of these exactly.

Re: question 3: No, "goodness" is not equivalent to consistency. After all, PA plays an unduly special role in the definition of "good", and not such a special role in the idea of "consistent". An example of a theory which is consistent (on the standard assumption that PA is) but not "good" is PA + "PA is inconsistent". This proves the $\Sigma_1$ statement "PA is inconsistent", but no $\Pi_0$ statement entailing this in PA.

Answer by Sridhar Ramesh for existence of a field that has a non surjective ring homomorphism

2012-05-02T05:31:53Z

Consider the field of rational functions in the infinitely many variables $x_0, x_1, x_2, ...$ (each particular rational function using only finitely many of these), and the endomorphism which shifts variables' indices up by 1.

(Originally, I had asked here "Also, who says the only nonzero ring homomorphism from $\mathbb{R}$ to $\mathbb{R}$ is the identity? I find that hard to believe, at least given Choice", but now, all I can say is "D'oh!")

Abel summation of the alternating series of primes?

2011-05-28T05:18:23Z

Consider the ordinary generating function of the sequence of primes ($2+3x+5x^2+7x^3 + ...$); by the ratio test and the prime number theorem, its radius of convergence is $1$. Thus, we might well ask about the limit of its value as $x$ approaches $-1$ from above (i.e., about the Abel summation of the alternating series of primes $2 - 3 + 5 - 7 + ...$). So I do! Is this limit well-defined? Is it finite? If so, what is known about its value? (I pessimistically suspect I will be told it is actually disappointingly infinite, or even worse, that the limit diverges by oscillation, but I haven't enough experience in this sort of thing to confidently rule out more interesting possibilities...)

[I realize the alternating series of primes has partial sums with arbitrarily large magnitudes, by the existence of arbitrarily large prime gaps, so there's no hope for it to be convergent in the standard sense...]

"Highly balanced" periodic functions

2012-01-11T03:31:45Z

The function $f(x) = e^{2\pi ix}$ on the domain $\mathbb{R}/\mathbb{Z}$ has the property that, for every $n > 1$ and every $x$, $\displaystyle \sum_{i = 0}^{n-1} f(x + \frac{i}{n}) = 0$.

Other such functions can be found by simply postcomposing a linear function to this example (thus, for example, $x \mapsto \cos(2\pi x) : \mathbb{R}/\mathbb{Z} \to \mathbb{R}$ also has this property).

Beyond those, are there any other "natural" examples of functions with this property (on the same domain $\mathbb{R}/\mathbb{Z}$, but with any codomain)?

[Of course, one can freely construct the codomain as a monoid with generators $\mathbb{R}/\mathbb{Z}$ and all the necessary relations; slightly less trivially, one could take the codomain to be a ring, the map to be exponential, and $f(\frac{1}{n}) - 1$ to be invertible for each prime $n$, in the same freely constructed fashion. I can't quite put my finger on why, but I don't want to count these as "natural" examples (probably because the condition for each (or essentially each) distinct $n$ is handled separately, instead of flowing all at once from some underlying property)]

Answer by Sridhar Ramesh for Union of a object (a set) in the Elementary Theory of the Category of Sets

2011-11-21T00:18:01Z

There is a sense in which there is a (trivial, tautological) axiom of (disjoint) union in the elementary theory of the category of sets. In any category with pullbacks, one can think of a slice above an object X (that is, a map into X) as representing an X-indexed set (the idea being that the set associated to any particular point in X is the fiber of that point under that map; pullback then acts as reindexing). One might then ask what the disjoint union of an indexed set is. Well, it will simply be the domain of the representing slice! (Since the domain of a map amounts to the same as the union of all its fibers).

(Of course, this does not touch upon the traditional idea of set theory as about "sets of sets of sets of sets...". To model such a theory within a theory of unstructured collections, you must use membership trees, as David notes.)

Answer by Sridhar Ramesh for What is a complex inner product space "really"?

2011-11-04T08:28:46Z

A complex inner product space is just a real inner product space along with a designated 90 degree rotation (where this means a linear operator sending every vector to an equally large but perpendicular vector)*. If you understand why one might care about real inner product spaces, and you understand why one might be furthermore interested in 90 degree rotations (or equivalently, rotations by constant angles more generally+), then you understand why one might care about complex inner product spaces.

[*: Specifically, given such a real inner product space $V$ with 90 degree rotation operator $J$, view $V$ as a complex vector space by taking $(a + bi)v = (a + bJ)v$, of course. And define a complex inner product $*$ from the real inner product $\cdot$ via $v * w = v \cdot w + (v \cdot Jw)i$. To go in the other direction, from a complex inner product space to a real inner product space with 90 degree rotation operator, is even easier: take $v \cdot w$ to be the real component of $v * w$, and take $Jv$ to be $iv$. One can straightforwardly check that these two processes are inverse to each other and produce structures satisfying the appropriate axioms.]

[+: Let us say $R$ is a rotation by a constant angle if $R$ is a linear, length-preserving operator such that $\frac{Rv \cdot v}{v \cdot v}$ is constant. It is straightforward to show that this is equivalent to $R$ being of the form $\cos(\theta) + \sin(\theta)J$ for some angle $\theta$ and some 90 degree rotation operator $J$, so the study of constant angle rotations in general reduces to the study of 90 degree rotations in particular]

Answer by Sridhar Ramesh for Can the Riemann hypothesis be undecidable?

2011-11-01T07:54:14Z

I do not know anything about zero-finding algorithms for $\zeta$, so I will make only one small remark which doesn't require such knowledge: If the Riemann Hypothesis is false, then it is provably false (in ZFC, or any similar system).

This is because Robin's theorem tells us that the Riemann hypothesis is equivalent to the assertion that, for every natural $n \geq 5041$, the sum of the divisors of $n$ is less than $e^{\gamma} n \log{\log{n}}$; since there are programs which calculate this latter quantity to arbitrary precision, and thus can verify whether this inequality holds for any given $n$, we find that the Riemann hypothesis is a $\Pi_1$ statement: it is equivalent to the assertion that some computer program never outputs "NO" on any input. (Although not familiar with the proofs of Robin's theorem, etc., I assume they can be carried out in ZFC, and thus establish the relevant equivalence within ZFC.). There may be more direct ways to establish that the Riemann hypothesis is a $\Pi_1$ statement, such as by knowledge of algorithms which enumerate to arbitrary precision the zeros of $\zeta$, but at any rate, there is this one.

Accordingly, if the Riemann hypothesis is false, then the relevant computer program does output "NO" on some input, from which it would follow that ZFC proves that that computer program outputs "NO" on that input, and thus ZFC would prove the Riemann hypothesis to be false.

The possibility still remains, however, as far as I know, that the Riemann hypothesis may be true but unprovable in ZFC.

Answer by Sridhar Ramesh for What is a colimit, really?

2011-07-28T22:08:10Z

Well, the thing that may or may not be a "real functor" (and which may even fail to exist if the limit(/colimit) does not always exist) is in any case a "profunctor" (that is, a functor into $Set^{C^{op}}$ (or $Set^C$ for colimits) rather than into $C$). The limit of a diagram will actually exist just in case the profunctor's value at that diagram is a representable presheaf (that is, one in the range (up to isomorphism) of the Yoneda embedding). If one makes a choice of such a representation at every diagram, one can factor the entire profunctor through the Yoneda embedding, into a genuine functor. This of course is precisely the choice you want to avoid, but it indicates that one can at least still treat the profunctor as an "anafunctor" in such cases (essentially, a functor whose value at an object/morphism is only determined up to isomorphism, in a coherent way). Further reading on profunctors and anafunctors (for example, at the nLab) may be precisely the sort of thing you are looking for.

In short: profunctors are the way to describe adjoints which may exist only partially, while anafunctors are the way to describe functors whose construction requires a number of arbitrary choices (with anafunctors both avoiding the "evil" in making any single choice and the need for the Axiom of Choice in making so many of them).

Answer by Sridhar Ramesh for Surreal Numbers and Set Theory

2011-07-21T21:15:41Z

Yes, every surreal number is also an element of $V$ (at least, once you choose some method of encoding ordered pairs of sets as sets). The (highly recursive) characterization of which elements of $V$ are surreal numbers is precisely the definition of the surreal numbers: an element of $V$ is a surreal number just in case it is an ordered pair $(L, R)$ of sets of surreal numbers, with every element of $L$ being less than every element of $R$, with the definition of the ordering being, etc., etc. (Note, however, that this particular embedding of the surreal numbers into $V$ doesn't respect surreal number equivalence; it depends on the particular selection of $L$ and $R$ sets defining the surreal number.)

Conversely, while not every element of $V$ is a surreal number, there is at least a natural way of encoding every ordinal (and thus every cardinal, under the usual Axiom of Choice-based identification of cardinals with their initial ordinals) as a surreal number: the encoding of the ordinal $\alpha$ is the surreal number specified with an empty right set and a left set consisting of the encodings of all the ordinals less than $\alpha$. Thus, if there are large cardinals in $V$, there are corresponding elements in $No$.

Answer by Sridhar Ramesh for Why is the output of an LTI system the convolution of the input funtion and the impulse response?

2011-06-22T00:08:56Z

Well, it's just as simple as this: the output at any moment reflects the effect of the input at just that moment, plus the lingering effect after one second of the input from one second before, plus the lingering effect after two seconds of the input from two seconds before, plus the lingering effect after three seconds of the input from three seconds ago, etc. [And half a second and 2.8 seconds and so on as well...]. That is, the sum (or, rather, integral) over all t of "The input from t seconds ago" * "The amount of lingering effect a unit of input contributes after t seconds". That is, precisely a convolution of the input signal and the impulse response.

What are examples of theorems which were once "valid", then became "invalid" as standard definitions shifted?

2011-06-15T17:50:14Z

That is, results established by correct proofs within some framework, yet the manner in which their author or the general mathematical community at the time would describe these results would, in later times, be interpreted as constituting a false claim, due to changing fashions as to how to standardly formalize some of the relevant concepts.

I imagine this sort of thing has happened often (e.g., with shifting accounts of "polyhedra" a la Lakatos' "Proofs and Refutations", or a motley of different definitions of "continuity" before standardization on the one we use now), but I do not have enough awareness of history to be able to provide solid examples (e.g., it seems plausible to me that Darboux may have considered himself to have proven that every derivative is continuous, taking the intermediate value property to be defining for continuity, but I do not know if this is an accurate account of what he claimed).

Can the similarity between the Riesz representation theorem and the Yoneda embedding lemma be given a formal undergirding?

2011-06-13T20:13:29Z

For example, by viewing Hilbert spaces as enriched categories in some fashion? (I suppose the same idea of considering the inner product of a Hilbert space as a generalized Hom-set has also been pondered in connection with the similarity of adjoint transformations and adjoint functors, though I'm not aware of any more formal correspondence there either)

Edit for clarification: The full similarity I see is this:

For any Hilbert space $H$, we have its inner product, a continuous linear map from $H^{op} \otimes H$ to $\mathbb{C}$ [where $H^{op}$ is $H$ with its inner product's argument order flipped]; currying this gives a continuous linear map from $H^{op}$ into the Hilbert space of continuous linear maps from $H$ to $\mathbb{C}$. The Riesz representation theorem says this is an isomorphism.

Similarly, for any category $H$, we have its Hom functor, a continuous functor from $H^{op} \times H$ to $Set$ [where $H^{op}$ is $H$ with its Hom functor's argument order flipped]; currying this gives a continuous functor from $H^{op}$ into the category of continuous functors from $H$ to $Set$. The Yoneda embedding lemma says this is an embedding; furthermore, under suitable conditions (e.g., if $H^{op}$ is equivalent to a presheaf category), this is an equivalence.

Answer by Sridhar Ramesh for Arithmetic fixed point theorem

2011-05-28T03:25:34Z

You could have discovered the fixed point theorem yourself! You'd just need the problem to be motivated the right way. For example, let's look at it as a kind of programming challenge...

Suppose you wanted to write a program that referred to its own source code at some point.

You could try to write it in BASIC (or Java or Haskell or English or Peano Arithmetic or whatever your favorite programming language is). But, you might find that to be too tricky at first. So nevermind BASIC; you decide to instead simply invent a hypothetical new programming language BASIC++, which is just like BASIC, but augmented with built-in support for programs to be able to access their own source code: this language has a basic keyword "myOwnSourceCode" within it, which is to be interpreted as just what you'd think from the name.

How does one actually run a BASIC++ program? Well, one thing you might do with a BASIC++ program (let's call it P) is compile it into an ordinary BASIC program, by going through its source code and replacing every instance of the keyword "myOwnSourceCode" with, of course, the expression of the actual source code for P.

So now we know how to write BASIC++ programs which refer to their own source code (it's trivial by the design of the BASIC++ language), and we also know how to compile BASIC++ programs into ordinary BASIC programs.

Of course, by combining those two, this means you can write BASIC++ programs which refer to the compilation of their own source code into BASIC.

And then, by actually compiling such a program into BASIC, you're left with, in fact, an ordinary BASIC program which refers to (which is to say, does whatever the programmer wants it to do with) its own source code.

This is precisely the structure of the fixed point theorem: $F$ is some BASIC-definable function, the free variable $v$ (in a BASIC++ program) is the "myOwnSourceCode" keyword, $sub(P, num(P))$ compiles a BASIC++ program $P$ into ordinary BASIC, $H$ is the BASIC++ program which applies $F$ to the compilation of its own source code into BASIC, and $A$ is the compilation of $H$ into BASIC; thus, as an instance of the pattern above, $A$ is an ordinary BASIC program which applies $F$ to its own source code. [The fact that the free variable of $F$ was also chosen to be named $v$ in the presentation given in the question is, incidentally, an unnecessary and irrelevant distraction]

(Of course, in the arithmetic fixed point theorem, "BASIC" is instead "Peano Arithmetic", but it's the same fundamental construction, whatever the particular context it is to be interpreted in)

Answer by Sridhar Ramesh for Why hasn't mereology suceeded as an alternative to set theory?

2011-05-09T00:04:31Z

In algebraic set theory a la Joyal and Moerdijk, the subset relation is taken as fundamental, with membership only being a derived notion (specifically, the cumulative hierarchy is taken to be the free "ZF-algebra"*; i.e., partial order with small joins and an abstract "singleton" operator. The order corresponds to subsethood, and x is defined to be an element of y just in case the singleton operator applied to x yields a subset of y). I can never quite grasp what it is that mereology is supposed to be all about as a supposed contrast to set theory, but if it's just a matter of viewing subsethood as more elementary a concept than membership, well, there you go.

[*: ZF-algebra isn't a great name for the general concept of such structures, in my opinion, since they have very little to do with specifically Zermelo-Fraenkel set theory. Note that, while every object in the cumulative hierarchy is uniquely a join of singletons (and in this way can be viewed as a plain old bag of elements), in more general ZF-algebras, there may be objects which are not joins of singletons, thus carrying a more mereological flavor; in particular, these illustrate that subsethood is not definable in terms of membership, firmly establishing subsethood as the more primitive notion in this context]

What does the term "yoga" mean in mathematics?

2011-05-06T00:59:34Z

Just exactly what the title says; often, in mathematics, particularly in the vicinity of Grothendieck, I see reference to "the yoga of...". What exactly does the term "yoga" mean in these contexts?

Is it possible for a nontrivial category to have a slice classifier?

2010-11-11T18:15:19Z

The concept of a subobject classifier is of course standard and ubiquitous. But is there any nontrivial example of an unrestricted slice classifier?

Specifically, what I mean by this is, is there any non-preorder category with pullbacks with a morphism m into an object X such that ALL other morphisms can be taken as a pullback of m along some morphism into X? And, if so, is it even possible to have furthermore that parallel morphisms from any object Y into X are equal just in case the pullbacks of m along them are isomorphic as objects of the slice category over Y?

Naturally, if we demand further structure on the category (e.g., local cartesian closure), this becomes impossible by Cantor type arguments in its internal logic, but if we only demand pullbacks, can it be done?

Answer by Sridhar Ramesh for Montague's Reflection Principle and Compactness Theorem

2010-03-19T20:29:16Z

For any finite set of axioms K of ZFC, ZFC proves "K has a model", via the reflection principle as you note. However, ZFC does not prove "for any finite set of axioms K of ZFC, K has a model". The distinction between these two is what prevents ZFC from proving that ZFC has a model.

(That is, even though, as you note, ZFC proves "if every finite set of axioms K of ZFC has a model, then ZFC has a model", as ZFC proves compactness, it does not follow that ZFC proves the consequent of this implication, as in fact ZFC does not prove the antecedent; ZFC only proves each particular instance of the antecedent, but not the universal statement itself.)

Answer by Sridhar Ramesh for Confusion over a point in basic category theory

2010-02-19T21:24:54Z

(Expanding on Yuan's point about the irrelevance of "machine language" and JT's about "the wrong question to ask":)

In a sense, one oughtn't even be able to ask whether two topological spaces (i.e., objects of Top) are equal, only whether they are isomorphic; if one can't ask about equality, then one certainly can't speak of cardinality (with respect to such equality), and so there is no notion of the cardinality of the collection of objects isomorphic to a given one.

However, if you construe every topological space as implicitly carrying extra non-topological information via which such a non-topological notion of equality is defined (e.g., if you take the points of topological spaces to furthermore be elements of the cumulative hierarchy of well-founded sets of sets of sets..., allowing one to ask whether points in distinct spaces are equal by appeal to this extra structure, and accordingly whether spaces themselves are equal by virtue of an isomorphism sending points to equal points), then, of course, the question can be answered (in the given example, as noted above, the answer will be that the isomorphism classes form proper classes). But this is not really a question about the category of topological spaces, as such; this is a question about the particular manner in which one may choose to realize the intuitive theory of topological spaces within the ontology of another (meta)theory/implement the structure of the category of topological spaces within a context imposing further structure as well.

If one avoids selecting such "implementation details", then the question is meaningless, in precisely the same way as questions such as "Is the integer 9 an element of the rational -3/5?" are meaningless in the abstract.

If a category is "monadic", is it necessarily so in a unique manner?

2010-02-16T07:32:21Z

Just a minor curiosity that's flitted across my mind, but that's (part of) what this site's for, right?:

Is it possible for Hom(a, -) and Hom(b, -) to both be monadic functors from C to Set, for non-isomorphic objects a and b in C? Ideally, the answer would come with either a nice example or an outline of a nice proof of impossibility (i.e., proof that all monadic representable functors on a category are isomorphic).

Answer by Sridhar Ramesh for "Philosophical" meaning of the Yoneda Lemma

2010-02-12T21:58:05Z

If you have basic experience with abstract algebra, the ideas in the Yoneda lemma should be quite familiar and even intuitive; the apparent difficulty is only in recognizing them in this new presentation.

You can think of "category" as meaning the same thing as "algebraic theory in a multisorted language with only unary functions" (the objects of the category being the sorts of the language, the morphisms being the definable functions, and the equalities between (composites of) morphisms being the laws of the theory). From this perspective, a functor from C to Set is simply a model of the theory corresponding to C, and natural transformations of such functors are homomorphisms of models. The Yoneda lemma then is about free models: specifically, it says that for every sort s, the "term model" of terms with a single variable, of sort s (equivalently, definable functions with domain s) is the free model on a single generator of sort s. [It may be unfamiliar when expressed as "Nat(Hom(s, -), M) ~= M(s), naturally in M", but that is indeed all this categorical expression is saying]

The so-called co-Yoneda lemma mentioned in the other comments also has a nice interpretation from this perspective, amounting to the demonstration that every model can be specified by generators and relations.

(I wouldn't say this is The One Right Way to think about the Yoneda lemma, because it's useful to view it from many different perspectives, but this is certainly One Right Way to think about the Yoneda lemma.)

Effects of "weak" vs. "strict" categories in Eckmann-Hilton arguments

2010-02-11T03:55:31Z

A standard example for demonstrating the need for genuinely weak n-categories is that a weak 3-category with unique 0- and 1-cells amounts to the same thing as a braided monoidal category (by an Eckmann-Hilton argument), but were one to use a strict 3-category instead, this would automatically become a fortiori symmetric. In trying to get a better intuition for "the right notion" of weak categories (this is still unsettled, right?), I was wondering if anyone could give me a good intuition for what step in the argument for symmetry in the strict case we want to fail in the weak case and why. [I suppose this amounts to more generally giving a good intuition for what higher-dimensional coherence isomorphisms we should refrain from demanding to exist in the definition of weak categories, and why, but this example seems in particular like a usefully illustrative introductory context]

Answer by Sridhar Ramesh for Compact Hausdorff and C^*-algebra "objects" in a category.

2010-02-10T10:35:30Z

Question 1: If I understand you correctly, you're proposing that $\mathbb{C}$ should be a compact Hausdorff object in some category because it represents a functor from that category to the category CH of compact Hausdorff spaces (in something like the sense that the functor $Hom(-, \mathbb{C})$ into Set factors through the forgetful functor from CH to Set). But I don't see why this should be sufficient to make $\mathbb{C}$ a compact Hausdorff object.

That is, presumably, from the approach of functorial semantics, a compact Hausdorff object in a category C should be a product-preserving functor from L to C, where L is the dual of the Kleisli category for the ultrafilter monad on Set (that is, L is the Lawvere theory whose category of (Set-)models is the category of compact Hausdorff spaces). I can see how, more generally, for any Lawvere theory L and category C, every C-model of L (i.e., a product-preserving functor F from L to C) induces a representable functor Hom(-, F(1)) from C to Set which factors through the forgetful functor from Set-models of L to Set. But it's not obvious to me that the converse of this holds as well (that every representable functor from C to Set with this factorization property arises from some C-model of L).

Perhaps I'm missing something and your reasoning for $\mathbb{C}$ being a compact Hausdorff object is something more than this. Perhaps I'm hopelessly confused. But, tentatively, I think the answer to question 1 is "No" or at least "Not necessarily".

(Edit: As seen below, the correspondence does go both ways, so the last line is retracted, leaving the second-to-last line...)

Answer by Sridhar Ramesh for Can we recognize when a category is equivalent to the category of models of a first order theory?

2010-02-10T20:32:02Z

I'm not sure if this is exactly the sort of thing you are looking for, but call a category a "Boolean logos" just in case it has finite limits, the subobjects of any object form a Boolean algebra under inclusion, and pullback along any morphism induces a homomorphism of such Boolean algebras with left and right adjoints. [Much of this definition is redundant, but no matter]. Boolean logoses, functors between them which preserve all the defining structure, and arbitrary natural transformations between those comprise a two-category, which I'll call BoolLog.

Up to equivalence, the categories of all models of some theory in multi-sorted classical first-order logic with equality and the elementary embeddings between them are precisely those of the form BoolLog[B, Set]. That is, a category C is equivalent to one of the form Mod*(T) just in case there is some Boolean logos B such that C is equivalent to the full subcategory of Set^B consisting of those functors which preserve Boolean logos structure.

This isn't really saying much (the definition of a Boolean logos is a very straightforward categorical rendering of the definition of multi-sorted classical first-order logic with equality [although, like I said, it could be pared down a bit. And, of course, we can easily tweak the former definition around a little to correspond to variants on the latter (e.g., the single-sorted case, the intuitionistic case, etc.)]), but, perhaps such categorical rendering is all you were looking for (although, re-reading the reply you gave to my comment above, I suspect you were after a different sort of answer. Oh well.)

EDIT: I may as well add a paring down of the definition now. Another (equivalent) way to define a Boolean logos is as a category with finite limits, a right adjoint to pullback of subobjects along any morphism, and an initial object, such that certain maps constructed out of this structure have inverses (explained below). The category BoolLog has these as 0-cells, functors preserving finite limits, initial objects, and right adjoints to subobject-pullback as 1-cells, and arbitrary natural transformations as 2-cells; as before, the Hom-categories BoolLog[B, Set] are the categories of models of B and elementary embeddings between them. The requirement for preservation of initial objects destroys many of the completeness/cocompleteness properties for models which we might otherwise have expected from universal algebra; e.g., there won't necessarily be finite limits of models or "free" (i.e., initial) models.

There are two isomorphism conditions to complete this definition of a Boolean logos: 1) the unique maps from an initial object to its product with any other object should be isomorphisms [i.e., products distribute over 0-ary coproducts], and 2) from the previous structure, it follows that the subobjects of any object form a cartesian closed preorder with an initial object. In these preorders, the initial objects should be dualizing [which suffices to make these Boolean algebras].

I didn't add conditions to force Boolean logoses to represent complete theories, but that's easy enough: this happens just in case the only subobjects of the terminal object are the unique maps into it from itself and the initial object. And, of course, consistency amounts to asking for these two maps to be distinct; equivalently, the terminal category is the unique Boolean logos representing an inconsistent theory.

EDIT2: Whoops, also, in both definitions, I forgot to add the Beck-Chevalley condition: for every object A, the right adjoint to subobject pullback along the projection A x - $\rightarrow$ - should be a natural transformation (from Sub(A x -) to Sub(-)).

Answer by Sridhar Ramesh for Hat Problem/Hamming Codes

2010-02-11T09:34:46Z

Well, I wouldn't say there's just one case where they lose, but it depends on how you count cases. Remember, the idea is that the number of people is of the form $2^n - 1$. Accordingly, if we take a case to be an ordered assignment of colors, then there are $2^{2^n - 1}$ different cases. The fraction of these in which the prisoners is win is $(2^n - 1)/2^n$, but the denominator here isn't the number of cases, on this method of counting them; there's more than one case in which they lose.

Anyway, the way it works is that in a Hamming code, some cases (specifically, $2^{2^n - 1 - n}$ of them) are picked as "well-formed" such that for every case A, there is a unique well-formed case B such that the number of color changes between A and B is at most 1.

So, suppose the prisoners use the strategy "Consider both possible cases compatible with the information available to you. If one of them is well-formed (they won't both be), then guess in accordance with the other one. Otherwise, in the case where neither of them is well-formed, you should refrain from guessing". What will the outcome be?

What happens is that, in those cases which are well-formed, every prisoner guesses wrong, since every prisoner will take the first branch of the above strategy. On the other hand, in those cases which aren't well-formed, there is a unique prisoner who goes down the first branch and guesses correctly, while every other prisoner goes down the second branch and refrains.

Accordingly, the number of cases in which the prisoners lose is the number of well-formed cases; that is, $2^{2^n - 1 - n}$. So the fraction of cases in which the prisoners lose is $2^{2^n - 1 - n}/2^{2^n - 1} = 1/2^n$. Like I said, though, this isn't just one case (if we identify cases with ordered assignments of colors).

(Incidentally, if you'd like to know how to actually construct a Hamming code, you can take the well-formed cases to be those with the property that, for every $i$, there are an even number of black hats at positions whose $i$th bit is 1 (using position numbering starting at 1). It should be straightforward to verify that this has all the properties mentioned above)

Answer by Sridhar Ramesh for What is information-theoretic lower bound?

2010-02-11T03:10:04Z

I suspect you are discussing the bounds given by Shannon's work on information theory and so-called Shannon entropy (e.g., the bounds given by the Shannon coding theorem). However, I think you need to be more specific about the context you are looking at before anyone can give a good response to "what does it really means". (Indeed, I think your question could well-stand to be clearer in general.)

Comment by Sridhar Ramesh

2012-12-01T00:41:23Z

Surely, the thing to do is to use q = p(1) + 1 rather than q = p(1), so as not to have to treat the case p(q) = q^n on an ad hoc basis.

Comment by Sridhar Ramesh

2012-11-29T11:10:10Z

Oh, bother, I suppose I'm actually just repeating Robert Israel's answer...

Comment by Sridhar Ramesh

2012-11-19T23:21:53Z

This site is for research-level mathematics. If you go to math.stackexchange.com instead, they will be more helpful to you.

Comment by Sridhar Ramesh

2012-11-18T01:25:04Z

What does "separated by the same geodesic distance" mean for two points?

Comment by Sridhar Ramesh

2012-11-17T19:23:14Z

Well, one caveat: One needs that Tarski's result is constructive enough that we have not just "For every T, for every model, there is a G such that...", but in fact "For every T, there is a G such that for every model...". But, basically, were Tarski's result phrased as strongly as its proof actually warranted, it would give us everything.

Comment by Sridhar Ramesh

2012-11-17T18:54:02Z

I've modified the word of the second paragraph to alleviate this concern. The second incompleteness theorem follows from the simultaneous "external" and "internal" truth of Tarski's theorem (by which I mean, the fact that Tarski's theorem is both true and provable (or, just as well, true inside every model)).

Comment by Sridhar Ramesh

2012-11-02T22:19:00Z

It's also worth noting that the trivial topos, like all toposes, internally considers itself to be non-trivial. It just happens to also consider itself to be trivial...

Comment by Sridhar Ramesh

2012-11-02T22:17:31Z

In the internal logic of the trivial topos, "there is no rational square root of two" is true. It's just that "there is a rational square root of two" is also true. The internal logic of the trivial topos happens to validate all statements; that's what makes it so trivial. But it also means it doesn't harm anything, or make any difference to the model-theoretically valid statements, to consider it a legitimate model.

Comment by Sridhar Ramesh

2012-10-21T18:53:11Z

I don't think the omnific integers can admit an ordinal-valued (as opposed to omnific integer-valued) Euclidean function; an ordinal-valued Euclidean function should still lead to being a unique factorization domain, in the usual way, but the omnific integers lack unique factorization (e.g., 2, 3, 5, 7, ..., all remain prime, but $\omega$ is divisible by all infinitely many of them).

Comment by Sridhar Ramesh

2012-10-07T06:02:56Z

"given that Seat 15 was selected, there are 30 possible rows that are equally likely to be selected". This is incorrect; the rows are not equally likely to be selected. But this site is for research-level questions. If you go to math.stackexchange.com, they will happily help explain to you why, conditioned on a particular seat number having been selected, it's more likely to have come from a smaller row with less alternatives.

Comment by Sridhar Ramesh

2012-10-03T17:06:31Z

Naive question: what is the sense in which these final tessellations live in FOUR-space?

Comment by Sridhar Ramesh

2012-10-03T04:18:40Z

Are you sure it wasn't \vDash ($\vDash$)?

Comment by Sridhar Ramesh

2012-09-23T23:52:03Z

It's not clear to me that {1, 2, ..., n} is contained in $T_n$. How do I get 2 or 3 triangles with just 3 vertices?

Comment by Sridhar Ramesh

2012-09-19T03:53:19Z

("If a proof if" should be "If a proof of", of course. I am too lazy to delete the comment and retype the whole thing just to fix it)

Comment by Sridhar Ramesh

2012-09-19T03:51:10Z

If a proof if $p$ implies $q$ by contrapositive (establishing $\neg q$ implies $\neg p$) is useful because one learns intermediately that ($\neg r_1$ implies $q$), ($\neg r_2$ implies $q$), etc., then a proof of $p$ implies $q$ by contradiction (establishing $\neg (p \wedge \neg q)$) is useful because one learns intermediately ($p \wedge \neg r_1$ implies $q$), ($p \wedge \neg r_2$ implies $q$), etc.