# Questions tagged [transfinite-induction]

The transfinite-induction tag has no usage guidance.

21
questions

6
votes

2
answers

468
views

### Is strengthening Foundation in NBG sufficient to make it prove Con(ZFC)?

Can $\sf NBG$ class theory prove the foundation scheme:
Foundation schema: if $\Phi(X)$ is a formula in which "$X$" occurs free and only free, and in which "$Y$" doesn't occur, ...

0
votes

1
answer

98
views

### Is there a canonical mapping between countable transfinite ordinals and $\omega$? What about recursive ordinals?

Consider $\omega^2$. We can build a simple bijection between the ordinal and $\omega$ similarly to how the bijection between $\mathbb{Q}$ and $\mathbb{N}$ can be built.
I was wondering if there is a ...

4
votes

0
answers

171
views

### Construction of a function by transfinite recursion

Let $\mathcal F:=\{f_\xi\colon \xi<\mathfrak c\}$ be a family of functions from $\Bbb R$ to $\Bbb R$ and $K$ be a nonempty perfect set. The question is
Construct a function $g\colon \Bbb R \to \...

2
votes

2
answers

172
views

### Diagonalization over a normal function and its derivatives on transfinite ordinals

Let $\Phi(0,\beta)$ a normal function from $On$ to $On$, and let $\Phi(\alpha,\beta)$ be the $\alpha$-th derivative of $\Phi(0,\beta)$. For example, let $\Phi(0,\beta)=\aleph_\beta$. Then, all ...

0
votes

1
answer

101
views

### (Seeking Definition) What Does it Mean for a Space to have Rim-Type $\alpha$? Or the 'derivative' of a Countable Set?

I've encountered a definition in several papers, but literally none of them define the term. They all instead reference a book by Menger that has never been printed in English. The term is "rim-...

1
vote

0
answers

176
views

### Partition $\mathfrak c$-dense set to $\mathfrak c$- many dense set

A subset of $A\subset\mathbb R$ is called $\mathfrak c$-dense if $ |A\cap I|=\mathfrak c$ for any none open interval $I\subset\mathbb R.$ Then, there is a partition for $A$ to continuum many dense ...

1
vote

1
answer

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

24
votes

5
answers

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

15
votes

1
answer

480
views

### Group actions and "transfinite dynamics"

$\DeclareMathOperator\Sym{Sym}$I have a question about what I shall name here "transfinite dynamics" because it involves iterating a topological dynamical system $G \curvearrowright X$ ...

2
votes

2
answers

432
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

2
answers

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

7
votes

1
answer

485
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

0
answers

127
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

1
answer

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

17
votes

1
answer

1k
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

1
answer

801
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

1
answer

404
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

1
answer

283
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

1
answer

130
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

1
answer

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

27
votes

5
answers

3k
views

### What is induction up to $\varepsilon_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 $\varepsilon_0$, which has ...