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.
1,158
questions with no upvoted or accepted answers
11
votes
0
answers
425
views
Example of $\aleph_1$-categorical linear order
Is it possible to have an $L_{\omega_1,\omega}$-sentence $\phi$ in a vocabulary that includes $<$ that satisfies the following?
$<$ is a linear order on a definable subset;
$\phi$ is $\aleph_1$-...
- 2,932
11
votes
0
answers
275
views
A variant of strong ideals, is it consistent?
Is it consistent relative to large cardinals that there is a precipitous ideal on $\omega_1$ forcing a generic elementary embedding $j : V \to M \subseteq V[G]$, such that $j(\omega_1) = \omega_n^V$ ...
- 18.1k
11
votes
0
answers
304
views
The Chang model after collapsing an inaccessible limit of Woodins
If $\kappa$ is an inaccessible cardinal and $G \subset \operatorname{Col}(\omega,\mathord{<}\kappa)$ is a $V$-generic filter, then in $V[G]$ the Chang model $L(\text{Ord}^\omega)$ satisfies "every ...
- 5,551
11
votes
0
answers
438
views
Does Sageev's result need an inaccessible?
In 1981, building on work by Ellentuck in 1974, Sageev showed ("A model of ZF + there exists an inaccessible, in which the Dedekind cardinals constitute a natural non-standard model of arithmetic," ...
- 19.3k
11
votes
0
answers
269
views
Maximality of linear orders in the Keisler order on theories
Recently Malliaris and Shelah (see their preprint http://math.uchicago.edu/~mem/Malliaris-Shelah-CST.pdf) have shown that theories with $SOP_2$ are maximal in the Keisler order. A preceding result of ...
- 529
11
votes
0
answers
509
views
Existence of a regular subposet which collapses everything except the top cardinal
Suppose $\delta$ is an inaccessible cardinal, and $\mathbb{P}$ is the Levy Collapse $\text{Col}(\kappa, \delta)$ which adds a surjection from $\kappa \to \delta$ (for some regular $\kappa < \delta$)...
- 2,281
11
votes
0
answers
219
views
Savings property: A transformation which turns nonnegative martingales into uniformly integrable ones
Background
I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mises). However, since ...
- 6,267
11
votes
0
answers
507
views
Using Lindstrom's theorem to prove Craig interpolation
[EDIT: The theorem I call "Beth definability" below is apparently not generally called that (wikipedia notwithstanding; see https://math.stackexchange.com/questions/288450/two-forms-of-beths-theorem). ...
- 19.3k
11
votes
0
answers
533
views
Various definitions of recursion from ordinal machines
Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
11
votes
0
answers
312
views
full support iteration of semiproper forcings
Suppose $\langle P_\alpha,\dot{Q}_\alpha:\alpha\leq\omega_1\rangle$ is a full support iteration of (semi)proper forcings. Is the full limit $P_{\omega_1}$ (semi)proper or at least stationary set ...
- 529
11
votes
0
answers
1k
views
Reverse mathematics strength of identically zero polynomials are the zero polynomial
According to wikipedia, the statement "every polynomial over a countable field that is not the zero polynomial has only finitely many roots" is equivalent to RCA0 over RCA0* (which is called ERCA-0 in ...
user5810
11
votes
0
answers
305
views
What are the logical morphisms from a topos E to Set?
If $E$ is a topos, is there a nice way to characterize the category of logical morphisms $E\to Set$? Is it complete and/or cocomplete?
The topos $Set$ geometrically represents a point; what does it ...
- 8,559
10
votes
0
answers
310
views
Determinacy coincidence at $\omega_1$: is CH needed?
This is a follow-up to the last part of an old MSE answer of mine. Briefly, an analogue at $\omega_1$ of Steel's equivalence between clopen and open determinacy can be proved assuming $\mathsf{CH}$, ...
- 19.3k
10
votes
0
answers
307
views
Feferman's universes for proof assistants?
This question was prompted by a discussion from another MO question about the consistency of ZFC. There are some mathematicians who are comfortable with ZFC but uneasy with large cardinals. For them,...
- 78.7k
10
votes
0
answers
162
views
How nice can sets of reals be under $\mathsf{ZF} + \mathsf{BPI}$?
It's well known that the full axiom of choice is not needed to prove the existence of non-measurable subsets of $\mathbb{R}$. In particular, the Boolean prime ideal theorem ($\mathsf{BPI}$) is ...
- 10.3k
10
votes
0
answers
319
views
Extending models of topological set theory
$\mathsf{GPK_\infty^+}$ is an alternative set theory in which we have comprehension for formulas which are positive in a certain sense; see the SEP article for more detail (or this MO post, which ...
- 19.3k
10
votes
0
answers
593
views
Reference request for a complete and formal Duality Principle in category theory
Most textbooks on category theory only sketch the meaning of the Duality Principle. But even when they do it more formally, I have only seen a version so far which concerns the language of a (single) ...
- 61.5k
10
votes
0
answers
291
views
Is ZF + "all sets of reals have the Ramsey property" + "there is a set without the Baire property" consistent?
A question which was mentioned in passing by Larson when discussing geometric set theory.
Are there models of set theory where all sets of reals have the Ramsey property but there is a set of reals ...
- 139
10
votes
0
answers
408
views
Theories of truth
Not knowing much about logic, I thought that in mathematics saying that a (closed) sentence $\varphi$ in a (formal) theory $T$ is "true" amounted to one of the following notions:
Syntactic ...
- 22.7k
10
votes
0
answers
269
views
Martin's Maximum implies stationary/club Chang's conjecture?
Chang's Conjecture (CC) states: for any $f: [\omega_2]^{<\omega} \to \omega_1$, there exists a set $X\subset \omega_2$ of order type $\omega_1$ such that $|f''[X]^{<\omega}|\leq \aleph_0$.
...
- 3,138
10
votes
0
answers
317
views
Definability up to isomorphism versus definability of an isomorphic copy
Question: Is it provable in ZFC that every structure that is ordinal definable up to isomorphism has an ordinal definable isomorphic copy? If not, what are some counterexamples? All structures are ...
- 6,112
10
votes
0
answers
277
views
How does a theory give rise to a category with finite products?
In the paper Diagonal Arguments and Cartesian Closed Categories (here), Lawvere presents a fixed-point theorem that generalizes both Cantor's theorem and Gödel's (first) Incompleteness Theorem.
In ...
- 499
10
votes
0
answers
316
views
What kind of objects can code a universe?
Jensen proved that given $V\models\sf ZFC+GCH$, there is a class generic real $r$, such that $V[r]=L[r]$, and no cardinals are collapsed.
We know that this can be modified such that $r$ is minimal, i....
- 38.2k
10
votes
0
answers
168
views
Isomorphisms mod nonstationary
Suppose $G \subseteq \mathrm{Add}(\omega_1)$ is generic over $V$. Let $X_i = \{ \alpha : G(\alpha) = i \}$. Is it true that $P(X_0)/\mathrm{NS} \cong P(X_1)/\mathrm{NS}$?
- 18.1k
10
votes
0
answers
273
views
How wealthy are canonical inner models?
One of the way a person shows their wealth is by having many diamonds. The same can be said about models of $\sf ZFC$. We can add generic diamond sequences, while preserving the old ones, so in some ...
- 38.2k
10
votes
0
answers
288
views
Undetermined Banach-Mazur games: beyond DC
This question is a follow-up to this one; see that question for the definition of Banach-Mazur games. There James Hanson showed that ZF+DC proves that there is an undetermined Banach-Mazur game; ...
- 19.3k
10
votes
0
answers
401
views
Equational theory in the signature (+,*,0,1) of sedenions and beyond
Consider a Cayley-Dickson algebra $(X,+,∗,0,1)$, that is an algebra generated from the reals by the Cayley-Dickson construction. From complexes to quaternions, we lose commutativity of multiplication, ...
- 2,063
10
votes
0
answers
500
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_\...
- 61.6k
10
votes
0
answers
350
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,116
10
votes
0
answers
185
views
stationary reflection in $[\kappa]^\omega$
It is well-known that the following reflection principle is consistent relative to a supercompact:
For all $\kappa \geq \omega_2$ and all stationary $S \subseteq [\kappa]^\omega$, there is $X \...
- 18.1k
10
votes
0
answers
226
views
Is there an expansion of $(\mathbb{N},+,<)$ by a pairing function that is still NIP?
I was told once that there is a theory consisting of just a pairing function that is stable, although I cannot find a reference for it. This motivated my question, which is essentially the title, ...
- 10.3k
10
votes
0
answers
431
views
On the Number of Parallel Automorphism Lines
Given a group $G$, one can define the transfinite line of iterative automorphisms of $G$ to be the following chain of the groups where $G_{\alpha+1}=Aut(G_{\alpha})$ for each ordinal $\alpha$ and the ...
10
votes
0
answers
579
views
Is the Banach game quantifier "intractable"? (Becker's guess)
(This is a revised version of the original question. Below I work in $\mathsf{ZF+DC+AD}$, but I would be happy to add further axioms if appropriate: $\mathsf{ZF+DC+AD_\mathbb{R}}$, for example, seems ...
- 19.3k
10
votes
0
answers
434
views
A new maximality principle and its consequences
Let us consider the following maximality principle:
$(MP_*):$ For all uncountable regular cardinals $\kappa, 2^{<\kappa}=\kappa^{+}$
and all trees of height and size $\kappa$ are specialized.
It ...
10
votes
0
answers
268
views
Strongly compact vs Shelah cardinals
Does Con(ZFC+there exists a strongly compact cardinal) imply the Con(ZFC+there exists a Shelah cardinal)?
10
votes
0
answers
256
views
Collapsing the Linear Time Hierarchy and finite axiomatizability of bounded arithmetic
It is well known that if ${\bf T_2}$ (or $I\Delta_0+\Omega_1$) is finitely axiomatizable, then the Polynomial Hierarchy collapses.
Q. Is there any similar relation between $I\Delta_0$ and Linear ...
- 1,699
10
votes
0
answers
356
views
Inner models and strongly compact cardinals
The following question is motivated by a result of Magidor that it is consistent that the least strongly compact cardinal is the least measurable cardinal.
Question. Assume $\kappa$ is a strongly ...
10
votes
0
answers
507
views
Riemann hypothesis in Zilber's field
Question. What is known about the situation (truth or falsity) of Riemann hypothesis in the Zilber's field?
10
votes
0
answers
447
views
(A little bit) Beyond the E-recursive
The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
- 19.3k
10
votes
0
answers
207
views
Can we find minimal-diameter metrics without computability?
A beautiful argument by Nabutovsky and Weinberger (see http://math.uchicago.edu/~shmuel/fractal.ps) shows that, if $M$ is any smooth compact manifold of dimension $\ge 5$, then the diameter functional ...
- 19.3k
10
votes
0
answers
238
views
Homogeneity of a variant of Prikry forcing
Prikry forcing is easily seen to be cone homogeneous (for any $p, q \in \mathbb{P}$, there are $p' \leq p, q' \leq q$ and an isomorphism $\Phi: \mathbb{P}/p' \simeq \mathbb{P}/q'$); in particular for ...
10
votes
0
answers
289
views
When does $HOD^{V[G]} \subseteq V$?
Assume that $\mathbb{P}\in HOD$ is non-trivial. It is well-known that if $\mathbb{P}$
satisfies some homogeneity properties, then $HOD^{V[G]} \subseteq V$, where $G$ is $\mathbb{P}$-generic over $V$.
...
10
votes
0
answers
242
views
Two cardinal obstructions
Given a theory $T$ and a formula $\phi(x)$ we say that they admit a $(\kappa, \lambda)$ model if there is a model $M$ such that $|M| = \kappa$ and $|\phi(M)| = \lambda$.
In all examples that I know ...
- 886
10
votes
0
answers
349
views
Is there a "hereditary" construction for $L$?
Recall that $L$, Godel's constructible universe is constructed by defining the following hierarchy:
$L_0=\varnothing$, for a limit ordinal $\delta$, $L_\delta=\bigcup_{\alpha<\delta}L_\alpha$, and ...
- 38.2k
9
votes
0
answers
129
views
Locally presentable and accessible categories without the axiom of choice?
Is there a good reference for the study of locally presentable and accessible categories without the axiom of choice? For instance, it seems one will need to understand:
What is a good notion of $\...
- 61.6k
9
votes
0
answers
417
views
Does Wedderburn's Theorem hold constructively?
Wedderburn's Theorem states that every finite division ring is commutative. Perhaps even more surprising, this implies that every finite reduced ring is commutative. The proofs that I am aware of ...
- 61.5k
9
votes
0
answers
191
views
Is there an Arithmetized Completeness theorem for intuitionistic theories?
For classical theories, Henkin's completeness proof can be arithmetized. This leads to the result that for classical theories $T$ and $S$ if $\sigma$ is a formula enumerating $S$ in $T$ then $S \leq T ...
- 481
9
votes
0
answers
144
views
Are there good criteria for the topological models where BD-N and BD hold?
A (non-empty/inhabited) subset $S$ of $\mathbb{N}$ is said to be pseudo-bounded if for every sequence $x_n$ in $S$ we have
$\lim_{n\to \infty} \frac{x_n}{n} = 0$
Clearly all bounded subsets are pseudo-...
- 1,823
9
votes
0
answers
261
views
Can we have a 'universal class' for elementary embeddings $j\colon V\to V$
Work over $\mathsf{GB}$, Gödel-Bernays set theory (without choice). My question is the following:
Question. Is the following statement consistent with $\mathsf{GB}$? There is a universal class for ...
- 2,774
9
votes
0
answers
225
views
Continuum hypothesis analogue for substructures
This question was previously asked and bountied at MSE. Throughout, "theory" means "possibly-incomplete first-order theory in a countable language."
Say that a theory $T$ has CHS (...
- 19.3k