All Questions
6,026 questions
17
votes
3
answers
2k
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) ...
- 32.5k
3
votes
0
answers
255
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 ...
- 31
11
votes
1
answer
390
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\...
- 63.9k
3
votes
1
answer
212
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\...
- 42k
9
votes
2
answers
383
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 ...
- 42k
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 ...
- 4,219
9
votes
0
answers
471
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. ...
CommunityBot
- 1
5
votes
0
answers
213
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 ...
- 333
5
votes
1
answer
406
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 ...
- 839
1
vote
0
answers
174
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 ...
- 11.3k
12
votes
1
answer
845
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 ...
- 11.3k
5
votes
0
answers
191
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 ...
4
votes
1
answer
155
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 ...
- 47.4k
7
votes
1
answer
355
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 ...
- 869
8
votes
1
answer
241
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}$...
- 18.6k
43
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 ...
- 2,031
53
votes
7
answers
7k
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 ...
- 236k
32
votes
2
answers
2k
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, ...
- 756
4
votes
1
answer
154
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. ...
- 1,780
2
votes
1
answer
193
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\...
- 48.8k
20
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 ...
- 1,566
7
votes
4
answers
572
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 ...
- 17.7k
10
votes
1
answer
287
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 ...
- 515
7
votes
2
answers
644
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 ...
- 1,780
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(...
- 1,851
28
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 ...
- 2,031
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 ...
- 3,094
6
votes
1
answer
221
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]^...
- 48.9k
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 ...
- 236k
3
votes
1
answer
443
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)$...
- 236k
12
votes
1
answer
376
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 ...
- 1,467
-4
votes
1
answer
198
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,031
2
votes
1
answer
132
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 ...
- 2,031
-3
votes
1
answer
296
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,031
3
votes
0
answers
209
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 ...
- 1,313
6
votes
0
answers
185
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 ...
- 7,545
10
votes
1
answer
307
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 ...
- 1,851
5
votes
1
answer
265
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 ...
- 4,219
5
votes
1
answer
344
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)$ ...
- 11.3k
10
votes
1
answer
549
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 \...
- 63.9k
6
votes
2
answers
438
views
Stationary many subsets of $\kappa^+$ whose order type is a cardinal and whose intersection with $\kappa$ is an inaccessible cardinal
Is anything known about the consistency strength of the following statement?
$\kappa$ is a Mahlo cardinal and there is a stationary set of $a \in \mathcal{P}_\kappa(\kappa^+)$ such that $a \cap \...
- 1,799
11
votes
1
answer
1k
views
Are there mutually independent undecidable statements?
In a recursively axiomatized theory such as PA, are there undecidable statements that are arithmetically true but mutually independent (i.e., are there two statements A and B that are each undecidable ...
- 236k
6
votes
1
answer
220
views
On the number of complete Boolean algebras
In their 1972 paper On the number of complete Boolean algebras Monk and Solovay showed that if $\lambda$ is an infinite cardinal, then there are $2^{2^\lambda}$ many isomorphism types of
complete ...
- 32.5k
5
votes
0
answers
160
views
$S$ and $T$ globally isomorphic semigroups, with $S$ (commutative and) cancellative, iff $S$ is isomorphic to $T$?
Denote by $\mathcal P(S)$ the semigroup obtained by equipping the non-empty subsets of a "ground semigroup" $S$ (written multiplicatively) with the operation of setwise multiplication ...
- 10.5k
11
votes
1
answer
442
views
1970 question of Reinhardt - how large is this ordinal?
On page 241 of William Reinhardt's paper "Ackermann's set theory equals ZF" (Annals of Math. Logic vol. 2, 1970), question 4.15 is the following:
How large is the first ordinal $\gamma$ ...
- 2,031
7
votes
1
answer
494
views
Normal form for terms in language with two ring structures
Suppose I have two different ring structures on the same domain $\langle R,+,\cdot,0,1\rangle$, $\langle R,\oplus,\otimes,\bar 0,\bar 1\rangle$ and I throw the structures together into a single common ...
- 4,713
3
votes
2
answers
152
views
Membership Provability in co-RE Sets
We're interested in recursive predicates $P(n)$ with RE range $R$ and non-RE complement $R^\prime$. For various $n \in R^\prime$ we may be able to prove that $n \in R^\prime$. For instance, if $P$ ...
- 236k
1
vote
1
answer
196
views
Gödel coding and the function $z(x)$
The function $z(x)$ that associates to each formula $\alpha$ of $P$ its Gödel number $z(\alpha)$ is external to the system. How then can expressions in which $z(x)$ be involved be expressed in $P$? ...
- 236k
4
votes
0
answers
290
views
Which countable sets don't drastically change the definable topologies on $\mathbb{R}$?
For $\mathcal{M}$ an expansion of $\mathcal{R}=(\mathbb{R};+,\times)$ and $A\subseteq\mathbb{R}$, let $\tau^\mathcal{M}_A$ be the topology on $\mathbb{R}$ generated by the sets definable in $\mathcal{...
- 1
3
votes
1
answer
96
views
Is this form of replacement suitable for ZF - Powerset + well-ordering principle?
The following scheme can be understood as a form of replacement. Axiomatizing $\sf ZF$ with it instead of the usual replacement schema renders it immune to removal of extensionality; see here.
In an ...
- 236k