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,126
questions
4
votes
0
answers
160
views
+100
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}$ ...
16
votes
3
answers
1k
views
Recommendations to learn about the use of toposes in logic?
I'd like to learn about the use of toposes in logic. The "logic" side I know quite well, but of the "topos" side I am totally ignorant.
Which books/articles (formal and/or casual) ...
2
votes
0
answers
198
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 ...
7
votes
2
answers
406
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 ...
-10
votes
0
answers
148
views
Does this bijection prove the continuum hypothesis? [closed]
This is a cross-post from math stackexchange. It has been a week, but I can't provide a link because the original post was deleted.
First, I want to show the bijection that is going to be built. It ...
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\...
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\...
9
votes
2
answers
361
views
Does the Affine Pappus Axiom imply the Affine Desargues Axiom in affine planes?
I am interested in the affine version of the well-known Hessenberg's Theorem (saying that Pappian projective planes are Desarguesian).
First I introduce all necessary definitions.
Definition L. A ...
6
votes
4
answers
1k
views
Is every Heyting algebra the Lindenbaum algebra of an intuitionistic first order theory?
This question comes after the comments in the recent related question Sigma-complete Lindenbaum algebras?, but in its current form is sufficiently different in my opinion, and so I decided to follow ...
10
votes
0
answers
438
views
(A little bit) Beyond the E-recursive
The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
4
votes
0
answers
153
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 ...
5
votes
1
answer
384
views
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
0
votes
0
answers
137
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 ...
10
votes
1
answer
626
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 ...
19
votes
3
answers
2k
views
Algebrization of second-order logic
Is there an algebrization of second-order logic, analogous to Boolean algebras for propositional logic and cylindric and polyadic algebras for first-order logic?
4
votes
0
answers
130
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 ...
3
votes
1
answer
92
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 ...
6
votes
1
answer
294
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 ...
7
votes
1
answer
163
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}$...
2
votes
0
answers
123
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 ...
42
votes
9
answers
5k
views
The sets in mathematical logic
It is well known that intuitive set theory (or naive set theory) is characterized by having paradoxes, e.g. Russell's paradox, Cantor's paradox, etc. To avoid these and any other discovered or ...
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 ...
28
votes
2
answers
1k
views
Applications of Categorical Logic to Logic
This is definitely a very open ended question.
I have been studying Categorical Logic for a while now --- I've read Sheaves in Geometry and Logic, Adámek & Rosický's Presentable Categories, ...
-3
votes
0
answers
208
views
Are there known examples like this almost official exposition of ZFC that is very weak?
Pseudo-ZFC is a theory written in the usual language of set theory, i.e. mono-sorted first order logic with equality and membership. The extra-logical axioms are:
Extensionality: $\forall x \forall y:...
4
votes
1
answer
136
views
Does $A \leq_{\alpha} B$ imply $A \leq_{\beta} B$ for admissible ordinals $\alpha < \beta$?
My very superficial intuition of $\alpha$-recursion is that it replaces the tape in a Turing machine with $L_{\alpha}$ for some admissible $\alpha$, so that $L_{\alpha}$ functions as working memory. ...
2
votes
1
answer
115
views
Proof of Lindenbaum lemma without deduction theorem
I'm working on a formalization of Lindenbaum's completeness lemma for modal logic systems, but I've been stuck in a property. Namely, when trying to prove that:
$$\forall\Gamma,\forall\phi,\enspace\...
18
votes
3
answers
2k
views
How do I apply the Boolean Prime Ideal Theorem?
I have become aware of an amazing phenomenon from a myriad of questions and answers here on MathOverflow: many of the results that I would typically prove using the Axiom of Choice can actually be ...
7
votes
4
answers
414
views
A conservative extension of Peano Arithmetic
Ulrich Kohlenbach makes the following intriguing comment here:
"In the 70s S. Feferman introduced a mathematically strong system S=restricted(PA^omega)+QF-AC+mu for classical mathematics (and in ...
10
votes
1
answer
266
views
Complexity of the set of models of TA
Recall that the theory of true arithmetic $TA$ is the theory of standard model of arithmetic $\mathcal N$. I am interested in the complexity of the set of countable models of $TA$ in the lightface or ...
7
votes
2
answers
600
views
Ideals generated by Turing independent sets
Recall that $X \subseteq 2^{\omega}$ is Turing independent if no $y \in X$ is computable from the Turing join of any finite subset of $X \setminus \{y\}$.
Question 1. Can we construct a Turing ...
5
votes
0
answers
99
views
Variation on definition of logical functors avoiding power objects
Without power sets in meta-theory not every Grothendieck topos is an elementary topos, Set is still Grothendieck, but it lacks power objects.
Now I am looking for a definition of a logical functor ...
20
votes
2
answers
2k
views
Tennenbaum's Theorem and polynomials
Tennenbaum's Theorem theory says that in a countable non-standard model of arithmetic with an underlying set consisting of standard numbers, neither the polynomial $A(x,y):=x+y$ nor the polynomial $M(...
26
votes
2
answers
7k
views
Large cardinal axioms and Grothendieck universes
A cardinal $\lambda$ is weakly inaccessible, iff a. it is regular (i.e. a set of cardinality $\lambda$ can't be represented as a union of sets of cardinality $<\lambda$ indexed by a set of ...
18
votes
1
answer
979
views
Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$
Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$.
Alice's color is $\color{red}{\text{red}}$ and Bob's color is $\color{blue}{\text{blue}}$. In each step, for each $s\in S$,...
14
votes
1
answer
1k
views
Hilbert's sixth problem and QFT description
The Wikipedia entry on Hilbert's sixth problem about QFT description is “Since the 1960s, following the work of Arthur Wightman and Rudolf Haag, modern quantum field theory can also be considered ...
5
votes
1
answer
183
views
Chromatic number of the infinite Erdős–Hajnal shift-graph
For any set $X$, let $[X]^2= \big\{\{x,y\}: x\neq y \in X\big\}$. Let $\kappa$ be an infinite cardinal. Let $G_\kappa = ([\kappa]^2, E_\kappa)$ where $E_\kappa = \big\{\{a,b\}\in \big[[\kappa]^2\big]^...
67
votes
5
answers
10k
views
Decidability of chess on an infinite board
The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
3
votes
1
answer
428
views
Decidability survives new constants
Let $L$ be a finite first order language
and let $M$ be an $L$-structure with universe $\mathbb{N}$
that interprets all $L$-symbols as recursive sets
(so $M$ is a recursive $L$-structure).
Let $L(c)$...
12
votes
1
answer
362
views
Partition into antichains
I've read that the following statement is a result of Balcar, but I am unable to find a reference or a proof:
Theorem: If $\kappa\ge \lambda$ are infinite cardinals, then $[\kappa]^{<\lambda}$ can ...
-4
votes
1
answer
171
views
Is Bounding Reflection consistent?
Working in the first order language of set theory.
Let $\varphi^{*B}$ be the formula obtained from $\varphi$ by merely bounding all open quantifiers in $\varphi$ by the symbol "$B$".
Here a ...
2
votes
1
answer
125
views
Is it consistent to add a generalization axiom on top of Ext.+Subworld Separation+Reduciblity?
Let's work with Harvey Friedman's theory ${\sf K}(W)$ as in his seminar notes "Axiomatization of Set Theory by Extensionality, Separation, and Reducibility", formulated in the language of ...
-3
votes
1
answer
282
views
Can this form of reflection be consistent?
Is this form of reflection consistent?
First I'll begin by clarifying the notation I'm using here:
By a quantifier being relativized or bounded it means that the first occurrence of the quantified ...
-2
votes
0
answers
224
views
Demonstration of the Diagonal Lemma
Let $f(x)$ be a recursive function, $\alpha(x)$ a class-sign and $\alpha_f(x)$ a class-sign equivalent to $\alpha(f(x))$, i.e.:
$$\alpha_f(n)\Leftrightarrow\alpha(f(n))\,\textrm{ is provable for each ...
3
votes
0
answers
134
views
Homotopy type theory for semantics
It looks like I have been building up a theory that might require looking closely at Homotopy Type Theory vs. Category Theory with respect to semantics. I am considering two types of semantics that ...
23
votes
7
answers
3k
views
When can we prove constructively that a ring with unity has a maximal ideal?
Many commutative algebra textbooks establish that every ideal of a ring is contained in a maximal ideal by appealing to Zorn's lemma, which I dislike on grounds of non-constructivity. For Noetherian ...
6
votes
0
answers
132
views
Complexity of transfinite 5-in-a-row and other games
Suppose that 5-in-a-row is played on an infinite board, and after an infinite number of moves, if no one won yet and there is an empty square, the game just continues. At limit steps, it is the first ...
10
votes
1
answer
241
views
How short can the axioms of propositional logic be?
There are a number of axiom systems for classical propositional calculus. Here, I focus on those which use negation ($\neg$) and implication ($\to$) as the connectives, with Modus Ponens and ...
5
votes
1
answer
237
views
When are the congruence lattices nicer?
This is a purely idle question, but one I'm increasingly interested the more thought I put into it:
For $\mathcal{A}$ a universal algebra (that is, nonempty set together with some named functions), a ...
5
votes
1
answer
333
views
What is the proof of consistency of anterior reflection?
Let Anterior Reflection be the following principle: $$\forall \vec{v}~ \exists X: \operatorname {transitive} (X) \land \, (\varphi \to \varphi^{X"}) $$
where $\varphi$ is a formula in $\sf FOL(=,\in)$ ...
10
votes
1
answer
547
views
A decision problem concerning Diophantine inequalities
Let $S$ be a subset of $\mathbb{R}^n$ defined by a system $\theta$ of polynomial inequalities with integer coefficients. Let $S+\mathbb{Z}^n$ be all points of the form $s+z$ with $s \in S$ and $z \in \...