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
4 votes
1 answer
185 views

Can Category theory be founded in set theory using worldly cardinals instead of inaccessibles?

What is exactly demanded for a set theoretic foundation of Category theory? I saw generally two main approaches. One is Muller's who did the work in Ackermann's set theory, but his criteria seem to ...
user avatar
0 votes
0 answers
56 views

What's the consistency strength of adding this inference rule to Ackermann's set theory?

Working in the language of Ackermann set theory: Let $\phi(\vec{P},\vec{x})$ be a formula not using the symbol $V$, where $\vec{P}$ are predicate symbols definable in the language of set theory, and $\...
user avatar
10 votes
0 answers
274 views

Definition of "galaxy", due to Sabbagh/Samuel

Gabriel Sabbagh, a PhD student of Pierre Samuel, called his thesis Ensembles artiniens, univers et galaxies. I learned from a recent talk of Colin McLarty that Grothendieck, in his 1973 Buffalo ...
user avatar
4 votes
1 answer
64 views

Computable functionals avoiding embeddings of linear orderings

Given a linear order $\mathcal{S}$, let $\mathbb{A}_\mathcal{S}$ be the class of all ordertypes which do not embed $\mathcal{S}$ (= do not have a suborder isomorphic to $\mathcal{S}$). Say that a ...
user avatar
-1 votes
0 answers
58 views

" for all x in E , we have p(x) " [migrated]

Let E be an empty set . why the assertion "$(\forall x \in E) , p(x)$ " is true ??
user avatar
3 votes
1 answer
84 views

Is there a minimal first-order model that has IP theory?

I'm hoping to (prove that one cannot) find an infinite first-order $\mathcal{M}$ that is: Minimal (All definable subsets of $\mathcal{M}$ are finite or cofinite) IP (has the independence property) ...
user avatar
0 votes
0 answers
137 views

Can Set theory be interpreted in Relational Mereology?

In a posting to MathStackExchange, I've presented a theory of rudimentary relations having a rudimentary kind of membership together with a primitive ordered pairing with the aim for it to capture the ...
user avatar
2 votes
0 answers
63 views

When do Borel propositional theories have topologically tame truth assignments?

Let $(P_r)_{r \in \mathbb{R}}$ be an $\mathbb{R}$-indexed family of propositional variables. Let $\mathcal{L}$ be the collection of all propositional sentences formed from the variables $(P_r)_{r \in \...
user avatar
  • 6,384
4 votes
0 answers
88 views

Does second-order logic satisfy Craig interpolation for second-order languages?

(For simplicity, all languages are relational.) In analogy with first-order languages, say that a second-order language is a set of relation symbols of two kinds: first-order relation symbols and ...
user avatar
1 vote
0 answers
29 views

Can we add the singleton map to $\sf NFP$?

In $\sf NF(U)$ it is known that the singleton map $(x \mapsto \{x\})$ is not a set, which is a source of a lot of extremely counter-intuitive results in $\sf NF(U)$. However, a weakening of the ...
user avatar
6 votes
1 answer
242 views

Consistency strength of an attempt at higher order set theory

Work in a theory with (deep breath) a countable number of primitives denoted with capital letters from the end of the alphabet with numerical subscripts $\{X_n,Y_n,Z_n,\dots\}_{n<\omega}$ ...
user avatar
  • 6,601
2 votes
0 answers
74 views

Can this predicative kind of type-set theory reach the consistency of ${\sf Z}_2$?

Add a primitive total one place fuction symbol $\tau$, and a primitive binary relation $<$, to the language of set theory. Add the following axioms: Extensionality: $\forall z \, (z \in x \iff z\in ...
user avatar
6 votes
0 answers
266 views

Are there quantifiers that require multiple "steps" to define?

(Below I conflate quantifiers and quantifier symbols in a couple places for readability; I can change that if that actually makes things less readable.) For the purposes of this question, an $n$-ary ...
user avatar
8 votes
1 answer
444 views

Where was the Cantor normal form theorem first proved?

We all take for granted the theorem that every ordinal $\alpha > 0$ has a Cantor normal form, and there are plenty of proofs of it, some of which are on this site. However, where was it proved? Was ...
user avatar
  • 470
-1 votes
0 answers
30 views

A dumb axiom of collection [migrated]

Add to $ZFC$ the following axiom: Dumb Collection. For any predicate $\phi$ such that there exists a set $y$ satisfying $\phi$, there exists a nonempty set $x$ whose members are precisely the sets $y$...
user avatar
  • 6,601
1 vote
0 answers
173 views

Does ${\sf ZC + Universes + ZFC}^V$ meet Muller's criteria for a founding theory of Mathematics?

I was re-thinking Muller's criteria in Sets, Classes and Categories: page 14 for a theory that founds Mathematics. To him, it should be able to be a foundation of Category Theory. He lays down six ...
user avatar
1 vote
0 answers
81 views

Can all stages of the cumulative hierarchy beyond $V_\omega$ violate the weak partition principle?

This question is a follow up of this. Is it consistent for ALL infinite stages $V_{\alpha > \omega}$ of the cumulative hierarchy of $\sf ZF$, to violate the weak partition principle? That is, each ...
user avatar
5 votes
1 answer
132 views

Can a stage of the cumulative hierarchy violate the partition principle?

If we violate the partition principle and add to $\sf ZF$ the axiom that there exists a set $X$ that has a partition on it that is greater in cardinality than the set of singleton subsets of $X$. Can ...
user avatar
7 votes
1 answer
387 views

Has Goedel's Second Incompleteness Theorem been proven using Lawvere's Fixed Point Theorem?

This question is a request for assistance in surveying the existing literature on applications of Lawvere's Fixed Point Theorem (LFPT). Yanofsky [0] has demonstrated several applications of LFPT to ...
user avatar
  • 73
10 votes
0 answers
183 views

Examples of statements that are valid in every spatial topos

I am looking for statements¹ that, when interpreted in the internal language of a topos, are valid in all spatial toposes (i.e., the topos of sheaves of any topological space) that are not valid in ...
user avatar
  • 22.1k
2 votes
0 answers
93 views

Internal language of the Sierpiński topos

What is an internal language of the Sierpiński topos, which is defined as arising from the category $\mathsf{Set}^{\to}$, the category of arrows in $\mathsf{Set}$? Or more generally, is there a rough ...
user avatar
  • 437
4 votes
0 answers
199 views

How much "finitary combinatorics" can be emulated by an infinite Dedekind-finite set?

Throughout, we work in $\mathsf{ZF}$. Let $[n]=\{1,...,n\}$. Given a set $X$ and a first-order sentence $\varphi$, let $M_X(\varphi)$ be the set of isomorphism types of models of $\varphi$ with ...
user avatar
3 votes
2 answers
211 views

MAD family with the choosability property

By $[\omega]^\omega$ we denote the collection of infinite subsets of $\omega$. Two sets $A,B\in[\omega]^\omega$ are said to be almost disjoint if $A\cap B$ is finite. An almost disjoint family is a ...
user avatar
2 votes
0 answers
195 views

Pairs vs. two pieces: is the usual proof model-theoretically-optimal?

(For clarity, I'll use $R,S$ for binary relation symbols and $A,B$ for actual binary relations.) There is an equality between the numbers (up to isomorphism in the appropriate sense) of partitions of ...
user avatar
1 vote
0 answers
107 views

Can all relations and functions be implemented as sets in some fragments of set theory?

Define wholly stratified $\sf NF$ to be $\sf NF$ with its language restricted to stratified expressions. In this theory we can arrive at a general implementation of tuples, that is: $\langle x_1,..,...
user avatar
2 votes
1 answer
111 views

Codependent types in type theory

The nLab's article on coinductive types here states that There is an obstacle to the complete dualization of the usual rules for inductive types in homotopy type theory, including dualizing the ...
user avatar
1 vote
0 answers
86 views

Quantifying Gödel's Incompleteness Theorem and Sparsity of Examples [duplicate]

We know from Gödel's First Incompleteness Theorem that there are true statements in the natural numbers that have no proof. Obviously we know of many that do ("theorems"). Are results known ...
user avatar
  • 111
5 votes
1 answer
343 views

Notation classifying topos

The classifying topos of a geometric theory $\mathbb T$ is a topos $\mathcal E_\mathbb T$ such that for any other Grothendieck topos $\mathcal E$, the category of geometric morphisms from $\mathcal E_\...
user avatar
12 votes
2 answers
864 views

Is there a proof of strong normalisation that uses ordinal numbers?

I am currently trying to find a proof for strong normalisation of an extension of $\lambda$-calculus. I've tried several approaches and one would be to assign an ordinal number $\operatorname{cs}(t)$ ...
user avatar
2 votes
1 answer
114 views

Hard-to-"realize" instances of downward density

This question is motivated by a vague analogy between true paths in priority arguments and realizers - relative to an oracle - in the sense of intuitionistic logic. Intuitively, I'm looking for a ...
user avatar
6 votes
1 answer
239 views

A "negative" standard system

For $\mathcal{M}$ a (countable) nonstandard model of $\mathsf{PA}$, let $\mathsf{SS}(\mathcal{M})$ be the set of sets of natural numbers coded by elements of $\mathcal{M}$. There are various ways to ...
user avatar
9 votes
0 answers
195 views

Can "$\exists\mathcal{X}(R\cong C(\mathcal{X}))$" be expressed in "large" infinitary second-order logic?

Originally asked and bountied at MSE without success: Say that a ring $R$ is spatial iff there is some topological space $\mathcal{X}$ such that $R\cong C(\mathcal{X})$, where $C(\mathcal{X})$ is the ...
user avatar
13 votes
2 answers
1k views

Set theory without the empty set

Has there ever been a set theory without an empty set? Is this possible? I ask because we usually take the empty set to exist axiomatically or obtain it through separation and a nonempty set together ...
user avatar
  • 6,601
3 votes
0 answers
148 views

Is this recursion theoretic analogue of a criterion of weakly compact cardinal true?

Jensen proved that, if V=L, and $\kappa$ is a regular cardinal, then if for any stationary $A\subseteq \kappa$, the set $\{\alpha\mid A \text{ is stationary below }\alpha\}$ is stationary in $\kappa$, ...
user avatar
25 votes
2 answers
2k views

Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?

There are many interpretations of arithmetic in set theory. The Zermelo interpretation, for example, begins with the empty set and applies the singleton operator as successor: $$0=\{\ \}$$ $$1=\{0\}$$ ...
user avatar
1 vote
1 answer
91 views

(Maximal) almost disjoint families of true cardinality ${\frak c}$

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. We say $a,b\in [\omega]^\omega$ are almost disjoint if $a\cap b$ is finite. A subset $A\subseteq [\omega]^\omega$ is said ...
user avatar
1 vote
1 answer
80 views

If $X \leq_T Y + 0'$ does there exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$?

If $X \leq_T Y + 0'$ does there always exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$? Obviously, we can find $Z \leq Y$ where the $y$-th column of $Z$ has a limit equal to $X(y)$. Just let $\...
user avatar
  • 1,605
7 votes
1 answer
381 views

Set theory / Formal logic of Baba is You

''Baba is You'' is a recent puzzle game in which the player builds a set of rules by pushing squares with words written on them. If we leave aside the combinatorial difficulty of how to move the ...
user avatar
2 votes
0 answers
50 views

Weaker uniformisation theorems

An interesting topic in Reverse Mathematics is uniformisation theorems (see VI.2 and VII.6 in Simpson's SOSOA). Now, these theorems all express the following: for a suitable formula $\varphi$, there ...
user avatar
  • 1,879
6 votes
1 answer
174 views

Gaps in cardinalities of MAD families

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. We say $a,b\in [\omega]^\omega$ are almost disjoint if $a\cap b$ is finite. A subset $A\subseteq [\omega]^\omega$ is said ...
user avatar
0 votes
0 answers
77 views

Deontic logic and axiomatic pluralism

Background assumptions/definitions/questions (note that "S, A, B" stand for some sentence or other at issue per possible question; note also that these sentences can be imperatives, and in ...
user avatar
2 votes
0 answers
179 views

A formal definition of a useful theorem?

Sorry if this feels a bit squishy, but I'm wondering if there is any published work trying to give a fully formal definition of the notion of a useful theorem. I mean, in mathematics we all know that ...
user avatar
  • 1,605
6 votes
1 answer
659 views

An axiomatic approach to the multiverse of sets

Work in a theory where the primitives are classes $X,Y,Z,\dots$, and class membership $X\in Y$, and add an individual constant $\mathcal{M}$ called 'the multiverse'. Classes $V$ which are members of ...
user avatar
  • 6,601
1 vote
0 answers
101 views

What is the consistency strength of iterated sharps?

I've been interested in sharps such as $0^\sharp$, $0^{\sharp \sharp}$ and $\mathbb{R}^\sharp$, so I wondered about iterating sharps. Let $n \in \omega$ and $x \in V$. Define $x^{\sharp n}$ like so: ...
user avatar
  • 470
3 votes
0 answers
272 views

Does the following variant of common belief exist?

Let $A$ be a finite set of agents and $\mathtt{B}_a$ a modal operator where $\mathtt{B}_ap$ means agent $a$ believes proposition $p$. For now I don't assume any properties of $\mathtt{B}_a$, though ...
user avatar
  • 9,753
10 votes
1 answer
274 views

How hard must "no high-degree irreducibles" proofs be?

Let $\mathsf{RCF}$ be the usual theory of real closed fields and for $n>2$ let $\theta_n$ be the sentence "No degree-$n$ polynomial is irreducible." Since $\mathsf{RCF}$ is complete, for ...
user avatar
2 votes
0 answers
74 views

Consistency strength of Muller's modification of Ackermann set theory

In his 2001 paper Sets, Classes and Categories, F. A. Muller lays out a modification of Ackermann class theory that he claims is not conservative over Ackermann's original theory in the sense that it ...
user avatar
  • 6,601
7 votes
1 answer
173 views

Preservation of projective stationarity

A set $S \subseteq [\kappa]^\omega$ is called projective stationary if for every stationary $A \subseteq \omega_1$, and every algebra $F : \kappa^{<\omega}\to\kappa$, there is $z\in S$ such that $z$...
user avatar
  • 16.4k
4 votes
1 answer
111 views

Persistent finite axiomatizability, relational edition

Say that a finitely axiomatizable first-order theory $T$ (in a finite language $\Sigma$) is persistently finitely axiomatizable iff the set $T_{\mathsf{w/o=}}$ of equality-free $T$-theorems is ...
user avatar
8 votes
0 answers
276 views

How much downward density can we get without injury?

$\newcommand{\ran}{\operatorname{ran}}$This question is basically a riff on the first section of Maass' paper Recursively enumerable generic sets, with some rephrasing for readability. All results ...
user avatar

1
2 3 4 5
89