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.

Filter by
Sorted by
Tagged with
-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$ ...
Jannik Pitt's user avatar
  • 1,179
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_κ(λ)$ ...
Dmytro Taranovsky's user avatar
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 ...
Noah Schweber's user avatar
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 ...
abo's user avatar
  • 1,906
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 ...
Mikhail Katz's user avatar
  • 15.4k
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 ...
Gro-Tsen's user avatar
  • 30.2k
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 ...
Garrett Figueroa's user avatar
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 ...
Ember Edison's user avatar
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 ...
Christopher King's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Miviska's user avatar
  • 53
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? ...
Zuhair Al-Johar's user avatar
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&...
Zuhair Al-Johar's user avatar
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 ...
Dominic van der Zypen's user avatar
-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 ...
Zuhair Al-Johar's user avatar
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 ...
Dmytro Taranovsky's user avatar
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....
Speltzu's user avatar
  • 213
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 ...
Mike Battaglia's user avatar
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 ...
Command Master's user avatar
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)?...
Peter Gerdes's user avatar
  • 2,633
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 ...
user506835's user avatar
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 "...
Noah Schweber's user avatar
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, ...
Zuhair Al-Johar's user avatar
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 ...
Ynir Paz's user avatar
  • 285
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 ...
Tim Campion's user avatar
  • 61.6k
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 ...
Ben Sprott's user avatar
  • 1,319
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, ...
Zuhair Al-Johar's user avatar
-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 ...
Zuhair Al-Johar's user avatar
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 ...
Ynir Paz's user avatar
  • 285
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 ...
Dmytro Taranovsky's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Holo's user avatar
  • 1,645
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 ...
user's user avatar
  • 29
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 ...
Navid's user avatar
  • 43
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 ...
Farran Khawaja's user avatar
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, ...
Lxm's user avatar
  • 323
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 \,...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Dmytro Taranovsky's user avatar
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 ...
Logan 's user avatar
  • 31
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 ...
sai's user avatar
  • 83
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 ...
Lxm's user avatar
  • 323
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 ...
Anonymous grad student's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Lukas Holter Melgaard's user avatar
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 ...
Alexey Slizkov's user avatar
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 ...
Mike Battaglia's user avatar
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}$...
Miha Habič's user avatar
  • 2,289
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}$ ...
Noah Schweber's user avatar
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 ...
user avatar

1
2 3 4 5
104