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)

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
143 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
472 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
297 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
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
1answer
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
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
244 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
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
1answer
875 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
240 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
370 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
168 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
741 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
128 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
135 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
329 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
335 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
659 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
99 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
969 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
620 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
240 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
258 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
330 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
337 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
302 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
490 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
132 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 ...
4
votes
3answers
249 views

The existence of an algebra whose set of identities and first order theory are equivalent

Is there an algebra $A$ (for example a group) such that $Th(A)$ is logically equivalent to $id(A)$? In other words, is there an algebra $A$ such that $$ Mod(Th(A))=Var(A)? $$ Clearly finite algebras ...
2
votes
0answers
92 views

What are natural examples of non-relativizable proofs? [duplicate]

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles). Virtually all proofs seem to be relativizable, though. What are good examples of ...
0
votes
1answer
149 views

relatively free groups in $Var(S_3)$

Suppose $S_3$ is the symmetric group of order 6. Which elements of the variety $Var(S_3)$ are relatively free? This question is related to my previous question Relatively free algebras in a variety ...
25
votes
3answers
1k views

Latest stand of core model theory?

What is the "strongest" core model to this day? In particular, how far are we from a core model for supercompact cardinals? There are rumors of some notes from a workshop in 2004: ...
10
votes
1answer
279 views

Harvey Friedman's strict reverse mathematics vs. Cook-Nguyen's V$^0$

Harvey Friedman posted several manuscripts [1] proposing a program for "strict" reverse mathematics, in the sense that the base theory should be mathematically natural and coding-free. In them he ...