Questions tagged [lo.logic]
first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, theories of truth, truth revision, consistency.
5,134
questions
6
votes
2
answers
1k
views
What are the models of Peano Arithmetic plus the negation of the corresponding Gödel sentence like?
Since the Godel sentence for PA (G henceforth) is independent of PA, if PA is consistent, so is PA plus not-G. Thus, since PA is a first-order theory, if PA is consistent, PA plus not-G has some ...
6
votes
3
answers
630
views
Why does the Solovay-Tennenbaum theorem work?
I have decided to learn iterations at long last, and I am reading through Jech's Set Theory for now. The standard example after explaining what is an iteration with finite support is the following ...
6
votes
3
answers
937
views
Discontinuous functions without removable discontinuities
A function $f:\mathbb{R}\rightarrow \mathbb{R}$ has a removable discontinuity at a given real $x$ in case the left and right limits are equal but not to the function value, i.e. $f(x+)=f(x-)$ but $f(x)...
6
votes
5
answers
675
views
Stronger theorem not resulting from proof analysis
Suppose that we proved $\varphi$ from a theory $T$. Often we ask whether or not we could have proved $\varphi$ with a weaker theory, to find out we usually analyze the proof and try to figure out ...
6
votes
2
answers
483
views
A continuous notion of realizability
I have been interested in non-classical logics, off and on, for quite a while. This question is probably very basic, and I hope it is not too low-level for MO. My question stems from an attempt to ...
6
votes
4
answers
1k
views
Example of two structures
This is probably a very trivial question, still I don't seem to find an answer.
I'd like to see an example (in some language) of two countable structures $\mathcal{M}_1 $ and $ \mathcal{M}_2 $ with $...
6
votes
1
answer
1k
views
Can we hope to solve all Diophantine equations?
According to Godel result, neither ZFC nor other particular theory is strong enough to resolve all questions about, say, Diophantine equations. But maybe we can hope that a sequence of theories will ...
6
votes
2
answers
860
views
A specific Model of ZFC
In his paper "Some Second Order Set Theory", Joel Hamkins asked whether there is a model of set theory $V$ that is elementary equivalent to $V[G]$, Whenever $G$ is $V$-generic for the collapse of a ...
6
votes
2
answers
2k
views
Mathematics with the negation of AC
Clearly Very important results in Math require the Axiom of choice, for example "any vector space has a base". But in the absence of AC (i.e., only in ZF) it is possible that a vector space has no ...
6
votes
3
answers
785
views
Is it consistent with ZFC that for all ordinals $\alpha, \beta < \omega$ it holds that $2^{\aleph_\alpha} = 2^{\aleph_\beta}$?
Let $\gamma=\omega$ (the first transfinite ordinal). Is it consistent with ZFC that for all ordinals $\alpha, \beta < \gamma$ it holds that $2^{\aleph_\alpha} = 2^{\aleph_\beta}$?
If yes, can the ...
6
votes
3
answers
1k
views
A question about Transfinite Induction
The Transfinite Induction says: Let $\mathbf{P}(x)$ is a property, assume that, for all ordinal numbers $\alpha $ : If $\mathbf{P}(\beta)$ holds for all $\beta < \alpha$, then $\mathbf{P}(\alpha)$ ...
6
votes
5
answers
2k
views
A book explaining power and limitations of Peano Axioms?
Are there books or survey articles explaining the subject to a non-expert? To clarify what I mean, here is a couple of issues that I would like to read about. (I am mainly interested in references but ...
6
votes
2
answers
904
views
Defining rational numbers without using quotients or 0-truncations
Most definitions of the rational numbers as a higher inductive type in univalent homotopy type theory (such as those in the cubical Agda library for example) require either the use of a quotient set ...
6
votes
2
answers
1k
views
Ordinal analysis and proofs of consistency
$\epsilon_0$ is the proof-theoretic ordinal of PA. Gentzen proved the consistency of Peano's first-order axioms for arithmetic using primitive recursive arithmetic and induction up to $\epsilon_0$.
...
6
votes
2
answers
536
views
Is there a perfect set of ground model reals in the Cohen extension?
This question is motivated by the "interesting tidbit" in Hamkins' response here: https://mathoverflow.net/a/99025/10671, in which he demonstrates that, after Cohen forcing, there is a perfect set ...
6
votes
2
answers
1k
views
Embedding property of weakly compact cardinals
One of the characterizations of $\kappa$ being a weakly compact cardinal is being inaccessible, and for every $\kappa$-model $M$, there is a [$\kappa$-model] $N$ and an elementary embedding $j\colon M\...
6
votes
2
answers
804
views
The theory of a model of a theory that knows all formulas true in almost all its models
We are in first order logic world.
Let $\sigma$ be a finite signature and $T$ a consistent theory of $\sigma$.
Due to Löwenheim–Skolem theorem, we can consider the $\underline{set}$ of all at most ...
6
votes
2
answers
687
views
Are exponentials in categorical models of linear logic harmful?
Categorical models for linear logic with $\otimes$, $1$, $\&$, $\top$, $\oplus$, $0$, and $\multimap$ are typically symmetric monoidal closed categories (for modeling $\otimes$, $1$, and $\...
6
votes
3
answers
1k
views
computational complexity of primitive recursive functions
If we have a rewrite system for primitive recursive functions, which simplifies each term according to how the function was defined, then what is the computational complexity of this calculation? That ...
6
votes
3
answers
1k
views
Set theory inside arithmetics via the Ackermann yoga
Among the basic results of logic which, simple as they are, never fail to intrigue me, is Ackermann's interpretation of ZF-Infinity in PA (see for refs this MO question and here for an excellent ...
6
votes
3
answers
598
views
Is the union of two conservative extensions of a theory conservative?
Background/Motivation
A theory T over a signature(language) Σ is a set of formulae over Σ. These formulae are called the non-logical axioms of T.
To talk about what is provable in T we can agree on ...
6
votes
2
answers
599
views
What categories correspond to the typed lambda calculus with parametric types?
the unadorned typed lambda calculus correspond to the closed cartesian categories, but if we add in dependent or parametric types how are they then characterised?
6
votes
3
answers
821
views
Surjective Maps onto $\aleph$-numbers
We denote by $\frak p\le q$ the abbreviation that there is $f:\frak p\to q$ which is injective, and by $\frak p\le^\ast q$ we abbreviate that there is a surjection from $\frak q$ onto $\frak p$.
If $...
6
votes
2
answers
685
views
Cases where multiple induction steps are provably required
I am looking for references for theorems of the form:
1) Any proof of theorem $X$ requires $n$ applications of induction axioms
and especially
2) Any proof of theorem $X$ requires $n$ nested ...
6
votes
2
answers
692
views
Reasoning Using Countable Subsets of Real Numbers
The purpose of my question is trying to understand whether, in some cases, we can achieve greater certainty of reasoning (say when dealing with statements about natural numbers, integers or rational ...
6
votes
2
answers
924
views
Are omega-consistent extensions of PA always consistent with each other?
The question is as in the title. In the edit history you can find my attempt to formalise the question, but that was a failure, for reasons stated clearly in the comments. Thus, my question is just:
...
6
votes
3
answers
580
views
The size of Lindelof space
Question. Suppose that $X$ is a Lindelof space such
that every point of $X$ is a $G_{\delta}$-point. Then is it true that $|X| ≤ 2^{\omega}$?
6
votes
3
answers
371
views
Does this property of a first-order structure imply categoricity?
Let $\mathfrak{A}$ be a first-order structure over a relational language and let $\kappa$ be an infinite cardinal. Lets say that $\mathfrak{A}$ has the $\kappa$-property if for every structure $\...
6
votes
2
answers
489
views
What is the name of this type of groups?
Suppose $A$ is a finite set and $\Sigma=A\cup A^{-1}$. Let $L\subseteq \Sigma^{\ast}$ be a regular language on the alphabet $\Sigma$. Is there a common name for the group $G$ presented as:
$$G=\langle ...
6
votes
2
answers
743
views
Representation of μ-recursive functions
Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function?
According to Wikipedia, any μ-recursive function can be expressed as the ...
6
votes
2
answers
599
views
Are undecidable consequences of Con recursively enumerable?
Let $X\subset\Pi_1^0$ be the set of statements which are
provable in PA$+$Con(PA) but independent of PA.
Is $X$ recursively enumerable?
6
votes
2
answers
1k
views
Why can't mathematics be formalised in terms of classes rather than sets? [closed]
I've always been curious about the seeming compulsion to found mathematics upon sets, be it ZF(C) or some other system. Of course, there are other approaches these days like category theory and type ...
6
votes
4
answers
1k
views
Is every Heyting algebra the Lindenbaum algebra of an intuitionistic first order theory?
This question comes after the comments in the recent related question Sigma-complete Lindenbaum algebras?, but in its current form is sufficiently different in my opinion, and so I decided to follow ...
6
votes
1
answer
859
views
"$\kappa$ strongly inaccessible" = "every function $f:V_\kappa\to V_\kappa$ can be self-applied"?
Strongly inaccessible cardinals are usually introduced either as (a) cardinalities of models of ZFC or (b) cardinals which are not the power set of a smaller cardinal nor the supremum of a set with ...
6
votes
2
answers
522
views
How complicated is the formula expressing that a set is non-measurable?
The question is exactly stated by the title, i.e. how complicated is the formula $\psi(x)$ (in the language of set theory) expressing that a given set of reals $x$ is non-measurable?
A second ...
6
votes
2
answers
571
views
Forcing with product vs. box product
If we want to add one real number the simplest way to do it is to use Cohen forcing. The poset is $\lbrace p\colon n\to 2\mid n\in\omega\rbrace$ which is a countable set. We can think of this as ...
6
votes
3
answers
3k
views
Is it important to distinguish between meta-theory and theory?
In his book on set theory, Kunen often emphasizes how important it is to distinguish between statements in the theory and the meta-theory. I have two questions:
a) When we are talking about set theory,...
6
votes
5
answers
2k
views
Set theories that do require the existence of urelements?
I am looking for an axiomatic set theory that not only admits the existence of urelements/atoms (via two-sortedness or an additional unary predicate) but requires it, e.g. by an axiom like "for each ...
6
votes
1
answer
804
views
Generalize the Gödel sentence requires a fixed point theorem
I am trying to generalize the Gödel sentence as follows.
Define a pair of sentence $A$ and $B$ such that:
\begin{gather*}
A := \lnot \operatorname{Prov}(\hat B) \\
B := \operatorname{Prov}(\hat A)
\...
6
votes
3
answers
514
views
Limits of determinacy on reals
For $X\subseteq\mathbb{R}^\omega$, say that $X$ is determined if the associated game on $\mathbb{R}$ of length $\omega$ (players I and II alternate playing reals, player I wins iff the sequence built ...
6
votes
2
answers
706
views
Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one reductions)?
Most well known sets in $\Sigma_1 \setminus\Delta_0$, such as the
Halting problem, are complete in $\Sigma_1$, relatively to the
many-to-one reduction. In fact I don't know any example of a (non ...
6
votes
2
answers
197
views
Separation of almost disjoint families by ground model almost disjoint families
Suppose that $V$ is a model of $\sf ZFC$, and for concreteness I should point that at this point I am interested in $V=L$ as a ground model.
Suppose that $V[c]$ is a Cohen extension of $V$ where $c$ ...
6
votes
2
answers
344
views
Smallest base to reach partial recursive functions as a closure of unbound search
It is customary to define the class of partial recursive functions by taking the set of primitive recursive functions $PR$ and taking closure over unbound search operation.
Do we need the "whole&...
6
votes
3
answers
968
views
Provability in Second-Order Arithmetic without the Successor Axiom
Consider second-order Peano Arithmetic Z2, i.e. the two-sorted first-order theory with induction and comprehension. Remove the assumption about the totality of the successor relationship (the ...
6
votes
2
answers
532
views
From the product lemma to to a result about powersets
Recall the product lemma from Easton's famous paper, which tells us something about when we have a forcing notion (which may be a proper class) that splits as a product with one factor $\lambda^+$-cc ...
6
votes
2
answers
912
views
Subscript 0 in Reverse Mathematics
What does the subscript 0 mean on terms like $\mathsf{ATR}_0$? Does it mean the same thing in $\Pi^1_k\text{-}\mathsf{CA}_0$?
If I frame higher order analogues of these, should I change that ...
6
votes
2
answers
376
views
Measures that are not OD
Is anything known about the consistency strength of the statement:
"There is a normal measure (on a cardinal) that is not ordinal-definable"?
In particular, is it consistent relative to the ...
6
votes
2
answers
468
views
Reconstructing a model from its definable sets
Let $\mathcal{M}$ be an infinite model of a first-order language, and for each $n$, let $\mathcal{B}_n$ be the algebra of definable sets of $n$-tuples from $|\mathcal{M}|$.
Given $\{\mathcal{B}_n\mid ...
6
votes
3
answers
874
views
Fraissé limit of the finite linear orderings
Hodges in his Shorter Model Theory promises to show "in what sense the finite linear orderings 'tend to' the rationals rather than, say, the ordering of the integers" (p. 160). After going through his ...
6
votes
2
answers
1k
views
Simple book on model theory
I was expressed by how Mendelson describes models in his Introduction to mathematical logic. Now I am looking for a nice model theory guide. The book (video source, etc.) must:
Include the concrete ...