## New answers tagged lo.logic

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); ...

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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 $\...

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

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

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

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

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

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

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

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

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

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

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

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

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

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}^{\...

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

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

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

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.

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

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

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

Top 50 recent answers are included

#### Related Tags

lo.logic × 4374set-theory × 1927

model-theory × 675

computability-theory × 438

reference-request × 420

forcing × 399

large-cardinals × 317

ct.category-theory × 248

proof-theory × 238

theories-of-arithmetic × 201

axiom-of-choice × 199

descriptive-set-theory × 184

mathematical-philosophy × 167

foundations × 150

computational-complexity × 109

reverse-math × 108

soft-question × 106

constructive-mathematics × 105

nt.number-theory × 104

ho.history-overview × 93

gr.group-theory × 92

type-theory × 90

gn.general-topology × 86

computer-science × 81

topos-theory × 80