Stack Exchange Network

Stack Exchange network consists of 175 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

Questions tagged [transfinite-induction]

The tag has no usage guidance.

2
votes
2answers
241 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
170 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
256 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
86 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
222 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
806 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-...
2
votes
1answer
407 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
266 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
213 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
112 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
424 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 ...
25
votes
4answers
2k 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 ...