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.

Filter by
Sorted by
Tagged with
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 ...
Pablo's user avatar
  • 61
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 ...
Asaf Karagila's user avatar
  • 38.1k
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)...
Sam Sanders's user avatar
  • 3,901
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 ...
Noah Schweber's user avatar
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 $...
ftonti's user avatar
  • 382
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 ...
Bogdan Grechuk's user avatar
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 ...
Rahman. M's user avatar
  • 2,341
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 ...
user avatar
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 ...
Vladimir Reshetnikov's user avatar
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)$ ...
Dong xiaowei's user avatar
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 ...
Sergei Ivanov's user avatar
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 ...
user avatar
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$. ...
John Baez's user avatar
  • 21.3k
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 ...
jonasreitz's user avatar
  • 1,166
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\...
Asaf Karagila's user avatar
  • 38.1k
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 ...
P. Grabowski's user avatar
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 $\...
Wolfgang Jeltsch's user avatar
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 ...
AKS's user avatar
  • 63
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 ...
Mirco A. Mannucci's user avatar
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 ...
Giacomo Cozzi's user avatar
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?
Mozibur Ullah's user avatar
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 $...
Asaf Karagila's user avatar
  • 38.1k
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 ...
manzana's user avatar
  • 335
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 ...
SSequence's user avatar
  • 861
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: ...
N. Virgo's user avatar
  • 1,316
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}$?
user avatar
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 $\...
Ramiro de la Vega's user avatar
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 ...
Sh.M1972's user avatar
  • 2,183
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 ...
Mark T's user avatar
  • 85
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?
Alex Gavrilov's user avatar
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 ...
Noldorin's user avatar
  • 800
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 ...
godelian's user avatar
  • 5,642
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 ...
Adam's user avatar
  • 3,247
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 ...
user38200's user avatar
  • 1,446
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 ...
Asaf Karagila's user avatar
  • 38.1k
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,...
Martin Brandenburg's user avatar
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 ...
Hans-Peter Stricker's user avatar
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) \...
Thuc Hoang's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Armando Matos's user avatar
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$ ...
Asaf Karagila's user avatar
  • 38.1k
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&...
user avatar
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 ...
abo's user avatar
  • 1,844
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 ...
David Roberts's user avatar
  • 33.8k
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 ...
Colin McLarty's user avatar
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 ...
Trevor Wilson's user avatar
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 ...
Henry Towsner's user avatar
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 ...
Hans-Peter Stricker's user avatar
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 ...
Rebel Yell's user avatar

1
45 46
47
48 49
103