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,127
questions
6
votes
0
answers
399
views
Can Set Theory be turned into Infinite Arithmetic?
The following system I'd label as "Infinite Arithmetic" is simply an endeavor to extend second order arithmetic to the infinite ordinal world, and extending with it the representation of ...
2
votes
0
answers
200
views
The most powerful inner model and a $\Delta^2_1$ well-ordering of the reals
With the current research, it seems that we are in a position to get extremely powerful absoluteness theorems (like $\Sigma^2_0$-absoluteness, $\Sigma^2_1$-absoluteness, $\Sigma^2_2$, $\diamondsuit_G$,...
2
votes
1
answer
243
views
Inner model for KP and a Well-Ordering of the Reals
It is well known that Gödel proved the following theorem:
$\mathsf{ZFC + V=L}$ has a $\mathit{\Delta}^1_2$-good well-ordering of $\mathbb{R}$. (Gödel, Addison)
So:
Is there an inner model for KP/Z/....
16
votes
2
answers
637
views
Operations on the set of large cardinal axioms
Here's a question from a non-set-theorist, but a sometime-user of large cardinals.
The name Cantor's attic is pretty evocative for the collection of large cardinal axioms: looking through the pages ...
1
vote
0
answers
161
views
Can the Constructible Universe be built in absence of Unions and Power?
Can $L$ be built in
$\sf ZF$ $\sf-Regularity-Union-Power+ Boolean \ Union$?
We know that $L$ can be built in $\sf KP$, but here we don't have Set Union.
If the answer is to the negative, then would ...
10
votes
1
answer
220
views
How much of second-order arithmetic do you need for $\mathbf{\Sigma}^1_1$-determinacy to give you countable transitive models of $\mathsf{ZFC}$?
This is in some sense a follow-up to this question.
The answer there says that over $\mathsf{Z}_2$ (second-order arithmetic), (boldface) $\mathbf{\Sigma}^1_1$-determinacy is enough to entail the ...
3
votes
0
answers
111
views
Is it consistent to have an infinite antitone sequence of elementary embeddings such that the involved models include iterated sharps?
$\DeclareMathOperator\crit{crit}$Background essays (the material I've tried to understand in leading up to this question):
Daghighi, et. al. [2014], "The foundation axiom and elementary self-...
1
vote
0
answers
153
views
Solution of an equation over free group
Let $F_n$ be a free group on $n$ generators. Let $w \in F_n$ be a word such that there does not exist any solution in $F_n$ for the equation $w.w(t_1, \ldots, t_n) = 1$, where $t_1, \ldots, t_n$ are ...
9
votes
0
answers
406
views
Does Wedderburn's Theorem hold constructively?
Wedderburn's Theorem states that every finite division ring is commutative. Perhaps even more surprising, this implies that every finite reduced ring is commutative. The proofs that I am aware of ...
5
votes
2
answers
622
views
MIP*=RE theorem and its impact on logic and proof theory
In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
6
votes
1
answer
230
views
Existence property for second-order propositional logic
Consider the intuitionistic second-order propositional calculus (SOL) formulated in the full $\wedge,\vee,\rightarrow,\bot,\top,\forall,\exists$ language.
Question: Assume that $\Gamma$ and $\Psi$ are ...
11
votes
1
answer
370
views
Does every finite affine plane have the doubling property?
Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms:
Any distinct points $x,y\...
2
votes
0
answers
51
views
Finite (schema) axiomatizability of representable cylindric algebras
If we know that the class of all representable cylindric algebras of dimension $\alpha$ (for any ordinal number $\alpha>2$) is NOT finitely (schema) axiomatizable*, then does it (perhaps trivially) ...
2
votes
1
answer
368
views
Impredicativity, definition, recursion and conservatism
Suppose we in an impredicative framework isolate the fixed point
$$Gx\leftrightarrow A(G,x)$$
from a $Gx$ obtained by $\Pi^1_1$-comprehension as equivalent to $\forall K((A(K,x)\to Kx)\to Kx)$, where $...
2
votes
1
answer
261
views
I have a problem about elementary submodels of ZFC
So suppose $\kappa$ inaccessible so that $V_\kappa$ is a model of ZFC, using Skolem and the Mostoswky collapse we have a countable elementary submodel $M$ of $V_\kappa$. This implies that for any ...
8
votes
2
answers
548
views
Turing degrees of sets separating two computably inseparable sets (theorems and antitheorems)
Let $A\subseteq\mathbb{N}$ be the set of Gödel codes of theorems of Peano arithmetic, and $B\subseteq\mathbb{N}$ be the set of codes of antitheorems (i.e, refutable statements, statements whose ...
7
votes
1
answer
229
views
How did Szmielew prove that Pasch's axiom is a consequence of the circle axiom?
It is alleged that Szmielew proved that Pasch's axiom is a consequence of the circle axiom. The source is said to be
The Pasch axiom as a consequence of the circle axiom, Bull.Acad.Polon.Sci.Sér.Sci....
14
votes
1
answer
1k
views
(Very) Large numbers, Chaitin's incompletness theorem and a specific upper bound
Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>...
5
votes
1
answer
277
views
Words which are not inverted by any endomorphism
Let $w$ be a word in a free group $F_2$ of two generators $x_1, x_2$ such that there does not exist any endomorphism of free group which takes $w$ to $w^{-1}$. Let $w_1, w_2$ be two words in the same ...
6
votes
1
answer
265
views
The Parity Principle and $\mathbf{C}_2$ (choice for $2$-sets)
The Parity Principle states that
if $X\neq \emptyset$ is a set, then there is $\mathcal B\subseteq \mathcal P(X)$ such that whenever $a,b\in \mathcal P(X)$ with $a\mathbin\Delta b = \{x\}$ for some $...
7
votes
1
answer
949
views
Propositional calculus, first order theories, models, completeness
In the usual context of model theory one studies first order theories: the Gödel completeness theorem asserts that $\varphi$ is a theorem of a theory $T$ (i.e. $\varphi$ is provable from the axioms of ...
6
votes
1
answer
172
views
Consistency in pure type systems
Summary
My question is about how (i) a certain presentation of pure type systems in the $\lambda$-cube, bears on (ii) a standard definition of consistency in pure type systems. In short, I'm ...
4
votes
2
answers
276
views
Is there a consistent, unsound, $\omega$-inconsistent, effective theory that doesn't prove its own inconsistency?
Can we have a consistent and effective (fulfilling Godel's criteria) first order theory $T$, that is both arithmetically unsound and $\omega$-inconsistent, and yet doesn't prove its own inconsistency (...
18
votes
2
answers
1k
views
What notable theorems cannot be automatically proven without choice using Shoenfield absoluteness?
There have been a couple of recent questions, here and here, regarding the role of the axiom of choice in real-analytic results with applicability to general relativity. This lead me to look at some ...
8
votes
2
answers
1k
views
Can we effectively axiomatize a theory that proves the negation of its own Gödel's sentence?
For any consistent and effective theory $T$ fulfilling Gödel's criteria, let $G_T$ be the Gödel sentence of $T$, that is: $$ G_T \iff \neg \exists x: \operatorname{Proof}_T(x,\ulcorner G_T \urcorner)$$...
10
votes
2
answers
415
views
The additive structure of clusters of nonstandard models of arithmetic
Given $\frak M$ a countable nonstandard model of $\sf PA$ and let $a\in M$ be a nonstandard element. A "cluster around $a$" is the set of successors and predecessors of $a$, a cluster is a ...
5
votes
2
answers
695
views
What is lost in General Relativity without Hahn-Banach axiom in the ZF+HB set theory?
In the same spirit of this question:
How much of mathematical General Relativity depends on the Axiom of Choice?
I want to go radically further ahead and ask for what remains of mathematical general ...
4
votes
0
answers
236
views
Cantor-Bernstein phenomena for structures (and a "moderate zigzag" property)
My favorite proof of the Cantor-Bernstein theorem is the one that argues by "histories" - given injections $f:A\rightarrow B$ and $g:B\rightarrow A$, we identify each element of $A$ as ...
10
votes
2
answers
426
views
Is the set of permissible numbers of models of various cardinalities computable?
This question arose in the comments to this question.
Let $X$ be the set of pairs $(m,k)$ such that there is some (consistent complete countable first-order) theory $T$ with exactly $m$ models of size ...
52
votes
7
answers
6k
views
Are there any undecidability results that are not known to have a diagonal argument proof?
Is there a problem which is known to be undecidable (in the algorithmic sense), but for which the only known proofs of undecidability do not use some form of the Cantor diagonal argument in any ...
6
votes
1
answer
374
views
Thick Canadian trees
A Canadian tree (also called a weak Kurepa tree) is a tree of height $\omega_1$ with levels of cardinality $\leq \omega_1$ and at least $\omega_2$ many uncountable branches. Let's call a Canadian tree ...
6
votes
1
answer
338
views
Quantifier complexity of definition of compactness
This question is inspired by the post on quantifier complexity of
continuity. We work with metric spaces M
considered as two-sorted first-order structures (M,$\mathbb R$,d,+,⋅,<)
where $d:M^2→\...
4
votes
1
answer
703
views
Why adhere to $\omega$-consistency with respect to Godel's proof of first incompleteness?
On MSE I've asked a question about why did Godel assume the theory in question to be $\omega$ consistent [on top of effectiveness] for his proof [actually the second part of his proof] of first ...
13
votes
1
answer
494
views
Is there a complete uncountable theory with two countable models?
This is a question originally asked at MSE a few years ago; the original poster hasn't been active in a while, so I'm taking the liberty of asking it here:
Is there a complete first-order theory $T$ ...
8
votes
2
answers
650
views
Is the existence of substructures satisfying a theory absolute?
Given a first-order structure $\mathfrak{A}$ and a first-order theory $T$ one can ask if
$$
\varphi(\mathfrak{A}, T) := ``\text{there is a substructure } \mathfrak{B} \text{ of } \mathfrak{A} \text{ ...
3
votes
1
answer
201
views
Another implication of the Affine Desargues Axiom
Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms:
Any distinct points $x,y\...
2
votes
1
answer
120
views
Splitting $\Pi^0_2$ Singletons?
Given a (non-computable) $\Pi^0_2$ singleton $Y$ are there Turing incomparable $\Pi^0_2$ singletons $X_0, X_1$ with $Y \equiv_T X_0 \oplus X_1$?
What about the same question for arithmetic ...
14
votes
0
answers
415
views
Which functions have all the common $\forall\exists$-properties of continuous functions?
This is an attempt at partial progress towards this question. Meanwhile, Sam Sanders pointed out that my original term was already in use, as were a couple other back-up terms, so ... oh well.
For a ...
4
votes
1
answer
216
views
Can a halting oracle determine if a Turing machine is an ordinal?
For the sake of clarity, I am regarding a computable relation on $\mathbb{N}$ as a $2$-symbol ($0$ and $1$) Turing machine $T$ which halts on any initial binary string (which are interpreted as some ...
4
votes
0
answers
143
views
On self-reference in a weak structure
Below, all structures are countable and in finite languages. This question is motivated by the following: "To what extent is self-reference possible when nothing like the diagonal lemma holds?&...
6
votes
1
answer
272
views
What is the power of the “anti-halting” oracle?
Let me first ask the question, and then, as it may seem a bit cryptic, explain how it comes up (and whence the “anti-halting oracle” in the title):
Notations: we write $\langle m,n\rangle$ for a ...
4
votes
0
answers
354
views
Does $e^x$ let the reals build any new ordinal functions?
This question is closely related to this one. Belatedly, it occurred to me that I'd probably picked the wrong test question. I'm leaving that question up because I don't think it's bad per se, but I ...
5
votes
1
answer
406
views
Uniform strategy on Kastanas' game
I think my question applies to most games, but for the sake of concreteness, I shall consider one specific game in this question. We consider the game posed by Ilias Kastanas in his paper On the ...
1
vote
0
answers
91
views
Need help unpacking the interdependence of axiomatic set theory and first-order logic
I'm currently self-studying both Von Neumann Set Theory (not ZFC but rather axiomatic set theory with the undefined notion of class) and First-Order Logic.
I've been self-studying the following ...
20
votes
4
answers
2k
views
Is Bauer–Hanson’s result “there is a topos where the Dedekind reals are countable” novel?
Last year, Andrej Bauer gave a talk showing that there is a topos in which the set of Dedekind reals is (sub)countable, and thus, you cannot prove that $\mathbb{R}$ is uncountable without LEM. He ...
0
votes
1
answer
372
views
How bad is Coq proving both $T$ and $\lnot T$? [closed]
Question: How bad is Coq proving both $T$ and $\lnot T$? Can it be abused?
Back in 2011 on the coq-club mailing list there was a thread:
Is the Daniel Schepler's inconsistency real?.
In the thread ...
7
votes
0
answers
246
views
Something like "o-minimal ordinal analysis"
Below, by "nice structure" I mean "o-minimal expansion of $(\mathbb{R};<)$ by countably many continuous functions and open relations."
Suppose $\mathfrak{A}=(\mathbb{R};<,......
32
votes
2
answers
2k
views
Quantifier complexity of the definition of continuity of functions
This was previously asked at MSE, but I was told to ask it on MO. Consider the structure $(\mathbb{R};+,-,*,0,1,<)$. We adjoin to it a unary function $f$ defined everywhere on the set of real ...
40
votes
3
answers
5k
views
How much of mathematical General Relativity depends on the Axiom of Choice?
One of the cornerstones of the mathematical formulation of General Relativity (GR) is the result (due to Choquet-Bruhat and others) that the initial value problem for the Einstein field equations is ...
-3
votes
1
answer
151
views
Propositional logic without rules of inference and assumptions (except MP) [closed]
I was wondering whether it would be possible to do propositional logic without any rules of inference and assumptions (except modus ponens).
I have the following axioms:
$ p \to (q \to p) $
$ (p \to (...