Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

16
votes
0answers
358 views

Is every model of modular arithmetic either even or odd?

Modular Arithmetic (MA) has the same axioms as first order Peano Axioms (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$. ...
11
votes
0answers
168 views

The (un)decidability of Robinson-Arithmetic-without-Multiplication?

Take our old friend Robinson Arithmetic, and cut it down to a theory of successor and addition. To spell that out (just to ensure that we are singing from the same hymn sheet), take the first-order ...
11
votes
0answers
335 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 ...
9
votes
0answers
163 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 ...
9
votes
0answers
405 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
187 views

Could it be that Goldbach conjecture is undecidable?

The result closest to Goldbach conjecture is Chen's theorem [Sci. Sinica 16 157–176], the proposition ``1+2''. It is natural to ask if it is likely that under our arithmetic axioms the Goldbach ...
7
votes
0answers
117 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 ...
6
votes
0answers
45 views

Representation theorem for Heyting algebras?

A fundamental theorem by Stone asserts that any Boolean algebra is isomorphic to a subalgebra of the archetypical Boolean algebras, that is the power sets of a set $X$ (equipped with intersection, ...
6
votes
0answers
172 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
117 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 ...
6
votes
0answers
235 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 ...
6
votes
0answers
248 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 ...
5
votes
0answers
93 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
125 views

Gödel's Completeness Theorem and logical consequence

At the end of a long process of "rumination" on "old" math log textbooks, I've found the "missing link" - from my personal point of view - between some issues I've raised in the previous months : (i) ...
5
votes
0answers
130 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
268 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
107 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 ...
5
votes
0answers
361 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
120 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
62 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
96 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, ...
4
votes
0answers
46 views

Unification in languages without function symbols or with relational terms.

In case a logic formula is mechanically constructed, obtained as the specification of an expression in an imperative programming language for example, the functional constraints could be implicit in ...
4
votes
0answers
107 views

Relationship between paradoxes in logic and geometry/topology

Though I've been reading for years, this is my first question here. Believe it or not, I've tried the search feature- apologies if this is a duplicate. The main point of this post can be summarized ...
4
votes
0answers
152 views

Puzzle - zero knowledge proof

I am solving the following problem : I have edge-matching puzzles, where all pieces are squares and the grid has $n$*$n$ format. There is no global image to guide a puzzle solver. Despite the puzzles ...
4
votes
0answers
47 views

The quantifier “most”

It is well known that the quantifier "most", understood as "more than half the ps" is not first-order definable. This is one of the results Barwise and Cooper (1981: p122-3), in "Formal Semantics: the ...
4
votes
0answers
193 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 ...
4
votes
0answers
68 views

How to show the existence of appropriate faithful interpretation and theory?

I tried to solve this exercises, proposed in 'A Mathematical Introduction to logic' by Enderton §2.7 exercises 1. Assume that $L_0$ and $L_1$ are languages with the same parameters except that ...
4
votes
0answers
90 views

Infinite “String” of Implication Statements

This question is inspired by the conversations at Does this require transfinite induction? First of all, does an infinite string of implication statements have a conclusion? I don't think so, but I ...
4
votes
0answers
188 views

Difference between elementary submodel and elementary substructure

This is a really "elementary" question, forgive the pun. What is the difference between an elementary submodel and an elementary substructure (in first-order Logic)? Sincere thanks for help.
4
votes
0answers
77 views

What are the “ordinary” (e.g. arithmetic) consequences of the universe axiom?

Consider the first-order theory obtained by adjoining to ZFC (or, better, Mac Lane set theory) the Grothendieck–Verdier (or Bourbaki?) universe axiom: For each set $x$ there exists a Grothendieck ...
4
votes
0answers
165 views

What is the correspondence between the semantic compactness of logics and the compactness of Stone spaces?

According to the answer by François G. Dorais, we know that a logic $\mathfrak L$ is compact iff its Stone space of the Lindenbaum–Tarski algebra of the empty theory (w.r.t the deductive system) is ...
4
votes
0answers
318 views

Krivine Machine

Can someone please point out online resources to learn about Krivine Machine? My professor briefly touched it while teaching a course in Computer logic. google did not turn up much except some papers ...
4
votes
0answers
133 views

Cutest proof that PA proves its finitely axiomatised subtheories are consistent?

Back in 1952, Mostowski proved that PA proves the consistency of its finitely axiomatised sub-theories. Any pointers to particularly nice later proofs of this lovely result? Or indeed particular nice ...
4
votes
0answers
82 views

An “internal” condition on $T$ so that for the standard provability predicate, $T$ proves $\text{Pf}(\underline S)$ implies $T$ proves $S$?

This is probably quite basic, but I'd like to make sure I got this right. Regarding the proof of Goedel's first incompleteness theorem, say that we have $T$ containing $PA$ effectively axiomatizable ...
4
votes
0answers
193 views

Starting my nephew out on the journey to higher mathematics.

My nephew is 8 years old and shows great promise as a student. Sadly, as most of you know most programs in secondary education don't offer any foundational courses for higher mathematics. What ...
4
votes
0answers
224 views

Interesting applications of the cofinite topology?

Background: I'm doing some expository writing on intuitionistic logic and I have been toying with the idea of demonstrating its applicability via models where the denotations are taken from a Heyting ...
4
votes
0answers
264 views

logic lectures on youtube

Currently I am reading Logic an Structure by Dirk van Dalen (2008). As I am missing some basics I try to find related lectures on youtube. I frequently watch MIT, Stanford, and University of ...
3
votes
0answers
37 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...
3
votes
0answers
37 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...
3
votes
0answers
83 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. ...
3
votes
0answers
63 views

Models of infinite groups and 'Group-like' objects

Let $G$ be an infinite group, and for simplicity, we will assume that $G$ is also countable. Now, with $G$ in mind, we construct a new language $L_G=\{f_{a_i\_},f_{\_a_i}:a_i\in G\}$ where ...
3
votes
0answers
44 views

Efficient software for producing (expression) trees “on the fly,” with good editing (e.g. cut/copy/paste) facilities?

A formula like $\forall x \exists y(x+y=0)$ can be represented as a tree. Something like so: ...
3
votes
0answers
68 views

Finding a finite model

Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this: Suppose $L$ is a language which includes an infinite list ...
3
votes
0answers
40 views

Linear regression, reversing it back then.

Need's formatting, editing will take some time.
3
votes
0answers
47 views

Logic in closed symmetric monoidal categories; reference request.

Suppose we want an algebraic theory $T$ to be interpretable in any closed symmetric monoidal category $\mathbf{C}.$ I am thinking in particular of the case where $\mathbf{C}$ is the category of models ...
3
votes
0answers
96 views

Substitute Proof by Contradiction/Negation with Direct Proof or Proof by Contrapositive

When do proof by contradiction, or by negation, or direct proof, or proof by contrapositive all work equally well? When can any one be chosen as the proof form? I'm interested in a pragmatic answer ...
3
votes
0answers
63 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
3
votes
0answers
191 views

Convert a WFF to Clausal Form

I'm given the following question: Convert the following WFF into clausal form: \begin{equation*} \forall(X)(q(X)\to(\exists(Y)(\neg(p(X,Y)\vee r(X,Y))\to h(X,Y))\wedge f(X))) \end{equation*} ...
3
votes
0answers
62 views

Question on a Theorem from Chang-Keisler's Model Theory concerning $\Sigma^0_n$ sentences

The Theorem is 3.1.11 and states that for $n>0$ the following are equivalent : $\phi$ is equivalent both to a $\Sigma^0_{n+1}$ and a $\Pi^0_{n+1}$ sentence. $\phi$ is equivalent to a Boolean ...
3
votes
0answers
61 views

Are there some kind of “multialgebras” with terms or equations, where an operation can result with different values in different places?

Many-valued (multivalent, polivalent) operations are studied in multialgebras. Applied to a certain value of its argument, a many-valued operation o(x) can result in different values. But in ...