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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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, ...

5
votes
0answers
23 views

Does this consequence of measurability in terms of games of length $\omega+1$ imply measurability?

For any two structures $\mathcal{M}$ and $\mathcal{N}$ in the same first-order language $\mathcal{L}$ and any ordinal $\theta$, let $G_\theta(\mathcal{M},\mathcal{N})$ be the two-player game of ...
7
votes
0answers
237 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 ...
33
votes
7answers
3k views

Paradoxical Mathematical Objects Pending for Construction [duplicate]

The possible properties and applications of some mathematical objects have been described far before their rigorous mathematical definition. Some of them even had a seemingly paradoxical description ...
6
votes
1answer
172 views

Interpreting a space in Baire space: how many facts do I need to understand the whole thing?

Below I'm working in ZF+DC+AD or similar; I want enough choice that things don't explode, but I also want the Wadge hierarchy to be well-behaved everywhere. Since this question is a bit long, I've put ...
2
votes
1answer
111 views

Is any real closed extension of $\mathbb R$ characterized up to isomorphism by its ladder?

Let $R$ be a real closed field. Recall that the ladder of $R$ is the divisible, ordered abelian group obtained by quotienting $R$ by a certain equivalence relation. Note that $R$ has trivial ladder ...
0
votes
0answers
95 views

Intuition of Łoś's theorem [on hold]

Łoś's theorem: If $F$ is an ultrafilter on $I$, $M_i$ is a model with domain $A_i$, then for any formula $\phi$ of L and any sequence $f/F \in (\prod A_i / F)^\omega$ $$\prod M_i/F \vDash_{f/F} \phi \...
3
votes
1answer
97 views

Strongly reducible but not effectively interpretable

A countable structure A is strongly reducible to a structure B if there is a uniform turing functional which, given a copy of the atomic diagram of B, computes a copy of the atomic diagram of A. A is ...
-8
votes
0answers
134 views

The heartbeat of the earth [closed]

My partner and I are not mathmaticians... We have an interesting question that we think we have come up with an answer to If the earth had a heartbeat... What would it be? We have tried to work it ...
5
votes
3answers
283 views

Formalizations of the idea that something is a function of something else?

I'll state my questions upfront and attempt to motivate/explain them afterwards. Q1: Is there a direct way of expressing the relation "$y$ is a function of $x$" inside set theory? More ...
0
votes
0answers
83 views

Can you clarify the apparent difference between two set theory proof techniques? [closed]

I'm working my way through Rosen's $\textit{Discrete Mathematics and it's Applications}$ (7th edition) after a break of several years. In the discussion of proving set theory identities, an argument ...
15
votes
1answer
215 views

Proof as a Σ₁ approximation to truth: what about higher degrees?

Let us posit that the goal of mathematics is to study mathematical truths, and let us stick to arithmetic for simplicity: so let $\mathscr{T} \subseteq \mathbb{N}$ be the set of (Gödel codes of) true ...
11
votes
1answer
343 views

Fixed points of injective self-maps

Is it consistent in $\mathsf{ZF}$ that there is a set $X$ with more than $1$ point such that every injective map $f:X\to X$ has a fixed point?
27
votes
1answer
712 views

Is this conjecture strictly weaker than P=NP?

My three computability questions are related to the following group theory question (first asked by Bridson in 1996): For which real $\alpha\ge 2$ the function $n^\alpha$ is equivalent to the Dehn ...
1
vote
2answers
138 views

Time functions of non-deterministic Turing machines (a better question)

This is a more precise version of that question. 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 ...
2
votes
1answer
110 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
165 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 ...
10
votes
1answer
389 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 ...
-2
votes
0answers
50 views

Set models of ZFC and their perspectives on themselves and on other models [migrated]

Say $L$ is a PL1 language and $T$ is an $L$ theory. Then we have: (Gödel) Completeness. $T$ consistent $\Rightarrow$ $T$ has a (set) model Say $T = ZFC$ and $M \subset N$ for two (set) ...
1
vote
1answer
94 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 ...
5
votes
1answer
234 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
162 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
422 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
625 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/...
19
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
277 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
171 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
301 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
232 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
471 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
173 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 ...
5
votes
1answer
417 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 ...
4
votes
1answer
273 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
174 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}...
5
votes
0answers
173 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 $...
10
votes
1answer
372 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 ...
9
votes
0answers
194 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
163 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 ...
-1
votes
0answers
91 views

Consistency of a modification of ZF with restricted comprehension

Consider a modification of ZF with the axiom schema of separation replaced by the restricted comprehension which can only be applied to statements $P$ satisfying the following condition: for any ...
12
votes
1answer
820 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
149 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
334 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
159 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 ...
24
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 ...
7
votes
1answer
230 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
73 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 ...
3
votes
0answers
120 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
162 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
139 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
142 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 ...