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.
5,152
questions
1
vote
0
answers
51
views
Is there a restriction of Linear Temporal Logic that has a "Markov" property?
I have a problem, that I can formulate as model-finding in Linear Temporal Logic (via Büchi automata). I also have the additional knowledge, that there is always satisfied a Markov-like property, ...
- 283
7
votes
1
answer
302
views
Consistency strength of the existence of a transitive model of $\mathsf{ZFC}^-$ with a $\kappa$-complete ultrafilter
Let $\mathsf{ZFC}^-$ be the Zermelo-Fraenkel set theory without power set axiom.
For a transitive model $M$ of $\mathsf{ZFC}^-$ and an cardinal $\kappa\in M$ in the sense of $M$, an unary predicate $U$...
- 2,774
0
votes
1
answer
226
views
Is the following injectivity schema provable in ZF-foundation?
Is the injectivity scheme present in the below axiomatic exposition of a first-order set theory provable in $\text{ZF}$?
Extensionality: $\forall A,B \ [\forall x \ (x \in A \leftrightarrow x \in B) \...
- 9,256
3
votes
2
answers
670
views
Extendibility vs supercompactness
The following quotes comes from "Cantor's Attic"'s page on supercompacts:
If κ is $|V_{κ+η}|$-supercompact with $η<κ$ then it is preceeded by a stationary set of $η$-extendible cardinals. If $κ$ ...
- 615
7
votes
1
answer
411
views
What is this property exhibited by some logical systems?
I'm migrating this question from MSE to MO, as in the span of five months, it received 6 upvotes but no answers. If my language needs to be fine-tuned in any way, constructive suggestions and guidance ...
- 193
5
votes
1
answer
484
views
How to kill a $\Sigma_{n+1}$-correct cardinal softly ($n>1$)?
A cardinal $\kappa$ is $\Sigma_n$-correct iff $V_\kappa \prec_n V$. For n>1, how to force a $\Sigma_{n+1}$-correct cardinal to be $\Sigma_{n}$-correct but not $\Sigma_{n+1}$-correct?
For $n=1$, we ...
- 53
2
votes
1
answer
407
views
Does the axiom schema of Replacement follow from the abstract notion of the iterative conception of sets?
Let's define an iterative function $V^F$ to indicate a iterative hierarchy building function that iterates a function $F$ starting from $\emptyset$ after a well ordering relation set $R$ whose domain ...
- 9,256
21
votes
1
answer
724
views
Are $\mathbb C$ , $\mathbb C[X]$ definable in $\mathbb C[[X]]$?
Let $L$ be a first-order language and $M$ be an $L$-structure. Let $D \subseteq M^n$ . Let us say $D$ is definable in $M$ if for some finite set (possibly empty) $A=\{a_1,...,a_m\} \subseteq M$ and ...
user111524
38
votes
7
answers
6k
views
Is V, the Universe of Sets, a fixed object?
When I first read Set Theory by Jech, I came under the impression that the Universe of Sets, $V$ was a fixed, well defined object like $\pi$ or the Klein four group. However as I have read on, I am ...
- 680
11
votes
4
answers
974
views
Gödel's speed-up from constructive to classical logic?
Gödel's speed-up theorem implies that some proofs can get significantly shortened when allowing extra axioms. There are concrete examples of this phenomenon for instance when moving from Peano ...
- 359
14
votes
3
answers
892
views
Forcings predicted by core model theory $+$$ZFC$ results proved by the method of core model theory
I have two unrelated question.
First question. To motivate the question, let me explain an example. The natural way to force the failure of singular cardinals hypothesis ($SCH$), is to start with a ...
7
votes
1
answer
291
views
Games in non-standard models
Has anyone studied Combinatorial game theory in non-standard models?
In particular, we can work in either non-standard models of set theory, or we can work in non-standard models of arithmetic, where ...
- 5,821
7
votes
1
answer
292
views
Model theory of the restricted complex analytic functions
Let $\mathbb{C}_{an}$ be the expansion of the structure $(\mathbb{C}; +,-,×,0,1)$ by adding the restricted complex analytic functions. This is the complex analog of the familiar $\mathbb{R}_{an}$ in O-...
- 1,438
8
votes
1
answer
584
views
Applications of "model-theoretic" forcing
The notion of forcing was invented by Paul Cohen, who used
it to prove the independence of the Continuum Hypothesis. He constructed a model of set theory in which the CH fails, thus showing that CH ...
- 1,882
36
votes
0
answers
1k
views
Rigid non-archimedean real closed fields
Question. Is there a countable rigid non-Archimedean real closed field?
Background:
As usual, a structure is said to be rigid if the only automorphism of the structure is the identity map.
It is ...
- 17.1k
6
votes
2
answers
693
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 ...
- 861
2
votes
1
answer
265
views
A generalization of Vaught's two cardinal theorem
I'm trying to determine whether or not the following generalization of Vaught's two cardinal theorem is true.
Let $T$ be a complete theory in a language with a unary predicate $U$ and a binary ...
- 10.3k
7
votes
2
answers
665
views
Is every true statement independent of $PA$ equivalent to some consistency statement?
Most true statements independent of PA that I know of is equivalent to some consistency statement. For example
Con(PA), Con(PA + Con(PA)), Con(PA + Con(PA) + Con (PA + Con(PA)), $\dots$
Goodstein's ...
- 5,821
2
votes
1
answer
519
views
What is the proof-theoretic ordinal of KPh?
If we work in this notation:
$$C_0 (\alpha, \beta) = \beta \cup \lbrace 0 \rbrace$$
$$C_{n+1} (\alpha, \beta) = \lbrace \gamma + \delta, \omega^\gamma, \Omega_{\gamma}, I_{\gamma}, \psi_\pi(\eta) | \...
- 482
4
votes
4
answers
853
views
Can we add set complements on top of ZF?
Can we introduce complements on top of the standard set theory $\text{ZF}$ and have some comprehension axioms about them, like in defining a "small set" as an element of a stage of the Cumulative ...
- 9,256
3
votes
1
answer
150
views
Product of types in stable theories
Let $T$ be stable and $M \models T$. Given two types $p(x) \in S_x(M)$ and $q(y) \in S_y(M)$ there is a canonical way to get a type in $S_{xy}(M)$. Define
$$p(x) \otimes q(y) = tp_{xy}(ab/M)$$
where $...
- 886
7
votes
2
answers
403
views
Characterizations of infinite compact Abelian groups and probability spaces based on the forcing notion they give
Let $G$ be an infinite compact Abelian group with the collection $\mathcal{B}$ of Borel subsets of $G$, and $m$ the (unique) normalized Haar measure on $\mathcal{B}$. This gives a natural forcing ...
5
votes
1
answer
185
views
preservation of forcing rigidity in iterations
Say that a partial order $P$ is forcing-rigid in a model $V$ if whenever $G \subseteq P$ is generic over $V$, then in $V[G]$, $G$ is the only filter which is $P$-generic over $V$. This implies there ...
- 18.1k
4
votes
1
answer
489
views
What would be the effect of replacing Separation by Injective Replacement?
Let "Injective Replacement" be the following schema:
If $\phi(x,y)$ is a formula in which only x,y occur free, and only free, then:
$\small \forall
A \ [\forall x \in
A \exists y (\phi(x,y)) \...
- 9,256
5
votes
2
answers
849
views
An axiom for collecting proper classes
I'm currently working on some universal algebra using proper classes (in MK class theory), and I repeatedly run into situations where I want to collect together some proper classes as the members of a ...
- 9,009
1
vote
1
answer
123
views
Connections between algebraic semantics and computational complexity of a logic?
I'm re-posting this question from cstheory.SE hoping to have more luck.
I'm a computer scientist learning a bit about algebraic logic and I was wondering how knowing the algebraic semantics of a ...
- 121
17
votes
0
answers
834
views
Ramsey's theorem for the first uncountable ordinal
Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...
- 11.3k
5
votes
1
answer
393
views
A question about ordinal analysis
I have several questions related to ordinal analysis.
According to [1], here are the proof-theoretic ordinal of some well-known theories (using $|T|$ do denotate the proof-theoretic ordinal of $T$):
...
- 615
22
votes
1
answer
866
views
Is the axiom $\Diamond\Box\varphi\to\Box\Diamond\varphi$ in c.c.c. forcing potentialism equivalent to the productivity of c.c.c. forcing?
This question arose in connection with a lecture series on
Potentialism
that I have just completed here in Hejnice in the Czech Republic at
the Winter School 2018 (see
Slides). Several of us discussed ...
- 225k
10
votes
1
answer
387
views
Iterated forcing with distributive forcing notions
Assume $(\kappa_n| n<\omega)$ is an increasing sequence of inaccessible cardinals with $\kappa_\omega=\sup_{n<\omega}\kappa_n.$. Let
$((\mathbb{P}_n| n \leq \omega), (\dot{\mathbb{Q}}_n | n<\...
9
votes
1
answer
386
views
Injection from $\aleph_2$ into the power set of $\mathbb{R}$
Assume $\mathsf{ZF} + \mathsf{DC}$. Must there exist an injection from $\aleph_2$ to $\mathcal{P}(\mathbb{R})$? If not, what is the consistency strength of the nonexistence of such an injection?
I ...
- 5,551
1
vote
0
answers
340
views
Proving $\omega_1$ is inaccessible in $L(r)$ [closed]
I am trying to prove that $\omega_1$ is strongly inaccessible in $L(r)$ for all $r \subseteq \omega$ from the assumption that $\omega_1$ is inaccessible to reals, i.e., that $\omega_1^{L(r)} < \...
- 11
9
votes
1
answer
707
views
Can the Turing degrees be linearly ordered?
Assuming the axiom of choice, every set can be linearly (indeed, well-) ordered. However, without choice this can fail, as witnessed most drastically by the consistency of amorphous sets. More ...
- 19k
7
votes
2
answers
521
views
What is the status of the assertion "There are arbitrarily large cardinals with the tree property"?
Of course, if you want your cardinals with the tree property to be strongly inaccessible, then you're asking about weakly compact cardinals. But what if you don't want them to be strongly inaccessible?...
- 61.5k
4
votes
0
answers
224
views
Short Diophantine definition of the sum-of-divisors function (using less than 100 variables)?
Is there a short Diophantine definition of the sum-of-divisors function? Is there a polynomial $p$ such that
$$c = \sum_{d|n}d \ \leftrightarrow \ \exists x_1, \ldots x_{100}\ p(c,n,x_1, \ldots x_{...
user44143
3
votes
0
answers
254
views
Can ZF be interpreted in a theory axiomatized by a version of replacement and infinity?
Dana Scott had once proved that Zermelo's set theory $``\text{Z}"$ can be interpretable in the first order set theory whose axioms are just the axioms of:
Separation: if $\phi$ is a formula in which ...
- 9,256
2
votes
0
answers
93
views
Universal abstract elementary classes and closure operators
In this article Hyttinen and Kangas claim that universal abstract elementary classes which are categorical are essentially classes of vector spaces as soon as the model reaches a critical cardinality.
...
- 8,186
9
votes
1
answer
540
views
"Towers" on singular cardinals with countable cofinality
Let $\lambda$ be a singular cardinal of countable cofinality.
Is there necessarily a sequence $\{A_\alpha\mid\alpha<\lambda^+\}$ of countable subsets of $\lambda$, such that $\alpha<\beta$ if ...
- 38.2k
9
votes
1
answer
580
views
Substitutional modality
An informal definition of a logical truth is a sentence that's true in virtue of its form alone: $\phi$ is logically true iff all substitutions of $\phi$ that leave its logical vocabulary alone are ...
- 357
-2
votes
1
answer
320
views
Representing logic formulae in manifolds [closed]
Is there a meaningful way to transform logical equations (for instance $a \implies b$; $b \land a \implies c$ etc.) into geometrical representation in spaces such $\mathbb R^n$, $\mathbb C^n$ or ...
- 17
1
vote
1
answer
284
views
Is Calculus of Constructions type inhabitance semi-decideable?
I'm wondering if type inhabitance for the calculus of constructions is semi-decideable. I know the following:
System F inhabitance and, correspondingly, second-order unification are semi-decideable
...
- 31
11
votes
1
answer
444
views
Ways to add Aronszajn trees which are neither Souslin nor special
By an Aronszajn tree, I mean a tree of height $\omega_1$ with countable levels and no branch. Such a tree is Souslin if it has no uncountable antichains and special if it can be written as the ...
- 1,832
23
votes
1
answer
1k
views
Is it consistent with ZF that $V\to V^{\ast \ast}$ is always surjective?
In a comment to a recent question, Jeremy Rickard asked whether it is consistent with ZF that the map $V \to V^{**}$ from a vector space to its double dual is always surjective. We know that "...
- 78.3k
2
votes
1
answer
171
views
Is this kind of predication preserved under co-extensionality?
Define: $x=^*y \iff \forall m \ (m \in x \iff m \in y)$,
i.e. $=^*$ is co-extensionality relation.
Define: $ Set(x) \iff \forall y,z \ (y \in x \wedge z=^*y \implies z \in x)$
i.e. a set is a ...
- 9,256
8
votes
1
answer
591
views
On measurable cardinals
Let $\kappa$ be an uncountable cardinal and $(P(\kappa),\cap,\cup, ^c,\kappa,\emptyset)$ the Boolean Algebra of all subsets of $\kappa$.
Fact: If there exists a countably complete non-principal ...
- 2,932
7
votes
0
answers
195
views
Query about iterated collapse forcing
I have heard it said that it is possible to use Woodin's iterated collapse forcing to prove that the theory $\textsf{ZF}$+"there exists a non-trivial elementary embedding $j:V_{\lambda+2} \rightarrow ...
- 2,005
6
votes
1
answer
210
views
A "dense" extension of the set of primitive recursive functions
Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make ...
user39297
8
votes
1
answer
328
views
Iterated forcing and the super tree property at $\omega_2$
It is a theorem of Baumgartner and Laver that iterating Sacks forcings of weakly compact length gives rise to the tree property at $\omega_2$. Natural questions (at least for me) are: do we get ...
- 3,138
2
votes
0
answers
102
views
Why can a least fixed point operator only be expanded finitely many times?
If we expand modal logic with least and greatest fix point operators $\mu$ and $\nu$, respectively, we obtain the logic $L_\mu$.
An alternating automaton on infinite trees has a state space that is ...
- 21
1
vote
2
answers
480
views
Equivalents of Replacement under removal of Extensionality?
Is the following schema equivalent to the axiom schema of Replacement over the rest of axioms of $ZF$ [equality axioms, full versions of Pairing, Union and Power; Infinity, Foundation, Extensionality]....
- 9,256