2
votes
0answers
62 views

Countable model theory for $\omega$-stable theories?

This is a bit of a fishing expedition, because I'm not sure what I'm looking for. Very vaguely stated, here's the driving question: What conditions on an $\omega$-stable theory make the class of ...
10
votes
1answer
373 views

Harrington's unpublished note “The constructible reals can be anything”

Around 1974, Leo Harringto wrote an unpublished note entitled "The constructible reals can be anything", in which he proved that it is consistent that being $\Delta^1_n$ is the same as being ...
4
votes
1answer
572 views

solvable word problem without algorithm

Let $G$ be a finitely generated group. I wonder if there are examples where: 1) The word problem is known to be solvable in $G$ but there is no algorithm known. 2) The word problem is known to be ...
10
votes
1answer
292 views

Elements of the method of forcing in some papers of N. N. Luzin

In the paper Eléments de la méthode de forcing dans quelques travaux de N. N. Lousin. (French) [Elements of the method of forcing in some papers of N. N. Luzin] Amphora, 469–479, Birkhäuser, ...
1
vote
0answers
68 views

Interesting fragments of first-order logic induced by sorting?

In first approximation, modal logic (I'm using the term loosely) can be understood as an interesting fragment of first-order logic (for simplicity I ignore e.g. how modal logic relates to ...
0
votes
0answers
89 views

topological space of Wang Tile

When trying to reprove a theorem in Wang tile: An established proof in Wang Tile which I doubt , a few notions are provided which I would like to seek for more information: For a given set of blocks ...
3
votes
3answers
730 views

An established proof in Wang Tile which I doubt

When I was reading the paper: Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305. from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf I could not ...
2
votes
1answer
209 views

Absolutness of $\Pi_1^1$ statements

Shoenfield absoluteness is well known for $\Pi_2^1$-statements, but it does not hold between a countable transitive model of ZFC and the universe. But it is also known that $\Pi_1^1$ statements are ...
12
votes
3answers
428 views

Formal/rigorous treatment of (im)predicativity/predicativism

There are several places on the web where one may find quite intuitively understandable accounts of (im)predicativity; here on MO I found two questions with very good detailed answers (Predicative ...
5
votes
0answers
337 views

Last Status of Feferman's Conjecture on Indefinite Value of Continuum

The "true" value of $2^{\aleph_0}$ is one of the most fundamental open questions of mathematics and its philosophy. Hundreds of set theoretic results during the last century don't say anything more ...
2
votes
0answers
101 views

Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...
14
votes
6answers
2k views

What “forces” us to accept large cardinal axioms?

Large cardinal axioms are not provable using usual mathematical tools (developed in $\text{ZFC}$). Their non-existence is consistent with axioms of usual mathematics. It is provable that some of ...
10
votes
2answers
533 views

Questions about Prikry forcing and Cohen forcing

I have some questions. The first one is about the product of Prikry's forcing. Let $\kappa$ be a measurable cardinal, $U_1, U_2$ be normal measures on $\kappa$ and let $\mathbb{P}_{U_1}, ...
3
votes
1answer
146 views

Proof of existence of recursively inaccessible and Mahlo ordinals

As in title - I'm looking for a proof of the existence of a countable recursively inaccessible or recursively Mahlo ordinals, especially the first one. When looking for it in all the papers I stumbled ...
10
votes
1answer
331 views

Applications of SCH outside of set theory

Recall that the Singular Cardinals Hypothesis (SCH) says that if $\kappa$ is a singular cardinal and $2^{cf(\kappa)}<\kappa,$ then $\kappa^{cf(\kappa)}=\kappa^+.$ Clearly it has many applications ...
4
votes
3answers
357 views

Systematic brute-force searches for counterexamples

This is getting nowhere on math.stackexchange.com, so I'm putting it here. Gödel's completeness theorem says that for every statement in first-order predicate calculus with equality, there is either ...
6
votes
1answer
231 views

Does the totality of Ackermann's function prove the consistency of $\Sigma_1$-induction?

It is well known that Ackermann's function is not primitive recursive. Therefore, the theories of primitive recursive arithmetic (PRA) and of $\Sigma_1$-induction ($I\Sigma_1$) cannot prove the ...
4
votes
0answers
92 views

Relation between fundamental theorem of Ehrenfeucht-Fraisse games and notions of bisimulation and simulation

Vijay D alluded to the relation between the fundamental theorem of Ehrenfeucht-Fraisse games and notions of bisimulation and simulation in response to the whats-a-magical-theorem-in-logic question. ...
10
votes
0answers
140 views

Maximality of linear orders in the Keisler order on theories

Recently Malliaris and Shelah (see their preprint http://math.uchicago.edu/~mem/Malliaris-Shelah-CST.pdf) have shown that theories with $SOP_2$ are maximal in the Keisler order. A preceding result of ...
5
votes
1answer
114 views

Attribution of an equivalence of the existence of omega-models of RCA0

There are many well-known equivalences in reverse mathematics between statements of the form "Every set is contained a countable coded $\omega$-model of $T$" and $S$, where $S, T$ are subsystems of ...
8
votes
3answers
569 views

Consistency of Analysis (second order arithmetic)

Is there a proof of the consistency of Analysis (second order arithmetic), which is similar to Gentzen's proof of the consistency of arithmetic? Update: Which (different) methods can be used to ...
3
votes
1answer
214 views

Colorful model theory

There are a number of concepts in model theory - often situated around Hrushovski's amalgamation method (see for instance http://math.univ-lyon1.fr/~wagner/nijmegen.pdf) - which are colorfully named: ...
4
votes
1answer
213 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 ...
4
votes
1answer
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?
9
votes
1answer
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 ...
-2
votes
1answer
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 ...
4
votes
2answers
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 ...
2
votes
0answers
166 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 ...
8
votes
0answers
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 ...
2
votes
0answers
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
0answers
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 ...
8
votes
3answers
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 ...
22
votes
4answers
958 views

What is the definition of a large cardinal axiom?

In different books one can find different implicit definitions for a large cardinal axiom. My question is that which one of these definitions are more popular or standard amongst set theorists? Any ...
7
votes
1answer
238 views

Are superstrong stronger than strongly compact cardinals? (or vice versa)

In the last part of Kanamori's excellent "The Higher Infinite" there is a small diagram about the strength and consistency strength of some major large cardinal axioms. Below supercompact cardinals ...
0
votes
0answers
103 views

What references cover finitary systems of Ramified Analysis with transfinite levels?

The ramified theory of types, invented by Bertrand Russell, is a way of dealing with impredicativity by breaking the comprehension schema of second-order logic into levels. The comprehension schema ...
-4
votes
1answer
238 views

Is there a precise definition of “mathematical formula”? [closed]

In the Wikipedia article for Formula (which has no references), it is claimed that: "The informal use of the term formula in science refers to the general construct of a relationship between given ...
5
votes
0answers
268 views

Reference for Wang Tile

I am working on projects in solving ground state of generalized ising models. One recent work involves tiling with basic tiles that filled the whole lattice. For example, we could obtain results: ...
2
votes
1answer
208 views

Forcing Language

I asked the following question (slightly paraphrased) about a week ago in Stack exchange but no one knew the answer to the particular question. I was hoping someone here might be able to help me. ...
6
votes
4answers
1k views

Interactions of number theoretic conjectures and other fields of mathematics

There are many interesting open conjectures in number theory. My question is not about partial results or possible ways to prove them. It is about their interactions with the other fields of ...
4
votes
1answer
244 views

Consistency Strength of the Failure of Square on Singular Cardinals

Q1. What is the consistency strength of the failure of square on singular cardinals? Q2. What are known as partial results in this direction?
6
votes
2answers
233 views

Possible Choices for Cofinality of $\aleph_n$ without Choice

$\text{ZFC}$ proves that each $\aleph_{n}$ for $n\in \omega$ is a regular cardinal. But it seems without the Axiom of Choice there are many consistent possible choices for cofinality of such ...
12
votes
3answers
570 views

The interplay between certain aspects of interpretability, model theory and category theory

I have some questions about the interplay of interpretability, model theory and category theory. Since I had difficulties in finding literature or other helpful information about this topic, it would ...
6
votes
1answer
542 views

A Hot Betting On HOD

Remark: This question is based on an open question at the end of a paper by Hamkins, Kirmayer, and Perlmutter: "Generalizations of the Kunen Inconistency". $HOD$ as an inner model of $ZFC$ lies ...
4
votes
2answers
265 views

Can we force with Fraisse filters to solve Vaught's conjecture?

Around the classic Fraisse amalgamation theorem in model theory we have the following notions: Definition (1): If $M$ be an $\mathcal{L}$-structure then define: $age(M):=\lbrace N~|~N~\text{is ...
1
vote
0answers
209 views

Logical and alphabetological variant?

The notion of alphabetical variant is well known, so that a formula $x=x$ is an alphabetical variant of $y=y$ if $x$ and $y$ are distinct variables. One may want to consider the set term $\{x:x \neq ...
13
votes
6answers
1k views

The origins of forcing in mathematical logic and other branches of mathematics

As everyone knows, forcing was created by Cohen to answer questions in set theory. Question 1. What are the first applications of set theoretic forcing in other branches of mathematical logic, like ...
2
votes
1answer
87 views

Predicates encoding functions in Grzegorczyk-hierarchy

A $2$-ary predicate $R$ in Grzegroczyk-hierarchy is binary-valued function $R\colon\mathbb{N}^2\to\{0,1\}$. We say $R$ encodes function $f:\mathbb{N}\to\mathbb{N}$ if $R(x,y)$ is true if and only if ...
2
votes
0answers
350 views

Deducing Skolem's nonstandard integers from downward Lowenheim-Skolem?

If one has a nonstandard model $\mathcal{N}$ of PA and adjoins to the first-order theory the countable list of axioms $1<H,\, 2<H,\, 3<H, \ldots$ (satisfied in $\mathcal{N}$) for all the ...
9
votes
1answer
262 views

Universal $(\Sigma^2_1)^{\text{Hom}_{\mathord{<}\lambda}}$ set

Does anyone know of a reference for the fact that if $\lambda$ is a limit of Woodin cardinals, then the pointclass $(\Sigma^2_1)^{\text{Hom}_{\mathord{<}\lambda}}$ is $\omega$-parameterized? By ...
9
votes
1answer
436 views

Is there a probability theory developed in intuitionistic logic?

Since Boole it is known that probability theory is closely related to logic. According to the axioms of Kolmogorov, probability theory is formulated with a (normed) probability measure ...