Questions tagged [transfinite-induction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
71 views

Lambda system generated by a non-atomic collection

Consider a probability space $(X,\Sigma,P)$. Let say that a collection $\mathcal{B}\subseteq\Sigma$ is non-atomic if for every $E\in\mathcal{B}$ and $\alpha\in(0,P(E))$ there exists $F\in\mathcal{B}$ ...
22
votes
4answers
2k views

What's the use of countable ordinals? (prompted by a remark of Tim Gowers)

In a typically lucid and helpful page of notes for students, A beginner’s guide to countable ordinals, Tim Gowers explains how the countable ordinals can be “constructed rigorously in a way that ...
5
votes
0answers
202 views

Group actions and “transfinite dynamics”

I have a question about what I shall name here "transfinite dynamics" because it involves iterating a topological dynamical system $G \curvearrowright X$ through ordinals. I do not know whether this ...
2
votes
2answers
282 views

(Types of) induction on infinite chains

This question may be trivial, or overly optimistic. I do not know (but I guess the latter...). I am a group theorist by trade, and the set-up I describe cropped up in something I want to prove. So ...
1
vote
2answers
207 views

Does Regularity schema imply $\in$-induction when added to first order Zermelo set theory?

That $\in$-induction fails to be a theorem schema of first order Zermelo + Foundation (see here), then it appears that it is more eligible to replace axiom of Regularity (Foundation) by a Regularity ...
2
votes
1answer
293 views

Is $\in$-induction provable in first order Zermelo set theory?

Are there models of first order Zermelo set theory (axiomatized by: Extensionaity, Foundation, empty set, pairing, set union, power, Separation, infinity) in which $\in$-induction fail? I asked this ...
2
votes
0answers
88 views

The premises of Aczel's inductive definitions

This is a follow-up to https://stackoverflow.com/questions/49650053/are-inductive-definitions-finitely-generated-in-isabelle As I said there, Aczel writes in his paper An Introduction to Inductive ...
-2
votes
1answer
251 views

Towers of induced functions

Suppose $\mathbb{X}$ and $\mathbb{Y}$ are classes, and $f:\mathbb{X}\rightarrow\mathbb{Y}$. It seems like pretty standard course to consider an 'induced function' $f:\mathcal{P}\mathbb{X}\rightarrow\...
15
votes
1answer
892 views

Is there a stronger form of recursion?

I'm wondering if there are any recursion principles more general than the following, first given by Montague, Tarski and Scott (1956): Let $\mathbb{V}$ be the universe, and $\mathcal{R}$ be a well-...
3
votes
1answer
563 views

careful exposition of transfinite recursion

Given a well ordered set W and a family of sets X(w) indexed by the elements w of W, transfinite recursion allows one often to define a function f on W that takes values f(w) in X(w). (I distinguish ...
3
votes
1answer
294 views

Adding consistency statements to Peano arithmetic allows more instances of transfinite induction?

Consider the hierarchy given by $\cal S_0 =$ first-order Peano arithmetic, $\cal S_{\alpha+1}=\cal S_{\alpha} + Con(S_\alpha)$ (a consistency statement for $\cal S_\alpha$), and if $\alpha$ is a limit ...
3
votes
1answer
229 views

Transfinite sequence of contiguous simplicial maps

Recall that two simplicial maps of (abstract) simplicial complexes $f,g\colon K\to L$ are contiguous if $f(\sigma)\cup g(\sigma)$ is a simplex of $L$ for every simplex $\sigma\in K$. Contiguous ...
1
vote
1answer
116 views

Generalized connected components decomposition for Priestley spaces

Preliminaries A partially ordered space is both a poset and a topological space. It has connected components both as a topological space, and connected components as a poset, i.e. the maximal ...
3
votes
1answer
452 views

How much of ZFC do I need to construct this cofinal, order-preserving class function?

EDIT: I'm bumping this, because while Joel ruled out some naive options, my question in bold below is not yet answered. Suppose I have a directed partially ordered set $(\Gamma,\leq)$ with a bottom ...
26
votes
5answers
3k views

What is induction up to epsilon_0?

This is a question asked out of curiosity, and because I can't understand the Wikipedia page. I have often been told that PA cannot prove the validity of induction up to $\epsilon_0$, which has been ...