**4**

votes

**1**answer

215 views

### Perfect set property implies $\omega_1$ is a limit cardinal in $L$

Specker proved in 1957 that if in $V$ every set of real numbers has the perfect set property, than in $L$, $\omega_1^V$ is actually a limit cardinal.
The original proof is in German, and I've been ...

**2**

votes

**0**answers

102 views

### Does the Lévy collapse obey this nice characterization? [duplicate]

This question is related to an issue in my answer to Monroe Eskew's question on the failure of Cantor-Bernstein for the Lévy collapse.
Question. Is the Lévy collapse $\text{Coll}(\omega,\lt\kappa)$ ...

**6**

votes

**1**answer

169 views

### Failure of Cantor-Bernstein for the Levy Collapse

Related to this question, is it possible to give an example of the failure of Cantor-Bernstein for complete embeddings of forcing notions involving the Levy Collapse $Col(\omega,<\kappa)$? Suppose ...

**5**

votes

**1**answer

214 views

### A model of Krivine

In a paper by J.-L. Krivine, Modèles de ZF+AC dans lesquels tout ensemble de réels définissable en termes d'ordinaux est mesurable-Lebesgue [C. R. Acad. Sci. Paris Sér. A-B 269 (1969), A549–A552, ...

**5**

votes

**1**answer

154 views

### What do algebraic theories with strictly terminal trivial models look like?

By algebraic theory I mean one in the sense of Lawvere, i.e. a collection of finitary operations, including projections, together with a multi-composition satisfying the obvious axioms. (I believe ...

**7**

votes

**1**answer

474 views

### Starting Hilbert's Program on the other end

The idea of Hilbert's program was to start with a simple finitary logic and proof the consistency of more complex systems in this system. Of course, this turned out to be problematic. Even when ...

**4**

votes

**1**answer

109 views

### Replace Morley sequence over some set by one over a finite set, s.t. they both satiesfy a certain formula

Let $T$ be a stable $L$-theory with elimination of imaginaries. We work in the monster model $\mathfrak C$ of $T$. Let $A$ be a small (infinite) set of the monster, $\phi(x,y)$ be a $L(A)$-formula and ...

**7**

votes

**2**answers

454 views

### What is the name of this type of groups?

Suppose $A$ is a finite set and $\Sigma=A\cup A^{-1}$. Let $L\subseteq \Sigma^{\ast}$ be a regular language on the alphabet $\Sigma$. Is there a common name for the group $G$ presented as:
$$G=\langle ...

**4**

votes

**1**answer

186 views

### Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate.
Is the Van der Waerden's function itself elementary in the sense of Kalmar?

**2**

votes

**1**answer

239 views

### Expressive power of first-order category theory

Given the signature $\lbrace \mathsf{dom}, \mathsf{cod}, \mathsf{id},\circ \rbrace$ and the axioms of category theory – which are expressible in the signature's first-order (FO) language – ...

**2**

votes

**1**answer

118 views

### How many elementary equivalent models are unifiable by ultrapower?

Definition. A class $\mathcal{C}$ of pairwise elementary equivalent $\mathcal{L}$-structures is unifiable by ultrapower if there is an index set $I$ and an ultrafilter $F$ on it such that $\forall ...

**9**

votes

**4**answers

1k views

### Are there non-diagonal proofs for Cantor's continuum and Godel's incompletness theorems?

There is a formal definition for the notion of a formal proof.
Question 1. Is there any formal definition for the notion of a diagonal formal proof?
Consider the following theorems both proved by ...

**1**

vote

**0**answers

57 views

### First-order Peano Axioms and order-completeness of $\mathbb{N}$ [closed]

Definition: An ordered set is order-complete if any nonempty subset with an upper bound, has a lowest upper bound or supremo.
Notation: We denote the system of first-order Peano Axioms (along with ...

**9**

votes

**1**answer

184 views

### Obtaining a lightface pointclass from a boldface one

Define a pointclass to be:
boldface inductive-like if it is $\mathbb{R}$-parameterized, has the scale property, and is closed under $\wedge$, $\vee$, $\forall^\mathbb{R}$, $\exists^\mathbb{R}$, and ...

**9**

votes

**0**answers

160 views

### Reverse mathematics of meromorphic functions on Riemann surfaces

Various sources touch briefly on the reverse mathematics of measure theory and complex analysis. But I have found none on the uniformization theorem for Riemann surfaces or the existence of ...

**10**

votes

**3**answers

841 views

### Is it ever a good idea to use Keisler-Shelah to show elementary equivalence?

The most useful way I know to show that two structures are elementarily equivalent is Ehrenfeucht-Fraisse games. These are quite nice and intuitive, and even when I can't use them to solve my problem ...

**4**

votes

**1**answer

135 views

### Finite generation of vector identities

This question is partially motivated by Looking for a comprehensive referece for vector identities, although that question may not be appropriate for MO.
Consider the set $\mathcal{E}$ of all valid ...

**5**

votes

**1**answer

188 views

### A ZFC construction to get a proper extension which is a $\omega_1$-model

In $V$, let me call a set theory structure A is a $\omega_1$ model if the $\omega_1$ of $A$ is the same as the $\omega_1$ in $V$ (up to isomorphism). The question I would like to ask is the following: ...

**6**

votes

**1**answer

175 views

### Skolem Hulls in $H_{\omega_2}$

I put this on stack exchange over a week ago with no answer, so let's try here.
Consider a model of the form $\mathfrak{A} = (H_{\omega_2}, \in, \lhd, f_0, f_1, ...)$, some expansion of ...

**-2**

votes

**1**answer

182 views

### Natural constructions (not depending on parameters) [closed]

Consider graph clusterings as a prototypical example of (logical) constructions.
Let a clustering of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$.
I am looking for a ...

**8**

votes

**2**answers

231 views

### Vaught's conjecture for partial orders

In
``Steel, John R. On Vaught's conjecture. Cabal Seminar 76–77, pp. 193–208''
the following is proved:
Theorem. Let $\phi\in L_{\omega_1,\omega}.$ If every model of $\phi$ is a tree, then $\phi$ has ...

**9**

votes

**3**answers

328 views

### Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation:
coloring in lattice
Reference for Wang Tile
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
...

**2**

votes

**3**answers

335 views

### Can a Decidable Theory Have Non-recursive Models?

Tennenbaums' theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA.
...

**4**

votes

**2**answers

285 views

### Forcing for Arbitrary First Order Theories

Forcing is a relative model construction method for models of $ZF$ as a particular first order theory using models of another first order theory (forcing companion) that in this case is the theory of ...

**6**

votes

**2**answers

995 views

### Is Turing degree actually useful in real life? [closed]

In theoretical computer science, we classify problems according to their Turing degree. Is there any practical application of this?
Edit: Given that we cannot explicitly and mechanically understand ...

**5**

votes

**1**answer

139 views

### Intermediate submodels which do not satisfy AC

The following is known:
Theorem. Suppose $V[G]$ is a generic extension of $V$ by a set forcing, and let $N$ be a model of $ZFC$ with $V\subseteq N\subseteq V[G].$ Then $N$ is a generic extension of ...

**9**

votes

**4**answers

466 views

### Are there two computable binary trees such that each has a branch not computing any branch through the other?

It is a well-known elementary classical result in computability theory that there are computable infinite binary trees $T\subset 2^{<\omega}$ having no computable infinite branch. (One can build ...

**6**

votes

**0**answers

166 views

### When is a reduction not a reduction?

Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of ...

**4**

votes

**1**answer

200 views

### Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...

**3**

votes

**3**answers

289 views

### Godel's Second Incompleteness theorem and Models

As I understand it, Godel's completeness theorem essentially says that if a sentence $\phi$ can be proven in a first order theory $\Gamma$, then $\phi$ is satisfied in all models $\mathcal{U}$ of ...

**2**

votes

**0**answers

167 views

### How many Dedekind-finite sets can $\mathbb{R}$ be partitioned into?

Building off Asaf Karagila's answer to my previous question (Can $\mathbb{R}$ be partitioned into dedekind-finite sets?) on partitioning $\mathbb{R}$ into strictly Dedekind-finite sets:
(1) What ...

**-1**

votes

**1**answer

153 views

### Algebra generated by a tree [Edit] [closed]

Suppose that $(T,\leq)$ is a partially ordered set, we say $T$ is a tree* if for every $i\in T$, $\{s: s\in T, s\leq t\}$ is a well-founded chain.
What I need to know is: Can the algebra ...

**11**

votes

**4**answers

835 views

### Weak forms of the Axiom of Choice

Let $n\geq 2$ be a natural number and consider the following:
$AC(n)$: For each family $\{X_i\}_{i \in I}$ of $n$-element sets the product $\prod_{i\in I}X_i$ is non-empty.
Is it known that for ...

**8**

votes

**1**answer

239 views

### Can $\mathbb{R}$ be partitioned into dedekind-finite sets?

Assuming $ZF$ itself is consistent, it is consistent that there are sets $D$ which are infinite but cannot be placed in bijection with any of their proper subsets; such sets are called "strictly ...

**4**

votes

**1**answer

184 views

### Climbing quickly up $L$

This question is motivated by Joel David Hamkins' answer to Godel's Constructible Universe in Infinitary Logics (A Possible Approach to HOD Problem), in which he shows that, if we replace ...

**15**

votes

**1**answer

862 views

### Gödel's Constructible Universe in Infinitary Logics (A Possible Approach to HOD Problem)

Gödel's constructible universe ($L$) is defined using definable power set operator in first order logic ($\mathcal{L}_{\omega ,\omega}$). One can produce such a universe in infinitary logics in ...

**1**

vote

**1**answer

328 views

### Transfinite induction vs induction in mathematics

What are the nontrivial theorems one can prove about natural numbers which need transfinite induction? By "need transfinite induction" I mean one can show that the statement is not provable in ...

**8**

votes

**0**answers

237 views

### From Frege to Gödel - German equivalent?

I know this question does not quite fit here, but I felt it could best be answered here. I recently stumbled upon the book From Frege to Gödel, which is a sourcebook containing some of the most ...

**4**

votes

**2**answers

368 views

### Reverse Math of High Sets?

Is there a standard principle in reverse math that is known to be equivalent (over $RCA_0$) to the existence of a set of high (Turing) degree? I'm interested in the general case, but would be happy to ...

**2**

votes

**0**answers

89 views

### Comparing two non-deterministic Turing equivalents as basis for Logic, request for references

I am designing a logic, that is simpler than FOL + PA. And I like to know if there already exists something in this direction.
First of all a non-deterministic Turing equivalent is defined by ...

**6**

votes

**0**answers

164 views

### “Fraïssé limits” without amalgamation

All structures are countable with countable signature.
Given a structure $\mathcal{A}$, the age of $\mathcal{A}$, $Age(\mathcal{A})$, is the set of structures isomorphic to finitely-generated ...

**1**

vote

**1**answer

113 views

### A question about consistent fragments of formalized mathematical theories with Natural Deduction

Ref to : Sara Negri & Jan von Plato, Structural Proof Theory (2001).
In Ch.6 : Structural Proof Analysis of Axiomatic Theories [page 126-on], they
give a method of adding axioms to sequent ...

**16**

votes

**3**answers

720 views

### Function extensionality: does it make a difference? why would one keep it out of the axioms?

Yesterday I was shocked to discover that function extensionality (the statement that if two functions $f$ and $g$ on the same domain satisfy $f\left(x\right) = g\left(x\right)$ for all $x$ in the ...

**7**

votes

**1**answer

238 views

### Fields of characteristic zero via ultraproducts

Is every noncountable field of characteristic zero the ultraproduct (using a non principal ultrafilter over the set of prime numbers) of fields of positive characteristic?

**1**

vote

**2**answers

126 views

### Quantifying simplicity, in the case of trigonometric and exponential functions

The pair of identities the sine and cosine of a sum of two terms as functions of the sines and cosines of the terms separately is not as simple as the identity that expresses the exponential of a sum ...

**4**

votes

**0**answers

133 views

### The theory of two finite linear orders

My colleague Matthias Baaz is looking for a reference for the following question (or possibly theorem):
Let T be the "theory of pairs of finite linear orders". That is, consider all finite ...

**8**

votes

**3**answers

296 views

### Who proved “sets in every generic are already in the ground model?”

Suppose $\mathbb{P}$ is a notion of forcing in the ground model $V$, and $X$ is a set which is in $V[G]$ for every $\mathbb{P}$-generic filter $G$. Then $X\in V$ already, by a fairly simple (if ...

**6**

votes

**1**answer

222 views

### Robinson Arithmetic and Composite Numbers

Define a number $n$ to be composite if it can be written as $a\cdot b$ for some $a,b$ where $a,b\neq 1$.
Define $p$ to be prime if $p=a\cdot b$ implies $a=1$ or $b=1$.
The theorem that every ...

**4**

votes

**0**answers

85 views

### Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$

Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in ...

**1**

vote

**2**answers

328 views

### Bishop's paradox of the countability of sequences

In 'Foundations of Constructive Analysis', in the notes at the end of the first chapter, Bishop poses an apparent paradox as an exercise for the reader:
Since every sequence of rational numbers ...