# Questions tagged [lo.logic]

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, theories of truth, truth revision, consistency.

4,017 questions
Filter by
Sorted by
Tagged with
42 views

### Computable bound on the minimum number of negations to make a statement provable

Suppose we are working in an intuitionistic logic. A statement $T$ is called $k$-verifiable for an integer $k\geq 0$ if the $k$-fold negation of $T$ has a proof. A statement $T$ is verifiable if it is ...
91 views

### Is ZF + “all sets of reals have the Ramsey property” + “there is a set without the Baire property” consistent?

Are there models of set theory where all sets of reals have the Ramsey property but there is a set of reals without the Baire property? A set $A \subseteq [\omega]^\omega$ has the Ramsey property iff ...
79 views

364 views

### Is this compactness property for “satisfiability on $\mathbb{R}$” consistent?

This was originally part of this older question of mine, but in retrospect that question should have been broken into two parts - this is the still-unanswered part. Let $\Sigma$ be the language of ...
204 views

### Do escaping sets “uniformly” cover dominating sets under determinacy?

For $\mathbb{A},\mathbb{B}\subseteq\mathcal{P}(\omega^\omega)$, say $\mathbb{A}$ spreads onto $\mathbb{B}$ iff there is some $F:\omega^\omega\rightarrow\omega^\omega$ such that for all $X\in\mathbb{A}$...
198 views

### What is the smallest countable limit ordinal in which 'lost melodies' occur

The question is in the title. This question is in response to the following paragraph found at the end of Prof. Hamkins' answer to my MathOverflow question, Are ITTM's necessary to compute Turing's &...
305 views

### Is the supremum of L-definable cardinals silver-indiscernible

Let $\kappa$ be the supremum of ordinals first order definable in L without parameters. Assume $0^\sharp$ exists. Is $\kappa$ the least silver indiscernible ordinal?
154 views

### Can this weakish system of arithmetic express multiplication for second-sort numbers?

Consider a 2-sorted first-order logic with equality (for first-sort entities). The first sort consists of numbers, the second sort (which will be capitalized) of unary functions. There is one constant,...
374 views

### Practical Benefits of HTT/univalent foundations for assisted proofs

I'm trying to understand what the claimed practical benefits of HTT/univalent foundations are for doing computer assisted proofs and while I've seen a lot of claims of benefits they all seem to be ...
73 views

### Can superstability of a countable theory be characterized in terms of not 'weakly trace interpreting' a particular structure?

The concept that I want to think about in this question is very similar to trace definability, introduced here and also independently by Guingona, but is somewhat different from it. There's a very ...
154 views

642 views

### Is “There exists an unbounded non-measurable set but no bounded non-measurable set” consistent with $\mathsf{ZF}$?

This is a follow-up to this question. We say that a set $A \subseteq \mathbb{R}$ is bounded if there exists a finite interval $(a,b)$ such that $A \subseteq (a,b)$. Working in $\mathsf{ZFC}$, the ...
667 views

### What is the “Prikry–Silver collapse” when CH fails?

We all know and love Cohen reals, and we can (and often do) define the Cohen forcing as partial functions $p\colon\omega\to 2$ with finite domain. The Prikry–Silver forcing is defined as partial ...
293 views

### What are internal complete atomic boolean algebras, intuitively?

The category of complete atomic boolean algebras $\mathbf{CABA}$ is equivalent to $\mathbf{Set}^{\mathrm{op}}$ via $$\mathbf{Set}^{\mathrm{op}} \to \mathbf{CABA}, ~ X \mapsto (P(X),\bigcup,\bigcap).$$ ...
297 views

### What is meant by a computational interpretation of univalence?

In homotopy type theory the univalence axiom implies function extensionality. Suppose we have a recursive set we are not sure is empty (e.g. the set of even integers$\geq 4$ that are not a sum of two ...
210 views

207 views

### Definable constructions in o-minimal geometry

Recently I've been working with o-minimal expansions of $(\mathbb{R},\times,+)$, and I want to work "internally" to the language of o-minimal sets instead of working with "definable ...
106 views

### 2-REA PA degrees

Remember that an n-REA set is a set of the form $A_0 \oplus A_1 \oplus \cdots \oplus A_n$ with $A_n$ relatively r.e. in $A_m, m<n$ (so $A_0$ is r.e.) and that a degree is PA just if it computes a ...
Suppose $\Gamma\vdash A\vee \Delta$, where as usual $\Gamma$ and $\Delta$ are thought of as sets of propositions and the turnstyle is for logical consequence, or entailment. Given the assumption, may ...