User marc alcobé garcía - MathOverflow

Universe view vs. Multiverse view of Set Theory

2010-09-22T12:31:17Z

Here I refer to Hamkins' slides:

http://lumiere.ens.fr/~dbonnay/files/talks/hamkins.pdf

particularly, to the "Universe view simulated inside Multiverse", p. 22.

My question is: is it very unsound to ask if the Multiverse view could be simulated (in a similar sense) inside Universe?

If it is, why is it? If it is not, why should one prefer one view to the other?

Feferman's extensional and intensional applications of the method of arithmetization

2011-05-12T13:01:40Z

At the very beginning of Feferman's Arithmetization of metamathematics in a general setting it can be read:

The method of arithmetization, as developed by Gödel[10], exploits the possibility of defining within a formal theory $\mathcal{T}$, or in arithmetical theories closely related to $\mathcal{T}$, various syntactical and logical notions concerning $\mathcal{T}$. In broad terms, the applications of the method can be classified as being extensional if essentially only numerically correct definitions are needed, or intensional if the definitions must more fully express the notions involved, so that various of the general properties of these notions can be formally derived.

He then proceeds to enumerate results of what he calls the extensional type (Gödel's first incompleteness theorem, non-definability of predicates in formal theories, undecidability of various theories and degrees of unsolvability of various theories), results of intensional type (Gödel's second incompleteness theorem, comparison of theories by relative consistency proofs and ordinal logics), a result of mixed character (the arithmetization of Gödel's completeness theorem for first-order logic), and finally of proofs which are "instances where intensional methods are used to deduce purely extensional results" (the proofs of non-finite axiomatizibility of various theories $\mathcal{T}$ obtained by showing $\mathcal{T}$ to be reflexive, i. e. that the consistency of every finite subtheory of $\mathcal{T}$ is provable in $\mathcal{T}$).

I guess that for the trained logician these examples suffice for him or her to get a clear sense of what is meant by intensional and extensional methods and results in this context, but this is not my case. I would be grateful if anyone could help to make these notions precise.

Thank you in advance.

Martin's "Philosophical Issues about the Hierarchy of Sets"

2011-04-29T11:36:42Z

Some months ago (October 2010), in the context of the Workshop on Set Theory and the Philosophy of Mathematics, Professor Donald A. Martin gave a talk entitled "Philosophical issues about the hierarchy of sets".

Abstract: I will discuss some philosophical questions about the cumulative hierarchy of sets, its levels, and their theories. Some examples:

(1) It is sometimes asserted one cannot quantify over everything. A related assertion is that each of our statements about the universe of sets can from a different perspective be seen as a statement about some Va. Thus the class-set distinction is really a relative one. Does this make sense? Is it right?

(2) Is the first order theory of V determinate? Does every sentence have a truth value? Are there levels of the hierarchy whose first order theories are indeterminate? If so, what is the lowest such level? What about L and the constructibility hierarchy?

(3) There are many examples of proofs of a statement about one level of the hierachy that use principles about a higher level. Under what conditions and in what sense do these count as establishing the lower level statement?

I will discuss these questions mainly from a viewpoint that takes mathematics to be about basic mathematical concepts, e.g., those of natural number, real number, and set.

I am highly interested in learning how these questions might be answered (as you may problably know from previous questions of mine here in MO), so I would be grateful if anyone could give any information in this respect, especially for those questions of 1 and 3 (I am afraid it is almost impossible to do justice to 2 in a few lines).

Slaman and Woodin on Mathematical logic

2011-03-02T09:55:18Z

At the references section of the wikipedia article for Definable set, one finds the following entry:

Slaman, Theodore A. and W. Hugh Woodin. Mathematical Logic: The Berkeley Undergraduate Course. Spring 2006.

What kind of material is it? Manuscripted lecture notes? Is it available somehow? I'm highly curious about its content.

Intended interpretations of set theories

2011-02-14T09:00:12Z

In his Set Theory. An Introduction to Indepencence Proofs, Kunen develops $ZFC$ from a platonistic point of view because he believes that this is pedagogically easier. When he talks about the intended interpretation of set theory he says such things as, for example, that the domain of discourse $V$ is the collection of all (well-founded, when foundation is introduced) hereditary sets.

This point of view has always made me feel a bit uncomfortable. How can a variable in a first-order language run over the elements of a collection that is not a set? Only recently I realized that one thing is to be a platonist, and another thing is to believe such an odd thing.

A first-order theory of sets with a countable language can only prove the existence of countably many sets. Let me call them provable sets for short. Platonistically, we wish our intended interpretation of that theory to be one in which every provable set is actually the set the theory says it is. So we don't need our interpretation to contain every set, we just need that it contains at least the true provable sets. This collection is, really, a set, although it doesn't know it.

To be a bit more concrete, if one is a platonist and the cumulative hierarchy is what one has in mind as the real universe of sets, one can think that the $V$ of one's theory actually refers to a an initial segment of that hierarchy, hence variables run no more over the real $V$ but only over the elements of some $V_\alpha$.

There's a parallel to these ideas. For example, when we want to prove consistency with $ZFC$ of a given sentence, we do not directly look for a model of $ZFC$ where that sentence is true, but instead we take advantage of knowing that every finite fragment of $ZFC$ is consistent and that every proof involves only finitely many axioms.

My question is: then, is this position tenable or am I going awfully wrong? I apologize that this seems a philosophical issue rather than a mathematical one. I also apologize for stating things so simply (out of laziness).

Answer by Marc Alcobé García for How To Present Mathematics To Non-Mathematicians?

2011-01-07T12:55:27Z

If I had to explain large cardinals in 10 minutes my first source of inspiration would be Kanamori's excellent writings about their (whiggish) history. People like history. I wouldn't spend any time trying to justify or prove any result. Maybe 2 minutes to explain the cumulative hierarchy so that everybody understands the typical picture of V. If people guess there is a long coherent tradition of research starting from Cantor, hence of interest in the field, I think that's enough. They really don't need to understand anything, just have a general feeling of a sort of flow of ideas.

Answer by Marc Alcobé García for What would you want to see at the Museum of Mathematics?

2010-12-29T13:36:35Z

Rather than providing concrete examples, I would like to make a suggestion about two possible guiding lines.

If you agree that mathematics is about solving problems of a certain kind, then two sensible goals for a museum of mathematics could be showing:

what kind of problems mathematics deals with, and
how it deals with them.

The first goal cannot be exhaustive for obvious reasons, but I think it should be broad enough to give the visitor an idea of the diversity of mathematics (applied or not), i. e. examples from as many various branches as possible should be given.

For the second goal, Polya's views about how to solve mathematical problems could be helpful, or modern works about "visual" mathematical thinking. I think visitors should be able to feel some connection between mathematical problem solving and applying "common sense" strategies (here is a hidden goal: to demistify a bit the work of mathematicians).

To focus on one or the other goal in different degree can result in very different kinds of museum, but I think any of them would deserve the name "Museum of mathematics". Not so one that didn't meet any of both goals.

Semidecidable sets

2010-12-28T14:19:10Z

A set $S$ (of natural numbers) is (semi)decidable if its (semi)characteristic function is effectively calculable.

From a set theoretic point of view, the semicharacteristic function of a set is just a particular subset of its characteristic function. Consider the subsets of the characteristic function of a given set which are supersets of its semicharacteristic function. All of them are partial functions, but some might be effectively calculable, and some might not. I don't know how to call these functions, but let me use $f_S$ as a variable that ranges over them for a given set $S$ .

Is there any S for which the only effectively calculable $f_S$ is its semicharacteristic function?

Statements that require the existence of non-standard models to hold

2010-10-05T13:04:17Z

From the Incompleteness theorems, if ZF is consistent, one knows there are models of ZF satisfying ¬Con(ZF). These models must be non-standard (in the sense of being models whose ordinals are not well-ordered), and so must be the proof of an inconsistency from the axioms of ZF in them.

Now, ¬Con(ZF) is a very special kind of arithmetical statement. My question is, are there other kinds of statements consistent with ZF known to require the existence of non-standard models to hold?

If there are any, how does one recognize them?

Answer by Marc Alcobé García for Is it important to distinguish between meta-theory and theory?

2010-10-07T09:46:26Z

As you already mention in the body of your question, there are also philosophical reasons for doing so. See, for example, Kunen's "The Foundations of Mathematics" Chapter 3 (esp. Sec. 3.2 Keeping them Honest).

I'll try to quickly outline it here, freely using Kunen's own ideas and words (but if you find any mistake here, it'll be my fault).

As to what is the metatheory we cannot say exactly. Basically it is ordinary finitistic reasoning about finite objects, or in other words, "how we think about the world". You need finitistic reasoning even to understand finitistic reasoning (you can get nothing from nothing). So this is why one usually regards it as what is "really true".

The formalist point of view needs, in order to be philosophically justified, to develop logic twice:

Working in the metatheory, one develops formal logic, proving finitistic theorems about one's notion of formal proof to make sense of it, particularly Soundness saying that if $\Sigma$ proves $\phi$ then $\phi$ is true in all finite models of $\Sigma$ .

Then, one goes on to develop ZFC, and within ZFC, one develops all of standard mathematics, including (not finitistic) model theory. To develop model theory, one must again develop formal logic. One uses at this stage the same reasoning, but now both the languages and the structures for them have arbitrary cardinalities, and the reasoning is formalized within ZFC.

But if you are a platonist and think that the ZFC axioms are obviously true, I don't think there is much need for such a distinction.

Existence of an $\omega$-nonstandard model of ZFC from compactness

2010-10-02T09:21:21Z

I have read several times that assuming Con(ZFC), and using compactness it can be proved the existence of a model of ZFC with an ill-founded $\omega$. How is that? Any reference will be welcome.

Subsets of sequences of natural numbers vs. strategies under ZFC

2010-07-28T20:09:52Z

This question is related to a previous question of mine:

http://mathoverflow.net/questions/32966/determinacy-interchanging-the-roles-of-both-players

Given any set A of sequences of natural numbers, every strategy (no matter for which player) is either winning (W), or losing (L), or neither(N) for A.

So depending on A, the set of all strategies available for any of both players can be, a priori, of any of the seven kinds: W (all winning), L (all losing), N (all neither), WL (some winning and the rest losing), WN (some winning and the rest neither), LN (some losing and the rest neither) and WLN (some winning, some losing, and the rest neither).

This makes a total of 49 situations (now taking into account both players). Of course, not all of them are possible because we have the following restrictions:

a. If one player has a winning (losing) strategy, the other one cannot have a winning (losing) strategy. b. If one player has only winning (losing) strategies, the other one only has losing (winning) strategies.

I don't know of any other restrictions (not derivable from them, for example it follows that if one player is WL for A, the other one can only be N).

This leaves us with the following possible situations:

(I'd draw a table here, but unfortunately I don't know how to edit it; I tried html without sucess)

W for I and L for II
L for I and W for II
N for I and N for II
N for I and WL for II
N for I and WN for II
N for I and LN for II
N for I and WLN for II
WL for I and N for II
WN for I and N for II
WN for I and LN for II
LN for I and N for II
LN for I and WN for II
WLN for I and N for II

My question is, could one find examples (prove the existence of subsets of sequences of naturals) for each situation only assuming ZFC?

Some are obvious, like the empty set for 2 or the set of all sequences for 1, or like the set of all sequences with a 1 in the odd positions for 8, but others may be not.

Determinacy interchanging the roles of both players

2010-07-22T15:59:27Z

Let me refer to Jech's "Set Theory" Chap. 33 Determinacy:

"With each subset A of $\omega^\omega$ we associate the following game $G_A$ , played by two players I and II. First I chooses a natural number $a_0$ , then II chooses a natural number $b_0$ , then I chooses a1, then II chooses b1, and so on. The game ends after $\omega$ steps; if the resulting sequence $<a_0, b_0, a_1, b_1, ...>$ is in A, then I wins, otherwise II wins.

A strategy (for I or II) is a rule that tells the player what move to make depending on the previous moves of both players. A strategy is a winning strategy if the player who follows it always wins. The game $G_A$ is determined if one of the players has a winning strategy.

The Axiom of Determinacy (AD) states that for every subset A of $\omega^\omega$ , the game $G_A$ is determined."

Now, there is some apparent lack of symmetry in the definition of the $G_A$ game: the player who plays first (I) attempts for a sequence in A.

What happens if we interchange the roles of both players? I. e. if we let the player who plays first attempt for a sequence not in A? Let us call this game $G'_A$

Is it the case that for every subset A, A is determined wrt $G_A$ iff A is determined wrt $G'_A$ ?

Tractability of forcing-invariant statements under large cardinals

2010-07-21T07:24:30Z

It is usual to mention theorems of the kind:

Th. Assume there is a proper class of Woodin cardinals, $\mathbb{P} $ is a partial order and $G \subseteq \mathbb{P}$ is V-generic, then $V \models \phi \iff V[G] \models \phi$

where $\phi$ is some set theoretic statement (like "the Strong Omega Conjecture holds"), as some sort of evidence that $\phi$ is a statement less intractable than other statements like CH which are not focing-invariant.

My question is, in wich sense are these statements more tractable? What kind of "empirical evidence" gives support to the hope that they can be decided by large cardinal axioms?

Weakest subsystems of second order arithmetic for mathematical logic

2010-07-07T15:29:52Z

It is known that to prove completeness of first-order logic for countable languages WKL₀ is enough. But, is it the weakest subsystem where one can prove it?

What about the incompleteness theorems? Is it known which are the weakest subsystems of second order arithmetic where one would be able to prove each of them?

Answer by Marc Alcobé García for Models of ZFC Set Theory - Getting Started

2010-06-27T09:37:33Z

This answer is going to be a bit too informal, but I hope it helps.

Imagine we have the collection of all sets. Let us call them the real sets, and their membership relation the real set membership. The empty set is "actually" empty, and the class of all ordinals is "actually" a proper class.

Now that we have the real sets we can use them as the "ontological substratum" upon which everything else will be built from. And this, of course, includes formal theories and their models.

A model of any first-order theory is then only a real set. This applies to your favorite set theory too. So the models of your set theory are only real sets (but the models don't know it, just as they don't know if their empty sets are actually empty or if their set membership is the real one).

This view fits well, for example, with the idea of moving from a transitive model to a generic extension of it or to one with a constructible universe: we are simply moving from a class of models to another one, each one consisting of real sets.

But this view also leaves us with too many entities, and maybe here we have an opportunity to apply Occam's razor. It looks like we have two kind of theories: one for the real sets, which is made of things that are not sets (we can formalize our informal talk about them, but that does not make essentially any difference), another one for the models of set theory, which is made of sets.

The real sets and the theory of the real sets belong to a world where there are real sets, but there are also pigs and cows, and human languages and many other things. We don't need all that to do mathematics, do we? So why not diving into the wold of the real sets and ignore everything else?

If this story sounds too platonistic, I am sure it must have a formalistic counterpart.

With my question:

http://mathoverflow.net/questions/28869/how-to-think-like-a-set-or-a-model-theorist

I expected to obtain an official view about all this stuff. I somehow succeeded on this, but as you can see, I'm still working on it.

Here is a related answer to a related question which I also find useful:

http://mathoverflow.net/questions/15685/is-it-necessary-that-model-of-theory-is-a-set/15713#15713

Non-computable but easily described arithmetical functions

2010-06-23T07:28:48Z

I have read about the existence of functions of the kind described in the title in several places, but never seen an instance of them. Sorry if this is too much an elementary question to be posted here.

How to think like a set (or a model) theorist.

2010-06-20T17:55:43Z

Kenneth Kunen in his “The Foundations of Mathematics” writes:

‘Set theory is the study of models of ZFC’ (p. 7)
‘Set theory is the theory of everything’ (p. 14)

With (1) Kunen is pointing to a change in the intended use of the axioms of ZFC: ‘there are two different uses of the word “axioms”: as “statements of faith” and as “definitional axioms”.’ (p. 6).

With (2) he means ‘set theory is all-important. That is

All abstract mathematical concepts are set-theoretic.
All concrete mathematical objects are specific sets.’ (p. 14)

According to (1), to be a set is to be any of the individuals of the universe of a particular model of ZFC, just like being a numeral (standard or not) is being any of the individuals of the universe of a particular model of PA (here I am using Shoenfield’s terminology in “Mathematical Logic”, p. 18).

But, according to (2), models are sets too, as any other objects dealt with in the metatheory.

What's more, models of set theory are defined in terms of relative interpretations of set theory into itself, a syntactical concept. (See Kunen’s “Set Theory. An Introduction to Independence Proofs”, p. 141), which makes the whole thing a bit more confusing.

The view of the axioms of set theory as "definitional axioms" is appealing. And more in regard of (2) since then they pretend to define all that there is. The study of models of set theory has an intrinsic interest, but why reduce the study of set theory to it? Or stated another way, why abandoning the old view?

I would like to know if set theorists do stick to one view or another or shift comfortably between both at need, and the reasons they have to do so.

Breaking the circularity in the definition of N

2010-06-14T20:17:47Z

Some days ago, I posted a question about models of arithmetic and incompleteness. I then made a mixture of too many scattered ideas. Thinking again about such matters, I realize that what really annoyed me was the assertion by Ken Kunen that the circularity in the informal definition of natural number (what one gets starting from 0 by iterating the successor operation a finite number of times) is broken “by formalizing the properties of the order relation on ω” ( page 23 of his “The Foundations of Mathematics”). What does actually “breaking the circularity” mean? Is there a precise model theoretic statement that expresses this meaning? And what about proving that statement? Is that possible?

Incompleteness and nonstandard models of arithmetic

2010-06-01T07:09:21Z

The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome.

Reading Peter Smith's "Gödel Without (Too Many) Tears", particularly where he gives a nonstandard model of Q, I began wondering if the reason for the existence of nonstandard models of arithmetic has anything to do with incompleteness theorems.

I do not know if categoricity implies completeness (in the sense of every sentence being decidable by proof), but anyway, it seems reasonable, when one is formalizing a given (informal) theory, to try to "force" somehow the formal theory to talk "almost exclusively" about the intended interpretation. So I started thinking if some axiom (or axiom schema) could be added to PA in order to forbid its most obvious nonstandard models.

The first idea in this line was: ok, we have our class of terms 0, S0, SS0, etc. So, if we found a way to tell that for every x there is some term to which it is equal, we would be done.

But then I realized that our terms are defined inductively and that we are making implicitly the assumption: “and nothing else is a term”, very similar to the desired “and nothing else is a number” we would like to add to PA. This thought sort of worried me: every metatheoretic concept (terms, formulas, and even proofs!) is based on assumptions like these! (I have not still found a way out of these worries).

Leaving that apart. What if we move on to a stronger theory (with different axioms, but with an extension by definitions that proves every axiom of PA), for example ZFC? Natural numbers become then 0 (the empty set) plus the von Neumann ordinals (obtained by Pair and Union) that contain no limit ordinal. The set of natural numbers is obtained from Infinity, just selecting them by Comprehension. Kunen says in page 23 of his “The Foundations of Mathematics” that the circularity in the informal definition of natural number is broken “by formalizing the properties of the order relation on omega”. Could nonstandard models survive this formalization?

Well, I think I've read somewhere that being omega is absolute, so forcing would not be a way to obtain such nonstandard models. Also, I am not sure if (the extension by definitions from) ZFC set theory is a conservative extension of PA, but then it would not be able to prove anything about natural numbers (expressible in the language of arithmetic) that PA alone cannot prove. So somehow it looks like nonstandard models must manage to survive! Maybe due to the notion of being a subset of a given set not being particularly clear (although it looks like it should not be problematic with hereditarily finite sets).

Thank you in advance.

Answer by Marc Alcobé García for Proof of Gödel incompleteness

2010-06-07T13:17:35Z

I think reading:

http://sammelpunkt.philo.at:8080/1126/1/Bagaria.pdf

is going to help you.

Jech's proof is rewritten a bit more explicitly (see section "III. SHORT PROOFS"), and then used in the next section to prove Gödel's second incompleteness theorem for weaker theories than ZF.

Answer by Marc Alcobé García for Papers that debunk common myths in the history of mathematics

2010-06-01T08:45:48Z

A recent one could be Peter Milne's "On Gödel Sentences and What They Say" Philosophia Mathematica (III) 15 (2007), 193–226. doi:10.1093/philmat/nkm015 debunking the myth that Gödel sentences are true because they say of themselves that they are unprovable.

Sorry, I realize this is not exactly what was being asked. However, there is still some analogy with the pattern "someone was believed to do or say something while in fact he/she didn't".

Answer by Marc Alcobé García for Examples of common false beliefs in mathematics.

2010-06-01T12:43:18Z

A common false belief is that all Gödel sentences are true because they say of themselves they are unprovable. See Peter Milne's "On Goedel Sentences and What They Say", Philosophia Mathematica (III) 15 (2007), 193–226. doi:10.1093/philmat/nkm015

Comment by Marc Alcobé García

2011-05-01T19:56:02Z

Asaf, I think Joel refers in his slides to the staggering diversity of models of set theory as giving rise to different set concepts (please correct me if I am wrong, I didn't check). I am not sure one can make this identification the other way round. I would not, a priori, think of an instantiation of a set concept as a model of a first-order theory of sets.

Comment by Marc Alcobé García

2011-04-30T20:08:02Z

I suppose that something counts as an instantiation of the full set concept if its powersets contain every conceivable subset (if this really means something), but also if it contains every conceivable ordinal (again, if this really means something).

Comment by Marc Alcobé García

2011-04-30T18:07:25Z

Thank you vey much, Joel. Do you know where could I read more about $V_\delta\prec V$ and its properties? Also, I have googled for Martin's articles and the most recent that I have found is "Multiple Universes of Sets and Indeterminate Truth Values" (2001).

Comment by Marc Alcobé García

2011-04-29T20:25:20Z

@jc Yes, I have, but with no success by now.

Comment by Marc Alcobé García

2011-03-12T12:50:00Z

It looks like it is that study of definability what motivated its inclusion among the references for the article I mentioned in my question. Thank you very much.

Comment by Marc Alcobé García

2011-03-02T11:20:17Z

If it has not been published, maybe I ought to ask the authors directly. I have no idea of what kind of material it is (manuscripted lecture notes?).

Comment by Marc Alcobé García

2011-03-02T11:13:35Z

That'd be great!

Comment by Marc Alcobé García

2011-02-15T07:25:18Z

It's a pity only one answer can be accepted. Thanks a lot.

Comment by Marc Alcobé García

2011-01-16T11:14:32Z

Obviously, how to make these ideas concrete depends very much on your target public.

Comment by Marc Alcobé García

2010-12-29T07:53:58Z

Let me add this link to a brief exposition of how Post's problem was ultimately solved: en.wikipedia.org/wiki/…

Comment by Marc Alcobé García

2010-11-03T14:02:38Z

Thanks a lot for your answer, Carl. I guess there's another difference. Can one effectively write a formula defining such a $\zeta$?

Comment by Marc Alcobé García

2010-10-07T16:05:55Z

Maybe you have institutional access to Springerlink and you don't know it. The book is available there for free.

Comment by Marc Alcobé García

2010-10-02T16:09:50Z

Thanks to both for your answers.

Comment by Marc Alcobé García

2010-10-02T10:24:10Z

Not well-founded, i. e. with infinite descending epsylon-chains. In case it is not clear enough, I am asking for some (sketch of a) proof for that result, not for an explanation of why such models exist or for what they look like.

Comment by Marc Alcobé García

2010-09-25T11:22:50Z

Thanks a lot for your answer. There's just one point I don't fully understand. Why should the simulated multiverse of the first approach include the set-theoretic background universe V? After all, the full multiverse doesn't include any such thing...