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
2answers
570 views

What does “simplification of proofs as evaluation of programs” mean?

I am currently going through Philip Walder's "Proposition as Types" and a passage of the introduction has struck me: for each way to simplify a proof there is a corresponding way to evaluate a ...
2
votes
0answers
200 views

Is there a $\Sigma^0_3$-complete ideal on $\omega$?

In Kechris's book "Classical Descriputive set theory" Chapter 23 (Exercise 23.4), it claim that there is a $\Sigma^0_\xi$-complete ideal on $\omega$ for each $\xi\geq 3$. There is a candidate ...
5
votes
1answer
301 views

Details for Woodin's forcing argument for a saturated ideal from the Levy collapse

Theorem 2.65 in Woodin's book shows that a saturated ideal on $\omega_1$ exists after Levy-collapsing a Woodin cardinal $\delta$ to $\omega_2$. I am confused about the part of the argument where he ...
9
votes
1answer
280 views

Can there be a tree of height $\omega_2$ having all levels countable, with no cofinal branch?

For many years I had the idea that if a well-founded tree is both very tall and very narrow, then it must have a cofinal branch. For example, it is a fun exercise to show that any $\omega_1$-tree ...
11
votes
0answers
298 views

On sentences true in all finite groups (revisited)

Let $w$ be a group word with variables $\bar x, \bar y$, where $\bar x=(x_1,\dots ,x_m)$ and $\bar y=(y_1,\dots ,y_n).$ I am interested in the following questions. (1) Is the sentence $(\forall\bar ...
7
votes
1answer
191 views

Introducing meets while preserving directed closure

A poset $\mathbb{P}$ is called well-met iff every pair of compatible conditions in $\mathbb{P}$ has a greatest lower bound. Question: Suppose $\mathbb{P}$ is a separative partial order which is ...
5
votes
0answers
94 views

O-Minimal sentences in $L_{\omega_1,\omega}$?

Is there any meaningful sense in which we can talk about o-minimal sentences of $L_{\omega_1,\omega}$? I can give a first attempt, easily; given a countable fragment $F$ and a sentence $\Phi$ in that ...
22
votes
1answer
897 views

How hard is it to destroy a diamond? (with a real)

If we start with $V\models\lozenge$, it is not hard to force the failure of diamond. You can blow up the continuum, or destroy all the Suslin trees. You can blow up the continuum of $\aleph_1$, and ...
7
votes
3answers
266 views

Do non-normal states exist in the Solovay model?

Let H be an infinite dimensional Hilbert space. Then there exist non-normal states on B(H) in ZFC (i.e. states that are not represented by a density operator). Is this also true in the Solovay model ...
1
vote
2answers
159 views

Are monoids with zero and partial homomorphisms related?

Context: Let $\Sigma=\{U,C,A,G\}$ and $L\subset\Sigma^*$, i.e. $L$ is a language over the alphabet $\Sigma$. Let $\Sigma'=\{0,1\}$ and define a homomorphism $f:\Sigma^*\to\Sigma'^*$ by extending $U ...
38
votes
4answers
1k views

On sentences true in all finite groups

Let $w$ be a group word with two variables $x$ and $y$. Is the sentence $(\forall x)(\exists y)w=1$ true in every group if it is true in every finite group? The same question about the sentence ...
4
votes
1answer
166 views

Induction and nonstandard halting times of standard machines

For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: ...
4
votes
2answers
130 views

${\frak b}$ and ${\frak d}$ defined with $\leq$ instead of $\leq^*$

Let $\omega^\omega$ denote the collection of all functions $f:\omega\to\omega$. For $f,g\in\omega$ we define $f\leq g$ if $f(n)\leq g(n)$ for all $n\in\omega$; $f\leq^* g$ if there is $N\in\omega$ ...
7
votes
0answers
336 views

Godel's second incompleteness theorem for non-r.e. theories

R. Jeroslow in this paper proves that a non-recursively enumerable theory whose set of theorems is $\Delta_2$-definable may prove consistency of itself but it can not prove 2-consistency of itself. ...
5
votes
1answer
331 views

Elementary equivalence of the direct product and direct sum of groups

It is well-known that the direct product of any family of abelian groups is an elementary extension of the direct sum of the family (see e.g. Lemma A.1.6 in the book `Model Theory' by W. Hodges, ...
5
votes
1answer
113 views

Minimal degrees of structures

For this question, a structure means a first-order structure in a computable language with domain $\omega$; a copy of a structure $\mathcal{A}$ is a structure $\mathcal{B}\cong\mathcal{A}$. Given a ...
6
votes
1answer
282 views

If two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?

Fix a first-order signature $\Sigma$. There is an equivalence relation $\sim$ on the class $\Sigma\mathrm{-Str}$ of all $\Sigma$-structures given by $M \sim N$ iff $M$ and $N$ are elementarily ...
2
votes
1answer
154 views

Explanation of the definition of Saturated Sets in Lambda Calculus

I have a question on the definition of Saturated Sets, as particular subset of the set of strongly normalizing terms in lambda calculus. Here is the definition: a set $S$ of strongly normalizing ...
29
votes
0answers
748 views

Bidi: A new cardinal characteristic of the continuum?

This question assumes familiarity with combinatorial cardinal characteristics of the continuum. Identify an infinite set $a\subseteq\mathbb{N}$ with its increasing enumeration. Thus, for each natural ...
1
vote
1answer
295 views

Is second-order ZFC categorical with regard to its proper class models

Second-order ZFC offers partial categoricity in the sense that, given any two models, one of them must be isomorphic to an initial segment of the other [1]. However, this leaves questions regarding ...
2
votes
1answer
185 views

Is there a 'largest' second-order categorical axiomatization of set theory, extended from ZFC2

While it's possible to obtain categorical second-order axiomatizations of set theory by extending ZFC2 with additional axioms (see [1]), these axioms tend to be somewhat arbitrary (e.g. adding an ...
1
vote
1answer
99 views

PA proves that functions are total

Is there a total recursive function $f:N \to N$ such that for no $\Sigma_1$ formula $\phi(x,y)$ which defines it (i.e., defines its graph), is it true that PA proves that "$\phi$ defines a total ...
4
votes
0answers
116 views

Is the lowenheim-skolem number of nth order logic larger than the corresponding number for 2nd order logic

According to this paper, by Vaananen, the $LS$ number for $2^{nd}$ order logic is given by "the supremum of $Π_{2}$-definable ordinals", where "The Lowenheim-Skolem number $LS(L)$ of $L$ is the ...
4
votes
1answer
221 views

What consistency results follow the assumption: $\forall\alpha(\aleph_{\alpha+1}\nleq2^{\aleph_\alpha})$?

In a recent question on Math.SE it was asked whether or not For every infinite cardinal $\mathfrak m$ there is no $\aleph$ number, $\kappa$, such that $\mathfrak m<\kappa<2^{\mathfrak m}$. By ...
17
votes
4answers
679 views

Is there a Leibnizian model with no definable elements, in a finite language?

A first-order structure $M$ is Leibnizian, if any two distinct elements $a,b\in M$ satisfy different $1$-types; that is, if there is some formula $\varphi$ such that $M\models\varphi(a)$ and ...
15
votes
1answer
440 views

Whatever happened to $L(j)$?

So this question probably shows my inner model theoretic ignorance, but: In "Two remarks on elementary embeddings of the universe" (http://projecteuclid.org/download/pdf_1/euclid.pjm/1102969567), ...
1
vote
0answers
124 views

What can be said about a Boolean-valued structure from what the Boolean-valued forcing extension thinks about it?

Suppose that $\phi$ is a formula in the language of set theory such that there are some $n_{1},...,n_{k}$ such that if $V\models\phi(x)$, then $x=(X,R_{1},...,R_{k})$ and ...
11
votes
0answers
340 views

Decidability of $x^3+y^3+z^3 = c$

I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that ...
6
votes
0answers
255 views

Reference for “if the set $A$ is Suslin, then every $\Sigma^1_1(A)$ set is Suslin”

Does anyone know of a reference for one or both of the following facts (in $\mathsf{ZF}$)? If the set of reals $A$ is Suslin, then every $\Sigma^1_1(A)$ set of reals is Suslin. If $T$ is a tree on ...
13
votes
2answers
897 views

When does Vopěnka's principle hold?

Vopěnka's principle (VP) is the statement that, given any proper class $\{\mathcal{A}_\eta: \eta\in ON\}$ of first-order structures in the same language, there are some $\alpha\not=\beta$ with ...
7
votes
1answer
364 views

Explicit counter example to Vopěnka's principle in the constructible universe?

Vopěnka's principle is a large cardinal axiom which has many equivalent formulations. One of them, which I find especially appealing, is the following: if the universe is satisfies Vopěnka's principle ...
5
votes
1answer
98 views

When is a formula preserved under taking factors in a reduced product or the stalk in a Boolean product?

I want to know if there is a nice characterization of when a formula is preserved under taking reduced factors. We say that a formula $\phi$ is closed under taking reduced factors if whenever $I$ is ...
0
votes
0answers
100 views

A question on complexity notation

I am considering writing ''$\Pi^{n}_{i_{0},...,i_{n-1}}$-comprehension'' as abbreviation for ''$\Pi^{0}_{i_{0}}$-comprehension plus ... plus $\Pi^{n-1}_{i_{n-1}}$-comprehension'' in the context of an ...
3
votes
1answer
152 views

Maximality statements that cannot be proved using $\mathsf{ZL}$ [closed]

What are examples for maximality statements that cannot be proved using Zorn's Lemma?
9
votes
1answer
100 views

Strongly minimal set with DMP

Recall that a strongly minimal theory $T$ has the Definable Multiplicity Property (DMP) if for all natural $k$, $m$ and $\varphi(\bar{x},\bar{b})$ of rank $k$, multiplicity $m$, there exists a formula ...
5
votes
0answers
181 views

Universal anti-Horn classes?

Is there published work about universal anti-Horn classes? Anti-Horn formulas are also sometimes known as dual Horn. See also related question Is there any research of universal algebras ...
1
vote
0answers
98 views

saturated model [closed]

Suppose you have a saturated model N of a complete theory T without finite models. How is it possibile to construct a proper saturated elementary substructure of N of the same cardinality of N ? I ...
6
votes
2answers
621 views

How do I apply the Boolean Prime Ideal Theorem?

I have become aware of an amazing phenomenon from a myriad of questions and answers here on MathOverflow: many of the results that I would typically prove using the Axiom of Choice can actually be ...
1
vote
0answers
177 views

Seeking reference to result in this talk by Voevodsky [duplicate]

In this presentation by Vladimir Voevodsky [1], he mentions a result that there is a formula over the natural numbers with a single free variable such that one can prove that there is no algorithmic ...
3
votes
0answers
98 views

Fixed Points of the Friedman Stanley Jump

Consider the situation of a pair $(X,E)$, where $X$ is a standard Borel space and $E$ is an invariant equivalence relation on $X$*. The Friedman-Stanley jump of this pair is an equivalence relation ...
6
votes
1answer
266 views

Logical strength of “choice functions exist for well-ordered families”?

A colleague of mine suggested the following weakening of the axiom of choice: If $\mathscr{F} := \{F_\alpha\}$ is a well-ordered family of non-empty sets (i.e., there is a bijection between ...
6
votes
1answer
176 views

Degree of unsolvability of finding a open approximation to a Borel set, given its Borel code

It is well known that every Borel set has the property of Baire. That is, for every Borel set $B$, there is an open set $U$ and a sequence of dense open sets $D_n$ such that for every $x\in \cap_n ...
1
vote
0answers
182 views

Existence of $\lambda$-transitive linear orders for $\lambda \geq \aleph_0$

A linear order $(L, <)$ is $\lambda$-transitive iff any order-preserving bijection between sets of size $\lambda$ can be extended to an order automorphism of $L$. For $\lambda < \aleph_0$, ...
4
votes
1answer
161 views

Embedding of classical into intuitionistic linear logic

Following on from this recent question, there is another construction that is well-known, but I don’t know a good primary source for: the Kolmogorov-style double-negation embedding of classical into ...
9
votes
0answers
162 views

Consistency strength of $\aleph_2$-Souslin hypothesis

Question 1. What is known about the consistency strength of $\aleph_2$-Souslin hypothesis? Question 2. What is known about the consistency strength of having both $\aleph_2$-Souslin hypotheis and ...
5
votes
1answer
204 views

Conservativity of multiplicative linear logic over intuitionistic multiplicative linear logic

It is well known that multiplicative linear logic (MLL) is conservative over intuitionistic multiplicative linear logic (IMLL). In other words, if an IMLL formula is provable in MLL then it is already ...
7
votes
0answers
222 views

What is the Turing degree of $\mathbb{C}_{exp}$?

Let $\mathbb{C}_{exp}$ be the theory of the complex numbers in the language of exponential rings. I am interested in the Turing degree of $\mathbb{C}_{exp}$. As the natural numbers are definable in ...
5
votes
0answers
178 views

Can the first ordinal in which $V\neq HOD$ be $\aleph_\omega$?

Assume that $V\neq HOD$ and let $\kappa = \min \{\alpha\in On \mid \mathcal{P}(\alpha) \not\subseteq HOD\}$. Clearly, $\kappa$ is a cardinal. Question: Is it consistent that $\kappa = ...
38
votes
1answer
3k views

Mathematicians wearing hats on arbitrary total orders

I've been pondering the following generalisation of a famous problem (the special case where $T = \mathbb{N})$: Question: We have some totally-ordered set $T$ of mathematicians, each wearing a hat ...
8
votes
1answer
247 views

Notions of infinity in $\mathsf{ZF}$ without choice

Consider the following statements about a given set $X$ in in $\mathsf{ZF}$: (1) There is $x_0\in X$ such that there is a surjective map $\varphi: X\setminus\{x_0\}\to X$. (2) There is an injective ...