# 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,000 questions
Filter by
Sorted by
Tagged with
114 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 ...
152 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).$$ ...
232 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 ...
149 views

174 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 ...
93 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 ...
126 views

### A question on entailments in sequents

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

111 views

### Empty preimage under homomorphism of finitely presented groups with decidable word problems

Let $f:G\to H$ be a homomorphism of finitely presented groups with decidable word problems. Assume you are given explicit finite presentations for both $G$ and $H$ and you are given the words to which ...
411 views

### Is the diagonal of finitely presented groups computable?

Let $f:G\to H$ be a surjective homomorphism of finitely presented groups. If the kernel of $f$ is finitely generated then is $G\times_H G$ is a finitely presented group? Can one compute an explicit ...
805 views

### Element being trivial in a finitely presented group independent of ZFC

Is there an explicit finitely presented group $G$ and an element $g\in G$ such that the statement "$g$ is equal to the identity" is independent of ZFC?
130 views

### Empty preimage under homomorphism of finitely presented groups independent of ZFC

Is there a homomorphism of finitely presented groups $f:G\to H$ and an element $h\in H$ such that the statement "$f^{-1}(h)$ is empty" is independent of ZFC?
34 views

### Can all unions of sets above some level be constructible before the sets in some relative constructible universe?

Can we have some relative constructible universe $L(A) \ (or \ L[A])$ such that for some infinite ordinal $\gamma \leq |A|$ we have: for every subset $u$ of $A$, if $u$ is the union of a set $\sf U$ ...
62 views

### Empty preimage under homomorphism of finitely presented groups with decidable word problems

Let $G, H$ be finitely presented groups with decidable word problems. Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?...
269 views

### Do saturated models require choice?

Let $T$ be a first-order theory, and suppose we want to build a saturated model $\mathbb U$ of $T$. That is, we want a model $\mathbb U$ of cardinality bigger than $|T|$, saturated in its own ...
61 views

### How similar can a model of $I\Delta_0$ be to the intersection of all of its definable cuts?

Let $M$ be a model of $I\Delta_0$. Recall that a definable cut is a definable (possibly with parameters) subset $I$ of $M$ that is non-empty, downwards closed, and closed under successor. If we ...
251 views

### Can we choose a sequence of Hilbert spaces?

Let $n$ be a fixed natural number. Let $H$ be a complex Hilbert space and $H_1,\dotsc,H_n$ be closed subspaces of $H$. Set $H_0\mathrel{:=}H_1\cap H_2\cap\dotsb\cap H_n$ and let $P_i$ be the ...