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)

2
votes
1answer
83 views

Can tests for the convergence and divergence of series be used to create undecidable sentences?

Let f(k) be a recursive function which maps the set of positive integers into itself. Let T be a formalized theory which is axiomatizable and contains Peano's Arithmetic as a sub-theory. For example, ...
2
votes
1answer
105 views

Some very weak statements on choice

This is a follow-up question to Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$? Consider the statements $(\text{S}1)$ For any infinite set $X$ there ...
2
votes
1answer
104 views

Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?

Consider the statement For any infinite set $X$ there is an injection $\varphi$ from $(X\times\{0\}) \cup (X\times\{1\})$ into $X$. Does this imply the ${\sf AC}$?
4
votes
0answers
73 views

Ref request: modelling regular theories as an injectivity condition

The background to the following observation is standard material in categorical logic, and I thought this was was too — I don’t remember learning it, but I don’t think it is original — but I can’t now ...
-1
votes
0answers
50 views

Minimal CNF expression [on hold]

Given any propositional form A, I'm interested on finding an equivalent CNF form of minimal length. Length of a formula is defined as the number of atomic statements in the formula. For example, ...
-1
votes
0answers
69 views

Elementary derivation in a very stingy logical calculus [on hold]

Following up on my previous question, I am trying to understand the logical calculus defined here (p.183) by Buchholz and Weiner. I want to prove $0=0+0$. (I can prove $0+0=0$: I start with ...
2
votes
1answer
119 views

A derivation in Tait calculus

I have seen in at least two different places (here, p. 183; and here, last slide) the Tait calculus defined the following way. Here $\Gamma$ denotes a set of formulas $\{A_1, \ldots, A_k\}$, which is ...
1
vote
0answers
150 views

Reference request: Models of isomorphic languages result into isomorphic categories

This is basically a reference request by someone who has not been educated as a logician and would like to be rigorous about certain preliminary aspects of model theory. Fix an uncountable universe ...
6
votes
1answer
350 views

Taller models of ZFC

This question is somewhat related to a previous one, where I asked for new forms of infinite beyond the cardinal hierarchy. Using forcing techniques, at least the ones I know of, one starts from a ...
7
votes
2answers
211 views

How can any theory prove well-foundedness of ordinals above $\omega_1^{\text{CK}}$?

$\newcommand{\omegaoneck}{\omega_1^{\text{CK}}}$ Pardon the extremely basic question - this isn't quite my area - but I'm confused about the definition of proof theoretic ordinals. The proof ...
3
votes
1answer
167 views

Reference request: eliminating function symbols in predicate logic

Here is a basic technique in logic which seems well-known in folklore, but which I haven’t managed to find written down anywhere. $\newcommand{\T}{\mathbf{T}}$ Fact. Let $\Sigma$ be a signature (in ...
6
votes
1answer
165 views

Adding a truth-like predicate to PA

It is well known that adding a truth predicate to arithmetic in the most natural way leads to a contradiction. Suppose as usual that we add a one place relation T to the language of arithmetic, and ...
9
votes
1answer
307 views

Every measure on a set $X$ extends to the power set of $X$: Consistent or not with ZF?

Question. Is it consistent with ZF that every (countably additive, non-negative) measure $\mu: \Sigma \to \bf R$, where $\Sigma$ is a sigma-algebra on a given set $X$, extends to a (countably ...
4
votes
0answers
133 views

Set theory and forcing from the point of view of a formal system $G^+$ of Gentzen type

There are four papers by Vladimir Alfeevich Kuznetsov, which discuss the above titled topic: (1) Some problems in set theory from the standpoint of a formal system G+ of Gentzen type. (Russian) Akad. ...
4
votes
1answer
198 views

When does an infinite model have a proper class-sized elementary extension?

Suppose that a set of sentences of a 1st order language has an infinite model $M$. Under what conditions is there is a proper class-sized elementary extension of $M$? How does the answer change if ...
6
votes
2answers
138 views

a variant of the Kleene tree

The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known. I need a variant. (For those in the know, I need a c-bar which is ...
9
votes
0answers
314 views

Riemann hypothesis in Zilber's field

Question. What is known about the situation (truth or falsity) of Riemann hypothesis in the Zilber's field?
3
votes
0answers
141 views

Reducing Consistency of $PA$ [closed]

By godel translation consistency of $PA$ is equivalent to consistency of $HA$. I want to know any similar theorems for $PA$. 1.What is the minimal theory $T\subsetneq PA$ such that the proof of ...
5
votes
0answers
187 views
+50

Constructive compactness for countable models?

The compactness theorem for countable models is equivalent to the weak König's lemma by a result of H. Friedman and others as noted here, in the context of classical logic. The weak König's lemma in ...
2
votes
2answers
281 views

Non-Formal Applications: Higman and Kruskal

After looking through many papers, I noticed that most of the discussions and proofs for Higman's Lemma and Kruskal's Tree Theorem only have formal applications in set theory, logic, and type theory. ...
14
votes
1answer
229 views

Is the Martin's axiom number $\mathfrak m$ regular

The Martin's axiom number $\mathfrak m$ is the least cardinal $\kappa$ for which $\text{MA}_\kappa(\text{ccc})$ is false, i.e. the least cardinal such that there exists a ccc poset $P$ and a family ...
2
votes
2answers
162 views

Compactness for countable models?

How and where is it proved that WKL$_0$ proves the compactness theorem for countable models? (This is a follow-up to a comment of F. Dorais.)
1
vote
1answer
139 views

What restriction(s) of Goedel's primitive recursive functionals is (are) necessary and sufficient to prove the consistency of $PRA$

It is well known that one can use Goedel's primitive recursive functionals of finite type to prove the consistency of $PA$ (Peano Arithmetic). As such, one can certainly use them to prove the ...
6
votes
1answer
185 views

Does “$|{\cal P}_2(X)| = |X|$ for $X$ infinite” imply ${\sf (AC)}$?

This comes from a comment made by user bof in this thread. Let $X$ be a set, define ${\cal P}_2(X) = \big\{\{a, b\}: a\neq b\in X\big\}$. Consider the statement ${\sf (S)}$ If $X$ is an ...
5
votes
3answers
603 views

What does the axiom of replacement mean and why should I believe it?

Here Professor Blass describes the following cumulative hierarchy of sets: Begin with some non-set entities called atoms ("some" could be "none" if you want a world consisting exclusively of ...
3
votes
1answer
87 views

Weak Bounded Arithmetics

Let $\Sigma^b_i$ and $\Pi^b_i$ formulas be bounded formulas defined by Buss in language of $L_b$. $PIND(\phi(x))$ is the formula: $$\phi(0)\land \forall x(\phi(\left \lfloor \frac{x}{2} \right ...
5
votes
3answers
353 views

Can the omega-rule rescue Hilbert's program?

As known the second incompleteness theorem derailed Hilbert's program. However, Hilbert himself tried to rescue it with the $\omega \text{-rule}$, according to the following paper: ...
5
votes
1answer
253 views

How much choice does a linear or well-order on cardinals imply?

It is well-known that if the natural (partial) order on the class of cardinal numbers is a linear order, then it is in fact a well-order and the axiom of choice holds. I was, however, interested in ...
11
votes
1answer
258 views

Intutionistic Robinson Arithmetic

By Friedman translation $HA$ and $PA$ prove the same $\Pi_2$ formulas. Is it true for Intutionistic Robinson arithmetic(Robinson axioms with intutionistic logic) and classic Robinson arithmetic? ...
1
vote
1answer
830 views

What is the modern consensus on the difficulty of infinitesimals?

At a related thread at MSE an expert in reverse mathematics noted that "As the modern consensus is that only nonstandard models have infinitesimals, it will be quite challenging to give a concrete ...
12
votes
1answer
764 views

Reverse-engineer forcing: am I reinventing the wheel?

In the course of a project I’m working on, I’ve started playing around with a sort of “reverse-engineering” forcing. It seems interesting, but I have a sinking feeling I’m reinventing the wheel; does ...
7
votes
0answers
159 views

Can you define a probability measure on the set of countable transitive models of ZFC?

It is well known that the set of hereditarily countable sets $H(\omega_1)$ —or, if you prefer, $H_{\omega_1}$— has cardinality $2^{\aleph_0}$, and I understand that every countable ...
10
votes
0answers
244 views

Is the universality of the surreal number line a weak global choice principle?

I'd like to consider the principle asserting that the surreal number line is universal for all class linear orders, or in other words, that every linear order (including proper-class-sized) linear ...
3
votes
1answer
180 views

A question regarding the consistency of Nelson's Predicative Arithmetic

Following Dan Willard (from his paper "Self-Verifying Axiom Systems, the Incompleteness Theorem, and Related Reflection Systems", found on his homepage, pdf here): "Define an axiom system $\alpha$ ...
4
votes
0answers
157 views

Finding limit-nondecreasing sets for certain functions

This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we ...
4
votes
2answers
138 views

first order languages over graphs (and other discrete models)

A lot of research has been devoted to the study of first order language of graphs (FO). Formulas in this language are constructed using variables $x, y,\dots$ ranging over the vertices of a graph, the ...
8
votes
0answers
128 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
220 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
133 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
132 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
334 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. ...
1
vote
0answers
60 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
287 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
226 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
126 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^+$)?
23
votes
1answer
636 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 ...
29
votes
8answers
5k 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 ...
6
votes
1answer
348 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
144 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 ...