first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, ...

learn more… | top users | synonyms (1)

3
votes
0answers
116 views

Silver's unpublished work on reverse Easton iteration

Silver was the first person who used the method of reverse Easton iterations in connection with large cardinals, and used it to force the failure of $GCH$ at some measurable cardinal. At most papers ...
3
votes
0answers
48 views

A question on the incompleteness of quantified K.2 and S4.2 with the Barcan formula

I have been attempting to come to grips with Max Cresswell's account of this in Journal of Philosophical Logic 24 (4):379 - 403 (1995) where he presents proofs of the incompleteness of QK.2BF as well ...
5
votes
3answers
221 views

Does this property of a first-order structure imply categoricity?

Let $\mathfrak{A}$ be a first-order structure over a relational language and let $\kappa$ be an infinite cardinal. Lets say that $\mathfrak{A}$ has the $\kappa$-property if for every structure ...
1
vote
0answers
53 views

A question on completeness for quantified temporal logics

Quantified temporal logics have the Barcan formulas and its converses for both G (it will always be the case that) and H (it has always been the case that), so that both $\forall x G \alpha ...
8
votes
2answers
300 views

Ultracoproducts and Cartesian products

Let $X$ be a metrizable compact topological space, let $\mathcal U$ be an ultrafilter, and denote by $X^{\mathcal U}$ the ultracopower of $X$ with respect to $\mathcal U$. As a C$^*$-algebraist, I ...
6
votes
1answer
262 views

A “good scale” that is not really a scale

I don't know much about singular cardinal combinatorics, so I apologize in advance if I write something that is wrong or looks funny. First let me recall some basic definitions. Let $\lambda$ be a ...
11
votes
2answers
448 views

Failure of diamond at large cardinals

What is known about the failure of $\Diamond_{\kappa}$ (diamond at $\kappa$) for $\kappa$ (the least) inaccessible, (the least) Mahlo and (the least) weakly compact. Remark. The problem of forcing ...
14
votes
1answer
295 views

Three old questions on the Sacks forcing

I came across the two following Qs in 1970. Find reals $a,b$ such that $a$ is Sacks over $L[b]$ and vice versa $b$ is Sacks over $L[a]$. Note that a Sacks $\times$ Sacks generic pair definitely does ...
7
votes
1answer
261 views

Forcing, cuts, and Dedekind-finite cardinalities

Tl;dr version: there are two natural classes of cuts in the nonstandard model of arithmetic consisting of the Dedekind-finite sets (if, in fact, they constitute such a model); both these classes are ...
-5
votes
0answers
68 views

True lies logic [on hold]

Santa says lie on all days except one day... Once he made 3 statemnts on consequtive days : 1) I lie on monday and tuesday. 2) today is thursday, saturday or sunday. 3) I lie on wednesday and friday. ...
10
votes
3answers
1k views

Is there a categorical proof of Gödel's incompleteness theorem?

A significant result in set theory was shown by Cohen when he showed that the continuum hypothesis was independent of ZFC using a new technique called forcing. In Topos theory, this result has a new ...
1
vote
0answers
115 views

On directedness, transitivity and ancestral directedness

Let $\textit{C}$ be the modal logical schema $(\square (\square \alpha \rightarrow \alpha) \wedge \square (\square \lnot\alpha \rightarrow \lnot \alpha))\rightarrow (\square \alpha \vee \square \lnot ...
1
vote
0answers
37 views

Completeness results for quantified tense logics with BF?

Modal tense logics or temporal logics are important in that they correspond with partial orders and their extensions. Are there completeness results for quantified temporal logics with the Barcan ...
3
votes
2answers
446 views

Applications of propositional dynamic logic

Propositional dynamic logic (PDL) is an example of a (multi)modal logic with a structure on the set of modalities. In particular, the set of its modalities is indexed by "programs" and one can use ...
4
votes
1answer
158 views

On a modal correspondence

Is there an intuitive characterization of the correspondence for the modal logical formula $\square (\alpha \rightarrow \square \alpha) \rightarrow (\square \alpha \vee \square \lnot \alpha)$? In ...
6
votes
1answer
179 views

Is a computer program for correspondence theory available?

In the 1990s I some times used a computer program with the Max Planck Institute which helped with calculating complicated correspondences for modal logical formulas. Is some program like that ...
2
votes
1answer
109 views

A question on the modal logic S4.2

The modal logic S4.2 with the characteristic axioms 4: $\square \alpha \rightarrow \square \square \alpha$ and .2: $\lozenge \square \alpha \rightarrow \square \lozenge \alpha$ and T: ...
2
votes
2answers
133 views

Adjoint of Pushout as Modal Operators in Internal Logic

Regarding the internalization of mathematics to a particular category as in the nLab article: Internal Logic, there is a peculiar table mentioned in the section on Categorical Semantics in which there ...
16
votes
2answers
601 views

Which are the rigid suborders of the real line?

Which are the rigid suborders of the real line? If A is any set of reals, then it can be viewed as an order structure itself under the induced order (A,<). The question is, when is this structure ...
7
votes
1answer
246 views

Saturated Ultrapowers

I posted it on MSE and didn't receive any comments or answers, so I thought I would post it here. (See http://math.stackexchange.com/questions/895549/keisler-order-saturated-ultrapowers) Keisler's ...
5
votes
2answers
122 views

Algorithm for determining when polynomial iteration is bounded?

Let $f: \mathbb{Q}\to \mathbb{Q}$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates ...
2
votes
0answers
88 views

reference on aperiodicity and cluster [on hold]

From this image: I believe there is a message relating those clusters drawn in picture and aperiodic tiling. Does anyone have some reference on this? Thank you :)
12
votes
2answers
519 views

Are the quaternions not uncountably categorical?

Boris Zilber has argued that the field of the complex numbers is "logically perfect". For one thing, the theory of an algebraically closed field of characteristic zero is uncountably categorical: it ...
40
votes
2answers
4k views

A question about ordinal definable real numbers

If ZFC (Zermelo-Fraenkel set theory with the Axiom of Choice) is consistent, does it remain consistent when the following statement is added to it as a new axiom? "There exists a denumerably ...
-4
votes
1answer
214 views

When are two algorithms essentially the same? [on hold]

Inspired by Blass/Dershowitz/Gurevich's paper When are two algorithms the same? (which was referenced in another context here) I tried to boil down the question to the following situation: Consider ...
8
votes
0answers
176 views

Can Suslin lines ever be orderings of abelian groups?

I am interested in realizing linear orders as orderings of abelian groups. In particular, can Suslin lines (and other classes of line) be realised in this way? Let $\mathcal{C}$ be a class of ...
5
votes
0answers
95 views

A variant of Chang's model with choice

Let $M_n$, $n < \omega$, be a models of $ZFC$ with the same ordinals, closed under countable sequences. Let $\alpha_n$ be an ordinal which is a regular cardinal in $M_n$. Question: Is it possible ...
6
votes
2answers
293 views

A continuous notion of realizability

I have been interested in non-classical logics, off and on, for quite a while. This question is probably very basic, and I hope it is not too low-level for MO. My question stems from an attempt to ...
4
votes
1answer
337 views

Why is adopting Russell's Axiom of Reducibility as strong as eliminating the Ramified Hierarchy?

In order to respond to concerns of impredicativity, Bertrand Russell developed a system of ramified second-order logic, which is like regular second-order logic except the comprehension schema is ...
75
votes
42answers
16k views

What are the most attractive Turing undecidable problems in mathematics?

What are the most attractive Turing undecidable problems in mathematics? There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
11
votes
1answer
445 views

Time in Girard's Geometry of Interaction

Jean-Yves Girard writes at the end of his paper "Towards a Geometry of Interaction", page 105, that we have three intuitions about the nature of time: time is logic modulo the order of rules, time ...
4
votes
1answer
213 views

“Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?” [Tarski]

In his paper "Restricted set-theoretical defintions in arithmetic" Raphael Robinson cites a problem posed by Tarski: Is it possible to give a restricted set-theoretical definition of addition of ...
8
votes
0answers
124 views

Which forcing types preserve the axiom of determinacy?

Do we have some rudimentary understanding of some properties that a forcing can have in order to guarantee that it doesn't violate the axiom of determinacy? To be more specific, in Which forcings ...
4
votes
1answer
95 views

When are the congruence lattices nicer?

This is a purely idle question, but one I'm increasingly interested the more thought I put into it: For $\mathcal{A}$ a universal algebra (that is, nonempty set together with some named functions), a ...
4
votes
1answer
160 views

If questions are formalized as ideals of a boolean algebra, what kind of algebra of questions appears from Stone representation theorem?

Affirmative propositions make up a Boolean algebra, and Boolean algebras became part of classical algebra for over one century ago - in this sense they are "simple". But I did not encounter in ...
5
votes
1answer
516 views

Can formal logic give a precise notion of “canonical”?

Coming off of this discussion, I'm wondering what the term "canonical" really means. In that thread, many suggested category theory as a way to formalize the concept of what "canonical" means, using ...
-4
votes
1answer
169 views

An algorithm and symbolic manipulation for IF-THEN-ELSE [closed]

CONCLUSION (so far)  Look at the parentheses theorem and at the comments below the question(s) :-) As for now, only Dan Peterson has truly addressed the issue. Q1   Does there exists an ...
6
votes
1answer
136 views

Slim Kurepa tree at a singular strong limit cardinal of uncountable cofinality

For a strong limit cardinal $\kappa$ the notion of $\kappa$-Kurepa tree is trivial: the full binary tree is a $\kappa$-Kurepa tree. Accordingly, we consider the following strengthening: A slim ...
7
votes
5answers
3k views

Finding minimal or canonical expressions for Boolean truth tables

This is not an urgent question, but something I've been curious about for quite some time. Consider a Boolean function in n inputs: the truth table for this function has 2n rows. There are uses of ...
10
votes
0answers
204 views

Is there a “hereditary” construction for $L$?

Recall that $L$, Godel's constructible universe is constructed by defining the following hierarchy: $L_0=\varnothing$, for a limit ordinal $\delta$, $L_\delta=\bigcup_{\alpha<\delta}L_\alpha$, and ...
4
votes
0answers
134 views

Examples of unproven but likely true existential sentence (in the sense of incompleteness)

Some examples of universal statements that are unproven but likely true include the Riemann hypothesis (all non-trivial zeros of the zeta function have real part 1/2) and the Goldbach conjecture (all ...
10
votes
2answers
586 views

Questions about Prikry forcing and Cohen forcing

I have some questions. The first one is about the product of Prikry's forcing. Let $\kappa$ be a measurable cardinal, $U_1, U_2$ be normal measures on $\kappa$ and let $\mathbb{P}_{U_1}, ...
1
vote
1answer
78 views

A question on Carnap's modal semantics on the basis of Cochiarelli's primary semantics

I believe I learned that Carnap's state description semantics for propositional modal logic suffered from validating $\lozenge p$ for all atomic variables p. Re-reading Nino Cochiarelli's primary ...
0
votes
1answer
117 views

Definability of arithmetic functions and relations

Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand ...
4
votes
4answers
921 views

How short can we state the Axiom of Choice?

How short can we state a principle which is equivalent with the Axiom of Choice under $ZF$? The principle should be a sentence in the language of set theory with only $\in$ and$=$ as extralogical ...
10
votes
0answers
257 views

Ideas behind Gitik's solution of PCF conjecture

Recently Moti Gitik has refuted Shelah's PCF conjecture (see Short extenders forcings II ) by proving the following theorem: Theorem. Assuming the consistency of infinitely many strong cardinals, one ...
0
votes
1answer
89 views

Preserving Predimension Functions under Functional Convergences

Definition 1. If ‎$‎‎‎\mathcal{L}‎$ ‎is a‎ ‎countable relational ‎language, ‎a ‎predimension ‎class ‎‎‎‎‎$‎C‎$ is a class ‎of $‎‎\mathcal{L}$-structures with ‎the ‎following ‎properties:‎ ‎C1: ...
4
votes
2answers
193 views

What is the status of the extreme value theorem in forms of constructive mathematics, such as Smooth Infinitesimal Analysis?

In certain intuitionistic frameworks the extreme value theorem cannot be proved. Depending on the exact framework, counterexamples can be constructed as well; see for example pp. 294-295 in ...
1
vote
1answer
298 views

Is there any current development of a first order formalization of metamathematics?

I hope that this post isn't off topic, but I already asked math.stackexchange about first order formalizations of first order logic. There are provability logics and extensions in modal logic's that ...
12
votes
0answers
551 views

Does every Aronszajn tree has a Suslin or a Special subtree?

Question: Does every $\omega_1$-Aronszajn tree contains a Suslin sub-tree or a special Aronszajn sub-tree? Recall that Suslin trees are $\omega_1$-trees (trees of height $\omega_1$, and countable ...