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
0
votes
1answer
27 views

How does Cohen's theorem of transfinite induction relate to the the reagular (or more modern) one?

My understanding of transfinite induction comes from Weaver where he says: Theorem: Suppose that for every ordinal $\alpha$ $(\forall\beta<\alpha)\phi(\beta)\rightarrow\phi(\alpha)$ holds. Then $(\...
0
votes
2answers
60 views

Is the principle of transfinite induction (PTI) always not true on a set that is not well ordered?

It seems obvious to me that if for any domino (it is known that all previous dominos fell than this domino will also fell) than it is true that all dominos will fell. It should not matter if there is ...
0
votes
0answers
24 views

Construct function on perfect set such that the function is continuous

Let $A$ and $C$ be perfect sets ( perfect set is closed and has no isolated point) subsets of $\mathbb R$ and $A\cap \mathbb Q=\emptyset.$ Let $Z$ be subset of $\mathbb R$ such that it intersects ...
1
vote
1answer
80 views

Function with specific property

Let $f$ be a function on $\mathbb R$ that satisfies the following property $$ \text{For every} \ a,b\in\mathbb R \ \text{and for every perfect set }\ K\ \text{between} \ f(a)\ \text{and} f(b), f(a)&...
0
votes
2answers
47 views

Recursion theorem for ordinals proof

I'm trying to understand the proof of the recursion principle of ordinals, the theorem is: The proof of this theorem uses this other theorem: The proof is pretty long (I'm sorry) so I will try to ...
2
votes
1answer
47 views

Couldn't we state the principle of transfinite induction without the $0 \in A$ condition?

Principle of transfinite induction for ordinals: Let $A$ be a subset of the ordinal $\alpha$ such that $0 \in A$ for all $\beta \in \alpha$ if $\beta \subseteq A$ then $\beta \in A$ Then $A=\alpha$ ...
1
vote
0answers
33 views

Prove the limit step for $\Gamma (\alpha, \alpha)\le \omega^\alpha$

I'm working through Jechs Set Theory right now and encountered an exercise (3.5) to prove that the order type of $\Gamma(\alpha, \alpha):=\{(\xi, \eta): (\xi, \eta)<(\alpha, \alpha)\}$ is less than ...
1
vote
0answers
86 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 open interval $I\subset\mathbb R.$ Then, there is a partition for $A$ to continuum many dense set. ...
2
votes
1answer
89 views

$\mathbb R$ as continuum many of pairwise disjoint of Bernstein sets

The set $B\subset\mathbb R$ is called Bernstein set if neither $B$ nor $\mathbb R\setminus B$ contains any perfect sets. Theorem: $\mathbb R$ can be written as continuum many of pairwise disjoint ...
0
votes
1answer
94 views

family of pairwise disjoint sets in the complement of meager. set

Let $M$ be a meager subset of $\mathbb R$. I want to construct the following family in $\mathbb R\setminus M $ $$F:= \{A_{r}^\xi\colon r\in\mathbb R \ \&\ \xi<c\}$$ Such that all elemnets of $F$...
0
votes
1answer
30 views

Extension linear independent set to Hamel basis

If we have a linear independent set, then it is well known that by using Zorn's lemma it can be extended to Hamel basis. My question I have a linear independent set, call it $B_{0}$, I want to ...
2
votes
1answer
49 views

Does transfinite induction follow from second-order induction?

Second-order induction is defined normally. Does the title hold?
5
votes
0answers
107 views

Proof with transfinite induction

I'm trying to prove the following statement: Suppose that for every $r\in\mathbb{R}$ we are given a finite set $A_r\subseteq\mathbb{R}$ and that for any finite set $D\subseteq\mathbb{R} $, there ...
0
votes
1answer
73 views

split perfect set into countable many pairwise disjoint perfect sets

We know that each perfect set can be written as a continuum many pairwise disjoint many perfect set. This will rely on the well know theorem which says: Let $X$ be a nonempty perfect polish space. ...
0
votes
2answers
48 views

How to choose infinite number of different values from infinite set of infinite sets.

Let $ \aleph_{\alpha} $ be a cardinal and assume that $ \left\{ A_{\beta}:\beta<\aleph_{\alpha}\right\} $ is a set of sets, such that $ |A_{\beta}|=\aleph_{\alpha} $ for any $ \beta<\aleph_{\...
0
votes
1answer
36 views

Transfinite induction, proving $\operatorname{P}(0)$ although $\alpha = 0$ is out from hypothesis.

In a transfinite induction, if I have to prove that a predicate $\operatorname{P}(\alpha)$ is true $\forall \alpha \gt 0$, can I proceed showing $\operatorname{P}(0), \; \operatorname{P}(\alpha) \...
2
votes
0answers
69 views

How does Reinhardt's extension of the set-theoretic universe beyond $V_\Omega$ work?

In this answer it is stated that in William Reinhardt's paper 'Remarks on reflection principles, large cardinals, and elementary embeddings' (1974) Reinhardt suggests extending the set-theoretic ...
1
vote
2answers
71 views

Transfinite induction

Is it true that while using transfinite induction we dont need to prove the zero case? because, if we want to prove some property $ \psi $ , we assume that for any $ x\in A $ if for any $ y\leq x $ it ...
1
vote
1answer
82 views

Disparity between Induction and Well-ordering Principles

Over classical logic, the induction and well-ordering schemas are equivalent. These schemas state the following, given any linear ordering $(W,<)$ and property $Q$ on $W$: Induction: $∀k{∈}W\ ( \ ∀...
0
votes
1answer
63 views

Proving the cardinality of B<A (Terence Tao's Analysis I book Ex 8.5.15)

Let A and B be two non-empty sets such that A does not have lesser or equal cardinality to B. Using the principle of transfinite induction, prove that B has lesser or equal cardinality to A. (Hint: ...
0
votes
1answer
29 views

Question regarding initial segment and transfinite induction.

Suppose $X$ is an uncountable well-ordered set with $\leq$.For $x\in X$ ,define the initial segment of $X$ determined by $x$ as $I(x)=\{y\in X| y\leq x $ and $y\neq x\}$.Now my question is ,does there ...
0
votes
1answer
57 views

Using transfinite induction to split $R$ to continuum many pairwise disjoint subsets of $R$

I am looking for different ways to partition $R$. I know some like : (1) Define a relation as following $$x\sim y \ \text{iff} \ x-y\in\mathbb Q(x,y\in\mathbb R)$$. The equivalence classes have the ...
1
vote
0answers
69 views

Continuous function with some properties plus everywhere surjective function must be everywhere surjective

Let me starts with some definitions : $f\colon \mathbb R\to \mathbb R $ is everywhere surjective if $f[I]=\mathbb R$ for every nonempty open interval $I.$ $f$ is Darboux function if $f$ satisfies the ...
0
votes
1answer
62 views

$\Delta$-system lemma to show ccc

This is not a hard question but I do not know how to figure it out. Let $X$ and $Y$ be a nonempty sets. Let $\langle P,\leq\rangle=\langle P,\supset\rangle$ be be partially ordered where $P=\{f:D\to ...
0
votes
0answers
48 views

How can I write a perfect set as $c$ many pairwise disjoint perfect sets

I have been thinking about this question but I have not get complete answer yet. the question is Let $P$ a nonempty perfect subsets of $\mathbb R$ then $P$ can be written as continuum many pairwise ...
4
votes
1answer
99 views

CH implies $\omega_1$ pairwise disjoint of perfect set

This is an exercise in Fundamental of real analysis by James Foran. Prove that the continuum hypothesis implies that each perfect subset of $\mathbb R$ can be written as the union of $\omega_1$ ...
1
vote
1answer
50 views

Does every partial order admit a maximal chain?

Let $<$ be a strict partial order on a set $S$. Is there necessarily a set $C\subseteq S$ such that $C$ is totally ordered by $<$ and no proper superset of $C$ is totally ordered by $<$? My ...
1
vote
0answers
78 views

Trying to prove that cardinality of Borel $\sigma$-algebra is the cardinality of the continuum

I am trying to prove that the cardinality of the Borel $\sigma$-algebra on $\mathbb{R}$ equipped with the standard topology is $c$, where $c=|\mathbb{R}|$ is the cardinality of the continuum. My ...
0
votes
0answers
32 views

Ordinal equation [duplicate]

Here's a question from Kuratowski's "Set theory" (Chapter 7). Given the ordinal equation $\omega^a=b+c$ $(c>0)$. How to prove that $c=\omega^a$?
0
votes
0answers
38 views

Ordinal of the union

Consider a family $S$ of pairwise disjoint sets with an ordinal number $\alpha$. Let $S$ be ordered by $\beta$. I'm trying to prove that the naturally ordered set $\cup S$ has the ordinal number $\...
0
votes
1answer
66 views

What do we call a function that converges with composition over greater than $\omega$ times?

Let $S_n$ be an ordered set of numbers indexed by a countable ordinal $n\in\omega^\omega$ such as: $\ldots 7,49,343,\ldots5,25,125,\ldots,3,9,27,\ldots,2,4,8,\ldots$ Then let this be a topological ...
1
vote
1answer
115 views

using strong induction that there exists an integer $C$ that for all $D\ge C$ it is possible to return exactly $D$ by using only $2$ and $5$

Prove using strong induction that there exists an integer $C$ that for all $D \ge C$ it is possible to return exactly $D$ by using summed composites of only $2$ and $5$ so far i believe that $\exists ...
0
votes
1answer
65 views

How to apply Zorn's Lemma to prove cardinalities are a total order? [duplicate]

I'm currently self studying Analysis I by Tao. He's sprinkled a little set theory into this book, and I'm really struggling to apply it. After painstakingly proving Zorn's Lemma via another lemma, we ...
6
votes
1answer
195 views

Transfinite composition of monomorphisms is a monomorphism?

It seems to me that that this is true: In the category of Sets, transfinite composition of monomorphisms is again a monomorphism. Explicitly, given a $\lambda$-sequence $$X_0 \xrightarrow{f_1} X_1 \...
0
votes
1answer
81 views

A question about the cardinality of $\theta$-closed hull of a set

I have been reading a proof for the following proposition Proposition: Let $X$ be a Urysohn space. If $A$ is a subset of $X$, then $|[A]_\theta|\leq |A|^{\chi(X)}$ Here, $[A]_\theta$ denotes the $\...
1
vote
0answers
53 views

Alternating multilinear map with infinitely many arguments

From Wikipedia: A multilinear map of the form $f\colon V^n \to W$ is said to be alternating if it satisfies any of the following equivalent conditions: whenever there exists $1 \leq i \...
0
votes
0answers
40 views

Vector space of real valued function with size continuum

I know how I can construct a function such that $f^{-1} (y)$ has size less than continuum actually countable. Here is the proof, Define a relationship as following $$x\sim y \ \text{iff} \ x-y\...
1
vote
0answers
46 views

Every countable closed set is of uniqueness

I am following the proof of Cantor's theorem that every countable closed set is of uniqueness as given in Kechris' notes (available here, thm. 4.2, proof on p. 12). My doubts are the following: how ...
3
votes
1answer
63 views

Uniqueness of dimension in the infinite-dimensional case.

Say $V$ is a vector space over some field. Lemma Suppose $A,B,C\subset V$, $A\cup B$ spans $V$ and $B\cup C$ is independent. For every $c\in C$ there exists $a\in A$ such that if $A'=A\...
2
votes
1answer
342 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). The ...
0
votes
1answer
96 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
95 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
35 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
122 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
55 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?
3
votes
2answers
134 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
58 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
39 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
62 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
185 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 ...