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)

4
votes
0answers
106 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
154 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)$ ...
9
votes
2answers
603 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 ...
2
votes
2answers
192 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 ...
9
votes
4answers
786 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 ...
-2
votes
0answers
61 views

Are the following interpretations elementarily equivalent? [closed]

Are the following interpretations elementarily equivalent? $$ < \mathbb N, \le > \text{ and }<\mathbb N + \mathbb Z, \le> $$ If so, prove it. Else make a formula that distinguishes them. ...
7
votes
0answers
364 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 ...
4
votes
2answers
198 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
196 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
661 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
58 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
60 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
569 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
180 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
155 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
146 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
55 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
148 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
318 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
116 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
239 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
563 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
173 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
710 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
410 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
405 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
36 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
167 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
236 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 ...
12
votes
1answer
420 views

Is there a nonstandard model of arithmetic having precisely one inductive truth predicate?

$\newcommand\Tr{\text{Tr}}$My question is whether there can be a nonstandard model of PA having a unique inductive truth predicate. Background. If $\mathcal{N}=\langle N,+,\cdot,0,1,<\rangle$ is ...
0
votes
1answer
226 views

How to formalize “Is there a proof for every instance of the halting problem?”? [closed]

In a previous question that I asked here it turned out that for every instance of the halting problem, being the matter whether a certain computer program halts or runs forever, there exists a ...
0
votes
1answer
197 views

Is there a consistent theory for each instance of the halting problem?

I got a bit confused by a discussion about the provability of the Goldbach conjecture and the seemingly different opinions about this subject. Since I understand computer science better, I will ask my ...
5
votes
3answers
336 views

Extensionality in HoTT versus extensionality in internal language of a category

What's the extension of judgmental identity in HoTT (homotopy type theory)? The Martin-Löf intensional dependent type theory with identity types is called (definitionally) extensional if the ...
10
votes
3answers
722 views

Natural examples of Reverse Mathematics outside classical analysis?

Harvey Friedman at the 1974 ICM motivated Reverse Mathematics by the following statement: When the theorem is proved from the right axioms, the axioms can be proved from the theorem. Reverse ...
1
vote
1answer
179 views

Self-similarity for simple algebraic structures [closed]

I'm doing this thread because I have some ideas about how to define self-similarity in algebra, but I don't know if this is known at all. Any critics, comments and references are more than welcomed. ...
11
votes
3answers
1k views

Difference between ZFC and ZF+GCH

I hear that the axiom of choice (AC) derives from The generalized continuum hypothesis(GCH). And also hear that both AC and GCH are independent of Zermelo–Fraenkel set theory(ZF). So, I'm just ...
3
votes
2answers
283 views

A Question related to the Formula Hierarchy

Let large Latin symbols as $X$ and $Y$ denote sets of natural numbers and small symbols as $n$ and $n´$ denote natural numbers and small Greek letters stand for formulas. Suppose $\alpha$ is ...
1
vote
1answer
204 views

Concept of synchronizability

This thread is about the concept of synchronizability. It's a concept I tried to formalize in its most general sense but without success. The goal of this thread is therefore to try to formalize it in ...
9
votes
2answers
747 views

Decidability of decidability

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still ...
2
votes
2answers
238 views

System of boolean equations, Satisfiability

Are there any methods to "solve" large systems of boolean equations? $$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$ For example $$x_{1}\vee ...
7
votes
1answer
582 views

Does Nelson try to prove PA inconsistent directly?

Edward Nelson is known for his serious attempts to show that Peano axioms, and sometimes even weaker theories, are inconsistent. I wasn't able to find Nelson's papers anywhere, so I wanted to ask a ...
10
votes
1answer
371 views

Is there an $L$ like inner model for $\sf Z$?

Godel proved the consistency of the axiom of choice with the axioms of $\sf ZF$ by showing that given any model of $\sf ZF$, there is a definable class which satisfies $\sf ZFC$. The proof uses a lot ...
9
votes
0answers
252 views

Reinhardt cardinals and iterability

Work in $ZF$. Let $j:V\to V$ be a non-trivial elementary embedding which is iterable, so that we can iterate it and form models $M_\alpha, \alpha\in ON,$ with $M_0=V,$ and elementary embeddings ...
7
votes
0answers
160 views

Countable choice in $L(\mathbb{R}^*_G)$

Let $\lambda$ be a singular strong limit cardinal and let $G \subset \text{Col}(\omega,\mathord{<}\lambda)$ be a $V$-generic filter. Let $\mathbb{R}^*_G = \bigcup_{\alpha < \lambda} ...
6
votes
1answer
172 views

O-minimal Theories with Non-Dense Order Type

I asked this question on MSE, but I haven't received any comments or responses (also, it has a very low view count), so I thought I would also ask it here. In this paper, Knight, Pillay, and ...
7
votes
1answer
267 views

On $V$-decisive and weakly homogeneous forcings

Suppose that $\Bbb P$ is a forcing in $V$, we say that $\Bbb P$ is $V$-decisive if whenever $\varphi(x_1,\ldots,x_n)$ is a statement in the language of forcing, and $u_1,\ldots,u_n\in V$ then $1_{\Bbb ...
6
votes
0answers
216 views

Canonical functions in set theory and their applications

Given regular cardinal $\kappa>\omega,$ we can define the canonical functions $f_\alpha: \kappa\to \kappa,$ for $\alpha<\kappa^+.$ Some of their properties are presented in Chapter 22 of the ...
10
votes
3answers
456 views

The continuum hypothesis for packing shapes without overlapping

Consider the finite cross $C$ (=union of line segments $\overline{(0, -1)(0, 1)}$ and $\overline{(-1, 0)(1, 0)}$) and the unit half-circle $H$. It is easy to see that we may pack continuum-many ...