Tagged Questions

13
votes
13answers
557 views

objects which can’t be defined without making choices but which end up independent of the choice

It happens a lot of times that when one defines a new object (ring, module, space, group, algebra, morphism, whatever) out of given data one first chooses some additional structure …
11
votes
1answer
245 views

Lawvere’s fixed point theorem and the Recursion Theorem

Building off of Qiaochu's comment on my answer to a previous mathoverflow question, I would like to know: can the Recursion Theorem, $$\forall e\exists k[\Phi_e\text{ is total }\im …
2
votes
2answers
212 views

Reference request: Minimal Axiomatizations of PA over (+,x,<=).

Many years ago, when I was still a high school student, I came up with a certain first-order axiomatization of PA over the signature (+, x, ≤). Out of nostalgia, I've decided t …
2
votes
1answer
67 views

Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?

Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where …
11
votes
5answers
629 views

Are the two meanings of “undecidable” related?

I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". …
4
votes
1answer
169 views

Non-standard model of the domination principle

(Base theory $RCA_0$)The domination principle says there exists a function g such that g dominates any X-recursive function for any X in the model. i.e. For any $f\le_T X$, $\exis …
29
votes
0answers
227 views

Reasons to prefer one large prime over another to approximate characteristic zero

Background: In running algebraic geometry computations using software such as Macaulay2, it is often easier and faster to work over $\mathbb F_p = \mathbb Z / p\mathbb Z$ for a lar …
7
votes
4answers
482 views

On the large cardinals foundations of categories

(This question was posted on math.SE over two weeks ago, but received no answer. I am therefore posting it here as well.) It is well-known that there are difficulties in developin …
19
votes
2answers
787 views

Hahn’s Embedding Theorem and the oldest open question in set theory

Hans Hahn is often credited with creating the modern theory of ordered algebraic systems with the publication of his paper Über die nichtarchimedischen Grössensysteme (Sitzungsber …
3
votes
2answers
130 views

Validity in Kripke frames whose points are finite or infinite sequences

Suppose $D$ is a non-empty set and $\{ R_i : i \in \mathbb{N} \}$ is a family of binary relations on sequences over $D$ so that $R_i \subseteq D^i \times D^i$. Let $R_\omega \subse …
1
vote
1answer
82 views

dp-minimality and stability

What are some of the common popular stable theories that are known to be dp-minimal (or not dp-minimal)? Some dp-minimal examples I am aware of are strongly minimal theories, supe …
4
votes
1answer
164 views

Question about Shelah’s version of “Shooting a club” found in PIF

Suppose $S \subset \omega_{1}$ is stationary co-stationary. Then there is a forcing notion $P_{S}$ which shoots a closed unbounded $C \subset S$ without collapsing cardinals (or …
9
votes
0answers
91 views

Savings property: A transformation which turns nonnegative martingales into uniformly integrable ones

Background I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mis …
11
votes
1answer
352 views

First order decidability of rings vs Diophantine decidability

Are there known (preferably ``concrete'') examples of a ring $R$ (commutative, with 1) such that: $\bullet$ the first order theory of $R$ is undecidable, but $\bullet$ the posit …
1
vote
1answer
133 views

Elementary extensions and type spaces

If $M$ and $N$ are two $L$-structures, and $f: M \rightarrow N$ is an elementary extension, then given any subset $A$ of $M$, $f$ induces in a natural way a morphism $S^M_n(A) \rig …

1 2 3 4 5 92 next
15 30 50 per page