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
0answers
139 views

Sunflower lemma in a more general poset?

The sunflower 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_\lambda(\kappa)$ for $\kappa$ ...
-1
votes
0answers
158 views

Can we get rid of the primitive symbol $V$ in Ackermann's set theory this way?

I want to get rid of the primitive $V$ in Ackmerann set theory, without changing the axioms so much. I have the following try in my mind, but I'm not sure if it works. So we instead work in the pure ...
4
votes
0answers
148 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
354 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 ...
3
votes
1answer
192 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
62 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
213 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
145 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
88 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 ...
1
vote
0answers
48 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 ...
2
votes
0answers
103 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
112 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
158 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 ...
9
votes
0answers
258 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
219 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
241 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
100 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
103 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 ...
8
votes
1answer
261 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
108 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
171 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
1k 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 ...
0
votes
0answers
10 views

First order logic query [migrated]

Hi I am trying to get my head around logic equations. For example, I have ∃x discovered(x,y) - Does this mean there is one such x where x discovered y? and does ∀x∃y discovered(x,y) mean: for all x, ...
6
votes
1answer
731 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
173 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
283 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
204 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
48 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
201 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 ...
42
votes
7answers
3k views

What is an explicit bijection in combinatorics?

A standard way of demonstrating that two collections of combinatorial objects have the same cardinality is to exhibit a bijection between them. Browsing through some examples (here, there, yonder) ...
3
votes
1answer
140 views

Restricting First Order Logic to make it decidable [closed]

Just curious: This monday, I had an exam in Knowledge Processing. They asked what's the problem with FOL (compared to propositional), and I gave the textbook answer that iterating functions gives ...
7
votes
5answers
1k views

Is there any physical or computational justification for non-constructive axioms such as AC or excluded middle?

I became interested in mathematics after studying physics because I wanted to better understand the mathematical foundations of various physical theories I had studied such as quantum mechanics, ...
5
votes
1answer
310 views

Is it consistent that $|[\kappa]^{<\kappa}| > \kappa$?

Let $\kappa>0$ be a cardinal, and let $[\kappa]^{<\kappa}$ denote the collection of subsets of $\kappa$ having cardinality strictly less than $\kappa$. Is it consistent that $$|[\kappa]^{<\...
7
votes
1answer
519 views

Explaining the consistency of PRA and ZF from predicative foundations

Recently I got interested in predicative foundations, mostly because of Laura Crosilla's work and because Agda employs a predicative type theory. From the point of view of a predicative foundation to ...
6
votes
0answers
167 views

Can one use forcing as a step to prove the Keisler-Shelah isomorphism theorem?

Can one use forcing (perhaps at the expense of using larger ultrafilters) to prove the Keisler-Shelah isomorphism theorem? My idea is to use an ultrafilter $U$ on a set $I$ such that if $M=V^{I}/U$, ...
7
votes
2answers
201 views

Measure of the numbers with length of $n$ for a nonstandard number $n$

Is there any nonstandard model of $PA$ with the following properties? There exists a nonstandard number $n\in M$ such that $M\upharpoonright n$ is countable, Let $|x|=\lceil\log_2x\rceil$, ...
2
votes
1answer
77 views

Does every uncountably categorical theory have a $\varnothing$-definable strongly minimal imaginary?

An uncountably categorical theory always has a strongly minimal set definable over its prime model, but sometimes this set needs parameters to define. By a $\varnothing$-definable imaginary I mean ...
3
votes
0answers
100 views

Partial well-ordering of formulas

Given a theory $T$, for arbitrary formulas $φ$ and $ψ$ that provably in $T$ denote an ordinal, set $[φ]_T < [ψ]_T$ iff provably in $T$, the ordinal denoted by $φ$ is less than the ordinal denoted ...
2
votes
1answer
212 views

Termination of “unpacking” abbreviations

It is a normal practice to use a minimal set of operators in logical systems and construe the other operators as abbreviations. Let's look at the propositional logic: If $\mathcal{V}$ denotes the ...
8
votes
1answer
142 views

Is restricting Replacement and Separation enough to make $Q+I\Sigma_n$ bi-interpretable with Set Theory?

We have the result that $\mathsf{ZFCfin}$, the usual $\mathsf{ZFC}$ axioms with the axiom of infinity replaced by its negation, is bi-interpretable with $\mathsf{PA}$, first order Peano Arithmetic. We ...
13
votes
1answer
288 views

What are some good lower bounds on the consistency of the failure of the PCF conjecture?

Shelah's celebrated theorem states that $\aleph_\omega$ is a strong limit cardinal, then $2^{\aleph_\omega}<\aleph_{\omega_4}$. But the conjecture is that $\omega_4$ can be provably replaced by $\...
4
votes
0answers
138 views

Symmetry between V and HOD

Is it consistent that the set of ordinal definable real numbers is countable, but for every $y∈\mathrm{OD}∩ℝ$, every true $Σ_2^{V,y}$ statement holds in $\mathrm{HOD}$? Note that $Σ_2^V$ is the best ...
15
votes
1answer
752 views

Why are model theorists so fond of definable groups?

My PhD was on so called "pure" model theory, and my advisor was not very much interested in applications of model theory to algebra. Now I feel the need to fill in the gap, and I'd like to educate ...
1
vote
1answer
67 views

Decidability of S2S with real numbers

Is the theory of natural numbers and functions $ℕ → ℝ$ decidable under: - for natural numbers: $\mathrm{succ1}(n) = 2n+1$; $\mathrm{succ2}(n) = 2n+2$; equality - for functions: pointwise addition and ...
14
votes
0answers
435 views

Does inner model theory seek canonical models for large cardinals?

Like the author of this question, I have heard that a main goal of inner model theory is building canonical inner models for large cardinals. My questions are: (a) Is this accurate? (b) If so, in ...
6
votes
2answers
290 views

Poset dimension and width (Dilworth's theorem)

For a given poset $P$, let $\mathrm{dim}(P)$ denote the least cardinal $\kappa$ such that there exists a $\kappa$-sized collection of linear extensions of $P$, say $\mathcal{L}$, such that $\leq_P = \...
4
votes
1answer
267 views

Stronger negation of AC given by rejecting “infinite hat” puzzles

Some of the strangest implications of AC are the "infinite hat" puzzles, which are on Wikipedia, and have been talked about on MO several times, including some variants. There are different ways to ...
3
votes
1answer
235 views

Hartogs' Number of the Reals and $\Theta$ without choice

There are two important numbers that in some meaningful sense describe "how well-orderable" the reals are: Hartogs' Number $H(\Bbb R)$, also notated as $\aleph(\Bbb R)$, the least ordinal/well-...
10
votes
4answers
1k views

When is it okay to intersect infinite families of proper classes?

For experts who work in ZFC, it is common knowledge that one cannot in general define a countable intersection/union of proper classes. However, in my work as a ring theorist I intersect infinite ...