Stack Exchange Network

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

-1
votes
0answers
23 views

$\omega$th iteration of Cayley-Dickson construction

The first nine Cayley-Dickson hypercomplex algebras are real (1D), complex (2D), quaternion (4D), octonion (8D), sedenion (16D), pathion (32D), chingon (64D), routon (128D), and the voudon (256D) -...
0
votes
1answer
53 views

Is it possible to prove Regularity with Transfinite Induction only?

Let us assume that we have only statement of transfinite induction. (And maybe some other well-know axioms) My question: "Is it possible to derive from it a regularity axiom as a theorem?". Some of ...
0
votes
0answers
48 views

Does this ordinal (built by using ZFC + ordinal many large cardinals to attain yet larger ordinals) have a name?

Consider the following pair of functions: For α an ordinal, let $\nu(\alpha)$ be the least ordinal $\kappa$ such that $(V_{\kappa}, \in)$ is a model of ZFC in which there are $\alpha$-many ...
3
votes
1answer
34 views

Can I use mathematical induction here?

Given any digraph $D=(V,E)$ such that for every finite subset $S\subseteq V$ there exists a vertex $v_{S}\in V$ capable of reaching any vertex in $S$ via a directed path. Can one deduce there is a ...
1
vote
2answers
65 views

Choice and the principle of transfinite induction

Does the Axiom of Choice suffice to show Transfinite Induction in ZF? Also, if possible, could you please give some general remarks/insight on (i) worthwhile noting equivalencies or dependencies ...
0
votes
2answers
41 views

Tranfinite induction, 0.9…=1 [closed]

Can transfinite induction be used to demonstrate that 0.9...=1? More generally, can it be used to prove limits of sequences?
2
votes
2answers
79 views

Infinite family $\mathscr{A}\subseteq P(\omega)$ with criteria

First part: Prove that there's an infinite family $\mathscr{A}\subseteq P(\omega)$ such that: $X \in \mathscr{A} \Rightarrow |X|=\aleph_0$ $(X,Y\in \mathscr{A} \wedge X\ne Y)\Rightarrow |X \cap Y|&...
0
votes
0answers
56 views

$\forall \alpha$ ordinal, Prove that $\alpha+1=S(\alpha)$

$\forall \alpha$ ordinals, Prove that $\alpha+1=S(\alpha)$ My question is would this require transfinite induction to prove? and if so how would one do the successor case?
0
votes
1answer
24 views

Is Induction applicable only to well-ordered sets that are not bounded above?

I think the set needs to be bounded below to avoid occurrence of infinite descending chains for induction to be applicable but couldn't decide if it can be bounded above as well. Inductive step is P(...
2
votes
1answer
53 views

Every function can $f \colon \mathbb R \to \mathbb R$ can be represented as the sum of two one-to-one functions

How can one use the Principle of Transfinite Induction, i.e, "Let $P(z)$ be a mathematical statement that depends on the ordinal $z$. Suppose whenever $P(\eta)$ is true $\forall \eta<z,P(z)$ is ...
1
vote
1answer
85 views

Transfinite Induction Proof

I am being asked to prove the following: Show, by transfinite induction on $\alpha$, that: For all sets $x$, if $x \in V_\alpha$, then $\mathcal{P}(x)\in V_{\alpha+1}$. So, I am aware to use ...
2
votes
3answers
82 views

Source for problems to practice applying Zorn's lemma.

I have been stuck trying to prove things too many times to mention, where the idea I needed to use was Zorn's lemma. I would like to get to the point where applying transfinite induction is a natural ...
1
vote
1answer
128 views

Better bounds on my ordinal hyperoperators

I've defined some ordinal hyperoperators as follows: $$a\{b\}c=\begin{cases}a+1,&b=0{\rm~or}~c=0\\\sup\{(a\{b\}x)\{y\}a:x<c,y<b\},&\text{else}\end{cases}$$ For $a$ and $c$ that satisfy ...
0
votes
2answers
80 views

Ordinal is limit iff it is a multiple of omega

Show that an ordinal is a limit ordinal if and only if it is $\omega\cdot\beta$ for some $\beta$. Could someone please explain the existence of the greatest limit $\gamma_0 $ in Camilo Arosemena's ...
1
vote
1answer
87 views

If $\lambda$ is a limit ordinal , $0\le n < \omega$, $1<m<\omega$ then prove the following

If $\lambda$ is a limit ordinal , $0\le n < \omega$, $1<m<\omega$ Prove that $(\lambda+n)^{m}<\lambda^{m}*2$ and deduce that $(\lambda+n)^{\omega}=\lambda^{\omega}$. My attempt at the ...
2
votes
0answers
26 views

Fractran program size

On the subject of lower and upper bounds of John H. Conway's Fractran program size, if you tried to evaluate these using the pumping lemma, couldn't you create an infinity of fractions evaluating the ...
0
votes
1answer
39 views

Question about defining sequence via transfinite induction.

I have sequence $A_i$ where $i\in\mathbb{N}$ and every $A_i$ is countable. Let $A=\bigcup_{i\in\mathbb{N}}A_i$. I want to find new sequence of countable subsets of $A$ such that $C_i\subseteq A_i$ ...
1
vote
1answer
37 views

$V_\alpha, X \in V_\alpha$ and $|X|$.

I wish to know which $V_\alpha$ contain cardinalities of all its elements (for an ordinal $\alpha$). I've conjectured that all of them, and tried to prove this by the transfinite induction on $\...
0
votes
1answer
84 views

Rank of ordinal number

How do I show that $$ \operatorname{rank}(\alpha)=\alpha $$ for all ordinals $\alpha? I've attempted to solve this via transfinite induction but I could not get it right. Any help will be ...
3
votes
1answer
144 views

The Ackermann hierarchy vs. the fast growing hierarchy

Suppose we've defined the Ackermann hierarchy as follows: $$A_\alpha(n)=\begin{cases}n+1,&\alpha=0\\A_{\alpha[n]}(n),&\alpha\in\Bbb{Lim}\\A_\beta(1),&n=0,\alpha=\beta+1\\A_\beta(A_\alpha(...
2
votes
3answers
59 views

Logical question while trying to prove a theorem about comparing well-ordered sets

I'm reading Set theory of Jech. I try to prove Thm 2.8 for myself but I'm not sure if the first step of my proof is correct. So the theorem affirms that if $W_1$ and $W_2$ are two well-ordered sets, ...
4
votes
1answer
214 views

Transfinite induction (Atiyah and Macdonald)

Exercise 17 in chapter 4 of Introduction to Commutative Algebra by Atiyah and Macdonald hints for you to use transfinite induction to complete the proof. I have not come across transfinite induction ...
3
votes
0answers
96 views

Hahn Banach Theorem: Transfinite Induction

In the 4th book of Stein and Shakarchi, the statement of the Hahn-Banach theorem is as follows: Suppose $V_0$ is a linear subspace of $V$ and $p$ is a real sub-linear function on $V$, and that we ...
1
vote
0answers
82 views

Union of Connected Sets and Transfinite Induction

Recall the following theorem: Theorem Let $\{A_\alpha\}$ be a collection of connected subsets of $X$ such that $\bigcap_\alpha A_\alpha\neq\emptyset$. Then $\bigcup_\alpha A_\alpha$ is a ...
1
vote
1answer
393 views

Closed kernel implies continuous linear functional : Zorn's Lemma

I know that this question has been asked before, but I am thinking of a solution using Zorn's lemma. Stein and Shakarchi's volume 4 wants me to prove the above statement(exercise 35) using exercise 34:...
1
vote
1answer
66 views

Transfinite induction on inductively constructed CW complex

Let $X$ be a 2-dimensional path-connected CW-complex and let $W \subset X$ be a subcomplex. Further let $I$ be an index set of the path-components of $W$. Consider the following iterative procedure: ...
1
vote
0answers
33 views

The property of $α$-limit ordinals.

An ordinal $λ$ is defined to be a limit ordinal if, for all $ξ < λ$, $ξ + 1 < λ$. I am told that: We can define a stronger kind of limit ordinal by putting some ordinal $α$ in place of $1$ here: ...
1
vote
2answers
113 views

Definition of ordinal addition by transfinite induction (ZFC)

I work here in $\mathrm{ZFC}$. Transfinite induction is the following observation: Let $P(x)$ be a property. If $(1) \ P(0)$ is true $(2)$ for any ordinal $\alpha:$ $P(\alpha)$ is true $\...
1
vote
1answer
106 views

Prove the limit case: if $\alpha,\beta$ are countable ordinals, then $\alpha+\beta$ is also countable

I am trying to prove that if $\alpha,\beta$ are countable ordinals, then $\alpha+\beta$ is also countable. Both base and successor case has been done, now I am considering the limit case. Once I ...
-1
votes
1answer
44 views

How to use induction to prove that if $α+β=β$, then for every $n<ω,α⋅n\le β$ and hence $\alpha\omega\le \beta$?

Here $\alpha,\beta$ are ordinals. I know that it can be done by induction, but searching in my textbook I cannot find how exactly can I deal with it. I am completely new to ordinal arithmetic, so may ...
1
vote
1answer
29 views

For any well ordered set S, is SX[0,1) path connected?

While doing transfinite induction to prove that open long ray is path connected, I got this conclusion that for any ordinal α, αX[0,1) (in lexicographic order topology) is path connected. It seemed a ...
0
votes
1answer
39 views

Transfinite induction on a ascending chain of subgroups.

Let $G$ be a group and $H$ be an ascendant subgroup of $G$. Suppose that $X \leq H \leq K$, where $K$ has certain properties. I want to show that $K = N_G(X)H$. I have shown that $N_G(X)H \leq K$ Now ...
0
votes
1answer
66 views

Transfinite induction for collections that are not classes

In ZFC, a class is typically defined as the collection of sets $x$ that satisfy some formula $\varphi(x, p_1, \ldots, p_n)$ for parameters $p_1, \ldots, p_n$. We therefore have that all sets are ...
1
vote
1answer
21 views

extending finite properties

Suppose for any $N\in\mathbb{N}$ and any finite sequence $\{x_i\}_{i=1}^N$ with each $x_i\in[0,1]$, we have $\sum_{i=1}^N f(x_i)\geq \sum_{i=1}^Ng(x_i)$. Is there any way to extend this to show that $\...
0
votes
1answer
57 views

Transfinite Moduli

I'm looking at arithmetic $\mod ω$ (where $ω := |**N**| = 1+1+1+... =$ Lim($n$) : n ∈ N). Specifically, I'm trying to show that $... + \frac 18 + \frac 14 + \frac 12 + 1 + 2 + 4 + 8 + ... ≡ 0 \mod ω$...
3
votes
1answer
48 views

Is this a feasible way to show that a group $G$ is isomorphic to its opposite group $G^{op}$?

Let $G$ be a group with group operation $*$. Let $G^{op}$ be a group that shares the same base set with $G$ but the group operation $*^{'}$ is such that $a*^{'}b = b*a$. We would like to show that $G$ ...
2
votes
0answers
64 views

Induction, coinduction, and ordinal induction

As a computer scientists, I have been thought to use induction and coinduction principles for proving properties of finite and infinite structures, respectively. When does one use ordinal induction?...
2
votes
5answers
240 views

Using Strong Induction

The statement is: If $n$ is an integer with $n > 1$, then $n$ has a prime factor. I know you have to use $P(k+1)$ but I'm not sure how to implement that into the proof. Is this even going in the ...
0
votes
2answers
183 views

Transfinite induction on class of ordinals.

This was an exercise from Enderton's Text, Elements of Set Theory. I am unsure of my proof - and I wonder what other possible solutions there are. [7,25] (Transfinite induction schema) Let $\phi(x)...
2
votes
2answers
158 views

A specific example of transfinite induction

I am trying to understand better how transfinite induction can be applied in different concrete problems. Here is an example that seems relevant, but I am stuck on it. Consider a couple of points $p, ...
1
vote
1answer
41 views

Could you verify my proof by transfinite induction of: $\langle a_\xi : \xi< \alpha\rangle =\langle b_\xi : \xi< \alpha\rangle$?

I'm am trying to comprehend the proof on page 22 of Thomas Jech's Set theory and work out my first ever proof by transfinite induction. The problem is this: Le $G$ be a function (on $V$), then ...
1
vote
0answers
72 views

Using transfinite induction to compute fundamental groups

I want to compute the fundamental group of a space containing comb space along with boundary of $I \times I$ where I is $[0,1]$. Here is my attempt using transfinite induction and Van Kampen. Let's ...
5
votes
2answers
471 views

How does one prove transfinite induction in ZFC?

If one is able to use classes, it seems to me that the proof of transfinite induction is a simple extension of the usual proof of induction (and equal to the proof of transfinite induction on sets). ...
1
vote
1answer
50 views

“Hahn decomposition” for countable or arbitrarily many mutually singular probability measure

Let $(\mu_i)_{i\in I}$ be a collection of mutually singular probability measure on $(\Omega, \mathcal F)$.(i.e. any two of them are singular to each other). I am not sure if the following statement is ...
8
votes
0answers
260 views

Lebesgue Premeasure via Transfinite Induction

If $I=[a,b)$ we write $|I|=b-a$ for the length of $I$. Given a theorem of Caratheodory, the tricky part in showing the existence of Lebesgue measure is this: Lemma If $[0,1)$ is the disjoint union of ...
19
votes
10answers
2k views

What are the most prominent uses of transfinite induction outside of set theory?

What are the most prominent uses of transfinite induction in fields of mathematics other than set theory? (Was it used in Cantor's investigations of trigonometric series?)
19
votes
6answers
4k views

Principle of Transfinite Induction

I am well familiar with the principle of mathematical induction. But while reading a paper by Roggenkamp, I encountered the Principle of Transfinite Induction (PTI). I do not know the theory of ...
1
vote
2answers
103 views

Theorem $($Transfinite Induction and Construction$)$ (James Dugundji - 5.1, Page - 40)

Let $W$ be a well ordered set, and let $Q \subset W$. If $[ W(x) \subset Q] \Rightarrow [ x \in Q]$ for each $x \in W$, then $Q = W$. For each $a \in W$, the set $W(a) = \{x \in W; (x\prec a) \...
1
vote
1answer
104 views

A question on transfinite induction

The following were 2 problems given to us on transfinite induction, The transfinite induction I saw on books and books etc was using ordinals but the definition we were given is different and I still ...
7
votes
2answers
406 views

Application of Transfinite Induction

Our teacher gave us for practice to prove some properties of $V(\alpha)$ defined as $$V(0) = \emptyset,\; V(S(\alpha)) = \mathcal{P}(V(\alpha)),\; Lim(\alpha): V(\alpha) = \bigcup\{V(\beta)\; |\; \...