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
185 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
2answers
237 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
3answers
333 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
3answers
348 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
2answers
293 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
2answers
1k 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
1answer
144 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
4answers
476 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
0answers
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
1answer
203 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
3answers
300 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
0answers
171 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
1answer
154 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
4answers
836 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
1answer
248 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
1answer
185 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
1answer
880 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
1answer
330 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
0answers
242 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
2answers
371 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
0answers
90 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
171 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
1answer
114 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
3answers
750 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
1answer
239 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
2answers
129 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
0answers
136 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
3answers
297 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
1answer
225 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
0answers
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
2answers
332 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 ...
2
votes
3answers
336 views

Show that Z2 is not conservative over PA

It is well-known that $\mathsf{ACA}_0$ is a conservative extension of PA. I assume this theorem gets a lot of attention because $\mathsf{Z}_2$ is not conservative over PA. Thus there ought to be ...
2
votes
0answers
142 views

Algebras admitting quantifier elimination

I apologize if this question is meaningless or trivial: What are examples of Algebras admitting quantifier elimination? Especially are there Groups admitting quantifier elimination? I need to say ...
5
votes
4answers
669 views

“Introduction to mathematical logic” book from a formalist perspective

I'm looking for books that introduce the reader to mathematical logic assuming the perspective of a formalist. I've found that many books are more or less written for the platonist - like Kunen's ...
4
votes
1answer
100 views

Models of intuitionistic linear logic that reflect the resource interpretation

I am interested in models of intuitionistic linear logic, that is, the logic that you get if you take classical linear logic and restrict the set of operators to $\otimes$, $1$, $\multimap$, $\times$, ...
24
votes
1answer
2k views

A preprint of Sela concerning the work of Kharlampovich-Miyasnikov

Yesterday, Z. Sela published a preprint in arXiv which claims that the solution of Olga Kharlampovich and Alexi Miyasnikov for the Tarski problem on decidablity of the first order theories of free ...
22
votes
4answers
971 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 ...
5
votes
3answers
622 views

PFA: A New Godel's Program & A New Large Cardinal Ladder (Updated)

We know $PFA$ implies $2^{\aleph_0}=\aleph_2$. Q1. What does $PFA$ say about other values of continuum function? Does proper forcing axiom carry any further information about values of continuum ...
7
votes
1answer
242 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 ...
8
votes
1answer
260 views

What is the proof-theoretic ordinal of PA + Con(PA), PA + Con(PA + Con(PA)) etc., and why?

I seem to remember having read that the proof-theoretic ordinal (sup of ordinals the theory can prove well-ordered) of $\mathsf{PA} + \mathsf{Con}(\mathsf{PA})$ is the same as that of $\mathsf{PA}$, ...
4
votes
1answer
179 views

Why the axiomatic rank of the variety of groups is equal to three?

I am thankful of Anton Klyachko who introduced axiomatic rank to me: the axiomatic rank of a variety is the minimum number of variables which we need to define that variety by identities. It seems ...
8
votes
1answer
232 views

Genericity by names

If $P$ is a notion of forcing in $M$, then $G$ is a $P$-generic filter over $M$ if $G\subseteq P$ is a filter, and for every $D\in M$ which is a dense subset of $P$, $G\cap D\neq\varnothing$. ...
4
votes
1answer
331 views

Fundamental Problems in Mathematics that, without Computer Sciences, would not be resolved? [closed]

Could you please give examples of fundamental questions in mathematics (let us say, pure mathematics) which were resolved fundamentally by the use of computers? More precisely, are there examples that ...
2
votes
1answer
222 views

Elementary proof of bounds on factor polynomials

The question Getting a bound on the coefficients of the factor polynomial got very nice answers on Gelfond's theorem. But for work on proof theory of arithmetic I want a proof in arithmetic. The ...
1
vote
0answers
119 views

Dedekind reals in heyting valued models

Let $V^{H}$ be a Heyting valued model of intuitionistic set theory. What conditions does $H$ have to satisfy in order for the following claim to hold? (where $\| \phi(u) \| \in H$ is the truth value ...
4
votes
1answer
341 views

Why is adopting Russell's Axiom of Reducibility as strong as eliminating the Ramified Hierarchy?

In order to respond to concerns of impredicativity, Bertrand Russell developed a system of ramified second-order logic, which is like regular second-order logic except the comprehension schema is ...
8
votes
0answers
303 views

“Hard” separation results in reverse mathematics (or similar)

This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...
23
votes
2answers
492 views

When does the choice of the generic matter?

It is a somewhat curious phenomenon that, in forcing arguments, one usually doesn't care about any particular properties of the generic filter being used (this isn't strictly true; there are cases ...
0
votes
3answers
133 views

Negated varieties and their relatively free algebras

During the past days, I asked some questions in order to gain a clear understanding of the notion of "free algebras". I suppose that the question below is the most clear image of the concept I have ...
6
votes
1answer
97 views

Is 0' of PA degree relative to a non-low set?

Definitions: A set $X$ is of PA degree relative to a set $Y$ if every infinite $Y$-computable binary tree has an infinite $X$-computable path. A set $X$ is low if $X'$ is computable from ...