# Tagged Questions

**8**

votes

**3**answers

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

**3**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**3**answers

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

**3**answers

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

**0**answers

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

**1**answer

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

**4**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**3**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**3**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**0**answers

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 ...