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
vote
0answers
50 views

Is there a foundational approach that takes “structure” as primitive?

As per the title, I'd be curious to know if there have been attempts at constructing a foundation of mathematics taking, somehow, purely the notion of "structure" as primitive, maybe via a system of ...
3
votes
2answers
83 views

A ‘canonical’ bounded lattice with proper de Morgan negation?

Call a lattice negation $\neg$ proper de Morgan negation iff it satisfies the following conditions. $\neg\neg a=a$. $\neg(a\vee b)=\neg a\wedge\neg b$ and $\neg(a\wedge b)=\neg a\vee\neg b$. $a\...
4
votes
0answers
141 views

What's the smallest $\lambda$-calculus term not known to have a normal form?

For Turing Machines, the question of halting behavior of small TMs has been well studied in the context of the Busy Beaver function, which maps n to the longest output or running time of any halting n ...
5
votes
1answer
159 views

Every complex number has a square root via LLPO without weak countable choice

Is it possible to prove that every complex number has a square root using analytic LLPO, but avoiding Weak Countable Choice or Excluded Middle? Unique Choice is allowed. (Analytic LLPO is the ...
2
votes
0answers
166 views

Can we have the well founded world of NF obeying ZF?

The following question is about the possibility of having a world of sets obeying new foundations "NF" with their well founded sets obeying rules of ZF. It uses the revised version of Quines $``ML"$ (...
6
votes
1answer
203 views

Internal vs. external definability of inner models

Suppose $\kappa$ is an inaccessible cardinal. Is the following situation consistent? There is $p \in V_\kappa$ and a formula $\phi(x)$ such that there is exactly one $M \subseteq V_\kappa$ such that ...
-1
votes
0answers
97 views

If it is possible to define the Busy Beaver function for Hypermachines ($\Sigma_n$-machines of arbitrary $n>2$), how “strong” such a function will be?

Let $F_0(x)$ denote the Busy Beaver function for ordinary Infinite Time Turing Machines ($\Sigma_2$-machines). Assume that it is possible to define (in a similar way) Busy Beaver functions for ...
1
vote
1answer
121 views

The “higher topology” of countable Scott sets

Fix some computable bijection $b$ between $\omega$ and $2^{<\omega}$. For $r\in 2^\omega$, let $$[r]=\{f\in 2^\omega: \forall\sigma\prec f(b^{-1}(\sigma)\in r)\}$$ be the closed subset of Cantor ...
5
votes
1answer
423 views

What types are to mathematical proofs as types à la Martin-Löf are to constructive proofs, and what's wrong with them?

The question is motivated by this surprising sentence from Freek Wiedijk's The QED Manifesto Revisited. I agree that the QED-like systems that exist today are not good enough to start developing ...
2
votes
0answers
203 views

A decision problem from sheaf set theory?

Let $V^{X}$ be a sheaf model of ZF set theory, where $X$ is a topological space as it is defined in [1]. Let $T(y_1,\ldots,y_n)$ be an $B(T)$-free algebra as it is defined in [2], where $B(T)$ is the ...
1
vote
1answer
58 views

Non-relativized, Computable and Schnor randomness w.r.t a measure

Riemann and Slaman have some great work classifying what reals are 1-random with respect to a measure $\mu$ relative to $\mu$. In that paper they cite Levin and Kautz (but not to refs I can find) for ...
0
votes
1answer
54 views

Kurtz randomness and supermartingales with infinite *limit*

Suppose you replace the usual success conditions for a supermartingale (lim sup is infinite) with the requirement that the actual limit is infinite, e.g. a supermartingale $B$ succeeds on $X \in 2^\...
0
votes
0answers
78 views

Are there minor tweaks of hereditary replacement that can prove large cardinal properties?

Hereditary replacement: if $\phi(x,y)$ is a formula in which only symbols $x,y$ occur free, and those never occur bound, and in which symbol $B$ never occur; then: $$\big{(}\forall A [\forall x \...
8
votes
0answers
142 views

Topology is to semi-decidability, coarse structures are to what?

There is a folklore correspondence between topology as semi-decidability amongst computer scientists, which is explained in places like: The monograph Synthetic Topology: of Data Types and Classical ...
0
votes
0answers
107 views

Is there a standard way to relativize algorithmic complexity constructively?

Given an index set $A$ of indices that compute some (class of) structures such that $A$ is complete in the class $ \Pi^0_n$ in the arithmetical hierarchy, let’s say we want to determine the ...
0
votes
0answers
62 views

Could this intended maximal anti-foundation axiom result in increment of consistency strength over that of ZFC?

Starting with ZFC: Remove axioms of Extensionality and Foundation Add axiom schemata of Collection and Separation Add the axiom of reduction: $$\forall X \ \exists Y \subseteq X \ \forall x \in X \ \...
7
votes
1answer
130 views

Bounding and domination numbers for relation $\leq$ modulo $\omega$-nullsets

We say that $A\subseteq \omega$ is a nullset if $$\lim\sup_{n\to \infty} \frac{|A\cap n|}{n+1} = 0.$$ Let $\omega^\omega$ denote the set of functions $f:\omega\to\omega$. We define a pre-ordering ...
0
votes
1answer
84 views

Can we have cyclic generalized positive comprehension?

In positive set theory, the axiom scheme of generalized positive comprehension in $GPK^+_\infty$ [of Olivier Esser] is stated in a manner as to forbid the symbol of the asserted set to occur in the ...
20
votes
2answers
1k views

Could groups be used instead of sets as a foundation of mathematics?

Sets are the only fundamental objects in the theory $\sf ZFC$. But we can use $\sf ZFC$ as a foundation for all of mathematics by encoding the various other objects we care about in terms of sets. The ...
0
votes
0answers
114 views

Is this anti-foundation axiom consistent?

Starting with ZFC: Replace axiom of Extensionality by weak Extensionality (nonempty sets having the same members, are identical) Remove axiom of Foundation. Add the anti-foundation axiom which ...
-1
votes
1answer
119 views

Is cyclic replacement inconsistent with ZFC-Foundation?

Replacement: if $\phi(x,z)$ is a formula in which all and only symbols $``x,z,x_1,..,x_n"$ occur free, and non of them occur as bound, and in which the symbol $``B"$ never occur; then: $$\forall x_1,.....
8
votes
0answers
124 views

*Really* undetermined Banach-Mazur games?

This question is a follow-up to this one; see that question for the definition of Banach-Mazur games. In the absence of dependent choice, determinacy is arguably less natural than quasideterminacy. A ...
0
votes
0answers
139 views

Satisfying systems in Gödel's original proof of completeness

Gödel's original proof of completeness shows that a formula of the form $\forall \exists A$ is either satisfiable or refutable. The quantifier-free formula $A$ is composed of individual variables $v_i$...
10
votes
1answer
283 views

Does $Π^1_{2n+1} = (Σ^1_{2n+1})^{M_{2n-1}}$?

Every $Π^1_1$ formula $φ$ without free second order variables can be converted into a $Σ^1_1$ $ψ$ such that $φ ⇔ ψ^\mathrm{HYP}$, and vice versa. ($\mathrm{HYP}$ is the hyperarithmetical universe, ...
3
votes
0answers
202 views

Is there a second-order expression of '$\kappa$ is Reinhardt' in $NGB$, where $\kappa$ is a cardinal?

In their paper, "Generalizations of the Kunen inconsistency", (Annals of Pure and Applied Logic 163 (2012) 1872-1890, doi:10.1016/j.apal.2012.06.001, arXiv:1106.1951), Hamkins, Kirmayer, and ...
1
vote
0answers
91 views

Can small class choice be weaker than global choice and stronger than set choice + collection?

In this posting what was termed as "Proper Class Choice" principle turned to be equivalent to Global Choice over the base theory of "MK-Foundation -Limitation of size + Set Replacement*". However if ...
5
votes
0answers
198 views

General theory of the reals in Solovay-like models

Solovay's model is a famous model of $\sf ZF$ where we start in $L$ with $\kappa$ inaccessible, and we collapse all the ordinals below $\kappa$ to be countable, without collapsing $\kappa$ itself, and ...
9
votes
1answer
385 views

Logical completeness of Hilbert system of axioms

This is really a question about references. The entry in Russian Wikipedia about Hilbert's axioms states, in particular, that completeness of Hilbert's system was proven by Tarski in 1951. The ...
-1
votes
1answer
156 views

Is Proper Class Choice equivalent to Global Choice?

Working in "MK-Regularity-Limitation of Size + Replacement for sets", call it the Base theory, let's coin the following axiom: Axiom of Super-Choice:$$\forall \ relation \ R \ \exists F \subset R \ (...
22
votes
2answers
461 views

Undetermined Banach-Mazur games in ZF?

This question was previously asked and bountied on MSE, with no response. This MO question is related, but is also unanswered and the comments do not appear to address this question. Given a ...
0
votes
1answer
194 views

Set of definable real numbers?

Is there a set theory at least as strong as $KP\omega$ which has as a theorem that there is a set $\mathbb{D}$ of precisely the definable real numbers?
0
votes
0answers
71 views

What's the strength of capturing set theory in labeled Mereology?

To Atomic General Extensional Mereology + Bottom, add a primitive one place partial function symbol $L$, signifying "the label of", an add axioms: Distinctiveness: $Lx=Ly \to x=y$ Labels: $\forall x (...
-2
votes
1answer
124 views

Does MK prove internally that there are more proper classes than sets?

Is the following provable in MK? $\not \exists S: \\ \text{ } \\1. \ \ \forall s \in S \exists a,b (s=\langle a,b \rangle) \\ \text{ } \\2. \ \ \forall x (set(x) \to \exists! X (\neg set(X) \land \{...
-1
votes
1answer
181 views

Weak power set - what strength may it have?

In The Consistency of Classical Set Theory Relative to a Set Theory with Intuitionistic Logic in THE JOURNAL OF SYMBOLIC LOGIC Volume 38, Number 2, June 1973 page 316 Harvey Friedman's axiom 8* $Weak \...
6
votes
0answers
194 views

$0^\#$ in weak theories vs large cardinals in $L$

To better understand the transition from large cardinal axioms consistent with the constructible universe $L$ to large cardinal axioms transcending $L$, I am looking for natural equiconsistencies ...
0
votes
0answers
53 views

Reference Request: Had that Labeled-Mereological system been studied before?

This theory is an extension of Atomic General Extensional Mereology "AGEM", it adds a primitive total distinctive unary function $L$, denoting "The label of", and adds the following axioms about it: ...
1
vote
0answers
260 views

A countable set theory providing choice?

Instead of Zermelo set theory $Z$ take $Y$ = $Z$ minus the power set axiom plus Enumerability: $\forall x(x\neq \emptyset \to\exists f[f:\mathbb{N}\overset{onto}{\frown}x ])$ $\imath$ is the ...
1
vote
0answers
50 views

Is there a restrain on the total number of proper classes strictly smaller than the universe in variants of MK?

In an old discussion thread at sci.math, Herman Rubin said: " There exist models where all proper classes have the same cardinality; i.e., the universe is equinumerous with the class of ordinal ...
5
votes
1answer
154 views

Self-embeddings of uncountable total orders, 2

Let $S = (\Omega,\leq)$ be an uncountable dense total order, such that for all positive integers $m$ and all finite ordered sequences $a_1 < a_2 < \ldots < a_m$ and $b_1 < b_2 < \ldots &...
6
votes
0answers
250 views

How bad a proper forcing of size $\aleph_1$ can be?

This question concerns proper forcings of size $\aleph_1$. In the context of $\rm ZFC+\neg CH$, I couldn't find any counter example to the following property. Suppose $\mathbb P$ is a proper forcing ...
9
votes
1answer
467 views

Is there a ring for which the reducibility of a polynomial is undecidable?

Let $R$ be a ring such that all of its elements have a finite number of divisors, ie $\forall r\in R\, |\{x\in R: x|r\}|<\infty$. Then we can decide whether a polynomial in $R[t]$ is reducible ...
4
votes
1answer
176 views

Forcing square introduces diamond

Let $\mathbb S_\kappa$ be the standard forcing for $\square_\kappa$ by initial segments. This is $(\kappa+1)$-strategically closed. Observation: Let $T \subseteq \kappa^+$ be stationary. If $T$ ...
3
votes
0answers
133 views

Improving a Lindstrom-y fact about $\mathcal{L}_{\omega_1,\omega}$?

See e.g. the last section of Ebbinghaus/Flum/Thomas for the relevant background on abstract model theory. Below, all languages are finite for simplicity. "$HC$" is the set of hereditarily countable ...
3
votes
0answers
136 views

Elementary self-embeddings conservative over ZFC

Question: Is the following theory conservative over ZFC? And if not, what is its strength? Language: $∈$, $j$ (unary function symbol) Axioms: 1. ZFC (without separation and replacement for formulas ...
6
votes
1answer
258 views

Is $\prod_{X : \mathcal{U}} (X \to X) \cong 1$ consistent with type theory?

Assume we work in some minimalistic version of Martin-Löf type theory. Does it break consistency to postulate that the function that selects the identity function has an inverse? $$\prod_{X : \...
5
votes
1answer
403 views

Can $H_{\omega_1}$ and $H_{\omega_2}$ be in bi-interpretation synonymy?

This question concerns the possibility of the bi-interpretation synonymy of the structure $\langle H_{\omega_1},\in\rangle$, consisting of the hereditarily countable sets, and the structure $\langle ...
1
vote
1answer
149 views

Is every true $\Pi^0_1$ statement entailed from a consistency statement of $PA$?

I want to prove the following. For every $\Pi^0_1$ statement $\forall x\phi(x)$, where $\phi(x)$ is a $\Delta^0_1$ formula, there is $e\in\mathbb{N}$ such that $\forall x\phi(x)$ implies $W_e=PA$* ...
1
vote
1answer
119 views

Category of finite models of a $\tau$-sentence

Let $\varphi$ be an $\tau$-sentence, we define the generalized spectrum of $\varphi$ as the class of its finite models, $$\text{GenSpec}(\varphi):=\{\mathcal{A}; \mathcal{A} \models \varphi, \lvert A\...
6
votes
1answer
189 views

“Robinson arithmetic” for (some) levels of $L$?

I'll write "$\mathcal{L}_\alpha$" for the fragment $\mathcal{L}_{\infty,\omega}\cap L_\alpha$. Say that a countable admissible $\alpha$ is Robinsonian if there is some sentence $\varphi\in\mathcal{L}...
0
votes
0answers
299 views

Artificial intelligence simulating mathematicians (what a distopia!)

This is kind of soft and naive question, so feel free to shame on me :) I start from the fact that, in my opinion, what humans are interested in about mathematics are things that we find deep and ...

1 2 3 4 5 71