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)

22
votes
0answers
478 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 ...
18
votes
0answers
430 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 ...
13
votes
0answers
463 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 ...
12
votes
0answers
195 views

Spanning the reals with a small set - choicelessly

Working in ZF (so, no choice): is it possible that there is a set of reals $X$ such that $\vert X\vert<\mathbb{R}$, but $X$ generates $\mathbb{R}$ as a subgroup under addition? This seems ...
12
votes
0answers
196 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 ...
11
votes
0answers
209 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
222 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
178 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
181 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
160 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 ...
9
votes
0answers
534 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 ...
8
votes
0answers
117 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
114 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
97 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
234 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
157 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
334 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
154 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
168 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
91 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
165 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
270 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
261 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
348 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
111 views
+50

Injections between distinct models of the simply typed lambda calculus

Let a model of the simply typed lambda calculus be a Cartesian-closed functor from $C_T$ to Set, where $C_T$ is a free CCC (as in e.g. this reference, p. 83.) The simple case of one or two primitive ...
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
81 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
87 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
80 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
63 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
61 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
321 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
993 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
320 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
739 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
37 views

Determinacy and uniformization

It's known that $PD$ implies projective uniformization. Assuming $AD$, is there an analogous theorem that holds for all subsets of the plane (where the uniformizing functions are reasonably definable ...
4
votes
0answers
67 views

How to prove $\forall x,y\in\mathbb{R}: x^2+y^2 = (x+y)^2 \Leftrightarrow x=0\lor y=0?$

The question I really have is the structure and I am not sure to use pack-unpack or not. Here is my try: Let $x,y\in\mathbb{R}$ Assume $x^2+y^2 = (x+y)^2$ Then $x^2+y^2 = x^2+2xy+y^2$ #by ...
4
votes
0answers
52 views

Completing ordered Fields

How do these two forms of completion behave (in NBG) when fields are authorized to be proper classes? $(i)$: Every ordered field has a real closed, algebraic extension. $(ii$): Every ordered field ...
4
votes
0answers
116 views

Why is recursion theory suffering from terminological bloat?

Several questions on MSE in recent months and most recently this one have made me feel that recursion theory is suffering from terminology bloat. Why have so many synonyms for "recursive" and ...
4
votes
0answers
45 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
72 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
79 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
99 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
113 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
120 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 ...