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.

-4
votes
0answers
59 views

A few model theoretical questions on the *SR* type of $Peano Arithmetic$

Let $srPA$ be an extension of (FOL) $PA$ formal system, defined per the following: $srPA = PA + SR$ where: $SR$ $\leftrightarrow$ $(\lnot GC \land \lnot cGC)$ $GC$ $\leftrightarrow$ Goldbach ...
5
votes
2answers
196 views

Characterizing “bounded” distributivity in terms of dense open sets

Prikry forcing is a well-known example of a forcing which adds an $\omega$-sequence to some cardinal $\kappa$, but does not add bounded subsets to $\kappa$. There are other examples of forcings which ...
5
votes
0answers
136 views

Topological applications of $\mathfrak{p}=\mathfrak{t}$

I'm working on the Malliaris-Shelah's recent result of $\mathfrak{p}=\mathfrak{t}$, but I'm more interested in what possible topological applications can derivate from this equality. Searching in ...
6
votes
1answer
231 views

Failure of GCH at a strongly compact cardinal

Does Con(ZFC+ there exists a strongly compact cardinal) imply Con(ZFC+ there exists a strongly compact cardinal $\kappa+ 2^\kappa > \kappa^+$)?
0
votes
1answer
259 views

Smallest $\beta$ such that it is provable that $2^{\aleph_\beta} > 2^{\aleph_0}$

What is the smallest cardinal $\beta$ such that it is provable in ${\sf (ZFC)}$ that $2^{\aleph_\beta} > 2^{\aleph_0}$?
11
votes
3answers
369 views

Infinite descending consistency chains

What are some examples of consistent theories $T_i$ (extending elementary arithmetic EA) such that for $∀i∈ℕ \,\, T_i ⊢ \mathrm{Con}(T_{i+1})$? Such theories exist; see for example An infinitely ...
2
votes
0answers
51 views

What is the computational complexity of equivalence up to a critical point in the one generator free self-distributive algebra?

Suppose that there exists a rank-into-rank cardinal. Then let $R$ be the relation on the set of terms in the language of self-distributive algebras (or LD-monoids) on one generator where we set $R(s,t)...
-1
votes
1answer
224 views

What is the consistency strength of this kind of iterating Berkeley cardinals?

[EDIT] After suggestion from Monroe Eskew, and after having an e-mail correspondence with Prof. Joan Bagaria, I'll re-present the older question as the second in a series of 4 questions. I've had an e-...
3
votes
0answers
41 views

Proof that superstable theories with no Vaughtian pairs have no imaginary Vaughtian pairs

In 'Elementary pairs of models' by Bouscaren, she mentions with a remark at the end that if $T$ is a superstable theory then $T$ has a Vaughtian pair if and only if $T^\text{eq}$ has a Vaughtian pair, ...
55
votes
9answers
9k views

Arguments against large cardinals

I started to learn about large cardinals a while ago, and I read that the existence, and even the consistency of the existence of an inaccessible cardinal, i.e. a limit cardinal which is additionally ...
1
vote
0answers
122 views

Is it possible to construct a formal language that allows to refer to specific real numbers that encode ordinals accidentally writable by an ITTM?

Let $A$ denote a particular (fixed) algorithm to encode ordinals as real numbers. The exact technical description of $A$ is irrelevant for this question: it can be any algorithm that is mathematically ...
-3
votes
0answers
65 views

How to write a function defined by segments in a formula? [closed]

I would like to define a function like f(x) = 5 if x is even, and f(x) = 8 if x is odd by using a first order logic formula. Is it possible? if yes, how?
2
votes
2answers
777 views

Modal logic - satisfiability

Hi there, Assuming X and Y are modal formulae and diamond X is satisfiable and diamond Y is satisfiable, how would one show that they X AND Y is satisfiable? I don't think it requires much effort? ...
48
votes
10answers
14k views

What are some important but still unsolved problems in mathematical logic?

In the past, first-order logic and its completeness and whether arithmetic is complete was a major unsolved issues in logic . All of these problems were solved by Godel. Later on, independence of ...
1
vote
1answer
114 views

ZFC ability to express truth and $\omega$ - consistency

Some theories can lie about their own consistency (for example, if $PA$ is consistent then the theory $PA + \lnot CON(PA)$ is consistent, although it proves its own inconsistency). Now working with ...
3
votes
0answers
64 views

Can algebras of elementary embeddings be sufficiently described by two element subalgebras?

Let $\mathcal{E}_{\lambda}$ be the set of all elementary embeddings $j:V_{\lambda}\rightarrow V_{\lambda}$. Then $\mathcal{E}_{\lambda}$ can be endowed with a self-distributive operation $*$ where $j*...
6
votes
0answers
115 views

If $j_{1},…,j_{n}:V_{\lambda+1}\rightarrow V_{\lambda+1}$ are elementary embeddings, then does $j_{1}(A)=…=j_{n}(A)=A$ for some linear order $A$?

Suppose that $j_{1},\dots,j_{n}:V_{\lambda+1}\rightarrow V_{\lambda+1}$ are elementary embeddings. Then does there necessarily exist a linear ordering $A$ of $V_{\lambda}$ such that $j_{1}(A)=\dots=j_{...
23
votes
5answers
2k views

How do we construct the Gödel’s sentence in Martin-Löf type theory?

In Martin-Löf dependent type theory (MLTT), under the proposition-as-types correspondence, we sometimes say that a proposition $A$ is true if the type $A$ is inhabited. However, there is no doubt that ...
15
votes
1answer
653 views

Axiom of Choice versus V=L in opposition to large cardinals

Consider the following two observations: The axiom $V=L$ is incompatible with large cardinal axioms that are somehow "too large", like measurable cardinals. The axiom of Choice is incompatible with ...
5
votes
2answers
319 views

Cases where multiple induction steps are provably required

I am looking for references for theorems of the form: 1) Any proof of theorem $X$ requires $n$ applications of induction axioms and especially 2) Any proof of theorem $X$ requires $n$ nested ...
209
votes
29answers
28k views

What are some reasonable-sounding statements that are independent of ZFC?

Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC." For example, suppose A is an abelian group such that every ...
8
votes
0answers
178 views

Proper classes in Bounded Zermelo set theory

I want to know if there is a standard terminology for this among set theorists working with element-based set theories like ZFC. I will follow the convention that a class in any given set theory is a ...
1
vote
0answers
56 views

Consistency of reflective sequences

Is it consistent that there is a measurable cardinal $κ$, a $κ$-complete normal nonprincipal ultrafilter $U$ on $κ$, and $S∈U$ such that for every $T⊂S$ with $T∈U$ and $T$ ordinal definable from $S$ ...
5
votes
1answer
100 views

Given B,C incomplete, incomparable r.e. sets must C compute low r.e. set avoiding cone below B? (ADDED: Uniformly?)

I feel like there must be a classical result answering this question (or easily modified to do so) but a quick flip through Soare didn't produce anything so rather than waste time I figured I'd just ...
13
votes
1answer
241 views

Is there a constructive proof that in four dimensions, the PL and the smooth category are equivalent?

Summary Famously, the categories of 4-dimensional smooth manifolds and 4-dimensional piecewise linear manifolds are equivalent. Is there a constructive proof for this theorem or does it depend on the ...
10
votes
2answers
395 views

Is the existence of double complement of a set provable in Intuitionistic ZF?

In Powell's article [1] he introduces the axiom of double complement, which says a double complement $\{x : \lnot\lnot(x\in A)\}$ is a set for any set $A$. I can't find similar axiom from other ...
2
votes
1answer
73 views

Henkin-style completeness proofs for intuitionistic logic

Henkin-style completeness proofs are founded on a few basic presuppositions, such as the assumptions that the language of a logical theory must be enumerable, and that it must contain a (not ...
2
votes
2answers
227 views

Meta-incomputability

Is there a set $B$ about which it provably cannot be decided whether it is computable in $\mathsf{ZFC}$?
2
votes
1answer
106 views

System T, System F and arithmetical hierarchy

I refer to Proof and Types by Jean-Yves Girard for the definition of System T (pag. 46) and System F (pag. 81). In this treatise there are two base types, i. e. $\text{Int}$ (natural numbers) and $\...
7
votes
2answers
299 views

Syntax/semantics conflation leads to infinitary logic

It is written (cf. Moore 1980, page 100) that mathematical logicians (e.g. Peirce, Schröder, Hilbert) at the turn of the last century did not yet distinguish between syntax and semantics when ...
0
votes
1answer
158 views

Why the restrictions in the definition of Berkeley cardinals?

A cardinal κ is a Berkeley cardinal, if for any transitive set $M$ with $κ∈M$ and any ordinal $α<κ$ there is an elementary embedding $j : M → M$ with $\alpha<\text{crit}(j)<\kappa$. My ...
-4
votes
2answers
168 views

What happens if I replace a *unique natural number* that form a commutative Monoid with *the set of integers* Z that form a commutative Ring? [closed]

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was ...
19
votes
1answer
782 views

Fubini without CH

In Real and Complex Analysis, Rudin gives an example (due to Sierpinski) of a function $f:[0,1]^2\to[0,1]$ separately Lebesgue-measurable in each argument, such that $$ \int_0^1 dx\int_0^1f(x,y)\,dy \...
10
votes
1answer
334 views

The least admissible above a dominating real

Let $\mathbb{P}$ be the usual forcing which adds a dominating real: conditions in $\mathbb{P}$ are pairs $(p, f)$ with $p:\omega\rightarrow\omega$ finite partial and $f:\omega\rightarrow\omega$ total, ...
-3
votes
1answer
188 views

Can there be elementary embedding between a universe and a universe inside it?

[EDIT] the prior question was trivially false, however the intention is to arrange a possible world of such universes, in other words the question is about if it is possible to have a proper class $\...
17
votes
7answers
2k views

Understanding Specker's disproof of the axiom of choice in New Foundations

Hi all! I am trying to understand Specker (1953)'s proof (found here) that the axiom of choice is false in New Foundations. I am stuck on the following point. At 3.5 Specker writes: 3.5. The cardinal ...
9
votes
0answers
349 views

Reverse Mathematics of Euclid's theorem

Euclid's theorem that there are infinitely many prime numbers has multiple proofs, ranging from Euclid's original theorem that constructs a new prime from a finite list of such, to Euler's proof that ...
13
votes
4answers
2k views

Are there textbooks on logic where the references to set theory appear only after the construction of set theory?

This is cross posted from MathStackExchange. Since this is a reference request, I believe there will not be duplications of efforts in answers. This is also related to the question here. In ...
0
votes
0answers
260 views

What is the consistency status of this theory?

Let $K_2^+(W)$ be the following theory in the language $L(\in,W)$ with the constant symbol $W$. Extensionality: $\forall x (x \in a \leftrightarrow x \in b) \to a=b$ $\mathcal{Define:} \ set(x) \iff ...
0
votes
1answer
76 views

Strength of BTEE

What is the consistency strength of Basic Theory of Elementary Embeddings (BTEE) from The spectrum of elementrary embeddings j : V → V by Paul Corazza? BTEE uses the language of $(V,∈,j)$ and asserts:...
0
votes
0answers
87 views

Is there a clear inconsistency with intense reflection of top properties of the universe?

Let $V$ be the class of all sets, where sets are defined like in $MK$ as elements of classes. Properties of $V$ whose negations are unbounded (by element-hood & subset-hood) in $V$ would be ...
11
votes
0answers
236 views

Consistency strength of $j:L_δ→L_δ$ for some δ

What is the consistency strength of existence of a nontrivial elementary embedding $j:L_δ→L_δ$ for some ordinal $δ$? The consistency strength is strictly between totally ineffable and $ω$-Erdős ...
2
votes
1answer
306 views

Can Ackermann set theory find a natural interpretation in light\heavy class dichotomy?

I want to coin the notion of heaviness of a class as a function from classes to ordinals such that $$heaviness(x)=|TC(x)|$$, i.e. the heaviness of a class is the cardinality of its transitive closure. ...
8
votes
0answers
152 views

α-Mahlo vs weakly compact cardinals

Question: What is the consistency strength of existence of a $(κ^{++})^L$-Mahlo cardinal $κ$? I am particularly interested in how the strength compares to weakly compact cardinals (and other levels ...
1
vote
0answers
51 views

Questions in proof theory (PRA-provability of EA-theorems, Girards book from '87)

I've been working through a textbook, often encountering difficulties with the exercises. On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution. As I understand, ...
0
votes
0answers
39 views

Are the HBL derivability conditions necessary for Gödel's incompleteness theorems? (For Löb's theorem?)

I've been working through a textbook, often encountering difficulties with the exercises. On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution. As I understand, ...
0
votes
0answers
74 views

Shepherdson's conditions - a shortcut to the second incompleteness theorem?

I've been working through a textbook, often encountering difficulties with the exercises. On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution. As I understand, ...
16
votes
1answer
511 views

How is this fixed point theorem related to the axiom of choice?

I'm hoping the answer to this is well-known. Let $X$ be an ordered set (i.e. poset). An inflationary operator $f$ on $X$ is a function $f: X \to X$, not necessarily order-preserving, such that $f(x) ...
1
vote
0answers
69 views

n-consistency - provability/truth of $\Sigma^0_n$ and $\Pi^0_{n+1}$ -formulas; n-consistent extensions, etc

I've been working through a textbook, often encountering difficulties with the exercises. On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution. As I understand, ...
9
votes
3answers
1k views

Is there a version of the Archimedean property which does not presuppose the Naturals?

All the statements of the Archimedean property with which I am acquainted fundamentally uses ℕ -- more than as a totally ordered semi-group, really being the 'standard model' of the naturals. ...