# Tagged Questions

**1**

vote

**0**answers

25 views

### embdedding standard models of PA into nonstandard models [migrated]

Maybe it's well known to experts, but is there always an embedding $f$ of the standard model of Peano arithmetic into a nonstandard model? By Peano arithmetic I mean its first-order version, with the ...

**-2**

votes

**0**answers

174 views

### Proof theory and the generalized Riemann hypothesis [on hold]

Is there a disproof of the following?
CONJECTURE: Let $\chi$ be a Dirichlet character modulo $q$. Let $\varepsilon$ be a positive number with $0 < \varepsilon < \frac{1}{2}$. Let $T$ be a ...

**10**

votes

**1**answer

507 views

### Applications of set theory in physics

In the introduction of the paper "Links between physics and set theory", the following quote of Eris Chric is stated:
...

**3**

votes

**0**answers

106 views

### A property of the Frechet filter and every ultrafilter

(Joint question with Piotr Szewczak.)
Definitions and notation. By filter we mean a filter on $\omega$ containing the cofinite sets at least.
For a filter $\mathcal{F}$, let ...

**1**

vote

**1**answer

52 views

### Injecting premises into two implicational premises connected by a tensor (multiplicative conjunction) in linear logic

I have another question regarding linear logic: I want to get to the proof E, using the premises in (1-4). Is this at all possible?
1: $A$
2: $C$
3: $(A\multimap B)\otimes(C\multimap D)$
4: ...

**2**

votes

**0**answers

116 views

### Relationship between coherent toposes/coherent logic and coherent sheaves

I've heard it claimed that the adjective "coherent" in logic/topos theory (i.e. coherent logic, coherent toposes, coherent categories) was adopted to fit in with the terminology of coherent sheaves in ...

**2**

votes

**1**answer

163 views

### Mal'cev “rational equivalence” and model theory

In Universal Algebra, it is possible to say that two presentations denote the "same" kind of algebraic structures, if the two corresponding varieties are "rationally equivalent" (Mal'cev 1958).
In ...

**-3**

votes

**0**answers

108 views

### Interview Math question [closed]

Fill in the blank: Find the next number of the sequence: 16,47,64,81,121,?
This is an interview math question of finding the proper number, I can't figure it out, could someone help?

**4**

votes

**1**answer

262 views

### Does PA+Con(PA) entail the existence of non-standard models of PA?

Does $\textsf{PA}$+Con($\textsf{PA}$) entail the existence of non-standard models of $\textsf{PA}$?
Is there a reasonable way in which to code, inside $\textsf{PA}$, the statement that $\textsf{PA}$ ...

**4**

votes

**1**answer

138 views

### Generalizing a result of Kreisel on $\omega$-consistency

In (reference)The following result is attributed to Kreisel:
Lemma1(Kreisel) If $T$ is an $\omega$-consistent theory in the language of arithmetic and $\pi$ is a true $\Pi_1$ sentence, then $T+\pi$ ...

**13**

votes

**4**answers

1k views

### Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$?

In a conversation where it came up that the Pythagoreans probably found an enumeration of the rational numbers I erroneously remarked that Georg Cantor found a natural bijection from $\mathbb{N}$ to ...

**2**

votes

**2**answers

115 views

### Is there a good list of nomenclature for modal axioms?

I would like to see what names that has been suggested for useful modal axioms. By name here I mean some abbreviation such as $T$, $K$, $4$, $.2$, $E$ and so on. In particular I am interested in ...

**8**

votes

**2**answers

280 views

### For a partition of $\mathbb{R}$ into countably infinite sets, must there be an almost-disjoint family of $2^{\frak c}$ many selectors?

My question arises from a construction I gave in my recent
answer to a question of Alexander Pruss concerning large families of independent non-measurable sets of reals. In that argument, using
the ...

**0**

votes

**0**answers

57 views

### How create counterexample for some set in Complexity Theory? [closed]

We know from Martin Davis's book, $K$ is a Halting Set Problem as $K=\{e \mid e \in W_e\}$. $W_e$ is the set of inputs for which the program encoded by $e$ halts.
I read in the book that written ...

**1**

vote

**0**answers

105 views

### This modal logic semantics is not S5, but is it something else well-known?

The short form of the question is this:
Is there a model of modal propositional calculus that gives the modal operators the meanings
...

**2**

votes

**1**answer

80 views

### Representable cylindric algebras and correspondence with first-order models

The class $\textsf{Cs}_{\omega}^{reg}\cap \textsf{Lf}_{\omega}$ of locally finite and regular cylindric set algebras (of dimension $\omega$) can be seen as the algebraic counterpart of first-order ...

**7**

votes

**0**answers

126 views

### Decidabilty of the Hilbert lattice and quantum logic

What is known about the decidability of (first-order formulas in) the structure $(\mathcal{L}(H),\leq)$, where $\mathcal{L}(H)$ is the collection of all closed linear subspaces of a (separable) ...

**8**

votes

**1**answer

319 views

### If $\kappa$ is weakly inaccessible and $A\subset\kappa$, can $L[A]$ violate $\kappa^{\lt\kappa}=\kappa$?

In some current work, my co-authors and I had wanted in a certain
argument to appeal to $\kappa^{\lt\kappa}=\kappa$ in $L[A]$, in a
situation where $A\subset\kappa$ and $\kappa$ was weakly
...

**4**

votes

**1**answer

303 views

### Inaccessible cardinal and $\Sigma_1$ reflection

A theorem of A. Levy says that, if $\kappa$ is an inaccessible cardinal, then $V_\kappa\prec_{\Sigma_1}V$ namely $V_\kappa$ is an elementary submodel when considering only $\Sigma_1$ formulas.
Where ...

**3**

votes

**1**answer

185 views

### Hamkins infinite time Turing machines: dovetailing ordinal time

It is claimed in the Hamkins and Lewis founding article "Infinite time Turing machines" (proof of the gap existence theorem 3.4) that for $\omega$ steps of a computation of a machine performing a ...

**2**

votes

**0**answers

271 views

### A query on how to climb inaccessibles in £

I am investigating to what extent extensions of the librationist property or set theory £ may support relative inaccessible sets; see Librationist Closures of the Paradoxes and Elements of ...

**1**

vote

**0**answers

111 views

### Kripke frames as classes of partitions

Here's something I've been playing with off and on for a bit; I'm curious if anyone has seen it before.
For this question, a Kripke frame $K$ is a finite reflexive directed graph. (Reflexivity isn't ...

**14**

votes

**2**answers

491 views

### Scott-Solovay unpublished paper on ``Boolean valued models of set theory''

I have read some papers from 1970$^{th}$, and in some of them, the paper of Scott and Solovay on ``Boolean valued models of set theory'' is given as a main reference, with many references to the ...

**3**

votes

**3**answers

820 views

### Reverse Skolem's paradox

By using the Löwenheim–Skolem theorem & Mostowski collapse, in every model $V$ of $ZF+Con(ZF)$ there is a countable transitive set $M$ such that $(M,\in_M) \models ZF$. Is the following "converse" ...

**7**

votes

**3**answers

326 views

### Decision problem on triviality of intersection of two subgroups

What is known about the following decision problem?
Given two finite sets in a finitely generated group G,
decide whether the subgroups generated by them have trivial intersection.
Is this problem ...

**9**

votes

**1**answer

322 views

### History of Tarski's problems on free groups

As is known, Tarski posed his questions about first-order theories of non-abelian free groups around 1945. However, the questions were not published in his papers or books.
What is the original ...

**8**

votes

**3**answers

273 views

### Model-theoretic accounts of feasibility in bounded arithmetic and related systems

Various weak theories of arithmetic have been partially motivated by a concern with numbers (or functions/proofs) that are feasible. This concern is sometimes connected to an interest in strictly ...

**12**

votes

**6**answers

734 views

### Application of Fraïssé construction in set theory

As you know Fraïssé limit construction and its generalization, Hrushovski's construction, have many applications in model theory to build models with interesting property.
Now I would like to know ...

**6**

votes

**3**answers

472 views

### Category of Gödel Codings? [Reference Request]

Consider computation with the integers $\mathbb{Q}$. The traditional theory of recursive functions on $\mathbb{N}$ applies to $\mathbb{Q}$ by the identification of $\frac{a}{b} \in \mathbb{Q}$ with ...

**5**

votes

**0**answers

230 views

### Quasi-disjoint subsets of an infinite set and $\neg \mathsf{AC}$

Is it consistent with $\mathsf{ZF}$ (without $\mathsf{AC}$) that there is an infinite set $X$ and a subset $S\subseteq\mathcal P(X)$ of the same cardinality as $\mathcal P(X)$ with the property that ...

**12**

votes

**2**answers

1k views

### Do the real numbers “know” that they are countable in a larger model?

(This was first posted to math.stackexchange but had no answers there after several days):
Let ${\mathbb R}$ be the set of real numbers in whatever is your favorite model of $ZFC$. Then (by Levy ...

**2**

votes

**0**answers

61 views

### Potentiality classes and Borel reductions

In a 1998 paper by Hjorth, Kechris, and Louveau, there was a definition given of a "potentiality class." That is, given an invariant equivalence relation $E$ on a standard Borel space $X$, we say $E$ ...

**5**

votes

**1**answer

163 views

### Uncountably categorical theories which are interpretable in a strongly minimal

Definition: Let $\lambda$ be a cardinal. An $\mathcal{L}$-theory $T$ is called $\lambda$-categorical whenever every two models of $T$ of cardinality $\lambda$ are isomorphic.
Definition: An ...

**6**

votes

**1**answer

428 views

### Adding sets not containing arithmetic progressions of length three by forcing

Consider the following forcing notion: conditions in $\mathbb{P}$ are pairs $(s, N),$ where:
1) $s\in 2^{<\omega}$,
2) $N\in \mathbb{N}$,
3) (by identifying $s$ with a subset of $lh(s)$) $s$ ...

**6**

votes

**0**answers

177 views

### Tree property and singular strong limit cardinals

I heard that the following theorem is proved recently by Foreman-Magidor, which answers a famous old open question:
Theorem. It is consistent, relative to the existence of large cardinals, that ...

**9**

votes

**2**answers

451 views

### Non-Forcing and Independence

I asked this question about two weeks ago on MSE and haven't gotten an answer, so I thought I would post the question here.
Do there exists sentences which are independent of ZFC, cannot be shown to ...

**0**

votes

**1**answer

92 views

### Completeness of a set of propositional formulas [closed]

A set $\sum$ of formulas in propositional logic is complete if for each propositional formula $\phi$ either $\sum \vdash \phi$ or $\sum \vdash \neg \phi$. Clearly every inconsistent set of formulas ...

**11**

votes

**1**answer

312 views

### Is factorial definable using a $\Delta_0$ formula?

The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula.
Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)?
If not, why?

**1**

vote

**1**answer

226 views

### Confusion with proof about a fact $\mathbb{P}$-name [closed]

Let $\mathbb{P}$ be poset.
Let $B$ be a set. We say that a $\mathbb{P}$-name $\dot{b}$ is a nice name for member of $B$ if there is a maximal antichain $A\subseteq\mathbb{P}$ and a function ...

**6**

votes

**1**answer

112 views

### Chains of forking extension in stable theories

Let $T$ be an stable theory.
Further we work in the monster model of $T^{eq}$.
We say that a chain of types of the form
$$tp(a_1/A_1)\subset tp(a_2/A_2) ... \subset tp(a_n/A_n)$$
is a forking chain ...

**3**

votes

**1**answer

138 views

### A question on many-one reducibility

Let $\phi_0,\phi_1,\phi_2,\ldots$ be an acceptable programming system. For each $x\in\mathbb{N}$, let $W_x$ the domain of $\phi_x$, and let $K=\{x\in\mathbb{N}:W_x\neq\emptyset\}$. Is there a ...

**6**

votes

**1**answer

372 views

### Alternate proof of Morley's theorem?

I'm trying to understand the result given in the first box at slide 45 of this talk. Specifically:
1) What is the source cited? I have not been able to find any article by Keisler, Chudnovsky and/or ...

**5**

votes

**2**answers

323 views

+50

### Primitive Recursive Arithmetic via Universal Algebra

From the wikipedia article on Primitive Recursive Arithmetic (see http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic):
"Primitive recursive arithmetic, or PRA, is a quantifier-free ...

**7**

votes

**1**answer

220 views

### Is $ACA_0$ + `True Arithmetic exists' interpretable in $ACA$?

Maybe someone here can help me with a question concerning second-order arithmetic. Consider the system $ACA_T := ACA_0 + \exists X \forall x (x \in X \leftrightarrow T(x))$, where $T(x)$ is a ...

**6**

votes

**1**answer

275 views

### Axiom of choice and the equality between second-order constructible universe and HOD

I try to prove $L_{SO}=\mathrm{HOD}$, where $L_{SO}$ is second-order constructible universe which has similar definition with $L$ but it uses second-order definability rather than the first-order ...

**4**

votes

**1**answer

188 views

### Explicit bounds for transfer results in algebraic geometry

Assume you have an ideal $I\subseteq\mathbb{Z}[X_1,\ldots,X_n]$ of the polynomial ring in $n$ variables over the integers. For any field $\Bbbk$, I can consider the ideal ...

**3**

votes

**1**answer

216 views

### Was $\Sigma x$ used as quantifier?

Kurt Gödel in 1931 used $x\Pi a$ where we in contemporary notation would use $(\forall x) A$ or $(x)A$, and $Ex a$ where we would use $(\exists x) A$. I believe that I remember that $\Sigma xA$ has ...

**0**

votes

**0**answers

117 views

### Reference Request: Category of explicit maps between primitive recursive sets?

[Edited]
Let $\mathsf{PR}$ be the category defined as follows:
Choose a specific presentation of Primitive Recursive Arithmetic, that is, with a specific set of terms for primitive recursive ...

**4**

votes

**1**answer

132 views

### presaturated ideals

In this paper, Gitik and Shelah make the following claim (part of Proposition 1.5):
Claim (Gitik-Shelah): Suppose $\kappa < \lambda$ are regular, $2^\lambda = \lambda^+$, and $D$ is a normal ...

**1**

vote

**0**answers

155 views

### Property theories

Property theory is, as I have understood it, first of all characterized by an attempt to approach naive comprehension type-freely and without committing to extensionality.
There is e.g. the work of ...