# Tagged Questions

**29**

votes

**1**answer

738 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

**2**answers

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

**0**answers

66 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?

**5**

votes

**0**answers

63 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

**3**answers

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

**4**

votes

**1**answer

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

**6**

votes

**2**answers

177 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

**0**answers

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

**4**

votes

**1**answer

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

**8**

votes

**1**answer

181 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

**2**answers

339 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

**1**answer

124 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

**1**answer

274 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

**1**answer

674 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

**2**answers

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

**12**

votes

**1**answer

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

**10**

votes

**2**answers

444 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

**2**answers

420 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

**0**answers

42 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

**0**answers

187 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

**1**answer

180 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

**2**answers

293 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

**1**answer

478 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

**1**answer

232 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

**1**answer

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

**6**

votes

**3**answers

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

**11**

votes

**3**answers

756 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

**1**answer

201 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

**3**answers

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

**2**answers

291 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

**1**answer

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

**10**

votes

**2**answers

836 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

**2**answers

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

**6**

votes

**1**answer

617 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

**1**answer

385 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

**0**answers

255 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

**0**answers

172 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

**1**answer

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

**8**

votes

**1**answer

275 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

**0**answers

222 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

**3**answers

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

**15**

votes

**1**answer

433 views

### Is the regularity of finitely generated rings decidable?

Q: Is there an algorithm to decide whether a given finitely generated (over $\mathbb{Z}$) commutative ring is regular?
I mean by regular that the localization at every prime ideal is a regular local ...

**10**

votes

**2**answers

439 views

### Is every order type of a PA model the \omega of some ZFC model?

Let $N$ be a model of first-order Peano arithmetic, and let $\sigma$ be its order-type. Does it follow that there is a (non-transitive, expect when $M$ is the standard model) $ZFC$-model $M$ such that ...

**2**

votes

**2**answers

104 views

### proof that “small” sets in an extension by iterated forcing already appear in an earlier stage

In Kunen's book (introduction to independence proofs, ) the following lemma is proved (chapter 8, lemma 5.14):
Assume that in M, $\alpha$ is a limit ordinal,
$( ( \mathbb{P}_\xi : \xi \leq \alpha) , ...

**13**

votes

**4**answers

2k views

### Is it possible to formulate the axiom of choice as the existence of a survival strategy?

Consider the following situation:
There is an infinite set $G$ of giraffes.
A lion comes and announces a set $C$ of all possible colours and an infinite cardinal $\kappa$.
The hungry lion ...

**3**

votes

**1**answer

203 views

### How to change the successor of a singular with a Woodin?

I'm looking for references on how to change the successor of a singular cardinal from "more or less" minimal assumptions. If possible, then without adding bounded subsets to the singular either.
In ...

**6**

votes

**1**answer

188 views

### Consistency of Weak Diamond with a Weak Version of Martin's Axiom

If $S \subset \omega_1$ is stationary, then the weak diamond principle $\Phi(S)$ states that for any $F: 2^{<\omega_1} \to 2$, there is a $g: \omega_1 \to 2$ such that for all $f: \omega_1 \to 2$, ...

**5**

votes

**1**answer

369 views

### Forcing is intuitionistic

The main idea of why it´s necessary a generic filter $G$ to extend a countable transitive $\epsilon$-interpretation (not necessarily a model) $M$ is given by the condition (for which $G$ being a ...

**-1**

votes

**3**answers

186 views

### About “absolute proof” of Arithmetic consistency [closed]

Ok so as Godel's theorems states, you cant prove that Peano arithmetic is consistent by using only the axioms within Peano model. You need to use axioms or rules of inferations beyond the model you ...

**10**

votes

**4**answers

515 views

### Boolean Valued Models of PA

O.K, a massively naive question. I've never really studied any non-standard models of PA before. I was just wondering if there's ever been any attempt to use the kind of Boolean valued model theory ...