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, ...

learn more… | top users | synonyms (1)

1
vote
1answer
69 views

On whether a formula of KP is $\Pi_3$

In the context of KP, is the formula $\forall w(w\in x \leftrightarrow\forall y\exists z F(w,y,z))$ $\Pi_3$ when $F(w,y,x)$ is $\Delta_0$?
4
votes
0answers
273 views

Consequences of ZF+“all subsets of reals are Lebesgue measurable”

(I'm not sure if this is entirely suitable here so feel free to close it if it's not.) The statement "there is a Lebesgue measure on $\mathbb{R}$($2^\omega$)" means: there is a total $\sigma$-additive ...
6
votes
2answers
168 views

Decidability of diophantine equation in a theory

Given a theory $T \subseteq \operatorname{Th}(\mathbb{N})$, define the decision problem $D_T$ as follows: Given a polynomial $p$ with integer coefficients and variables $\bar{x}$, decide whether ...
9
votes
2answers
198 views

Is there a compendium of the consistency strength between the most important formal theories?

Preliminar Notions: A formal system is a tuple $(\Sigma,G,A,R)$ where $\Sigma$ is an alphabet (set of symbols), $G$ is a formal grammar on $\Sigma$ that generates a formal language $L$ (set of well ...
8
votes
0answers
183 views

Analogues of Primitive Recursive Functions

Let $\mathbf{A}$ be an admissible set (possibly with urelements). I am wondering if there is some good notion of "primitive recursive arithmetic" relative to $\mathbf{A}$. More precisely, I would like ...
2
votes
1answer
72 views

Total formulae in a theory equivalent to $\Delta_0$ formulae in the theory?

Let a formula $\phi$ of the language of first-order Peano arithmetic be total in a theory Th that extends PA iff, for any $k_1, \dots, k_n \in \omega$, Th $\vdash \phi(\bar k_1, \dots, \bar k_n)$ or ...
4
votes
2answers
246 views

Limits of determinacy on reals

For $X\subseteq\mathbb{R}^\omega$, say that $X$ is determined if the associated game on $\mathbb{R}$ of length $\omega$ (players I and II alternate playing reals, player I wins iff the sequence built ...
-1
votes
0answers
34 views

representing quasicrystal as tilings and appearing frequencies of each tile

Quasicrystal can be fully represented either using projection method or tilings with constraints. For the latter, is there some sort of study on the "appearing frequency" of each tile or even ...
5
votes
1answer
196 views

Are two forms of the Dual Schroeder-Bernstein property equivalent?

We know the Shroeder-Bernstein (SB) theorem can be proved in ZF, while the Dual Schroeder-Bernstein (DSB) can be proved in ZF+AC but not in ZF. Define as ISB the property that whenever there are both ...
4
votes
1answer
374 views

Did Brouwer evade uncountability?

I have the distinct memory of having often heard and read that intuitionism was inter alia geared to avoid Cantor's uncountable sets, and it may be that this was Brouwer's plan. But are there accounts ...
-2
votes
1answer
120 views

Does PA prove a sentence asserting that all of I-sigma(n) theories are consistent? [closed]

We know that PA proves consistency of $I\Sigma_{n}$ for any $n$. But does PA prove the sentence: $\forall n (con(I\Sigma_{n}))$?
1
vote
3answers
563 views

Brouwer vs. Cantor

Brouwer criticises Cantor e.g. in Intuitionistiche Mengenlehre. Is there a link or reference to some streamlined modern account of Brouwer's ideas?
11
votes
5answers
742 views

Does k(X) have a k-basis for every set X, without AC?

This question is inspired by Pace Nielsen's recent question Does a left basis imply a right basis, without AC?. For any field $k$, the field $k(x)$ of rational functions in one variable has an ...
10
votes
1answer
204 views

counterexample regarding quotient algebras in forcing

Suppose $A$ and $B$ are complete subalgebras of a complete boolean algebra $C$. Let $G \subseteq A$ be generic. In the extension $V[G]$, we can define the quotient algebras $B/G$ and $C/G$ in the ...
21
votes
2answers
669 views

Forcing as a replacement of induction and diagonal arguments

Let me give some examples motivating the question. The use of forcing instead of induction: For this consider Cantor's theorem: Theorem 1. Any two countable dense linear orders $I, J$ without end ...
6
votes
0answers
212 views

A new cardinality living in every forcing extension?

This question is motivated by the papers http://arxiv.org/abs/1405.7456 and http://arxiv.org/abs/1410.1224. Say that a set $X$ is "generically presentable" over $V\models ZF$ if there is some ...
13
votes
0answers
388 views

Has anyone read/debunked Yessenin-Volpin–Hennix “Beware of the Gödel-Wette paradox”?

A student recently asked me about the status of a 2001 arXiv post, Beware of the Gödel-Wette paradox!, by Alexander Yessenin-Volpin (aka Esenin-Volpin and several other transliterations) and Catherine ...
2
votes
1answer
219 views

Axiomatic ZFC Set Theory [closed]

Can the Axiom Schema of Comprehension be omitted from ZFC since it is implied by the Axiom Schema of Replacement?
-1
votes
1answer
89 views

types and elementary extensions [closed]

Let $\mathcal{M}$ and $\mathcal{N}$ be two $\mathcal{L}$-structures and suppose that for n-tupls $\bar{a}\in M^n$ and $\bar{b}\in N^n$, $tp^\mathcal{M}(\bar{a})=tp^\mathcal{N}(\bar{b})$ where ...
2
votes
3answers
297 views

The Set-Theoretic Multiverse and Joint Embeddings

I am curious whether or not the following axiom is independent of Hamkins's axioms for the Set-Theoretic Multiverse. Hamkins's axioms can be found here on pages 1-2 and here on pages 24-26. Consider ...
5
votes
0answers
225 views

Cardinal characteristics without choice

(I'm taking my definition of a cardinal characteristic from Blass' excellent article http://www.math.lsa.umich.edu/~ablass/need.pdf, which cites Vojtas/Fremlin/Miller; theirs is more general, but I'm ...
6
votes
0answers
185 views

Is there a notion analogous to separability but requiring definable rather than countable sets?

Among models of $\lambda$-calculus, some like the Bohm tree model have the property that every element is a directed sup of definable elements, whereas others like the $D_\infty$ and $P(\omega)$ ...
10
votes
2answers
650 views

Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper?

This may be inappropriate for MO, but here goes: if I have understood the statement of the Erdős–Rado theorem correctly, then it contains as a special case the following result: if $\mu$ is ...
4
votes
2answers
229 views

Is it consistent that $\frak{d} < 2^{\aleph_0}$?

Let $\omega^\omega$ denote the set of all functions $f:\omega\to\omega$. We write $f <^* g$ if there is $N\in\omega$ such that $f(n) < g(n)$ for all $n>N$. A set $D\subseteq \omega^\omega$ is ...
12
votes
4answers
884 views

Sierpinski's construction of a non-measurable set

In the early 20th century there was a lot of fuss over the axiom of choice implying that there are Lebesgue non-measurable sets of reals. In his book about The Axiom of Choice, Gregory Moore points to ...
7
votes
1answer
535 views

Application of the Riemann hypothesis and the ABC conjecture to independence results

In Old Home Page of Andreas Weiermann Andreas Weiermann has stated the following: Quite recently I submitted a preprint about an application of the Riemann hypothesis and the ABC conjecture to ...
5
votes
2answers
227 views

When does Skolemization require the axiom of choice?

Skolemization is often used for eliminating existential quantifiers, which is often useful for proving theorems, especially in automated resolution theorem proving. Skolemization in first order ...
5
votes
1answer
251 views

Existence of internal toposes/inner models in a topos

It has been known for some time that one can define a topos as a model of a (finitary) essentially algebraic theory (or in other words, can be defined internal to any category with finite limits). In ...
28
votes
1answer
700 views

Producing finite objects by forcing!

It is a trivial fact that forcing can not produce finite sets of ground model objects. However there are situations, where we can use forcing to prove the existence of finite objects with some ...
11
votes
2answers
1k views

Existential statement without witness

Are there existential theorems of ZFC, or PA say, with no witnesses? Ie does there exist a formula $\phi$ such that ZFC $\vdash\exists x \phi(x)$, but for all numerals $\underline{n}$, ZFC $\nvdash ...
2
votes
0answers
63 views

A question on recursion and transfinite recursion in extensions of KP

Is the $\Sigma_{n}$-recursion supported by $\Sigma_{n}KP=KP+\Sigma_{n}$-separation + $\Sigma_{n}$-collection equivalent with $\Sigma_{n}$ transfinite recursion? If not, how do these notions differ?
4
votes
0answers
61 views

TCAs (total combinatory algebras) with oracles

Is there a natural, non-trivial example of a TCA (total combinatory algebra, cf. pca) with a natural notion of an oracle?
8
votes
3answers
617 views

Does a left basis imply a right basis, without AC?

If $_DV_D$ is a $D$-$D$-bimodule, and we have a $D$-basis for $V_D$, do we still need AC to get a $D$-basis for $_DV$? (The original question appears below. But this shorter question gets at the ...
3
votes
1answer
195 views

Decidability of Frankl's union-closed sets conjecture

Is it conceivable that Frankl's union closed sets conjecture is undecidable in $\mathsf{ZFC}$, or is this quite implausible, perhaps due to the "finitistic" nature of the statement, or for some other ...
5
votes
2answers
165 views

Formal languages with non-unique interpretations of terms

In mathematical logic and model theory, one considers interpretations of syntactic expressions: terms without free variables are interpreted as elements of some structure, formulas without free ...
0
votes
0answers
155 views

Wolfram's axiom completeness

I have been reading Wolfram's A New Kind of Science, and as I was reading the section on systems of logic and axioms, I came across this axiom, for which all of the normal axioms of Boolean logic can ...
3
votes
1answer
64 views

Is below every cohesive set a 1-generic?

A set $X$ is called cohesive for $(R_i)_{i\in \mathbb{N}}$ if it is infinite and for each $i$ we have $X\subseteq^* R_i$ or $X\subseteq^* \overline{R_i}$. (Where $X\subseteq^*Y$ means that $X$ is ...
7
votes
1answer
162 views

Base change in homotopy type theory

Recall that with the internal language of 1-toposes, we have the nice, basic, and useful result that geometric sequents are stable under base change along geometric morphisms: If $\varphi$ and $\psi$ ...
7
votes
2answers
331 views

When can we reach a real by forcing?

I'm sure this is well-known, but: suppose I have a non-constructible real $r\in V-L$. Under what conditions is there a poset $\mathbb{P}\in L$ and a $G$ which is $\mathbb{P}$-generic over $L$, such ...
3
votes
1answer
121 views

A question on recursion in Kripke-Platek set theory with infinity and $\Sigma_{3}$-separation and $\Sigma_3$-collection

$\Sigma_{3}KP\omega$ be Kripke-Platek set theory with infinity and $\Sigma_{3}$-separation and $\Sigma_3$-collection. What strengthening of Barwise's Definition by $\Sigma$ Recursion (Theorem 6.4 on ...
9
votes
1answer
257 views

Busy beaver function vs low Turing degrees

Let $BB(n)$ denote busy beaver function. It's well known that $BB(n)$ dominates all computable functions (I'm quite certain it includes partial computable functions too). However, I was wondering if ...
14
votes
1answer
583 views

Is it possible to define higher cardinal arithmetics

In number theory there are several operators like ‎addition, ‎multiplication and ‎exponentiation defined from ‎$‎‎‎\omega‎‎\times‎‎\omega‎$ ‎to ‎‎$‎‎‎\omega‎$. Each ‎of ‎them ‎is defined as an ...
4
votes
2answers
179 views

Relation between Turing degrees and functions computable with them

Suppose $A<_T B$ ($A$ is a set computable from $B$ but not vice versa). Is it always the case that there exists a $B$-computable function which eventually outgrows all $A$-computable functions? Of ...
11
votes
1answer
728 views

Von Neumann's consistency proof

In the paper Zur Hilbertschen Beweistheorie, John Von Neumann has proposed a consistency proof for a fragment of first-order arithmetic (the fragment without induction and with the successor axioms ...
9
votes
2answers
420 views

Can a parent and child node have the same type in a well-founded digraph tree?

$\newcommand\toward{\rightharpoonup}$It would help me to understand something in a current research project if someone could provide an example of directed graph $\langle G,\toward\rangle$ with the ...
-1
votes
2answers
411 views

Can an algorithm decide whether a program computes all strings? [closed]

I am interested in the type of program, which is given as input to a Universal Turing Machine (UTM) with language $L$, and for which it holds that every possible finite string $s$ of symbols in $L$ ...
1
vote
0answers
37 views

Non overlapping boxes with constraint modelling [closed]

I'm stucked with this problem for 2 days and i've finished the ideas. Any hint is appreciated. Given a set of squares (2x2, 3x3, 4x4, 5x5), and a rectangular grid (9x7) place the squares on the grid ...
4
votes
0answers
184 views

A question on the size of an admissible ordinal

Let $\mathbf{L}_{\varsigma}$ be the level of ordinal $\varsigma$ of Gödel's constructible universe $\mathbf{L}$. Let $\Sigma_{3}$-KP be Kripke-Platek set theory with infinity and ...
-5
votes
1answer
171 views

An axiomatic system with a set of constants that form a complete ordered field [closed]

I am developing a ZFC axiomatic system where together with the empty set, there is a singular (and huge) set of constants that are themselves sets and form a complete ordered field (cof) these ...
7
votes
2answers
256 views

Peano arithmetic vs. fast-growing hierarchy with pathological fundamental sequences

Fundamental sequence for a countable limit ordinal $\alpha$ is an increasing sequence $\{\alpha[i]\}$ of ordinals of length $\omega$ such that $\lim_{i\rightarrow\omega}\alpha[i]=\alpha$. There are ...