Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

20
votes
0answers
419 views

How much set theory does the category of sets remember?

Question. Let $M$ be a model of enough set theory. Then we can form a category $\mathbf{Set}_M$ whose objects are the elements of $M$ and whose morphisms are the functions in $M$. To what extent is ...
15
votes
0answers
389 views

complete, finitely axiomatizable, theory with 3 countable models

Does it exist a complete, finitely axiomatizable, first-order theory $T$ with exactly 3 countable non-isomorphic models? A few relevant comments: There is a classical example of a complete theory ...
12
votes
0answers
190 views

References on filter quantifiers

This post is primarily a reference request. In combinatorics and other areas, we use filter quantifiers to simplify the statements of various definitions, theorems and proofs. The general idea is ...
12
votes
0answers
453 views

Non-axiomatisability and ultraproducts

Let $T$ be a first-order theory over a language $L$, and let $\mathcal{M}$ be a subclass of the class of models of $T$. As I understand it, if there is no theory $\hat{T}$ over $L$ whose class of ...
11
votes
0answers
204 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
10
votes
0answers
213 views

The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need ...
9
votes
0answers
162 views

An exercise in Fine Structure of constructible universe concerning projectum patterns

This question assumes some familiarity with Jensen's fine structure analysis of the constructible universe L (https://en.wikipedia.org/wiki/Jensen_hierarchy, ...
9
votes
0answers
177 views

A consequence of zero sharp (successor cardinals having countable cofinality)

So the existence of $0^\sharp$ in set theory is really the assertion on the existence of indiscernibles for the constructible universe $L$ that also "generate" $L$ (see ...
9
votes
0answers
155 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
8
votes
0answers
524 views

How strong is the statement that Thompson F is amenable?

Justin Moore's proof turned out to have an error I just attended Justin Moore's talk on this today. Since I am neither a group theorist nor a combinatorist, and is not familiar with ultrafilters I ...
7
votes
0answers
111 views

What can the reals of an inner model be?

This is probably a silly question. Call a set of reals $X$ a constructibility ideal (in analogy with a Turing ideal) if $X$ is closed under effective join $r\oplus s: n\mapsto 2^{r(n)}3^{s(n)}$ and ...
7
votes
0answers
107 views

Defined negation in intuitionistic linear logic

Is it possible to define a negation in intuitionistic linear logic, the way one does in intuitionistic logic, i.e. $A^{\bot} \equiv A \multimap \mathbf{0}$ (or, as it would be written in ...
7
votes
0answers
139 views

On proving the zero-one-law for first order logic

I'm trying to understand the proof of the zero-one-law for first order logic as provided in (Ebbinghaus-Flum, 1995). It goes as follows: Let $\tau$ be a relational signature. Let $r\in\mathbb{N}$, ...
7
votes
0answers
94 views

Infinite palindromes in number of nonisomorphic posets is independent of $\mathsf{ZF}$

The following is an "exercise" in P. Stanley's book "Enumerative Combinatorics": Let $f(n)$ be the number of nonisomorphic $n$-element posets (...) let $\mathcal{P}$ denote the statement that ...
7
votes
0answers
224 views

Fixed points in computability and logic

I asked this question on CS.SE, too: http://cstheory.stackexchange.com/questions/27322/fixed-points-in-computability-and-logic I would like to understand better the relation between fixed point ...
7
votes
0answers
154 views

Skolem Hulls in $H_{\omega_2}$

Consider a model of the form $\mathfrak{A} = (H_{\omega_2}, \epsilon, \prec, f_0, f_1, ...)$, some expansion of $H_{\omega_2}$ in a countable language, with $\prec$ giving a well-order. Does there ...
7
votes
0answers
326 views

Using the compactness theorem to show a set of first-order formula is equivalent to a set of quantifier-free formula

I am going through some theorems in Hodges' ``A shorter model theory'' and I have realized that I do not understand a certain argument regarding compactness. My question has two forms, I am sure that ...
6
votes
0answers
153 views

Transexponential Functions

Recall that $\exp(1,x) = e^x$ and $\exp(n+1,x) = e^{\exp(n,x)}$. Recall that $f(x)$ is transexponential if $f(x)$ is eventually greater than $\exp(n,x)$ $\forall n \in \mathbb{N}$ I am looking for a ...
6
votes
0answers
163 views

Anti-random reals

EDIT: This has now been crossposted at MO: http://mathoverflow.net/questions/219366/antirandom-reals. This is partially motivated by my question at mathoverflow: ...
6
votes
0answers
89 views

Elementary submodels in stationary logic.

In the paper "Stationary Logic" by Barwise, Kaufmann and Makkai the authors prove that stationary Logic L(aa) has Löwenheim number $\aleph_1$, i.e. every satisfiable set of sentences has a model of ...
6
votes
0answers
154 views

ZF and weakly inaccessible cardinals

This question should probably have been asked 3 years ago (perhaps it has and was removed for some reason?) In 2011, Alexander Kiselev claimed to have proved in ZF that there are no weakly ...
6
votes
0answers
260 views

Is Kunen's claim about non-equivalent forms of Axiom of Choice, true?

Consider the following forms of the axiom of choice: $AC_1:\forall F\neq \emptyset~~~(\emptyset\notin F~\wedge~\forall x,y\in F~~~(x\neq y\rightarrow x\cap y= \emptyset))\rightarrow \exists C~\forall ...
6
votes
0answers
254 views

Characterization of the First Order Theory of Ordered Abelian Groups via Quantifier Elimination

In the paper "Elimination of Quantifiers in Algebraic Structures" Macintyre, McKenna and van den Dries, proved that every field (ordered field) whose theory admits quantifier elimination in the ...
6
votes
0answers
119 views

Model theory in terms of type spaces/Lindenbaum algebras

Are there any good references that go into some detail of known 'translations' between properties of the type space of a model and the model theoretic properties of the model? All I seem to find are ...
6
votes
0answers
329 views

Foundation for category theory

Before a little premise: It's well known that we can internalize the notion of category, functor and natural transformation in any category with enough structure: for instance we can define what an ...
5
votes
0answers
139 views

“Clubbiness” of $\Pi^1_n$ sets

I'm sure this is just my google-fu failing me, but: what are sufficient large cardinal axioms to guarantee "Every (boldface) $\Pi^1_n$ set of countable ordinals contains or is disjoint from a club ...
5
votes
0answers
75 views

Is there a first-order formula expressing this property?

Suppose $R$ is a binary relation on $\{0,1\}^*$ (where $\{0,1\}^*$ is the set of all finite words over the alphabet $\{0,1\}$), and for all $x$, the number of $y$ such that $xRy$ is finite. Is there ...
5
votes
0answers
120 views

Reference request: equivalence between formulas in fixed point and first-order logic

I'm looking for materials on the relationship between first-order and fixed-point logics, specifically on the condition for a formula in some sort of fixed-point logic to have an equivalent ...
5
votes
0answers
82 views

Can all axioms of mathematical theories be expressed with predicate logic?

The book Roads to Infinity: The Mathematics of Truth and Proof stated that, "All the standard mathematical theories have axioms that can be expressed in predicate logic." Predicate logic generally ...
5
votes
0answers
72 views

What are some arguments/counterarguments for Zeilberger's “proof certificates”?

Here is the quote I wish to ask about: "I speculate that similar developments will occur elsewhere in mathematics, and will 'trivialize' large parts of mathematics, by reducing mathematical ...
5
votes
0answers
60 views

Deductive closure of sentence $\forall x \forall y F(x,y) \stackrel{.}{=} F(y,x)$ in language $\mathcal{L}$ is undecidable.

$\mathcal{L}$ is the language that contains a single binary function symbol $F$. In the earlier parts of this question, we were told to take the $\mathcal{L}$-structure $\mathcal{M}$ with universe ...
5
votes
0answers
59 views

Proving $\square(\forall v_1\neg\psi(v_1))\rightarrow\forall v_1\neg\psi(v_1)$ for a particular $\psi$.

I have a formula $\psi(v_1)$ that is equivalent in $\mathrm{PA}$ to $$\exists a\exists b\exists c\left[\neg\exists ...
5
votes
0answers
287 views

Gödel's Incompleteness Theorem in “Gödel, Escher, Bach”

Ok, so I'm reading the chapter on Gödel's Incompleteness Theorem in "Gödel, Escher, Bach" and I want to make sure I'm getting this right: the idea of the book's proof is to form the sentence "There ...
5
votes
0answers
53 views

Type-definable Forcing or forcing in a non-first order setting

Roughly speaking, in set forcing the forcing notion is a set from ground model's perspective and in class forcing its a definable subset of the ground model given by solutions of some formula with ...
5
votes
0answers
109 views

Functorial first order theories interpretation

Question will be a bit naive, so please, be kind. Consider first order theories, $\Gamma, \Gamma'$ . Let $\mathcal{M}$ be the category of models for $\Gamma$ and $\mathcal{M}'$ be the category of ...
5
votes
0answers
969 views

which branch of maths studies Standard Logical Matrices

In classical logic you have truthtables like: & | T | F ---|---|--- T | T | F F | F | F In many valued logic you have tables like: (this one is ...
5
votes
0answers
318 views

Logical consequence of Euclid's theorem

Are there any far reaching non-trivial consequences of Euclid's infinitude of primes where theorems make use of it? Wikipedia does not have the list of applications of this theorem, rather modern ...
5
votes
0answers
694 views

The Cantor Space as $\{0,1\}^{\mathbb{N}}$ and as $[0,1]$.

The Cantor-Space is defined as the space of all infinite binary sequences, i.e. the space $\{0,1\}^{\mathbb{N}}$. It has a natural metric, $$ d(x,y) = \inf\{ 2^{-|w|} : w \in pref(x) \cap pref(y) \} ...
5
votes
0answers
156 views

Interpretation of impure set theory within pure set theory?

I recently came across this paper, where the author (in section 3.1) gives an interpretation of ZFU within ZF. The author of the paper goes on to show what he calls the "synonymy" (i.e., that ZF and ...
4
votes
0answers
38 views

Group orderable iff all its finitely-generated subgroups are orderable

I want to proof this specifically using the Compactness Theorem from propositional logic (this is an exercise from Model Theory, Hodges). $G$ orderable means there is a total ordering s. t. $g\leq h$ ...
4
votes
0answers
71 views

Show undecidability by reducing from Hilbert's $10^{th}$ problem

To show that the existential theory of $\mathbb{Z}$ in the language $\{0, 1; +, \mid , \mid_p\}$ (where $x \mid_p y \Leftrightarrow \exists r \in \mathbb{N} : y=\pm xp^r$) is undecidable we have to ...
4
votes
0answers
75 views

Studying Algebraic Logic from Plotkin's Universal Algebra, Algebraic Logic, and Databases.

I wonder what do you think about this book Universal Algebra, Algebraic Logic, and Databases? I've looked for some reviews but found none so I can not determine if it's fine to learn about polyadic ...
4
votes
0answers
89 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
4
votes
0answers
112 views

Non-Forcing and Independence

Do there exists sentences which are independent of ZFC, cannot be shown to be independent through some method of forcing, and do not increase the consistency strength of ZFC (e.g. so Large Cardinal ...
4
votes
0answers
116 views

Incompleteness theorem

Correct me if I am wrong at any point! Godel's incompleteness theorem allows us to express "PA is consistent" in the language of Peano arithmetic, and shows that this is not provable in PA. Let's ...
4
votes
0answers
110 views

Is there a logic to formalize the concept of “understanding”

The question may seem little bit weird given that philosophers have been struggling to have a full grasp on the concept of "understanding". But I'm wondering if there are any logics (modal-based or ...
4
votes
0answers
130 views

Intuition for the choice of background (set) theory

Problem From the formalist point of view, any mathematical statement should ultimately be an assertion about the derivability of a certain formula in a certain formal system, call it the background ...
4
votes
0answers
128 views

Countable transitive $T \vDash ZFC-P$ with $\approx$ not absolute: why do we need $H(\aleph_3)$?

I am trying to solve Exercise IV.3.31 from Kunen's Foundations of Mathematics. I think I have a solution but I am confused by one of the hints. By request, here is the text of the exercise. ...
4
votes
0answers
138 views

How to think about iterated ultrapowers?

I would like to gain some basic intuition about iterated ultrapowers. I am perfectly happy with accepting the construction and can see that it fits into a fundamental role in many places (for example, ...
4
votes
0answers
131 views

Combinatorial packages of N items [[How many distinct Boolean Expressions can be made using N variables]]

Using just the AND operator, the number of distinct packages that can be built from a set of size $n$, is simply $2^n$. If one adds the operators OR and XOR, how many packages can be built? That is, ...