New answers tagged

1 vote

Notion of independence of Turing degrees

Rather belatedly, I should probably mention that Uri Andrews, Peter Gerdes, Steffen Lempp, Joe Miller, and I have written a paper on this: Computability and the symmetric difference operator (DOI); ...
user avatar
1 vote

If $X \leq_T Y + 0'$ does there exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$?

Ohh, I think I'm being dumb. The answer is no. Given $X \not\leq_T 0'$ we build $Y$ using the finite extension method and modify the usual minimal pair construction by coding in the bits of $X$ into $...
user avatar
  • 1,565
1 vote
Accepted

Set theory / Formal logic of Baba is You

The developer has a GDC talk where he talks about the mechanics which you might find interesting. My impression is it's a lot of random hacks, which may fit with your description.
user avatar
7 votes
Accepted

Gaps in cardinalities of MAD families

Yes, this is consistent. Suppose we force to add $\kappa$ mutually generic Cohen reals to a model of $\mathsf{CH}$, where $\kappa$ is some cardinal with uncountable cofinality. In the extension, there ...
user avatar
  • 14.7k
1 vote

An axiomatic approach to the multiverse of sets

This might not precisely answer your question, but why not use topos theory? The category of (Grothendieck) topoi has as its objects generalized universes of sets whose internal logic does no not ...
user avatar
0 votes

Persistent finite axiomatizability, relational edition

Let me collect some partial results and some speculation that may be useful here. The set $T_{w/o=}$ is axiomatized by $A_I$ in some cases. For example, if $A$ is preserved under quotient by the ...
user avatar
6 votes
Accepted

Preservation of projective stationarity

It is possible that $\sigma$-closed forcing destroys projective stationarity: Suppose $\mathcal A$ is a maximal antichain in $\mathrm{NS}_{\omega_1}^+$. Feng-Jech have shown that $$\mathcal S=\{N\in [...
user avatar
6 votes

How hard must "no high-degree irreducibles" proofs be?

I don’t know how to make use of the full power of the intermediate value theorem, hence I will work instead with a weaker axiomatization: let $\def\rcf{\mathrm{RCF}}\rcf'_k$ denote the first two ...
user avatar
7 votes

Free algebras from model theory perspective

Here are some papers. (1) Baldwin, J. T.; Shelah, S. The structure of saturated free algebras. Algebra Universalis 17 (1983), no. 2, 191-199. From the Math Review (written by Steve Comer): The authors ...
user avatar
0 votes

When are two proofs of the same theorem really different proofs

There is clearly something subjective in judging how much two proofs are "essentially equivalent". A possible definition, which unfortunately only covers a portion of cases, is the following:...
user avatar
1 vote

When are two proofs of the same theorem really different proofs

I would distinguish proofs by what else they show beyond the fact that is "officially" proved. For example, to show that Liouville's and Cantor's proof about the existence of transcendental ...
user avatar
  • 403
5 votes
Accepted

At which large cardinal, the theory of the minimal transitive model of ZFC starts proving its absence?

I don't like using the same notation to denote theories and ordinals, so I'll just use "$\alpha$" for the smallest ordinal such that $L_\alpha\models\mathsf{ZFC}$ (and assume that there is ...
user avatar
0 votes

$\Pi^0_2$ singleton of minimal arithmetic degree?

Less an answer than a potential sketch at an approach right now but I wanted to put it up here just in case it was right (but it's way too simple to be right) Let $A$ be a non-arithmetic $\Pi^0_2$ ...
user avatar
  • 1,565
0 votes

An exercise in fuzzy logics built from a t-norm

My teacher has provided a solution: Take a $[0, 1]_*$-interpretation with $I(\phi \rightarrow \phi * \phi ) = 1$, and say $a:=I(\phi)$. Define the function \begin{align*} h: [0, 1] & \rightarrow [...
user avatar
  • 301
7 votes

Is there a finitely axiomatizable class of structures whose equality-free theory is not finitely axiomatizable?

EDIT: As pointed out by Emil Jerabek in the comments, the argument for relational languages fails in the last step. However, the question is already answered by the example with function symbols. EDIT:...
user avatar
5 votes

Stone-Čech compactification

As for Q1, the answer is no. As remarked by Narutaka, the hyperstonean cover of $[0,1]$ does not have isolated points (Corollary 2.22) and all points of a discrete space $\Gamma$ are isolated in $\...
user avatar
  • 10.9k
2 votes

Construction of models for true but unprovable formulas

Yes, check out the Paris-Harrington theorem's use of indicators as one way to do this for a specific kind of Ramsey theorish combinatorial claim. It's kinda a tough slog but it's a really explicit ...
user avatar
  • 1,565
0 votes

How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?

This and related questions about decision times of ITTMs are addressed in this paper: "Decision times of infinite computations" https://arxiv.org/abs/2011.04942 The ordinal you are asking ...
user avatar
  • 1
8 votes

Does permission always work?

Dan's answer is very nice and should be the accepted answer. However, I thought it might be worth pointing out that there's a much easier counterexample to your first question (with the stricter ...
user avatar
10 votes
Accepted

Does permission always work?

No, there is a counterexample. The idea is that the use of the computation $X \le_T ran(g)$ can be much worse than identity, and since we only care about the reduction in one direction, we can drive ...
user avatar
  • 2,169
1 vote
Accepted

Consistency of the Hurewicz dichotomy property

The anwer is in: Tall, Franklin D.; Todorcevic, Stevo; Tokgöz, Seçil, The strength of Menger’s conjecture. In the paper they prove (among other things) that the Hurewicz dichotomy extended to all ...
user avatar
  • 823
0 votes

A weak (?) form of Shelah cardinals

I think any measurable Woodin cardinal is a limit of weakly Shelah cardinals. To see this, note that, if $\kappa$ is a Woodin cardinal, for any $f : \kappa \to \kappa$, $\kappa$ is a limit of ...
user avatar
5 votes

Reinhardt's ultimate classes

You can find Reinhardt's philosophy of set theory in "Set existence principles of Shoenfield, Ackermann, and Powell", Fundamenta Mathematica, vol 84, pp 5-34 and "Remarks on reflection ...
user avatar
2 votes
Accepted

How large is the supremum of minimal $V$-heights of all first-order set theories formulated in a particular language of FOST?

Your ordinal $\beta_\mathcal{L}$ is perfectly well-defined: in my opinion it's more easily thought of as $$\sup\{\alpha: \forall \beta<\alpha(V_\beta\not\equiv V_\alpha)\},$$ and this definition ...
user avatar
14 votes
Accepted

Can $\kappa^\lambda$ be large if $2^\lambda$ is small and $\lambda<\mathrm{cof}(\kappa)$?

It is consistent that such a pair exists, see my paper Singular cofinality conjecture and a question of Gorelic. To show that some large cardinals are needed, suppose for example $\lambda=\aleph_0 <...
user avatar
5 votes
Accepted

Are equinumerous size preserving models of a theory isomorphic?

There is no version of this question I can think of which has an affirmative answer. Let $\alpha,\beta$ be distinct countable ordinals such that $L_\alpha\equiv L_\beta\equiv L_{\omega_1^L}$ (which ...
user avatar
8 votes
Accepted

How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?

The answer to Question 1 is positive (thus the answer to Question 2 is also positive). More explicitly, the positive answer to Question 1 follows from the following well-known facts: Lemma 1. $(M,\...
user avatar
  • 14.5k
0 votes

A question about the axiom of dependent choice

It appears the result is a consequence of a general result of Joseph Shoenfield (A relative consistency proof, J. Symbolic Logic 19 (1954), 21–28) which, in turn, is an improvement of results of ...
user avatar
3 votes
Accepted

Can ZFC sets be interpreted as single rooted trees with accessible degree and countable height?

The details of your graph theory will matter - how, for example, are you going to experess "$(1,\mathsf{icc}, \omega)$" in your setting? - but certainly some version of this will work: in a (...
user avatar
2 votes

Properties of Jech's hierarchy of stationary sets (Exercise 8.13, 8.14 of Jech)

Here were my solutions from a few years ago, when I worked through Jech's 1984 paper on this topic. Exercise 8.13: If $\lambda<\kappa$ is the $\alpha$th regular cardinal, then $o(E_{\lambda}^{\...
user avatar
  • 14.8k
2 votes
Accepted

How do chains of elementary extensions compare to shrewdness?

As Cantor's Attic explains, if $\kappa$ is 0-uplifting, that is, there is a cardinal $\lambda \gt \kappa$ such that $V_\kappa \prec V_\lambda$ and $\lambda$ is inaccesible, $\lambda$ has a club subset ...
user avatar
3 votes

Tarski's original proof of quantifier elimination in algebraically closed fields

Passmore's PhD thesis has an introductory section developing an elementary quantifier elimination algorithm for algebraically closed fields of characteristic zero "from scratch" with much ...
user avatar
5 votes
Accepted

Tarski's original proof of quantifier elimination in algebraically closed fields

I doubt you’ll find a shorter proof than Swan’s which is equally elementary. In particular: For algebraically closed fields, you can stop in the middle of page 10 of the document, which should make ...
user avatar
  • 16.6k
2 votes
Accepted

Properties of Jech's hierarchy of stationary sets (Exercise 8.13, 8.14 of Jech)

After some googling I found the notes by J. D. Monk, which have answered the questions in the span of Theorem 2.68 to 2.91.
user avatar
4 votes
Accepted

What's the consistency status/strength of this limitation principle?

This principle is inconsistent: consider the formula $\theta(x)$ = "$x^+$ is the smallest infinite cardinal at which $\mathsf{CH}$ fails." The formula $\theta$ cannot hold on more than one ...
user avatar
6 votes
Accepted

Linear logic and linearly distributive categories

Yes, Cockett and Seely's comment about proof theory is a reference to the theory/category adjunction. Each kind of theory corresponds to a kind of category, for instance: Theory Category simply ...
user avatar
  • 58.9k
3 votes

Has there been any mathematical study of causality?

I am converting my comments into an answer. Setting aside the alleged parallel between causation and inference for a moment, there has indeed been some mathematical investigation of cause and effect. ...
user avatar
  • 64.1k

Top 50 recent answers are included