first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, ...

learn more… | top users | synonyms (1)

8
votes
0answers
133 views

Are there always large discrete families of normal measures?

Let $\kappa$ be a measurable cardinal. We give the Stone space of all ultrafilters on $\kappa$ the usual topology, where each $x\subseteq\kappa$ determines a basic open $[x]=\{U;x\in U\}$. The ...
-2
votes
1answer
262 views

A set theory and a model without the empty set [closed]

Im just asking out of curiosity. Is there a set theory $\mathcal T$ and a model $\langle M,E\rangle \vDash \mathcal T$ such that no set in M is empty: $$\left(\forall m\in M \right)\left(\exists n\in ...
4
votes
0answers
145 views

Two questions about the behavior of the continuum function

The first question asks about the global behavior of the power function in the case of finite gaps. Question 1. Fix a natural number $m>1.$ For each limit ordinal $\alpha,$ including $0$, let $\...
1
vote
1answer
156 views

Why is a cut-free system consistent?

Assume that the cut-elimination theorem holds for a system $T$. Then, for any proof that makes use of the cut-rule in $T$, there is a proof that does not make use of the cut-rule. An immediate ...
10
votes
1answer
407 views

What sort of large cardinal can continuum be?

I have stumbled across a related question asking which large cardinal properties can hold for $\aleph_1$. This question is probably also related, asking in what ways $\aleph_0$ is a "large" cardinal. ...
2
votes
0answers
67 views

models of $I\exists^+_1$

$\phi$ is a $\exists^+_1$ formula iff it is in language of arithmetic and does not have $\forall$,$\neg$ and $\rightarrow$, therefore $I\exists^+_1$ is theory of $Q$+induction axioms for $\exists^+_1$ ...
5
votes
1answer
328 views

Ill-founded models of set theory with well-founded ordinals

Let $(\mathcal{M},E)$ be an internally non-well-founded model of set theory i.e of $ZFC^{\neg f}=ZFC\setminus \mathrm{foundation}+\neg \mathrm{foundation}$, then $\mathcal{M}$ includes an infinite ...
16
votes
1answer
1k views

What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem. What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...
1
vote
1answer
271 views

Does mathematical induction presuppose the existence of a completed infinity?

Consider the following statement by Edward Nelson--this from the "Outline" of his 'proof' of the inconsistency of $PA$ (which Terry Tao found to contain an error): "The induction axiom schema of ...
5
votes
0answers
131 views

Failure of GCH at a strongly compact cardinal

Does Con(ZFC+ there exists a strongly compact cardinal) imply Con(ZFC+ there exists a strongly compact cardinal $\kappa+ 2^\kappa > \kappa^+$)?
24
votes
1answer
755 views

Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?

By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following: We are considering a ...
31
votes
8answers
6k views

What are some important but still unsolved problems in mathematical logic?

In the past, First order logic and its completeness and whether arithmetic is complete was a major unsolved issues in logic . All of these problems were solved by Godel. Later on, independence of ...
7
votes
1answer
371 views

Can an ultrapower be undone by forcing?

I am not 100% certain this question is appropriate for MO; I may just be missing something obvious. Also, I vaguely recall a similar question being asked here a while ago, but I can't find it; if it ...
2
votes
1answer
159 views

Is there a simpler axiomatization for the quantifiers? [closed]

There is those one Q5 to Q7 in https://en.wikipedia.org/wiki/Hilbert_system#Formal_deductions But I know the axioms of Boolean algebra were simplified to this https://en.wikipedia.org/wiki/...
11
votes
3answers
412 views

Algorithmic complexity of formal proof verification?

In this question, suppose $S$ is some popular real-world automated proof system that is stronger than or equivalent to Peano Arithmetic. I would be happy with a positive answer to the following for ...
19
votes
1answer
697 views

Variant of Conceptual Completeness

Let $\mathcal{C}$ and $\mathcal{D}$ be pretopoi, and let $f: \mathcal{C} \rightarrow \mathcal{D}$ be a pretopos functor (that is, a functor which preserves finite coproducts, finite limits, and ...
8
votes
2answers
485 views

What is an ordered structure, in general?

This is basically a reference request, but the post is going to be relatively long (and a little bit verbose): I apologize in advance for that. Premise. There are several examples of "ordered ...
2
votes
1answer
114 views

How to show certain theories are not existentially closed

To show that $ZFC$ is not existentially closed, we can use the following forcing argument: Let the ground model can model $V=L$ and the forcing extension model $2^{{\aleph}_{0}}=\aleph_{2}$. (Maybe ...
5
votes
0answers
86 views

Does every model of $I\Delta_0$ has an end extension to a model of $I\Delta_0+\Omega_1$?

Does every model of $I\Delta_0$ has an end extension to a model of $I\Delta_0+\Omega_1$? In End extensions of models of linearly bounded arithmetic paper the author said this problem is open. I want ...
2
votes
2answers
600 views

What logic can express this sentence?

Trying to figure out the logic in which the following formula is expressible: $\forall i\in N: (x_i > y_i)$, which is equivalent to the "infinite" conjunction $\bigwedge_{i\in N} (x_i > y_i)$. ...
23
votes
9answers
3k views

What is… A Grossone?

Y. Sergeyev developed a positional system for representing infinite numbers using a basic unit called a "grossone", as well as what he calls an "infinity computer". The mathematical value of this ...
24
votes
5answers
2k views

What are the advantages of the more abstract approaches to nonstandard analysis?

This question does not concern the comparative merits of standard (SA) and nonstandard (NSA) analysis but rather a comparison of different approaches to NSA. What are the concrete advantages of the ...
1
vote
1answer
166 views

A question regarding a fragment of Robinson Arithmetic

In his answer to the following mathoverflow question, The (un)decidability of Robinson Arithmetic without multiplication, Emil Jerabek proved that the following fragment: $\forall$x(Sx$\neq$0) $\...
37
votes
4answers
3k views

How undecidable is the spectral gap?

Nature just published a paper by Cubitt, Perez-Garcia and Wolf titled Undecidability of the Spectral Gap, there is an extended version on arxiv which is 146 pages long. Here is from the abstract:"Many ...
6
votes
1answer
192 views

Darboux property of non-atomic sigma-additive nonnegative measures equivalent to the AC?

A result commonly, and probably erroneously, attributed to W. Sierpiński is that every non-atomic, countably additive, nonnegative measure $\mu: \Sigma \to \bf R$, where $\Sigma$ is a sigma-algebra on ...
12
votes
1answer
585 views

What is the precise relationship between o-minimal theory and Grothendieck's “Esquisse d'un programme”?

I have seen various references in the literature to such a connection but they tend to assume that the reader is familiar with the connection, and limit themselves to providing additional detail. So ...
3
votes
1answer
151 views

When can we have “each subtheory is satisfiable iff it is recursively axiomatizable”?

Weak Version: Is there a 1st order language $L$ (with only countably-many formulas) such that for each recursive coding $C$ of the formulas of $L$, there is a theory $T$ of $L$ where $T$ is not ...
5
votes
1answer
311 views

A proper class of formulas with every set-sized (but no proper-class-sized) subcollection satisfiable

What feature(s) must a (non 1st-order) language with proper-class-many formulas have in order to guarantee that: There is a proper class P of formulas such that both (a) every set-sized sub-...
0
votes
0answers
103 views

Distribution of definable integers

Consider the distribution of all formulas of length less then n which define an integer in PA. So for instance f(7,n)=number of formulas of length less then n which output 7. Or the number of steps ...
7
votes
0answers
127 views

Kripke models of $HA$

Let $K$ be a kripke model and $k$ be one of its node, then $\mathcal{M}_k$ is classical structure of $k$. What is the strongest theory of arithmetic like $T$ such that for every kripke model $K\...
2
votes
1answer
136 views

[meta-]decision problem about decidability of finite Hilbert-style axiomatic systems

Consider some arbitrary language $S$ written over a given (propositional) signature with a finite collection of finitary constructors, and consider a procedure that receives as input an arbitrary ...
3
votes
1answer
226 views

Can we use this symbol? [closed]

We consider the ring $\mathbb{C}[e^{\lambda x} \mid \lambda \in \mathbb{C}]$ and the language $L=\{+, \cdot , \frac{d}{dx} , 0, 1\}$. The ring consists of elements of the form $$\sum_{i=0}^N \...
4
votes
3answers
223 views

End Extension models of $I\Delta_0$

Recently I'm thinking about question below, but I can not prove or disprove it. Is it true that for every model $M\models I\Delta_0$ there exists a model $M'\models PA$ such that $M'$ is end ...
9
votes
2answers
556 views

Why is there a need for ordinal analysis?

Consider the Peano axioms. There exists a model for them (namely, the natural numbers with a ordering relation $<$, binary function $+$, and constant term $0$). Therefore, by the model existence ...
8
votes
2answers
301 views

“Clubiness” of projective sets of ordinals

I'm sure this is just my google-fu failing me, but: what are sufficient, non-overkill large cardinal axioms which guarantee "Every (boldface) $\Pi^1_n$ set of (real codes for) countable ordinals ...
2
votes
0answers
113 views

Some questions regarding an alteration of Grzegorczyk's theory of concatenation, $\operatorname{TC}$

Consider Grzegorczyk's concatenation theory $\operatorname{TC}$, a "weak theory of words over the two letter alphabet $\Sigma=\{a,b\}$" (this from Grzegorczyk and Zdanowski's paper Undecidability and ...
14
votes
1answer
325 views

Convergence rate of Fagin's 0-1 law for first-order properties of random graphs

Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the ...
6
votes
0answers
190 views

Adding minimal subsets to $\aleph_\omega$

Given a cardinal $\kappa,$ recall that $X \subset \kappa$ is called fresh (over $V$), if $X \notin V,$ but $X \cap \alpha \in V$ for all $\alpha < \kappa.$ Question. Is it consistent that there ...
8
votes
1answer
180 views

Boolean-Valued Models: Why is $\| x=y \| \cdot \| \phi(x) \| \leq \| \phi(y) \|$?

Let $B$ be a complete Boolean algebra. Jech defines a Boolean-valued model $\mathfrak{A}$ of the language of set theory to consist of a Boolean universe $A$ and functions of two variables with values ...
13
votes
1answer
342 views

Is this theory decidable?

It is well-known that both Presburger arithmetic (by contrast with Peano arithmetic) and Tarski geometry are decidable. I was in the shower this morning and wondered whether there exists an elegant ...
3
votes
0answers
308 views

How close to being well-orderable does this make my powerset?

Let's work in a set theory without assuming AC (for instance, but not necessarily, ZF). Fix a set $k$ satisfying $k\times k \simeq k$, and consider its powerset $X = 2^k$. I have a technical condition ...
3
votes
1answer
223 views

When can you canonically extend an ultrafilter after forcing?

Suppose that $V$ is a model of $\sf ZFC$, and fix some regular $\kappa$, say $\omega_1$ for practical purposes. Let $\cal U$ be an ultrafilter on $\omega_1$ in $V$ which is non-principal and even ...
1
vote
2answers
366 views

Was “arithmetical translation” (coding in the Goedel sense) ever a part of Hilbert's Program?

Was "arithmetical translation" (that is, coding in the Goedel sense) ever a part of Hilbert's Program? I ask this question for several reasons: i) it gives the numerals |, ||, |||,.... an ersatz '...
0
votes
0answers
150 views

Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ? How can we prove the (...
2
votes
2answers
272 views

Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...
4
votes
1answer
82 views

Proving moduli of uniform continuity in RCA_0

Simpson's Subsystems of Second Order Arithmetic (pp. 134ff.) uses RCA$_0$ to prove various theorems of analysis for all continuous functions with a suitable modulus of uniform continuity. And he ...
1
vote
0answers
54 views

Fully residually free groups and completion

Let $G$ be a fully residually free group with a finitely generated profinite completion. Is $G$ necessarily finitely generated?
8
votes
2answers
574 views

Did Bishop, Heyting or Brouwer take partial functions seriously?

The partial μ-recursive functions which may or may not be provably total seem to have some direct relation to the initial motivations for intuitionistic mathematics. (Following Kronecker, one ...
4
votes
2answers
296 views

A property of uncountable almost disjoint families

Let $\mathcal{A}$ be an uncountable almost disjoint family (not necessarily maximal) of infinite subsets of $\mathbb{N}$. Denote by $\mathcal{A}_{\subseteq}=\{ B\subseteq\mathbb{N}:|B|=\omega \wedge \...
4
votes
0answers
176 views

Theories introduced by a class of forcing notions

The following notion is introduced by Mohammad Golshani. Let $V$ be a model of set theory and let $\mathcal{P}$ be a class consisting of non-trivial forcing notions in $V$. Let $$Th(V, \mathcal{P})...