Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
1answer
128 views

Do “seemingly impossible functional programs” work with arrow types interpreted as Turing machines?

The title is a reference to this article by Martin Escardo, referring to work by originally by Ulrich Berger. It occurred that the programs described in this article can interpreted in the Turing ...
4
votes
1answer
142 views

Density character of a metric space is an Ulam number

I am reading this paper and I came across the following sentence: Throughout the paper we silently assume [...] that the density character (i.e. the minimum cardinality of a dense subset) of ...
14
votes
1answer
540 views

Do we know the consistency strength of the Singular Cardinal Hypothesis failing on an uncountable cofinality?

Suppose that $\kappa$ is a strong limit cardinal. The singular cardinal hypothesis states $2^\kappa=\kappa^+$. We know that the failure of SCH requires large cardinals, and in fact is equiconsistent ...
12
votes
1answer
383 views

End-extending cardinals

Let us say a cardinal $\kappa$ end-extending if there is a function $F : V_\kappa^{<\omega} \to V_\kappa$ such that: (a) If $M \subseteq V_\kappa$ is closed under $F$, then $M \prec V_\kappa$. (b) ...
2
votes
2answers
454 views

Who first discovered the concept corresponding to the symbol of class comprehension?

Who first discovered the concept corresponding to the symbol of class comprehension {x/𝛗}used today in set theory ?
3
votes
1answer
121 views

First-order logic of projective planes over fields [closed]

Suppose $\mathbb{P}^2(k)$ is a projective plane defined/coordinatized over a commutative field $k$. Is the first-order logic of the plane completely determined by the first-order logic of $k$ ? (In ...
1
vote
0answers
76 views

Morley rank and forking in arbitrary theories

It's well-known that in a totally transcendental ($\omega$-stable) theory, $p(x)\subseteq q(x)$ is a non-forking extension if and only if $\text{MR}(p) = \text{MR}(q)$. In my answer to this Math ...
4
votes
0answers
133 views

Apart from Tarski's study, is there any other source that has been looking at the parallelism of concepts and theorems?

Alfred Tarski in his next study (Some Methodological Investigations on the definability of concepts, TARSKI, Logic, Semantics, Metamathematics. Papers from 1923 to 1938. Clarendon Press, Oxford, 1956, ...
13
votes
2answers
599 views

Set-theoretical foundations of Mathematics with only bounded quantifiers

It seems that outside of researchers in Mathematical Logic, mathematicians use almost exclusively bounded quantifiers instead of unbounded quantifiers. In fact, I haven't observed any other practice ...
10
votes
1answer
227 views

Examples of Kreisel-Putnam topological spaces

Let us say that a topological space $X$ is a Kreisel-Putnam space when it satisfies the following property: For all open sets $V_1, V_2$ and regular open set $W$ of $X$, if a point $x\in X$ has a ...
1
vote
1answer
103 views

Self-embeddings of uncountable total orders

A nice theorem of Dushnik and Miller (from 1940) states that if $(\Omega,\leq)$ is a countable total order, then either there is an element $\omega \in \Omega$ such that $(\Omega \setminus \{\omega\}...
5
votes
1answer
228 views

Number of ultrafilters in an extender

Assume GCH. Suppose $j: V\to M$ is an elementary embedding such that $\mathrm{crit}(j)=\kappa$, ${}^\kappa M \subset M$, $M\supset V_{\kappa+2}$. We can assume $j$ is defined from some extender of ...
0
votes
0answers
40 views

Existence of a stable approximation of a probability algebra

This question is motivated by the fact that the theory of atomless probability algebras is $\omega$-stable in continuous logic, despite the fact that discrete Boolean algebras are very bad ...
2
votes
0answers
78 views

Finite axiomatizability and $\mathrm{PA^{top}}$

Is $\mathrm{PA^{top}}$ finitely axiomatizable? If not, does it have a finitely axiomatizable extension (allowing new predicates but not new variable types) that has arbitrarily large finite models? $\...
3
votes
0answers
167 views

A consistent way to “decide” independent statements [closed]

Let us fix some mathematical theory T=T(0), such as ZFC. The aim is to develop algorithm A, which takes any statement S independent of T(0) as an input, and outputs axiom a(S) such that T(1)=T(0)+a(S) ...
7
votes
1answer
412 views

Cardinal characteristics of amorphous sets

In a universe where the continuum hypothesis ($CH$) fails we can ask about combinatorial cardinal characteristics of the continuum, but in a universe where $CH$ is true no such cardinals exist so this ...
2
votes
1answer
96 views

Complexity of deciding if an incomplete first-order theory has a stable completion

I'm curious about the problem of deciding if a given incomplete first-order theory has a stable completion from a descriptive set theory point of view. It seems likely that this problem is $\Pi_1^1$-...
1
vote
0answers
79 views

Approximating $3SAT$ by polynomials

Given $3SAT$ formula $\phi$ in $n$ variables and a $\mu\in(0,1/2)$ what is the smallest degree of polynomial $f\in\mathbb Z[x_1,\dots,x_n]$ such that for an $(a_1,\dots,a_n)\in\{0,1\}^n$ if $\phi(a_1,\...
12
votes
1answer
198 views

Does this “mixable” property have a standard name in constructive mathematics?

While thinking about constructive mathematics, I stumbled on the following notion, and I would like to know if it has a standard name, a simpler equivalent, or has appeared in the literature: Say ...
-2
votes
0answers
105 views

Can every first order theory have a finitely axiomatizable conservative extension in this sense?

Note: This is an edit of the previous question. By $T_2$ conservatively extends $T_1$ if and only if: There exists a function $F$ such that $T_2$ extends $T_1$ through $F$; and for every function $G$...
21
votes
1answer
701 views

Does “every” first-order theory have a finitely axiomatizable conservative extension?

I originally asked this question on math.stackexchange.com here. There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. ...
10
votes
0answers
382 views

Sunflower / $\Delta$-system lemma in a more general poset?

The sunflower lemma (or $\Delta$-system lemma) may be viewed as a statement about the poset $P_\omega(\omega_1)$, and the generalized sunflower lemma may be viewed as a statement about the poset $P_\...
-3
votes
0answers
334 views

Can we get rid of the primitive symbol $V$ in Ackermann's set theory without increment in consistency strength?

EDIT: Ackermann had presented his theory with a new primitive added to the language of set theory that is the "set-hood" primitive one place predicate symbol $\mathcal M$ or in common equivalent ...
4
votes
0answers
171 views

Ultrapower of a field is purely transcendental

Let $F$ be a field, $I$ a set, and $U$ an ultrafilter on $I$. Is the ultrapower $\prod_U F$ a purely transcendental field extension of $F$? According to Chapter VII, Exercise 3.6 from Barnes, Mack "...
8
votes
2answers
408 views

Constructivist defininition of linear subspaces of $\mathbb{Q}^n$?

Let me preface this by saying I'm not someone who has every studied mathematical logic or philosophy of math, so I may be mangling terminology here (and the title is a little tongue in cheek). I (and ...
5
votes
1answer
236 views

Models of $\mathsf{ZFC}$ with neither $P$- nor $Q$-points

A $P$-point is an ultrafilter $\scr U$on $\omega$ such that for every function $f:\omega\to\omega$ there is $x\in {\scr U}$ such that the restriction $f|_x$ is either constant, or finite-to-one. A $Q$...
0
votes
1answer
77 views

Quantifier elimination and where is this quantified convex program in the polynomial hierarchy?

I have a quantified convex program of the form that I need to solve $$\exists(x_{1,1},\dots,x_{1,n})\in\mathbb R^n\quad\forall(x_{2,1},\dots,x_{2,n})\in\mathbb R^n$$ $$\vdots$$ $$\exists(x_{2t-1,1},\...
2
votes
2answers
241 views

(Types of) induction on infinite chains

This question may be trivial, or overly optimistic. I do not know (but I guess the latter...). I am a group theorist by trade, and the set-up I describe cropped up in something I want to prove. So ...
11
votes
0answers
159 views

Ordinal-valued sheaves as internal ordinals

Let $X$ be a topological space (feel free to add some separation axioms like “completely regular” if they help in answering the questions). Let $\alpha$ be an ordinal, identified as usual with $\{\...
4
votes
0answers
95 views

Is Ackermann's set theory minus class comprehension equal to ZF?

Ackermann in 1956 proposed an axiomatic set theory. Reinhard proved that Ackermann's set theory equals ZF It's clear that Zermelo set theory can be interpreted in Ackermann's set theory minus class ...
2
votes
0answers
53 views

Is there a three valued logic whose game semantics corresponds to potentially infinite games?

Consider game trees with the following properties: Each node in the tree is one of the following: Verifier Choice: Has one or more children Falsifier Choice: Has one or more children No Choice: Has ...
3
votes
0answers
115 views

Definable modal logics in first-order structures

Suppose $X$ is a set, $\mathcal{W}$ is a family of subsets of $X$, and $\mu:\mathcal{W}\rightarrow\mathcal{W}$ is an operation on those sets. There is a natural way to assign a modal logic to the ...
5
votes
1answer
222 views

Amorphous proper classes in MK

Working in $ZFC$ every cardinal is either finite or in bijection with a proper subset of itself (Dedekind infinite). Without Choice it is consistent that there are infinite sets which can't be ...
0
votes
0answers
32 views

Combinatorial Logic for Rigid Logic

It's straightforward enough to derive a combinatorial logic for linear and ordered logic, by just taking the standard translation for intuitionistic logic, and modify the lambda-application case to ...
7
votes
2answers
178 views

Logic with “co-relations” - sources?

My question is on a seemingly-natural extension of classical logic that I've been playing around with a bit in the context of generalized recursion theory. I'm sure it's been treated extensively ...
10
votes
0answers
273 views

Connection between Provability Logic (GL) and geometry?

In Provability Logic (aka GL) we have The Beth definability theorem and De Jong-Sambin Fixed Point Theorem The former has a vague similarity to the implicit function theorem in that you can loosely ...
8
votes
1answer
225 views

Non-normal numbers definable without parameters in the langauge of differential rings with composition

Background: It is currently unknown whether $e$ is normal. A natural way to approach this question is to find a class to which $e$ belongs, and prove all members of that class are normal. For example, ...
9
votes
1answer
265 views

Fibers of the morphism from the free Heyting algebra to the free Boolean algebra

For $k\in\mathbb{N}$, let $H_k$ be the free Heyting algebra on $k$ variables $p_1,\ldots,p_k$ and $B_k$ be the free Boolean algebra on the same $k$ variables. Thus, $B_k$ has $2^{2^k}$ elements (...
0
votes
0answers
104 views

Writing Values in Limited Time (Infinite Programs)

Since there seems to be at least some interest in the question I asked, I will leave the previous version of question as it is (instead of deletion) and just briefly state the actual current question ...
1
vote
0answers
106 views

Arithmetic that corresponds to combinatorial rectangles and cylinder intersections?

Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets. In communication complexity the interpretation is more on intersection and union of ...
9
votes
1answer
267 views

A question on the ultrafilter number

Let $\mathfrak{u}$ denote the ultrafilter number, which is defined to be the minimum cardinality of a subset of $\mathcal{P}(\mathbb N)$ which is a base for a nonprincipal ultrafilter on $\mathbb{N}$. ...
4
votes
0answers
110 views

Continuous open self maps on Cantor space

A continuous self map on the Cantor space $C = \{0,1\}^\mathbb{N}$ is a mapping $f = (f_i)_{i\in \mathbb{N}}$ such that each $f_i$ is a map from $C$ to $\{0,1\}$ that depends only on a finite number ...
5
votes
1answer
180 views

Amalgamation via elementary embeddings

Can there exist three transitive models of ZFC with the same ordinals, $M_0,M_1,N$, such that there are elementary embeddings $j_i : M_i \to N$ for $i<2$, but there is no elementary embedding from $...
39
votes
2answers
2k views

Ultrafilters as a double dual

Given a set $X$, let $\beta X$ denote the set of ultrafilters. The following theorems are known: $X$ canonically embeds into $\beta X$ (by taking principal ultrafilters); If $X$ is finite, then there ...
5
votes
1answer
747 views

Which branches of mathematics can be done just in terms of morphisms and composition?

Consider the first-order language $L_{\omega\omega}$ of the signature $L:=\{\mathrm{dom}, \mathrm{cod}, \mathrm{comp}\}$, where $\mathrm{dom}$ and $\mathrm{cod}$ are unary function symbols and $\...
4
votes
2answers
177 views

Is the order arithmetic of the positive reals o-minimal?

Consider the structure of the positive real numbers $(0, \infty) $ with its unit $1$, its addition $+$, its multiplication $\times $, and its strict ordering $> $. Is this structure $$( (0, \infty)...
4
votes
1answer
289 views

Formalize ignorance

This is a spinoff of my attempt to capture the notion of 'explicit bijection' at https://mathoverflow.net/a/323827. I wonder whether it is possible to formalize the idea that an algorithm computing a ...
1
vote
1answer
208 views

An Apparent Incongruity

I thought of a certain point that seems to point to an apparent incongruity. Hopefully someone would promptly point out the logical mistake and/or some implicit assumption that may not hold under a ...
2
votes
0answers
50 views

Length of Gaps in Clockable Values

As I understand, there can't be any (total) OTM computable function (in traditional input/output sense) $f:Ord \rightarrow Ord$ such that $f(x)$ gives an upper-bound on the length of the $x$-th gap. ...
8
votes
1answer
217 views

Kleene realizability in Peano arithmetic

For completeness of MathOverflow and for clarity of the question, I will first recall a few things, including the the definition of Kleene realizability: experts can jump directly to the question ...