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

5,157
questions

-1
votes

0
answers

22
views

### "Weak" partial order where only some elements are reflexive

Are there interesting examples of "almost" partial orders $\preccurlyeq$, where only some elements $x$ satisfy the reflexivity axiom $x \preccurlyeq x$, but every $x$ has at least some $y$ ...

1
vote

0
answers

44
views

### Weak extender models for supercompactness without choice

Assume ZFC and a supercompact cardinal $κ$. Is it consistent that there is a weak extender model $N⊨\text{ZF}$ for supercompactness of $κ$ such that the axiom of choice (and well-ordering of $P_κ(λ)$ ...

2
votes

0
answers

33
views

### $\Pi^0_1$ sentences modulo "schematic entailment"

Let $\mathfrak{P}$ be the preorder of $\Delta^0_0$ (= only bounded quantifiers) formulas with one free variable in the language of arithmetic with a symbol for each primitive recursive function, under ...

6
votes

2
answers

548
views

### Does PA prove (Artemov-style) the consistency of a stronger system?

There was a recent question on Artemov's paper here on MO Situation with Artemov's paper?
In one of the answers there it was asserted (apparently incorrectly - see Noah Schweber's comments and ...

25
votes

5
answers

4k
views

### Situation with Artemov's paper?

Artemov's paper on Goedel's theorem has been on the arxiv since 2019. There was a (less than fully friendly) discussion of this on FoM. At stackexchange, I found only a brief mention at this MSE ...

12
votes

3
answers

1k
views

### Examples of concrete games to apply Borel determinacy to

I'm teaching a course on various mathematical aspects of games, and I'd like to find some examples to illustrate Borel determinacy. Open or closed determinacy is easy to motivate because it proves ...

8
votes

1
answer

186
views

### Does there exist a geometric morphism between the effective and topological topoi? Does one arise from synthetic topology?

I'm presenting in final projects for my computability and computational topology courses on the connections between computability, continuity, and logic. As a mathematician/unmentored baby logician ...

5
votes

0
answers

228
views

### The constructive Eudoxus reals

Recently arxiv submitted a new paper (Andrej Bauer, James E. Hanson, The Countable Reals) claiming an incredible theorem that Dedekind reals are not sequence-avoiding, and furthermore obtaining a ...

5
votes

0
answers

197
views

### Is it decidable whether a statement about reals (in the language of ordered rings) is constructively provable?

The language of ordered rings is a first-order language with operators for $+$, $-$, and $\cdot$, constants for $0$ and $1$, and relations for $<$, $=$ and $>$.
To decide whether such a ...

2
votes

1
answer

177
views

### Can there be a minimal remote cardinal?

Working in $\sf Z- Reg.$ we can have sets bigger than every well-founded set, let's label such sets as "remote". Now, suppose we'll add the axiom of existence of transitive closures, and the ...

5
votes

1
answer

275
views

### Why is it not possible to define the necessity operator internally $\Box: \Omega \to \Omega$ in a topos?

I am looking for ways to internalize the modal operator of necessity $\Box$, ending up with a morphism $\Box: \Omega \to \Omega$ satisfying the necessitation rule (if $\phi$, then $\Box \phi$) and the ...

4
votes

1
answer

396
views

### Can we have an axiom that refers to itself and the prior axioms of the theory it is an axiom of?

I know that this question is little bit imprecise, I'll try to present it in the best I can.
Can one have an axiom which is self referential with respect to itself and the theory in which it belongs?
...

1
vote

0
answers

46
views

### Is stratified Z - Infinity + there is a set as big as its powerset, consistent if NF is consistent?

The question of consistency of $\sf NF$ can be seen to be equivalent to the question of whether the theory "Stratified $\sf Z$ - Regularity - Infinity + There exists a set as big as its powerset&...

2
votes

1
answer

156
views

### Cardinality of maximal diverse families

Let $\kappa\geq \aleph_0$ be a cardinal. We say a collection ${\cal E} \subseteq {\cal P}(\kappa)$ is diverse if $|(A \setminus B) \cup (B \setminus A)| = \kappa$ whenever $A\neq B\in {\cal E}$. A ...

-1
votes

0
answers

87
views

### Can existence of uncountable sets be proved in a ZFC variant with mild definability restriction?

Starting with ZF[C], if we restrict Separation and Replacement to parameter free versions from Parameter free definable sets, re-write Infinity asserting existence of $\omega$. Add to it axioms of ...

4
votes

0
answers

121
views

### Consistency of definability beyond P(Ord) in ZF

Is it consistent with ZF that the satisfaction relation of $L(P(Ord))$ is $Δ^V_2$ definable? More generally, is it consistent with ZF that there is a $Δ^V_2$ formula (taking $α$ as a parameter) that ...

4
votes

1
answer

301
views

### Expressiveness in arithmetic

Let $\mathcal{S}$ be a formal system for arithmetic (e.g. $P$ or $PA$), $f:N^q\rightarrow N^p$ a function of $N^q$ on $N^ p$ and $\alpha(\mathbf{x})$ a formula of $\mathcal{S}$ with $p$ free variables....

5
votes

1
answer

466
views

### Hilbert's and Gödel's expanded definition of "Recursive Function"

There is a very interesting comment in this post:
I must also make one terminological caveat: Hilbert, and later Godel, used the phrase "recursive function" in a way very different from the ...

4
votes

0
answers

130
views

### Is there a statement in Presburger arithmetic about primes this simple heuristic fails for?

I came up with the following conjecture while thinking about ways to formulate some heuristics about primes:
Conjecture: Given a statement $s$ in Presburger arithmetic, using an additional unary ...

7
votes

2
answers

177
views

### Why does Weihrauch reducibility make use of multi-functions?

This is probably a kinda dumb question, but why is Weihrauch reducibility defined in terms of multi-functions (i.e. why isn't it just the degree structure of regular functions under that reducibility)?...

10
votes

1
answer

183
views

### Is $(\mathbb R_{\mathrm{an}}, (x\mapsto x^r)_{r\in\mathbb R})$ still the largest known polynomially bounded o-minimal structure so far?

From Chris Miller's paper in 1995, the structure $(\mathbb R_{\mathrm{an}}, (x\mapsto x^r)_{r\in\mathbb R})$,is the largest known polynomially bounded o-minimal structure as of that time. I wonder if ...

6
votes

0
answers

118
views

### What is this quotient of the free product?

Previously asked at MSE. The construction here can generalize to arbitrary algebras (in the sense of universal algebra) in the same signature with the only needed tweak being the replacement of "...

5
votes

1
answer

263
views

### Would strengthening Foundation and Choice in NBG, make it equi-consistent with MK?

This is a follow up to an earlier question about strengthening of foundation in relation to proving the consistency of ZFC. It was shown that it would achieve that, but it may fail short of MK. Here, ...

5
votes

1
answer

200
views

### Long chains of Dedekind finite sets

This is a variation on this question with amorphous cardinals replaced with dedekind finite sets.
Dedekind finite sets are sets that have no countable subset, and it is well known that this is a ...

21
votes

1
answer

1k
views

### Are the real numbers isomorphic to a nontrivial ultraproduct of fields?

Let $K_1, K_2, \dots$ be a countable sequence of fields, and let $\prod_{\mathcal F} K_i$ be the ultraproduct with respect to some nonprincipal ultrafilter $\mathcal F$.
Question: Can there be a field ...

1
vote

0
answers

105
views

### Monads for proof relevance in type theory

I am just getting started with homotopy type theory. After watching an introductory lecture, I was attracted to the concept of proof relevance. In my understanding, the core idea here is to elevate ...

6
votes

2
answers

469
views

### Is strengthening Foundation in NBG sufficient to make it prove Con(ZFC)?

Can $\sf NBG$ class theory prove the foundation scheme:
Foundation schema: if $\Phi(X)$ is a formula in which "$X$" occurs free and only free, and in which "$Y$" doesn't occur, ...

-2
votes

0
answers

114
views

### What happens if we restrict inputs in Separation and Replacement axioms to definable sets?

If we replace the axiom of Foundation by
Foundation schema: if $\varphi(x)$ is a formula in which "$x$" occurs free and only free, and in which "$y$" doesn't occur, whose free ...

13
votes

1
answer

532
views

### Long chains of amorphous cardinalities

An amorphous set is an infinite set that cannot be partitioned into 2 infinite subsets. An amorphous cardinality is the cardinality of an amorphous set. Working in $\sf ZF$, it is consistent that ...

2
votes

0
answers

87
views

### Uniformization and functions on Turing degrees

Assuming Martin's Conjecture on functions between Turing degrees, is AD + DC consistent with existence of an $f:\mathcal{D}_t → \mathcal{D}_t$ of rank $Θ$ ?
$\mathcal{D}_t$ is the set of Turing ...

3
votes

2
answers

600
views

### Can uncountable sets be proved to exist in this variant of ZFC with definability restrictions?

If we restrict all parameters in the set building axioms of $\sf ZFC$ to definable sets, would the celebrated Cantor's theorem still apply? Can existence of uncountable sets be proven at all?
The set ...

11
votes

1
answer

392
views

### Building the real from Dedekind finite sets

It is well known that the real numbers can be countable union of countable sets by starting with GCH and taking a finite support permutations while collapsing all of $\aleph_n$ for natural $n$.
The ...

1
vote

0
answers

81
views

### Quasi polynomial algorithm for NP complete problem [closed]

I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...

4
votes

1
answer

228
views

### Are there atoms in the lattice of intermediate logics?

A few days ago I stumbled upon this question on MS. The question is: Does the lattice of intermediate logics have an atom, i.e. an element that is strictly stronger than IPC but not strictly stronger ...

0
votes

0
answers

76
views

### Are gaps and loopy games interchangeable in the Surreal Numbers?

The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...

9
votes

1
answer

335
views

### Consistency strength of strongly compact cardinal

Where can I find a proof that strongly compact cardinal has higher consistency strength than Woodin cardinal, or even just strong? Recall that a strongly compact cardinal itself may not be strong, ...

1
vote

0
answers

147
views

### What is the strength of adding this de-schematizing inference rule to Ackermann's set theory?

Language: first order logic with equality, membership, and a constant symbol $W$.
Axioms:
Extensionality: $\forall z \, (z \in x \leftrightarrow z \in y) \to x=y$
Comprehension: $\exists x \forall y \,...

1
vote

0
answers

109
views

### Is this modified H. Friedman theory bi-interpretable with ZFC + ORD is Mahlo?

The following theory is a modification of Harvey Friedman $\sf K(W)$ theory.
Language: first order logic with equality, membership, and a constant symbol $W$.
Axioms:
Extensionality: $\forall z \, (z ...

6
votes

0
answers

113
views

### From HODs to corresponding models of AD

If $M$ is HOD of a model $N$ of $\text{AD}^+ + V=L(P(ℝ))$, what kind of forcing construction in $M$ gives back such an $N$?
HODs for $\text{AD}^+ + V=L(P(ℝ))$ are conjectured (and under anti-large ...

3
votes

0
answers

239
views

### Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?

If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not.
But ...

8
votes

2
answers

497
views

### Whether the pure implicational fragment of intuitionistic propositional logic is a finitely-many valued logic

Gödel (1932) showed that intuitionistic propositional logic (more precisely, any fragment with implication and disjunction) is not a finitely many-valued logic. What about the pure implicational ...

5
votes

0
answers

190
views

### Friedman's proof of covering lemma for $L$

There is a two-page proof of the covering lemma for $L$ using $\Sigma_n$ substructures (Theorem 3.10) in Sy Friedman's Fine Structure and Class Forcing, compared to the proof that spans about twenty ...

12
votes

1
answer

704
views

### Can proper classes have different sizes?

I'm presently working in a non-ZF set theory, where there are proper classes. (Think MK or VNBG.) And I'm interested in how to think about the possibility (or impossibility) of proper classes with ...

1
vote

0
answers

163
views

### How does the cardinality of a set and its powerset compare in the hereditarily rank-concordant constructible world?

Working in the constructible universe "$L$", if we define two kinds of ranks for any constructible set $x$, one being the ordinal index of the first $L_\alpha$ where $x$ appears as a subset ...

4
votes

1
answer

109
views

### Does this hierarchy of fragments of $I \Sigma_1$ collapse?

Does anyone know whether the following hierarchy of fragments of
$\mathrm{I} \Sigma_1$ (or rather
$\mathrm{I} \Pi_1$) collapses or not?
Let $\Sigma^b_n$ denote formulas in the language of arithmetic ...

5
votes

0
answers

155
views

### Higher-order equivalence of ordinals

I wonder which ordinals are second-order equivalent, and similarly for other logical equivalences. Let the signature be fixed and include only <. For concreteness, let us first ask for the first ...

4
votes

1
answer

197
views

### Simplified method of building an Aronszajn tree

There is a very interesting method to build an Aronszajn tree in Judith Roitman's "Introduction to Modern Set Theory", on pages 100-102. In short, we build a tree $T$ in which the nodes are ...

8
votes

1
answer

187
views

### A reference for forcing projections

The idea of a projection $\pi\colon\mathbb{Q}\to\mathbb{P}$ of forcing notions is something like a combinatorial stand-in for the fact that forcing with $\mathbb{Q}$ produces a generic for $\mathbb{P}$...

6
votes

0
answers

219
views

### Do maximal compact logics exist?

By "logic" I mean regular logic in the sense of abstract model theory (see e.g. the last section of Ebbinghaus/Flum/Thomas' book). My question is simple:
Is there a logic $\mathcal{L}$ ...

7
votes

1
answer

318
views

### Literature about formalization of "natural reasoning" in mathematical logic

In "Logic of sheaves of structures", X. Caicedo justifies the logic he introduces stating (more or less) that assertions about a point should really be understood as assertions about a ...