# Tagged Questions

**2**

votes

**2**answers

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

**-1**

votes

**0**answers

87 views

### Deriving $\Box p \rightarrow \Box \Box p$ if we have $\Box(\Box p \rightarrow p) \rightarrow \Box p$ [on hold]

Let $F = (W,R)$ - Kripke frame, $AL \rightleftharpoons \Box(\Box p \rightarrow p) \rightarrow \Box p $
Proof if $F \vdash AL$ then $R$ if transitive

**5**

votes

**1**answer

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

**27**

votes

**1**answer

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

**10**

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

54 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

**0**answers

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

**3**answers

507 views

+100

### 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

**1**answer

178 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

**2**answers

152 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

141 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

**1**answer

52 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

**1**answer

145 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

315 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

115 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

235 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

554 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

167 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

**1**answer

706 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

**2**answers

406 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

402 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

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

**0**answers

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

**1**answer

166 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

235 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

414 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

224 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

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

**3**answers

334 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

**3**answers

716 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

177 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

995 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

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

**1**answer

203 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

**2**answers

745 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

237 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

**1**answer

579 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

369 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

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

**0**answers

157 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

171 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

**1**answer

265 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

213 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

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

**14**

votes

**1**answer

381 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

421 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

102 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

1k 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

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

**5**

votes

**1**answer

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