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
61 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 ...
-1
votes
1answer
223 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}$?
2
votes
0answers
48 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)...
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, ...
11
votes
3answers
359 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 ...
-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?
1
vote
0answers
119 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
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*...
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 ...
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_{...
15
votes
1answer
649 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 ...
8
votes
0answers
177 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$ ...
13
votes
1answer
240 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 ...
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 ...
5
votes
2answers
318 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 ...
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 ...
-1
votes
1answer
221 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-...
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 $\...
0
votes
1answer
157 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
167 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
779 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 \...
7
votes
2answers
298 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 ...
-3
votes
1answer
187 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 $\...
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 ...
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 ...
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 ...
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, ...
16
votes
1answer
510 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) ...
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, ...
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. ...
1
vote
0answers
68 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, ...
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 ...
0
votes
0answers
62 views

Is Reflective Set Theory stronger than $\small {\mathsf{ARC}}$?

By $\mathsf{RfST}$ its meant Reflective Set Theory exposited in this posting I'll pose two specific questions here: Is $\mathsf{ARC}$ class theory a proper sub-theory of $\mathsf{RfST}$? Is $...
1
vote
0answers
236 views

Does this axiomatic system satisfy requirements for founding mathematics?

In this article, the author, F.A.Muller, suggests criteria for a founding theory of mathematics (pp:14-16). The author proposes $ARC$ Class Theory to embody these requirements. The motivation is ...
1
vote
1answer
50 views

Downward density of w-REA sets under arithmetic reducibility?

Is the question of the downward density of the w-REA sets under $\leq_a$ still open? If not can anyone point me to a proof? That is do we know if for every $\omega$-REA set $X >_a 0_a$ there ...
2
votes
1answer
106 views

Correct Proof Of ZBC Theorem From Odifreddi? Also Extension Question

So I'm looking at the proof of the ZBC lemma in Odifreddi's Classical Recursion Theory volume 2 page 808 and I don't see why $ 0' \oplus C$ produced computes $B'$ as claimed. The positive ...
1
vote
1answer
136 views

On a combinatorial set covering property

Let $\kappa < \lambda < \mu$ be infinite cardinals. Is there a collection ${\cal U}\subseteq {\cal P}(\mu)$ of subsets of $\mu$ with the following properties? for all $U\in {\cal U}$ we have $|...
0
votes
0answers
101 views

Can reflection in $V$ and reflection out of $V$ principles be used in the same theory?

I've noticed that most of the work in Ackermann set theory is primarily concerned with constructing sets in $V$, the rest of the classes are just excess material, carrying no comprehension over them. ...
4
votes
0answers
106 views

Can this reflective class theory interpret ZFC?

Reflective Set Theory $\mathsf{RfST}$ is formulated in first order predicate logic with extra-logical primitives of equality $``="$, membership $``\in"$, and a single primitive constant symbol $V$ ...
0
votes
1answer
86 views

Superintuitionistic logics which are not hereditary/monotonic: impossible or possible?

An intuitionistic Kripke model is a triple $\langle W,\leq, \Vdash \rangle$, where $\langle W,\leq \rangle$ is a preordered Kripke frame, and $\Vdash$ satisfies the following condition of ...
7
votes
1answer
182 views

Effective set= ordinal definable set

I just today realized that the concept of ordinal definability is defined in a different way by vopenka-Balcar-Hajek ``The notion of effective sets and a new proof of the consistency of the axiom of ...
0
votes
0answers
56 views

What is the limit to iterating class comprehension, reflection and limitation of size?

In posting about a reflection principle coupled with a limitation of size axiom over Ackermann set theory, the answer is that the theory is blown up to a Mahlo cardinal. I'm here just wondering if ...
8
votes
0answers
168 views

Reflection principle for intuitionistic Zermelo–Fraenkel?

The well-known reflection principle for classical Zermelo–Fraenkel states: For any formula $\varphi(x_1,\ldots,x_n)$ of the language of ZFC with free variables $x_1,\ldots,x_n$, ZFC proves $$ \...
22
votes
1answer
407 views

Is there a short proof of the decidability of Kepler's Conjecture?

I've believed that the answer is "yes" for years, as suggested in various sources with reference to Tóth's work. For example, the Wikipedia article for Kepler Conjecture says: The next step toward ...
3
votes
1answer
154 views

What is the strength of adding limitation of size and a simple version of reflection to Ackermann set theory?

The following theory is formulated in first order predicate logic with extra-logical primitives of equality $``="$, membership $``\in"$, and a single primitive constant symbol $V$ denoting the class ...
6
votes
0answers
254 views

measure of generic reals in forcing extensions

It is well-known that if $V[G]$ is a generic extension by adding a Cohen real, then the set $\{r \in V[G]: r$ is Cohen generic over $V\}$ has measure zero. On the other hand, if $V[G]$ is a generic ...