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
0 votes
0 answers
3 views

How hard must "no high-degree irreducibles" proofs be?

Let $\mathsf{RCF}$ be the usual theory of real closed fields and for $n>2$ let $\theta_n$ be the sentence "No degree-$n$ polynomial is irreducible." Since $\mathsf{RCF}$ is complete, for ...
user avatar
1 vote
0 answers
29 views

Consistency strength of Muller's modification of Ackermann set theory

In his 2001 paper Sets, Classes and Categories, F. A. Muller lays out a modification of Ackermann class theory that he claims is not conservative over Ackermann's original theory in the sense that it ...
user avatar
  • 6,221
2 votes
0 answers
33 views

Preservation of projective stationarity

A set $S \subseteq [\kappa]^\omega$ is called projective stationary if for every stationary $A \subseteq \omega_1$, and every algebra $F : \kappa^{<\omega}\to\kappa$, there is $z\in S$ such that $z$...
user avatar
  • 16.3k
2 votes
0 answers
28 views

Persistent finite axiomatizability, relational edition

Say that a finitely axiomatizable first-order theory $T$ (in a finite language $\Sigma$) is persistently finitely axiomatizable iff the set $T_{\mathsf{w/o=}}$ of equality-free $T$-theorems is ...
user avatar
1 vote
0 answers
83 views

How much downward density can we get without injury?

$\newcommand{\ran}{\operatorname{ran}}$This question is basically a riff on the first section of Maass' paper Recursively enumerable generic sets, with some rephrasing for readability. All results ...
user avatar
0 votes
0 answers
83 views

What is the set of axioms for this theory extracted from what is provable in the minimal model of ZFC?

This post is a follow up of this one posted to MathStackExchange. Working in $\sf ZFC + \exists M \, (M \overset{trs} \models ZFC)$, lets define a theory $T_0$ as: $$(\varphi \ \epsilon \ T_0) \iff \...
user avatar
-1 votes
0 answers
154 views

What are the hidden assumptions behind Harvey Friedman's claim, CSR?

I'm doing some archeology and trying to understand a claim. As summed up by David Roberts, on the FOM list in 2011: Let the statement "every infinite sequence of rationals in [0,1] has an ...
user avatar
  • 375
3 votes
1 answer
176 views

Free algebras from model theory perspective

Let $\mathbb{V}$ be a non-trivial variety of algebras, and let $F_S\in\mathbb{V}$ be a free algebra on a set $S$. I want to know what is known about the model theory of $F_S$; I know these objects are ...
user avatar
1 vote
0 answers
167 views

Set theory for category theory

Let $SC$ (sets and classes) denote the modification of Ackermann set theory laid out in F. A. Muller's Sets, Classes and Categories (denoted there by ARC -- a brief summary of the theory is given ...
user avatar
  • 6,221
1 vote
0 answers
67 views

How restrained are we in terms of metatheories when working with higher order logics with full semantics?

When working in the realm of first order logic one can use very basic mathematical backgrounds(in reverse mathematical sense) to prove interesting things about more "structures". In what ...
user avatar
  • 197
0 votes
1 answer
94 views

At which large cardinal, the theory of the minimal transitive model of ZFC starts proving its absence?

Let's take the minimal transitive model of $\sf ZFC$ which, I came to know, is some minimal $L_\kappa$ for a countable $\kappa$, that models $\sf ZFC$, and since its minimal so no subset of it can be ...
user avatar
0 votes
0 answers
59 views

What's the consistency strength of this kind of cardinal?

My friend introduced the following notion: Let $\xi > 0$, $\eta$ be ordinals, $n$ be a natural number and $\mathcal{A}, X$ be classes. A cardinal $\kappa$ is called $\mathcal{A}\textrm{-}\eta\...
user avatar
  • 290
4 votes
1 answer
274 views

Stone-Čech compactification

Is every hyperstonean space a Stone-Čech compactification of a discrete space? Is there a closed subset of Stone-Čech boundary that is extremally disconnected?
user avatar
  • 51
0 votes
0 answers
52 views

Proof of the Local Deduction Theorem, for one of many logics

I'm looking for a proof of the Local Deduction Theorem for any one of many logics. That is, a proof of the statement: $\Sigma \cup \{\phi\} \models \psi$ iff for some positive $n,$ $\Sigma \models \...
user avatar
  • 181
0 votes
1 answer
48 views

An exercise in fuzzy logics built from a t-norm

Consider the following t-norm: $$ a * b = \begin{cases} 2ab, &\quad\text{if }a, b\le1/2\\ \min\{a, b\} &\quad\text{otherwise} \end{cases} $$ We build from it the $\...
user avatar
  • 181
-3 votes
0 answers
90 views

Can restrictions on semantics of a theory that disrupts model isomorphism be accepted as semantics of pure mathematical theories?

This question might look to be philosophical, but actually what I'm posing here is the mathematical stance from it and not the philosophical aspect. I'll write some philosophical background just to ...
user avatar
5 votes
1 answer
125 views

$\Pi^0_2$ singleton of minimal arithmetic degree?

Is it known if there is a $\Pi^0_2$ singleton of minimal arithmetic degree? To elaborate a bit, this is asking whether there is a non-arithmetic set $X$ such that for any $Y$ arithmetic in $X$ either ...
user avatar
  • 1,515
2 votes
1 answer
197 views

Construction of models for true but unprovable formulas

Gödel's Completeness Theorem shows that first-order logic is (semantically) complete, namely, provability and validity coincide. Gödel's Incompleteness Theorem shows that there are theories where ...
user avatar
7 votes
2 answers
1k views

Does permission always work?

Suppose $g$ is a total computable injective function and $f$ is a total computable function satisfying $$g(x)<f(x)$$ for all sufficiently large $x$. Then we have $ran(f)\le_Tran(g)$; basically, ...
user avatar
5 votes
0 answers
117 views

On the correspondence between proof nets and sequents

1. Context While trying to answer my question on the existence of a (useful) graphical calculus for star-autonomous categories, I came across the paper Natural deduction and coherence for weakly ...
user avatar
  • 213
5 votes
1 answer
166 views

Reinhardt's ultimate classes

In the preface to Sets and Classes by Muller, several research programs are outlined that were in development concurrently with publication (or finished slightly beforehand) that he would have liked ...
user avatar
  • 6,221
-5 votes
1 answer
192 views

Are equinumerous size preserving models of a theory isomorphic?

If by a size preserving model we mean any bijection between any two elements of it is an element of it. Then: is it a thoerem of $\sf ZFC$ that for any theory $T$ any two equinumerous size preserving ...
user avatar
6 votes
1 answer
130 views

How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?

Recall that given a finite language $\mathcal{L}$, we say that an $\mathcal{L}$-structure is computably saturated (or recursively saturated) if for any computable set $\Sigma(\bar{x},y)$ of $\mathcal{...
user avatar
  • 6,344
6 votes
0 answers
112 views

Number of tautologies of a given size?

Fix some complete set of $L$ logical connectives such as $\{ \wedge, \neg \}, \{\Rightarrow, \neg \}, \{\ \vee, \wedge, \neg \}, \{ \uparrow\}, \{\wedge, \vee, \neg, \Rightarrow \}$ - I'll assume all ...
user avatar
  • 383
2 votes
1 answer
128 views

Can ZFC sets be interpreted as single rooted trees with accessible degree and countable height?

Let $T$ be a single directed tree, by parameters $(\kappa, \lambda, \zeta)$ of $T$ we mean: the number of root nodes in $T$, the strict upper bound on the number of children nodes per a node in $T$, ...
user avatar
14 votes
1 answer
340 views

Can $\kappa^\lambda$ be large if $2^\lambda$ is small and $\lambda<\mathrm{cof}(\kappa)$?

We work in ZFC throughout. The following question was posed to me by a friend: Can there exist cardinals $\kappa,\lambda$ such that $\lambda<\mathrm{cof}(\kappa)$ and $2^\lambda<\kappa<\...
user avatar
  • 23.3k
3 votes
0 answers
47 views

Explicit tautologies requiring lots/few uses of modus ponens in minimal proofs

I am interested in minimal length proofs of tautologies in propositional logic. For concreteness, let's fix a particular Frege system $F$ (i.e., sound and complete set of axioms and deduction rules ...
user avatar
  • 383
5 votes
1 answer
181 views

A question about the axiom of dependent choice

Let $\mathrm{NBG}^-$ be $\mathrm{NBG}$ minus the Axiom of Choice for Classes (including sets)). Further let $\mathrm{DC}$ be the Axiom of Dependent Choice for sets and $\mathrm{DC}^\omega$ be Bernays ...
user avatar
0 votes
0 answers
136 views

Thinning chains of elementary extensions

I'm bumping this question, since I'm still curious regarding the answer but this question seems to have gone unnoticed. This is a follow-up to this question, regarding a stronger variant of ...
user avatar
  • 290
0 votes
1 answer
100 views

How do chains of elementary extensions compare to shrewdness?

I thought of the following large cardinal axiom, extending the notion of $\theta$-upliftingness: Let $\eta$ be be an ordinal, and $X$ be a class of ordinals. $\kappa$ is called $\eta$-iteratively ...
user avatar
  • 290
3 votes
2 answers
254 views

Tarski's original proof of quantifier elimination in algebraically closed fields

I am currently helping teach a course about foundations of mathematics, which has thus far focused mostly on propositional and first-order logic. As part of the course, the students are each required ...
user avatar
2 votes
1 answer
116 views

What's the consistency status/strength of this limitation principle?

$\DeclareMathOperator\iCard{iCard}$In a prior posting If we limit matters what ZFC can prove, would that be consistent? to MO, I tried to capture the informal principle of whatever ZFC proves, it is, ...
user avatar
4 votes
0 answers
62 views

$\omega$ incompleteness of $\lambda$ calculus

In Plotkin's 'The $\lambda$-Calculus is $\omega$-Incomplete' (The Journal of Symbolic Logic Vol. 39, No. 2 (Jun., 1974), pp. 313-317), an example is given of two (untyped) $\lambda$-terms $M$ and $N$ ...
user avatar
2 votes
0 answers
150 views

What is the consistency strength of the following pattern of failure of the continuum hypothesis?

What is the least theory in which the following sentence is proved? $ \exists M: M\text { is CTM(ZFC+ GCH)} \land \forall \kappa \in Card^M (\kappa > 1 \implies \\\exists N: N \text { is CTM(ZFC) }...
user avatar
6 votes
1 answer
179 views

Linear logic and linearly distributive categories

I asked this question ten days ago on MathStackexchange (see here). Despite having placed a bounty on the question, I have not received any answers or comments until now. Following Nick Champion's ...
user avatar
  • 213
5 votes
2 answers
232 views

Properties of Jech's hierarchy of stationary sets (Exercise 8.13, 8.14 of Jech)

I must first preface that while this is indeed a question on an exercise, I believe this is advanced enough for MathOverflow. Let $\kappa$ be a regular uncountable cardinal. Recall that the notion of ...
user avatar
-1 votes
0 answers
79 views

Is the following relation between size-unreachability and fulfilling continuum hypothesis correct?

If we define $\operatorname {size-unreachable}$ set as a set of all subsets of it of strictly smaller cardinality than it. Formally, we define: $$ \operatorname {size-unreachable}(X) \iff X=\{Y \...
user avatar
-2 votes
1 answer
145 views

Which extension of ZFC proves that ZFC can only prove CH satisfied by the first two sets?

Which extension of $\sf ZFC$ prove that $$ {\sf ZFC} \not \vdash \exists x \, ( \operatorname {CH}(x) \land x \neq \emptyset \land x \neq 1)$$ Where $\operatorname {CH}(x) \iff \neg \exists \kappa \, (...
user avatar
1 vote
1 answer
332 views

The LNC as a mathematical theorem

One of the most intriguing things I've read about over the last few years is Diaconescu's theorem, which says that, in some forms of constructivist/intuitionistic set theory, even if the law of the ...
user avatar
-2 votes
1 answer
323 views

Has there been any mathematical study of causality?

Causality seems to play an important role in physics. There also seems to be a close parallel between "$P$ causes $Q$" and "if $P$ then $Q$." Mathematical logic studies logical ...
user avatar
-2 votes
1 answer
146 views

If we limit matters what ZFC can prove, would that be consistent?

I was thinking about a principle that occurred to me regarding provability in ZFC and truth. The principle outrageously states that: whatever ZFC shows, it is! In other words whatever ZFC can prove ...
user avatar
3 votes
1 answer
90 views

Equivalences of $\mathcal{F}$-Mahloness

Taken from Math Stack Exchange. Let $\mathcal{F}$ be a set of $\mathcal{L}_\in$-formulae, $\kappa$ be a cardinal and $A \subset \textrm{Ord}$. Then, $\kappa$ is called $\mathcal{F}$-Mahlo if $A \cap \...
user avatar
  • 290
1 vote
0 answers
89 views

Are those two theories equivalent?

Lets denote any set that is "the set of all strictly smaller subsets of it" as size- unreachable. Formally: $$\operatorname {size-unreachable}(X) \iff \\\forall Y (Y \in X \iff Y \subset X \...
user avatar
0 votes
0 answers
94 views

Is definable bounded separation equivalent to bounded separation?

If we have all axioms of Mac Lane set theory except Separation and add to them the schema of definable bounded separation, then would the resulting theory be equivalent to Mac Lane set theory? ...
user avatar
8 votes
2 answers
386 views

Comprehension axiom who helps in the opposite direction

Usually, having more comprehension axiom means the more you can prove. We wonder if the converse can be the case. Is there a natural problem $\mathsf{P}$ so that $\mathsf{P}+\neg(\Gamma-\mathsf{...
user avatar
  • 909
13 votes
1 answer
417 views

Ultracategories with one object

Historically, the theory of ultracategories was invented by Makkai to prove a strong conceptual completeness theorem for first-order logic, roughly: if $T$ and $S$ are two first-order theories such ...
user avatar
4 votes
1 answer
178 views

$\mathtt{PSP}$ implies the consistency of inaccessible cardinals

I'm looking for the proof that $\mathtt{PSP}$, the statement that every uncountable subset of the the Baire space $\mathbb{N}^\mathbb{N}$ contains an homeomorphic copy of the Cantor space $2^\mathbb{N}...
user avatar
  • 753
2 votes
0 answers
150 views

Generalized models of set theory

The forcing method can be viewed as building a Boolean-valued model of set theory. Some generalizations include Heyting algebra/sheaf/lattice-valued model. However, it seems these generalizations are ...
user avatar
  • 227
6 votes
1 answer
186 views

Decidability of completeness in propositional logic

Propositional logic can be presented as in Mendelson’s book, with the sole inference rule of modus ponens, and with the following three axioms: $$B \Rightarrow (C \Rightarrow B)$$ $$(B \Rightarrow (C \...
user avatar
  • 383
0 votes
0 answers
140 views

What is the strength of allowing multiple predecessor numbers?

If we have a theory of numbers, pairs of numbers, and sets of those, and axiomatize that the relation $<$ on numbers is both extensional and well founded, then this theory would prove all PA axioms ...
user avatar

1
2 3 4 5
88