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)

13
votes
0answers
310 views

Model existence for infinitary logics

One of the problems of infinitary logic is that it is possible for compactness to fail in a spectacular way: for example, one can concoct an inconsistent set of axioms whose proper subsets are all ...
13
votes
0answers
323 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)$. ...
10
votes
0answers
302 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
146 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
385 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 ...
6
votes
0answers
111 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
212 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
234 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
101 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 ...
5
votes
0answers
104 views

Axiom of Choice - Type Theory (Proof)

Background In Intuitionistic Type Theory (p. 27-28), Martin Löf provides a proof of the axiom of choice that is constructively valid. This version is considerably weaker than the ordinary set theory ...
5
votes
0answers
115 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
261 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
100 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
291 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
112 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
89 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
72 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) ...
4
votes
0answers
41 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
136 views

Was Fermat's last theorem proved based on Peano's postulates?

Is the proof of Fermat's last theorem solely based on the Peano's postulates $+$ first order logic? Or it contains other axiomatic systems as well? What does it mean from foundations of math ...
4
votes
0answers
91 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
143 views

Foundational theories, their uses, interactions and comparisons?

Until now, I heard that there are some theories for building mathematical objects (or at least it is what it seems to my poor knowledge). Some of these are: Set theory; Logic; Category theory; Type ...
4
votes
0answers
116 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
44 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
186 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
61 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
138 views

Proving Tychonoff's theorem with the Compactness theorem of logic

It seems to be known that Tychonoff's Theorem for Hausdorff spaces and the Compactness theorem of first order logic are both equivalent over ZF to the ultrafilter lemma. Does anyone know a slick proof ...
4
votes
0answers
69 views

Any work on Automated theorem proving by Pattern Recognition?

Are there some mathematicians or papers about Advanced ATP by Pattern recognition? Pattern recognition: recognize the patter from mathematic sentence, proof sequence.
4
votes
0answers
80 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
156 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
76 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
153 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
258 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
131 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
80 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
188 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
215 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
252 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

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
67 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
49 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
123 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
196 views

Under the impact of Gödel's incompleteness theorems, are the conclusions of statistics reliable?

After I read the Gödel's incompleteness theorems, I am confused about the following: Could you tell me if the conclusions of mathematical statistics are reliable? Gödel's incompleteness theorems ...
3
votes
0answers
59 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
60 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 ...
3
votes
0answers
81 views

generating complete consistent theories

This is a model theoretic question. I was reading Kremer & Mints's Dynamic topological logic paper, and it mentioned that by a “standard argument”, every consistent formula is a member of some ...
3
votes
0answers
52 views

temporal operators: interpreting them topologically in a dynamic topological system

There's a paper that i've been reading recently called "Dynamic Topological Logic" which can be found at: http://individual.utoronto.ca/philipkremer/onlinepapers/DTL.pdf. I have a question about ...
3
votes
0answers
117 views

meaning of ``partial converse''

In the definition of a commutative ring $(R,+,\times)$, one of the postulates given is that of uniqueness, i.e. that $$ a=a', b=b'\implies a+b=a'+b', ab=a' b'.$$ The text states that for the system ...
3
votes
0answers
78 views

Notation $X/Y$ in Vickers 'Topology via Logic

I am currently working through Vickers' book 'Topology via Logic'. At one point (Proof of Theorem 4.4.2) he uses the notation $X/Y = \{z\in S \mid \forall y\in Y: y\wedge z\in X\}$ (and $X\wedge Y = ...
3
votes
0answers
53 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
3
votes
0answers
95 views

Definition(s) for variable binding in first-order logic

The following statement made me realize that variable binding can be defined in first-order logic: The same holds for λ terms to define functions. There is no reason that they could not be ...