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.
11
votes
0answers
183 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 ...
9
votes
0answers
212 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)$.
...
9
votes
0answers
230 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 ...
8
votes
0answers
288 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
54 views
A question on non-standard ordinals in $\alpha-$recursion
Let $M$ be an admissible set, namely, $M\models KP$ where KP stands for axioms of Kripke–Platek set theory. Denote $\beta=M\cap ORD$ where $ORD$ is the class of ordinals. I wanted to prove ...
6
votes
0answers
85 views
Is there a useful Galois connection between Languages and Grammars?
I've just beginning to learn logic and proof theory - and the following rather vague and perhaps ill-formed question occurred to me.
Given an alphabet it's straightforward to construct the Language, ...
6
votes
0answers
169 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
74 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
72 views
Functions and metafunctions
I didn't get any responses to this question the first time around, so I've tried rewriting parts of it. If there's anything glaringly wrong with the questions I'm asking, please leave a comment!
...
5
votes
0answers
79 views
undecidability of the structure $(\omega,+,2^n)$
Is the structure $(\omega,+,2^n)$ undecidable? There is no easy way to define multiplication using a formula.
5
votes
0answers
113 views
Admissible ordinals…
a little question about admissible sets:
Is every $\mathfrak{M}$-admissible ordinals an admissible ordinal ? where $\mathfrak{M}$ is a
$L$-structure over $L=\{R_1,\dots,R_k \}$.
Thanks.
5
votes
0answers
151 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
58 views
Axiom of Choice-esque argument to show that a proof of a statement exists without actually giving a proof
What if the set of all well-formed statements in ZFC formed a kind of pseudo-category where a morphism f between objects A, B represented a formal proof that A implied B? What if that category could ...
4
votes
0answers
59 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
55 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
98 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) \}
...
4
votes
0answers
96 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
74 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
128 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 ...
4
votes
0answers
104 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
68 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
181 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 ...
3
votes
0answers
36 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
34 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 ...
3
votes
0answers
80 views
An Axiomatic Treatment of Mathematics from First Principles to the Major Subjects?
I'm looking for a book - more likely, books - that could take me from the axioms of mathematical logic up to the major subjects of mathematics, like analysis, algebra, geometry, etc.
For example, a ...
3
votes
0answers
59 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.
3
votes
0answers
34 views
Evaluate signatures logic
I need some help of the logic experts. I would like to evaluate the following signatures $\sigma$, such that $|\sigma^{Op}|=2$ and $t$ is a $\sigma$ term. Sometimes there are no solutions and ...
3
votes
0answers
42 views
Constructing an incomplete ordered field satisfying the nested interval property
Motivated by a problematic exercise in an analysis textbook, I decided to search for an example of an ordered field which satisfies the nested interval property yet fails to be complete.
I first ...
3
votes
0answers
33 views
Which CSL rules hold in Łukasiewicz's 3-valued logic?
CSL is classical logic. So I'm talking about the basic introduction and elimination rules (conditional, biconditional, disjunction, conjunction and negation).
I'm not talking about his ...
3
votes
0answers
63 views
The Logic of Satisfiability?
I am aware of some study into the logic of provability. It is generally taken to be intermediate in strength between S4 and S5 modal logics. Is there corresponding study into something like the logic ...
3
votes
0answers
87 views
What kind of logic is mine?
I'm completely unfamiliar with terminologies of mathematical logic and I have never taken any 'mathematical logic' class.
The first time i started to study Mathematics (Set Theory), I memorized the ...
3
votes
0answers
135 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 ...
3
votes
0answers
67 views
Existence of elementary substructures of a uncountable structure over a countable language
Let $\kappa$ be an regular uncountable cardinal carrying a $\tau$-structure for some countable language $\tau$. What can be said regarding the existence of ordinals $\alpha <\kappa$ carrying ...
3
votes
0answers
68 views
An application of Descriptive set theory in Model theory.
In page 162 of D.Marker Model theory book he proved that the set $S_n(F,T)$ of all $F$-types realized by some $n$-tuple in some countable model of $T$ is analytic (this is with any $F$:= $countable$ ...
3
votes
0answers
123 views
Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$?
There is a recursive definition of the set of squares which uses only addition:
$CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x
\lt z) \wedge (z \lt y)⇒\neg IS(z)$
$IS(x)⇔ x=0 ...
3
votes
0answers
143 views
Does the concept of predicativity need to be formalized to go beyond Feferman-Schutte ordinal?
Feferman-Schütte ordinal is sometimes said to be:
....first impredicative ordinal, though this is controversial, partly because there is no generally accepted precise definition of "predicative". ...
3
votes
0answers
117 views
Is there such a thing as “second-order-undecidability”? And what about higher order Undecidability statements?
I know that there are statements that are neither provable nor disprovable within some set of axioms, and I also know that such statements are called undecidable. Please allow me to call these ...
3
votes
0answers
215 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 ...
2
votes
0answers
29 views
What is the formulation of the Least Upper Bound propierty in First Order Logic?
I've been readining about the completeness Godel's theorems. Accordingly, the axioms of $R$ in first order logic make up one of these sets that is complete and consistent. But I've always seen the ...
2
votes
0answers
42 views
A question about consistent axiomatizable extensions of PA
Given $T\supset PA$ to be consistent and axiomatizable, I've been told that when $G\subset T$ is finite, and $\phi$ is a universal sentence, then:
($\star$) $PA\vdash ...
2
votes
0answers
34 views
What is the (propositional) logic associated with an orthomodular lattice?
In Quantum Mechanics the space of projections on the associated Hilbert Space of States forms an Orthomodular Lattice. Von Neumann calls this a Quantum Logic. When projections commute they generate a ...
2
votes
0answers
125 views
How to show Simp. and Creat. are $\Sigma^0_2$-Hard
Let Simp={$e:W_e$ is simple} and Creat={$e:W_e$ is creative}
I'm having troubles showing these sets are $\Sigma^0_2$-Hard, ie that any $\Sigma^0_2$ set can be many-one reduced to them.
I've already ...
2
votes
0answers
58 views
What exactly is Levy hierarchy?
Wikipedia lacks information on Levy hierarchy, so what exactly is Levy hierarchy? This will tell me what $\Delta_0$ means in KP set theory.
2
votes
0answers
83 views
Models of infinite cardinal and compactness
I'm stuck with this problem:
$L$ is first-order language with identity and $L_q$ a language obtained by adding to $L$ the quantifier $Q$. If $P$ is a formula and $x$ a variable, $QxP$ is a formula ...
2
votes
0answers
164 views
Deciding whether a formula is provable with a fixed number of universal generalizations
Let $y$ be Godel number of some formula which is derivable in some first-order logic. $F(y,n)$ is true if and only if the number of usage $Gen$(universal generalization) inference rule in any ...
2
votes
0answers
38 views
Is the validity of the Skolemization of a sentence A infers the validity of A?
I have a claim I need to prove or disprove. Let Sk(A) be the Skolemization of A (A is a sentence).
If Sk(A) is valid then A is also valid.
In other exercise I was asked if A is valid then Sk(A) is ...
2
votes
0answers
193 views
First Order logic with vertex covers
Let $G=(V,E)$ be a directed graph. Let $E$ be a binary relation such that $(x,y) \in E$ iff there is an edge from vertex $x$ to vertex $y$.
Let the world of first order interpretation be the set of ...
2
votes
0answers
116 views
Showing a formula is a tautology
I'm currently enrolled in a introductory course on logic and until now everything has been going great. I'm having some trouble with applying monotonicity and the strengthening/weakening of ...
2
votes
0answers
62 views
Ordering of multisets in “Paramodulation based theorem proving”
I'm reading this paper: http://www.lsi.upc.edu/~albert/papers/handbook.ps.gz
and I can't understand a part of it. it defines an ordering on multisets (it defines a multiset over $A$ as a function $A ...
2
votes
0answers
163 views
Sum and product of an ultrafilter
I know the following simple fact is true, but I can't find a good proof:
Over the naturals, the only ultrafilter $\mathcal U$ such that $\mathcal U \oplus \mathcal U = \mathcal U \odot \mathcal U$ is ...
