Stack Exchange Network

Stack Exchange network consists of 174 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.

2
votes
1answer
117 views

Topologically Ordered Families of Disjoint Cantor Sets in $I$?

Suppose that we have an uncountable collection $C_\alpha$ of disjoint Cantor Sets contained in the closed unit interval $I$. Suppose we have ordered the indices $\alpha \in [0,1]$ as well. Then is ...
4
votes
0answers
183 views

Can there be a segment of regular cardinals with the tree property capped by an almost-strongly-compact?

Recall that a cardinal $\kappa$ is $(\lambda,\infty)$-almost-strongly-compact if every $\kappa$-complete filter can be refined to a $\lambda$-complete ultrafilter. A cardinal $\mu$ has the tree ...
13
votes
1answer
422 views

Real numbers with given complexity

This may be an easy question or it may be related to a well known open problem in Computer Science. Let $\alpha>0$. We say that $\alpha$ is computed in time $T(n)$ if there is a Turing machine ...
1
vote
1answer
145 views

To what logic does the free Boolean sigma-algebra of countably many generators correspond to?

The free Boolean algebra on countably many generators is closely related to the classical (two-valued) propositional calculus (after identification of logically equivalent formulas). By the Stone ...
6
votes
1answer
253 views

Time functions of non-deterministic Turing machines

Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$. The smallest ...
8
votes
2answers
188 views

Expressive power of FO with $\mu$

Let us consider the first-order logic extended with the least fixed point operator (FO+LFP). That is, together with the usual first-order formulas, we also have formulas of the form: $$\mu X[\...
10
votes
1answer
465 views

Set-theoretical multiverses and their representation as functors? Why *the* multiverse?

In some related MO questions like The set-theoretic multiverse as a (bi)category it is discussed how one might represent the multiverse (see The set-theoretic multiverse) in a category theoretic way, ...
12
votes
2answers
688 views

Set theory bootstrapping

Let $\mathcal{L}$ be the first order language of ZFC set theory, and let $\mathcal{L}_{\infty,\infty}$ be the usual infinitary extension of the language allowing arbitrary long disjunctions/...
20
votes
2answers
1k views

Mathematical Evidence Backing $|\mathbb{R}|=\aleph_2$

The "true" size of the real line, $\mathbb{R}$, has been the subject of Hilbert's first problem. Due to the Goedel and Cohen's work on the inner and outer models of $\text{ZFC}$, it turned out to be ...
3
votes
3answers
323 views

How can you formalize the metamathematics conventionally used to state Godel’s theorem?

Gödel’s incompleteness theorem states that for any sufficiently strong formal system $T$ there exists a statement $G$ such that if $T$ is consistent, then $G$ is true but not provable in $T$. But I’m ...
5
votes
1answer
201 views

Model theory of Banach algebras

Let us consider the (metric) theory of Banach algebras. I have a sentence encoding the (possible) openness of multiplication in a given Banach algebra: $$(\forall x) (\forall y) (\forall \varepsilon &...
8
votes
2answers
319 views

Models of arithmetic in a signature with exponentiation but not addition and multiplication

Let $\mathcal{L}_{\mathrm{exp}}$ be the language with signature $(0, ^\prime, <, \mathrm{exp})$ (with $0$ interpreted as zero, $^\prime$ as successor, and $\mathrm{exp}(x)$ as $2^x$) and let $\...
9
votes
1answer
249 views

Embeddings of Boolean algebras in $\wp(\omega)/Fin$

If we assume MA+¬CH, then every boolean algebra with cardinality smaller than the continuum embeds in ℘(ω)/Fin. A proof of this result can be found in Theorem 1.1, Chapter 8 of the book "Hausdorff ...
13
votes
1answer
541 views

Can the Induction axiom in the Peano arithmetic be replaced by the irrationality of $\sqrt{2}$?

This is inspired by the Alexander Shen's post here: https://www.facebook.com/groups/mathpuz/permalink/1058782384297603/ (the post is in Russian, but it is easy Russian, and google translate should ...
8
votes
0answers
219 views

What metatheory proves cut elimination for Simple Type Theory?

Gaisi Takeuti's book Proof Theory proves cut elimination for Simple Type Theory (a combined result of several researchers). Thus it proves consistency of Simple Type Theory with full comprehension in ...
4
votes
1answer
467 views

What are examples of non-equivalent virtualizations of a large cardinal?

This is a follow up to my previous question concerning virtual large cardinals, that are generally weaker axioms of infinity obtained from ordinary large cardinals through the so-called virtualization ...
3
votes
1answer
306 views

On the Actual Potential of Virtual Large Cardinals

Virtual large cardinals belong to a relatively new breed of strong axioms of infinity. They often appear as statements of the following form: Definition. Suppose $A$ is a large cardinal property ...
6
votes
0answers
183 views

Does $0^{\#}$ imply that $L$'s set generic multiverse has irreconcilable theories?

Suppose $0^{\#}$ exists. Let $M(L)$ be the generic multiverse over $L$ as viewed in $V$, i.e. $M(L)$ consists of all $L[g]$ where $g \in V$ is $\mathbb{P}$-generic over $L$ for some forcing $\mathbb{P}...
7
votes
0answers
222 views

Co-cones in the Turing degrees

Let the cocone of a Turing degree ${\bf d}$ be the set $cc({\bf d}):\{{\bf c}: {\bf c}\not\ge_T {\bf d}\}$. I'm curious what's known about the various partial orders (isomorphic to ones) of the form $...
9
votes
1answer
402 views

On the Large Cardinal Strength of Normal Moore Space Conjecture

In his seminal 1937 paper, Jones [1] proved the following result about Moore spaces: Theorem. (Jones) If $2^{\aleph_0}<2^{\aleph_1}$ then all separable normal Moore spaces are metrizable. Then ...
10
votes
0answers
229 views

Importance of Simple Theories

In model theory, a complete first-order theory $T$ is said to be simple if each type does not fork over some subset of its domain of size at most $|T|$. Question (1). What is the significance of ...
6
votes
1answer
182 views

Cohen generics over the ground model still Cohen over other generic extensions?

Let $M$ be a countable transitive model of (enough of) ZFC. I'm looking for notions of forcing $\mathbb{P}$ such that if $G$ is $M$-generic for $\mathbb{P}$, then $c$ is a Cohen real over $M$ if and ...
15
votes
1answer
1k views

What is the modal logic of outer multiverse?

The mathematical multiverse could be viewed as a gigantic Kripke model with models of $ZFC$ as possible worlds connected to each other via a certain accessibility relation. The modal logic associated ...
11
votes
1answer
842 views

The Tall Tale of Terminating Transfinite Towers

The transfinite tower of iterative automorphisms of a group $G$ is simply definied to be the following chain of the groups where $G_{\alpha+1}=Aut(G_{\alpha})$ for each ordinal $\alpha$ and the direct ...
2
votes
1answer
164 views

Can a type in a lower universe be formed from types in higher universes?

A type universe is a type of small types that is closed under the basic type formation operations (dependent product, sum, coproduct etc.), that is to say for example that from $A \colon U_i$ and $x \...
2
votes
1answer
350 views

Problem on reading Jech's set theory about forcing (of Lemma 15.19)

As the proof in the picture, the author says that we can assume that every condition forces that $\dot{f}$ is a function form $\lambda$ to $A$. I guess that here he means that we can assume $A=M\cap ...
4
votes
1answer
163 views

Indecomposable ordinals and pseudointersection

Is the following claim correct (Chapter 13 before Theorem 87 of Todorcevic's book: Notes on forcing axioms): Let $\alpha$ be an infinite countable indecomposable ordinal and $U$ be an uniform ...
23
votes
1answer
1k views

Forcing and Family Contentions: Who wins the disputes?

The famous game-theoretic couple, Alice & Bob, live in the set-theoretic universe, $V$, a model of $ZFC$. Just like many other couples they sometimes argue over a statement, $\sigma$, expressible ...
8
votes
1answer
240 views

Is there a function from a Suslin tree to itself which send compatible elements to incompatible elements?

We say $S$ is a Suslin forest if adding a minimum to $S$ we have a Suslin tree. So a Suslin Forest is essentially a Suslin tree $S$ in which we drop the requirement for $S$ to have a single root. ...
0
votes
0answers
83 views

Example of a zero-knowledge protocol for a strictly Pi_n sentence?

I'm looking for an example of a zero-knowledge protocol such that (1) the prover Peggy can demonstrate to the verifier Victor that she has a proof of $P$ (to the usual standards of a zero-knowledge ...
4
votes
0answers
133 views

Non-special $\aleph_2$-Aronszajn trees in the Laver-Shelah model for $\aleph_2$-Souslin hypothesis

Assume $V=L$ and let $\kappa$ be a weakly compact cardinal. Let $G$ be $Col(\aleph_1, < \kappa)$ generic over $V$. Working in $V[G]$ force with a countable support iteration of forcing notions of ...
9
votes
0answers
167 views

Analogue of strong stationary reflection from MM

Foreman-Magidor-Shelah proved that if Martin’s Maximum holds, then for every regular $\kappa>\omega_1$, every stationary $S \subseteq S^\kappa_\omega$ contains a club of ordertype $\omega_1$. This ...
-2
votes
1answer
153 views

Can someone help me understand Curry's paradox? [closed]

I understand the general concept, that if you define a statement X such that X = X -> Y, you can prove that X is true regardless of Y so you can then prove any statement. What I don't quite understand ...
4
votes
0answers
149 views

Generic two-cardinal behavior of first-order sentences

This is a hopefully improved version of a question I asked before and then deleted because it was based on some fundamentally incorrect assumptions. Some first-order theories are able to control the ...
10
votes
1answer
236 views

The partial preorder on $\mathbb N$ generated by the finite axioms of choice

Let $\mathsf C_n$ denotes the statement: for any family $\mathcal F$ of $n$-element sets there exists a choice function (i.e., a function $f:\mathcal F\to\bigcup\mathcal F$ such that $f(F)\in F$ for ...
0
votes
0answers
103 views

Is this schema equivalent to Replacement under removal of Extensionality?

If $\phi(x)$ is a formula in which only symbol $``x"$ occurs free, and it only occurs free, and in which symbol $``y"$ never occurs; and if $\phi(y)$ is the formula obtained from $\phi(x)$ by merely ...
0
votes
1answer
224 views

Criterion of completeness

Wittgenstein (PR 181) talks about a criterion of completeness for the irrationals. I am trying to understand what this might mean. Completeness of the reals, in the decimal number system, is the ...
5
votes
1answer
461 views

Forall exists formula

This is a reference request. Let $A$ be a formula in the language of rings which is of the form $\forall_{x_1}\dots\forall_{x_n}\exists_{y_1}\dots\exists_{y_m} F$, where $F$ is quantifier-free. I once ...
9
votes
1answer
176 views

Elementary equivalence of monoidal categories =?

Recall that, in model theory, two models $M_1$ and $M_2$ of the same signature are elementary equivalent if $ M_1 \models \phi \Leftrightarrow M_2 \models \phi $ for every first order formula $\phi$ ...
8
votes
0answers
258 views

Is Videla's solution of Hilbert's tenth problem for rational functions over field of characteristic 2 wrong?

The paper in question. Quick introduction to the problem: suppose that $F$ is a finite field of characteristic 2 (for purposes of this post $F = \mathbb{F}_2$ will suffice) and let $F[t]$ and $F(t)$ ...
4
votes
0answers
109 views

Does comprehension for formulas in the analytical hierarchy imply comprehension for all formulas in second-order arithmetic?

The proof that all formulas of second-order arithmetic are $\Pi^1_n$ for some $n$ (i.e. can be written with a bloc of second-order quantifiers followed by an arithmetical formula) uses the axiom of ...
4
votes
1answer
285 views

How much homotopy type theory should be modeled by the unstable motivic category?

It's often said that homotopy type theory should be interpretable in any $\infty$-topos. But really it should be interpretable in any "predicative $\infty$-topos". I'm not quite sure what this means, ...
2
votes
1answer
297 views

What is the consistency strength of definable axiomatization of ZFC?

Let $x^\phi$ be the set $x$ that is definable after the parameter free formula $\phi$, i.e. formally we have: $$\forall y (y \in x^{\phi} \leftrightarrow \phi(y))$$ Now by $\text{definable ZFC}$ it ...
9
votes
2answers
520 views

On Applications of Forcing in Domain Theory

An interesting feature of domain theory is to use partial orders in order to provide a mathematical model for the computational approximation in a potentially infinite computational process (e.g. ...
6
votes
1answer
199 views

distributivity of termspace forcing

Laver introduced the concept of termspace forcing. If $\mathbb P * \dot{\mathbb Q}$ is a two-step iteration, then we can order the $\mathbb P$-names for elements of $\dot{\mathbb Q}$ by putting $\dot ...
3
votes
0answers
227 views

Upward confluence in the interaction calculus

The lambda calculus is not upward confluent, counterexamples being known for a long time. Now, what about the interaction calculus? Specifically, I am looking for configurations $c_1$ and $c_2$ such ...
2
votes
0answers
135 views

What is the consistency limit of accumulative typing below $\omega_1^{CK}$?

Let $Th_\zeta$ be a Mono-sorted first order theory with $\zeta$ representing some recursive ordinal notation system. Primitives: =, $\in$, $T_0, T_1, ..,T_i,..$ where i is an $\zeta$ ordinal, and ...
9
votes
0answers
253 views

ZF + “every Suslin set of reals is ${\bf \Sigma}^1_2$”

What is known about the theory ($\ast$) ZF + "every Suslin set of reals is ${\bf \Sigma}^1_2$"? By "reals" I mean elements of the Baire space $\omega^\omega$. For a cardinal $\kappa$, a set of ...
8
votes
1answer
288 views

Is every set smaller than a regular cardinal, constructively?

Constructively, my only interest in regular cardinals is in terms of the "$\Sigma$-universes" they generate. By a $\Sigma$-universe, I mean a collection of triples $(X,Y,f: X \to Y)$ closed under base ...
3
votes
1answer
149 views

Axioms for modal logics based upon counterfactuals

Suppose we have a logic for counterfactuals as with David Lewis. I here use $\Rrightarrow$ for the counterfactual conditional. So suppose we have: Rules: (1) If $A$ and $A\rightarrow B$ are ...