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)

8
votes
3answers
343 views

Formulas in a Field and in a Field Extension

Let $\mathbb F$ be a field and let $a, b, c, d$ be fixed elements in the field $\mathbb F$. Consider the formulas 1) $\exists\;x\;\;:\;\;x^2=-1.$ 2) $\exists\;x\;\;:\;\;(xa=c\land xb=d).$ Formula ...
3
votes
3answers
163 views

Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA

In models of PA with restricted induction power (for example, only $I\Sigma_n$ is present), the failure of higher induction scheme is characterised by the existence of definable cuts (like $\Sigma_2$ ...
4
votes
1answer
244 views

Consistency Strength of the Failure of Square on Singular Cardinals

Q1. What is the consistency strength of the failure of square on singular cardinals? Q2. What are known as partial results in this direction?
6
votes
2answers
222 views

Possible Choices for Cofinality of $\aleph_n$ without Choice

$\text{ZFC}$ proves that each $\aleph_{n}$ for $n\in \omega$ is a regular cardinal. But it seems without the Axiom of Choice there are many consistent possible choices for cofinality of such ...
8
votes
2answers
510 views

Intuitionistic algebraic topology?

Are there results in algebraic topology -- preferably relating to homology or homotopy or phraseable in simplicial sets -- that are not true in an intuitionistic logic? In other words, are there ...
9
votes
1answer
297 views

Ackermann's function over the reals

Ackermann's function is defined over integers $x$, $y$, $A(x,y)$, with conditions for when $x{=}0$ or $y{=}0$, and otherwise uses recursive definitions involving arguments $x{-}1$ and $y{-}1$. Is ...
10
votes
2answers
401 views

Ways to define “definability”

The notion of a definable set is not expressible in the language of set theory: there is no formula $\delta(x)$ that is equivalent with there being a formula $\phi(y)$ such that $x = \lbrace y : ...
3
votes
1answer
168 views

Failure of GCH at indescribable cardinals

Can $\Pi^m_n$ indescribable cardinal be the first one where $\text{GCH}$ fails? Hauser showed in Hauser,K.: Indescribable cardinals and elementary embeddings. J. Symb. Logic 56, 439457 (1991) that ...
4
votes
1answer
228 views

Interpreting the Galois theory of finite extensions of $\mathbb{Q}$ in PA

Any finite extension of the rationals, along with its Galois group, can be interpreted in Peano arithmetic by straightforward means. For a fixed bound $n$ in the degree this is uniform in the ...
4
votes
1answer
223 views

Proving decidability of formula without deciding it

I am looking for a theory $T$ and a formula $p$ such that there is a metaproof which establishes that either $T \vdash p$ or $T \vdash \neg p$, but which does not enable us to decide which of these ...
11
votes
3answers
554 views

The interplay between certain aspects of interpretability, model theory and category theory

I have some questions about the interplay of interpretability, model theory and category theory. Since I had difficulties in finding literature or other helpful information about this topic, it would ...
1
vote
3answers
377 views

Another adjoint pair: Definable sets and set-builder formulas

I see adjointness between the two concepts of "being a definable set" and "being a set-builder formula": A set $X$ is definable when there is a formula $\phi(x)$ such that $X = \lbrace x : ...
6
votes
0answers
158 views

Vaught conjecture for uncountable languages

Recall Vaught conjecture: the number of countable models of a first-order complete theory in a countable language is finite or $\aleph_0$ or $2^{\aleph_0}.$ Now let $\lambda$ be an uncountable ...
3
votes
1answer
92 views

Disobedience of some complete r.e. set to some additive cost function

An additive cost function is defined as $c: \omega\times \omega \to \mathbb{Q}_2$ such that it is recursive, monotonic (i.e. $c(x+1,y)\leq c(x,y)\leq c(x,y+1)$ and $c(x,y)=0$ whenever $x\geq y$, the ...
3
votes
4answers
223 views

What is the role of absoluteness in existence of a non-trivial self elementary embedding on an inner model?

ِDefinition (1): Call an inner model M "rigid" if there are no non-trivial elementary embeddings $j: M\longrightarrow M$. It is possible that $L$ is not rigid, while the problem is open for $HOD$. ...
7
votes
2answers
190 views

Natural $\Pi^1_2$ (or worse) classes of structures?

(To clarify, my interest is mainly lightface, that is, $\Pi^1_2$ instead of $\bf \Pi^1_2$, although it doesn't particularly matter.) This is just an idle curiosity. In logic, I find myself frequently ...
6
votes
1answer
517 views

A Hot Betting On HOD

Remark: This question is based on an open question at the end of a paper by Hamkins, Kirmayer, and Perlmutter: "Generalizations of the Kunen Inconistency". $HOD$ as an inner model of $ZFC$ lies ...
8
votes
1answer
276 views

Categorical Semantics for Second-Order Logics

I am currently doing some work using a categorical semantics of first-order logic. The specific semantics I am using is due to Andrew Pitts, as described in: Categorical Logic, Andrew M. Pitts, ...
5
votes
1answer
174 views

Is the consistency of $\mathcal{L}_{\infty\omega}$-sentences absolute?

The question is exactly that of the title. Suppose $\varphi\in V$ is an $\mathcal{L}_{\infty\omega}$-sentence, and $W$ is an inner model of $V$ such that $\varphi\in W$. Is the statement ...
11
votes
1answer
627 views

Can one cover the plane with less than continuum of lines?

I will be working in ZFC, but I am not assuming the Continuum Hypothesis (or Martin's Axiom). I know that it is consistent with ZFC that one can cover the real line with less than continuum of meager ...
4
votes
1answer
205 views

Nondeterministic Turing machines and the recursion theorem

This is almost certainly a silly question, but: I am currently reading Moschovakis' article "Kleene's amazing second recursion theorem" (http://www.math.ucla.edu/~ynm/papers/1602-002-1.pdf) and there ...
4
votes
2answers
237 views

On wild behavior of $\omega_{1}$ in the absence of some essential axioms of $ZFC$

The regularity of $\omega_{1}$ is one of the most well known facts of set theory. But it seems that in order to prove this simple fact we need the "full power" of mathematics! For example by an ...
2
votes
1answer
185 views

Are measures of a measurable cardinal measurable? (Edited and Updated Version)

Update: Regarding to Prof. Hamkins's guidance I restricted the questions to the "normal" measures to avoid trivial answers. Definition: Let $\kappa$ be a measurable cardinal. Define: ...
18
votes
0answers
312 views

Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them. Define the set $\mathcal{E}$ of ...
-1
votes
1answer
170 views

A question about whether impredicative formulae always lead to (paradoxical) inconsistencies in formalized theories

Are there any examples of mathematical theories T1,T2 which satisfy the following conditions? T1 and T2 have the same "vocabulary" and are both formalized in the classical first order predicate ...
1
vote
1answer
170 views

Is elementary equivalence absolute?

Assume we have two objects $M_1$ and $M_2$ models of respective $L_{\omega_1,\omega}$-sentences $\Sigma_1$ and $\Sigma_2$. Assume $M_1$ and $M_2$ are elementarily equivalent in some model of set ...
7
votes
0answers
289 views

What is known of the reverse math of Riemann-Roch?

I hope this is not too trivial, but I think this may be well known to someone (not me).
23
votes
3answers
729 views

Does every set of reals contain a measure-zero set of the same cardinality? Does it contain a meager set of the same cardinality?

This question arises from an issue in my post on Ashutosh's excellent question on Restrictions of the null/meager ideal. Question 1. Does every set of reals contain a measure-zero subset of the same ...
10
votes
1answer
290 views

Is the inclusion version of Kunen inconsistency theorem true?

The relations $\in$ and $\subsetneq$ seem so similar in some sense. For example they are equal on ordinal numbers. So there is a natural question about their possible similar behaviors on the ...
3
votes
2answers
241 views

Is There An Algorithmic Complexity Of A Random Distribution

Has anyone studied an equivalent to algorithmic complexity for probability distributions? This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...
3
votes
2answers
403 views

Are descriptive and ontological notions of equality equal? [closed]

‎Let ‎$‎‎a$ ‎and ‎‎$‎‎b$ ‎are ‎two "‎objects". ‎What ‎is ‎the ‎meaning ‎of‎ ‎‎$a=b‎‎$‎? This is one of the deepest problems of philosophy and logic because one needs a complete information about ...
9
votes
1answer
296 views

Does existence of a proper class model imply the consistency?

The fundamental theorem of model theory says that: Theorem: A first order theory is consistent if and only if it has a model. In the above theorem we assume that the domain of any model is a ...
5
votes
2answers
254 views

Can we force with Fraisse filters to solve Vaught's conjecture?

Around the classic Fraisse amalgamation theorem in model theory we have the following notions: Definition (1): If $M$ be an $\mathcal{L}$-structure then define: $age(M):=\lbrace N~|~N~\text{is ...
2
votes
1answer
191 views

What is the order type of $L$ with Godel's well ordering?

In some sense $Ord$ is a "proper class" ordinal. Unfortunately the notion of a proper class ordinal is not a straight forward generalization of the notion of "set" ordinals because the proper classes ...
2
votes
0answers
146 views

Is there a non-trivial consistency preserving transformation?

In ‎set ‎theory ‎"equiconsistency" (and not "consistency") ‎of ‎the ‎theories ‎is the‎ ‎main ‎part ‎of ‎researches. ‎So ‎we ‎usually ‎try ‎to ‎construct a‎ ‎new model ‎using a‎ ‎given ‎one. ‎In ‎the ...
7
votes
1answer
114 views

Is there a notion of Skolemization for continuous logic?

Is there a notion of Skolemization for continuous logic (that of Ben Yaacov)? It seems to me that a Skolem function would be a minimizer, and minimizers are not continuous (from the parameters of the ...
6
votes
1answer
206 views

the choice of representing formulas and Gödel's second incompleteness theorem

In Rautenberg's book (A Concise Introduction to Mathematical Logic, Universitext, Springer 2006), Gödel's second incompleteness theorem is stated: Theorem 3.2 (Second incompleteness theorem). PA ...
15
votes
2answers
1k views

Hilbert's 10th problem and nilpotent groups

I am asking this question on behalf of a colleague of mine who does not have an MO account. Nevertheless I am also interested in the answer. The question concerns relationships between Hilbert's ...
1
vote
0answers
176 views

Are there two mutually incompatible consistent sentences in the language of PA, neither of which is true in the standard model? [closed]

Are there sentences $\phi$ and $\psi$ in the language of PA and models $\mathcal{M}_\phi$ and $\mathcal{M}_\psi$ of PA such that $\mathcal{M}_\phi\models\phi$ and $\mathcal{M}_\psi\models\psi$, but ...
1
vote
0answers
204 views

Logical and alphabetological variant?

The notion of alphabetical variant is well known, so that a formula $x=x$ is an alphabetical variant of $y=y$ if $x$ and $y$ are distinct variables. One may want to consider the set term $\{x:x \neq ...
1
vote
0answers
148 views

A question on definable categories

One way to define a category set-theoretically might be to give four $\in$-formulas (not sets!) $$\begin{array}{rl} \mathsf{O}(X)&\text{(“$X$ is an object”)}\\ \mathsf{M}(X,Y,z)&\text{(“$z$ ...
15
votes
0answers
368 views

Souslin trees on the first inaccessible cardinal

This may be well-known or simply deducible from the existing theorems, but I didn't find an answer in my set theory books: Is there a model of $ZFC$ in which there are no $\kappa$-Souslin trees where ...
13
votes
3answers
708 views

Where is the end of universe?

In some sense the empty set ($\emptyset$) and the global set of all sets ($G$) are the ends of the universe of mathematical objects. The world which $ZFC$ describes has an end from the bottom and is ...
3
votes
0answers
342 views

Is there a notion of “predicative given the real numbers”?

A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
10
votes
1answer
150 views

n odd: $\bf\Delta^1_n$ wadge degrees are $< \bf\delta^1_{n+1}$

My adviser is out of town and there is a comment in the Van Wesep paper "wadge degrees and descriptive set theory" that I can't figure out. Work in ZF+AD throughout. As stated in the title, the ...
2
votes
0answers
238 views

Sorting of countabe set [closed]

Let $X$ be a countable ordered set. My question is very simple - Can we sort $X$ in countable number of steps? When $X$ is finite, the answer is obviously yes. But what is the answer when $X$ is ...
5
votes
1answer
170 views

Can we always permute Cohen reals?

Consider the Cohen forcing, and suppose that $\dot x,\dot y$ are names for reals, which are not in the ground model (i.e. $1$ forces that neither is in the ground model). Can we always find an ...
5
votes
2answers
242 views

Does the Feferman-Schutte analysis give a precise characterization of Predicative Second-Order Arithmetic?

A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
2
votes
2answers
276 views

A couple of questions about Turing machines that are bounded in space but have an infinite amount of time in which to operate [closed]

My previous post about this topic (deleted question No. 142986) was quite long and somehow, most of it got erased. I will try to summarize it. I would like to consider a type of Turing machine which I ...
1
vote
0answers
136 views

Relativization of Formulas and Models [closed]

I want to show that the definition of satisfiability is consistent with the definition given by relativization, i.e. Let $L=\{\in\}$. Let $M$ be a definable set and let $E\subset{M\times{M}}$. Let ...