Questions tagged [transfinite-induction]

Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers.

Filter by
Sorted by
Tagged with
2 votes
1 answer
41 views

If $X_1$,$X_2$ are wosets isomorphic to ordinals $\alpha_1,\alpha_2$ then $X_1\times X_2$ is isomorphic to $\alpha_2\cdot \alpha_1$

I want to prove the following: Let $X_1$,$X_2$ be wosets, isomorphic to ordinals $\alpha_1,\alpha_2$ respectively. Then $X_1\times X_2$, with the lexicographic order, is isomorphic to $\alpha_2\cdot\...
Alphie's user avatar
  • 4,720
0 votes
0 answers
35 views

Recursive definition for the sum of a transfinite sequence of ordinals

A transfinite sequence is a function whose domain is an ordinal $\alpha$. Let $C$ denote the class of all transfinite sequences of ordinals, and let $\text{On}$ denote the class of ordinals. Use the ...
Alphie's user avatar
  • 4,720
0 votes
0 answers
29 views

Mathematical induction and completness of metric space

Mathematical induction in form of - "in well-founded poset any progressive subset is total" (by progressive of $S$ i mean that $\forall x \ ((\forall a<x \ (a \in S)) \rightarrow x \in S)$...
nagvalhm's user avatar
1 vote
0 answers
40 views

Choosing parameters when doing induction

The (transfinite) induction principle says that, for any property $P(\alpha)$, the following is a theorem: $$ \forall \alpha \in On \ [(\forall \beta<\alpha \ P(\beta)) \implies P(\alpha)]\implies ...
Alphie's user avatar
  • 4,720
1 vote
0 answers
47 views

"Continuity" of properties

In (one of) the proofs of the Cantor-Bernstein-Schroeder theorem, one defines recursively a sequence of bijections along with a sequence of disjoint domains and co-domains. The (infinite) union of ...
Carlyle's user avatar
  • 2,817
1 vote
1 answer
74 views

Infinite induction

$1$- We can prove by induction that If $\preceq$ is a total ordering on $A$, every non-empty $\color{blue}{finite}$ subset $S$ of $A$ has a least element and a greatest element. $2$- But how to prove ...
user1035648's user avatar
0 votes
0 answers
33 views

Induction on Directed Acyclic Graphs with Root / Polytree

Assume $G$ is a directed acyclic graph (DAG) with one root node $u$. This makes $G$ a polytree, a DAG whose underlying undirected graph is a tree. Let's say we want to prove that statement $P$ holds ...
MB7800's user avatar
  • 51
0 votes
2 answers
157 views

Why transfinite induction only works on well-ordered set?

Could you please help me to know why transfinite induction only works on well-ordered set and not arbitrary set ? Why the fact that every susbset has a least element is necessary for transfinite ...
InTheSearchForKnowledge's user avatar
0 votes
1 answer
78 views

How to prove this alternative version of transfinite recursion

There are several formulations of transfinite recursion. I am interested in the following one. Let $(V, \in)$ be a model of ZF. Let $g_1$ be a set and $G_2,G_3 : V \to V$ be two definable class ...
user700974's user avatar
1 vote
1 answer
101 views

Why doesn't transfinite recursion imply dependent axiom of choice

The theorem of transfinite recursion states the following (A quick introduction to basic set Theory). Theorem 4.4 (Transfinite recursion). For every ordinal $\kappa$, set $A$, and map $^3 F: \...
wsz_fantasy's user avatar
  • 1,588
25 votes
2 answers
522 views

Metric spaces where each point sees each distance exactly once

Let $M$ be a metric space, and $S=\{d(x,y):x,y\in M\}$ be the set of all distances between points in $M$. Let's call $M$ a unique distance space if for all $x\in M$ and all $r\in S$, there exists a ...
Jonathan Love's user avatar
5 votes
1 answer
83 views

Transfinite Construction in Differential Fields proof

I'm learning differential fields theory and given my background in model theory I found this book. On p. 203 I find this: LEMMA 4.7.6. Let $K$ be a differential field, let $P \in K\{Y\} \neq$ be ...
Jordie Vincent's user avatar
1 vote
1 answer
40 views

Getting a limiting or infinite result by standard induction

For a proposition $P$, if one inducts using only standard induction (not transfinite induction) in order to show that $P(n)$ is true $\forall n \in \mathbb{Z}^{+}$, then can one claim $P(\infty)$ (...
Hyperi's user avatar
  • 55
3 votes
1 answer
111 views

Proving equivalence of two notions of an acyclic graph over graphs of arbitrary size

I'm trying to show that a simple proof calculus for a first-order theory of a strict partial order ($<$ and propertyless constant symbols) is compact without using the compactness of first-order ...
Greg Nisbet's user avatar
  • 11.6k
4 votes
0 answers
50 views

Question about the proof of compactness of events in Bernoulli measure

The problem is presented in Example 1.63 (page 29) of "Probability Theorey" 3rd edition by Prof. Achim Klenke. We construct a measure for an infinitely often repeated random experiment with ...
hmeng's user avatar
  • 339
2 votes
1 answer
94 views

I don't understand this proof: Trichotomy for ordinals (by double transfinite induction)

Hello everyone! The proof is from this book: https://st.openlogicproject.org/ I think I understand the black bracket (checked). What worries me is the blue bracket (question mark). As far as I ...
Ettore's user avatar
  • 517
0 votes
0 answers
85 views

Arguments for Primitive Recursive Arithmetic + \epsilon_0 Induction being "True"

Gentzen presented a proof of the consistency of PA. This proof can be formalized in PRA (Primitive Recursive Arithmetic) + "Transfinite Induction up to $\epsilon_0$". In order to accept ...
BENG's user avatar
  • 1,075
1 vote
0 answers
54 views

Can I add this assumption for arbitrary family?

Perhaps, my question is straightforward but I want to make sure. let's consider, $\mathcal F=\{f_{\xi}\colon \xi<\mathfrak c\}$ family of functions from $\mathbb R\to\mathbb R$. If want to prove ...
Gob's user avatar
  • 1,117
2 votes
1 answer
73 views

if $\omega^{\alpha} =A \cup B$ then $A$ or $B$ has order type $\omega^{\alpha}$

Show that if $\omega^{\alpha} =A \cup B$ then $A$ or $B$ has order type $\omega^{\alpha}$ where $\alpha \geq 1$ is a ordinal number. Hint: Use induction on $\alpha$ I don't know how to start with the ...
James R.'s user avatar
  • 133
11 votes
2 answers
2k views

Can you prove that proof-by-induction is invalid for the real interval [0, 1]?

We have a special function $S$ from the real interval $[0, 1)$ to the real-interval $(0, 1]$ which I will define near the end of this post. Someone claims that the following proof-schema is valid: We ...
Toothpick Anemone's user avatar
2 votes
2 answers
124 views

Construct a function that will be disjoint with continuum many lines

The symbol $\mathbb L$ will stand for the family of all lines in the plane that are neither horizontal nor vertical. Also, we put $\mathbb L_0:=\{\ell\in\mathbb L\colon \ell(0)=0\}$ lemma. Let $\...
00GB's user avatar
  • 2,391
4 votes
1 answer
118 views

What are some examples of fixed point problems where transfinite constructions elucidated the problem?

Maths is filled with various different kind of "fixed point theorems", sometimes even when they are not phrased as such, where we have an operation $f$ on objects of a certain kind and wish ...
Isky Mathews's user avatar
  • 3,225
3 votes
0 answers
215 views

I have some questions about the Ross-Littlewood Paradox

TLDR at the end. Hi, I recently saw this comment given by "completely-ineffable" on the r/badmathematics subreddit. And I just wanted to make sure if I understand it correctly and wanted to ...
Andrés Romero's user avatar
0 votes
1 answer
51 views

Is this proof of the First Transfinite Induction Principle incomplete or incorrect?

Context: Cheating on my homework. I am studying Smullyan and Fitting's Set Theory and the Continuum Hypothesis (2010: rev.ed.) and I have reached Chapter 4: Superinduction, Well-Ordering and Choice: $\...
Prime Mover's user avatar
  • 4,980
4 votes
1 answer
94 views

Where do I use finiteness in this proof of: In ZF, the compactness theorem implies the Axiom of Choice for collections of finite sets?

Work in ZF, and assume the compactness theorem. Let $\mathsf{AC}^\text{fin}$ be the sentence "every collection of finite non-empty sets has a choice function". UPDATE: Thank you to the ...
dingo's user avatar
  • 43
0 votes
1 answer
53 views

Obscure question in Smullyan and Fitting: "strengthening of definition by finite recurrence"

Context: self-study from Smullyan and Fitting's "Set Theory and the Continuum Problem" (revised 2010 edition), chapter 3, section 8, Definition by Finite Recursion. They give Theorem 8.1 ...
Prime Mover's user avatar
  • 4,980
0 votes
1 answer
121 views

Transfinite Construction, an intuitive interpretation.

Theorem (Transfinite Construction). Let $W$ be a well-ordered set, and $E$ an arbitrary class. Assume: For each $x\in W$, there is a given rule $R_x$ that associates with each $\varphi\colon W(x)\to E$...
Sebastián P. Pincheira's user avatar
1 vote
1 answer
135 views

Questions about the induction on cardinals

From Hereditary Cardinality and Rank : For an infinite cardinal $\kappa$, $$\forall x,\ \textrm{hcard }x<\kappa\rightarrow\textrm{rank }x<\kappa$$ We can show this by induction on $\kappa$. ...
user557's user avatar
  • 11.9k
1 vote
1 answer
94 views

Explain why transfinite induction does not assume that a property must be true for zero.

THIS QUESTION IS NOT A DUPLICATE OF THIS ONE!!! So I would like to discuss the following proof of transfinite induction which is taken by the text Introduction to Set Theory wroten by Karell Hrbacek ...
Antonio Maria Di Mauro's user avatar
1 vote
1 answer
114 views

Exercises on transfinite induction

Define by transfinite recursion $V(0)=\emptyset, V(\alpha+1)=\mathcal P(V(\alpha)), V(\alpha)=\cup_{\beta < \alpha}V(\beta)$ for $\beta$ a limit ordinal. I'm trying to show the following properties:...
user557's user avatar
  • 11.9k
3 votes
3 answers
119 views

How to prove the following inequality with "real" or "continuous" induction?

Consider the function $y(x)$ satisfying $y(0) = 1$ and $y'(x) = x^2 + y(x)^2$ for every $x$ in a maximal interval $(-a,a)$, for some $a \in (0,\infty]$. The function is nonelementary and very ...
Rob's user avatar
  • 6,707
8 votes
2 answers
135 views

Is there a pathological continuous function $\ f:\mathbb{R}\to\mathbb{R}\ $ that is nowhere increasing or decreasing and has no local extrema?

Is there a pathological yet continuous function $\ f:\mathbb{R}\to\mathbb{R}\ $ such that: For every $\ x\in\mathbb{R}\ $ and $\ \delta>0,\ \exists\ a,b,\ $ both in $\ (x,x+\delta),\ $ such that $\ ...
Adam Rubinson's user avatar
0 votes
0 answers
63 views

Question on the hierarchy of named Ordinals

I was wondering how many named transfinite ordinals there are, and what the notations and names are, arranged as a hierarchy which ignores the different levels on a single level of Ordinals (ω+1, 2ω, ...
Zoey's user avatar
  • 208
1 vote
1 answer
68 views

What contradiction arises from asuming strong induction on a set with no minimum?

Proposition: Let X be a totally ordered non-empty set such that whenever a subset A⊆X satisfies ∀x [(∀y<x ⟹ y∈A)⟹x∈A]; x,y∈X then A=X. Then X is well-ordered. This is the proposition that I'm ...
MMMagician's user avatar
1 vote
0 answers
76 views

A quick question about Set Theory and Uncountable Infinity [duplicate]

I noticed a factor about Set Theory that has somewhat confused me. Assuming CH, $2^{\aleph_0} = \aleph_1$. Taking into account Combinatorics, you can treat a number as a set of numbers; 0, 1, 2, 3, 4, ...
Zoey's user avatar
  • 208
0 votes
0 answers
66 views

Confusing about how the lemma can be stated

Let's consider the following: Lemma Let $g\in F(\beta)$ and $f\in \Bbb R^\Bbb R$ such that $f\restriction M= g\restriction M$ for some $M\subset \mathbb R$. Then $f\in F(\beta).$ Of course, no one ...
00GB's user avatar
  • 2,391
3 votes
1 answer
199 views

Prove by induction on $\alpha < 2^{\aleph_0}$ that $|\mathcal G_\alpha| < 2^{\aleph_0}$ and $\mathcal G_\alpha$ is not an ultrafilter over $\omega$

The following question is exercise 7.4 from Ernest Schimmerling's A Course on Set Theory which involves a construction from Tarski's theorem that extends filters to ultrafilters. I couldn't find much ...
Math Simp's user avatar
  • 124
1 vote
1 answer
178 views

If we can prove transfinite induction, why can't we prove induction?

Let $(J, <)$ be a well ordered set. Let $S_\alpha \equiv \{ j \in J: j < \alpha \}$ ( section by $\alpha$ of $J$). Transfinite induction says that for any subset $J_0$, if the following property ...
Siddharth Bhat's user avatar
4 votes
1 answer
189 views

Does there exist a Bernstein set such that a finite sum still Bernstein?

Recall that $B\subset\Bbb R$ is a Bernstein set if $B\cap P\neq\emptyset \neq P\setminus B$ for every perfect set $P\subset\Bbb R.$ It can be constructed by an easy transfinite induction. Moreover, ...
00GB's user avatar
  • 2,391
0 votes
1 answer
112 views

About Construction a one-to-one function from $(a,b)$ onto $[a,b]$

This question asked to construct one-to-one function from $(a,b)$ onto $[a,b]$. I know there is a function but it seems the question to define this function explicitly. How this can be done? Edit I ...
00GB's user avatar
  • 2,391
2 votes
2 answers
216 views

Another way for partition of perfect set

Let $P$ be a perfect $P\subset\Bbb R.$ Then there exists a family $\{P_{\alpha}\subset P\colon \alpha<\mathfrak c\}$ of pairwise disjoint perfect subsets such that $$P=\bigcup_{\alpha<\mathfrak ...
00GB's user avatar
  • 2,391
1 vote
0 answers
109 views

Examples of transfinite constructions in algebra

The nlab has a page on transfinite construction of free algebras on the existence of a free monad for a (pointed) endofunctor (accessible in a locally presentable category). My question is if the ...
user927503's user avatar
4 votes
1 answer
343 views

Proper definition of well-founded induction on a class

On Wikipedia it says that a binary relation $R$ on a class $X$ is well-founded if every non-empty subset $S \subseteq X$ contains a minimal element, i.e. there is some $x \in S$ such that $(y,x) \...
Tom's user avatar
  • 1,104
1 vote
0 answers
81 views

Transfinite recursion and the cardinality of Borel sets

Am doing an exercise on the cardinality of Borel sets where we have and arbitrary set $X$ and the set of countable ordinals $\Omega$. Given $\mathcal{E}\subset \mathcal{P}(X) $ with $\emptyset\in \...
Alphie's user avatar
  • 4,720
0 votes
1 answer
75 views

A well founded relation $R$ on a class $A$ does not need to be set-like

The theorem that justifies transfinite induction on a class states the following: Assume that $R$ is well-founded and set-like on $A$, and that $X$ is a non-empty sub-class of $A$. Then $X$ has an $R$...
BENG's user avatar
  • 1,075
0 votes
1 answer
39 views

Question about index

Sometimes basic elements are not easy to understand. It is well known result that every perfect can be written as pairwise disjoint perfect sets. Assume $P\subset\Bbb R$ be a perfect set. and let $\...
00GB's user avatar
  • 2,391
1 vote
1 answer
68 views

How to show that the Zermelo hierarchy is really a hierarchy?

In Cameron's Sets, Logic and Categories (p. 48-49), he sets out prove the following fact about the Zermelo hierarchy $V$, namely, that $V_\alpha\subseteq V_{s(\alpha)}$ for all ordinals $\alpha$. His ...
Doubt's user avatar
  • 1,719
3 votes
0 answers
104 views

Construct an additive group by transfinite induction

I know one way to construct a Bernstein set that is an additive group.Here is the way that I know. $\{P_\xi\colon \xi<\mathfrak c\}$ all nonempty perfect subsets of $\Bbb R.$ Choose, by recursion ...
00GB's user avatar
  • 2,391
1 vote
2 answers
106 views

Complement of the product of Bernstein set and meager set

Assume $M\subset\mathbb R$ be a meager set with cardinality $\mathfrak c.$ I want to construct a Bernstein set $B$ such that $\mathbb R\setminus(B\cdot M)$ has cardinality $\mathfrak c$ , $B\cdot M=\{...
00GB's user avatar
  • 2,391
1 vote
1 answer
68 views

"Proof" that every ultrafilter has a least element

Ultrafilters come in the principal and the free variant. Elsewhere it is said that principal is equivalent to the ultrafilter having a least element, i.e. one that is contained in every other element ...
Harald's user avatar
  • 611