Questions tagged [transfinite-induction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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, ...
Zuhair Al-Johar's user avatar
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 ...
Guillermo Mosse's user avatar
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 \...
00GB's user avatar
  • 179
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 ...
Delta89's user avatar
  • 21
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-...
John Samples's user avatar
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 ...
00GB's user avatar
  • 179
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}$ ...
Johann's user avatar
  • 11
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 ...
Peter Smith's user avatar
  • 1,599
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$ ...
Burak's user avatar
  • 4,135
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 ...
NotDominicRaab's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Gergely's user avatar
  • 291
-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\...
Alec Rhea's user avatar
  • 8,999
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-...
Alec Rhea's user avatar
  • 8,999
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 ...
Dan Grayson's user avatar
  • 1,403
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 ...
Lavinia Picollo's user avatar
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 ...
Michał Kukieła's user avatar
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 ...
Thomas Klimpel's user avatar
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 ...
David Roberts's user avatar
  • 33.9k
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 ...
David E Speyer's user avatar