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
1 answer
39 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: $\...
user avatar
  • 4,048
0 votes
0 answers
16 views

Applying the axiom of choice on the reals to use transfinite induction

Transfinite induction is the extension of mathematical induction to well-ordered sets, and the axiom of choice, from what I've read (although haven't seen examples or applications of), may be applied ...
user avatar
4 votes
1 answer
64 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 ...
user avatar
  • 43
0 votes
1 answer
26 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 ...
user avatar
  • 4,048
0 votes
1 answer
40 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$...
user avatar
1 vote
1 answer
62 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$. ...
user avatar
  • 10.9k
1 vote
1 answer
63 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 ...
user avatar
1 vote
1 answer
84 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:...
user avatar
  • 10.9k
2 votes
2 answers
50 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 ...
user avatar
  • 5,982
8 votes
2 answers
112 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 $\ ...
user avatar
0 votes
0 answers
55 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ω, ...
user avatar
  • 179
1 vote
1 answer
63 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 ...
user avatar
1 vote
0 answers
72 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, ...
user avatar
  • 179
0 votes
0 answers
65 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 ...
user avatar
  • 2,153
3 votes
1 answer
131 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 ...
user avatar
  • 149
1 vote
1 answer
95 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 ...
user avatar
4 votes
1 answer
174 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, ...
user avatar
  • 2,153
0 votes
1 answer
100 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 ...
user avatar
  • 2,153
2 votes
2 answers
174 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 ...
user avatar
  • 2,153
1 vote
0 answers
65 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 ...
user avatar
0 votes
0 answers
28 views

Parameters for well-founded recursion

For a set-like, well-founded relation $R$ on a class $X$, one may use well-founded recursion to define set $S_x$, $x \in X$, using sets $\{S_y \mid y\ R\ x\}$ that can be assumed to be already defined....
user avatar
  • 1,054
4 votes
1 answer
99 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) \...
user avatar
  • 1,054
1 vote
0 answers
33 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 \...
user avatar
  • 3,433
0 votes
1 answer
46 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$...
user avatar
  • 1,009
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 $\...
user avatar
  • 2,153
1 vote
1 answer
47 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 ...
user avatar
  • 1,599
3 votes
0 answers
101 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 ...
user avatar
  • 2,153
1 vote
2 answers
90 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=\{...
user avatar
  • 2,153
1 vote
1 answer
44 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 ...
user avatar
  • 549
0 votes
1 answer
52 views

Meager set and disjoint with line $y=ax$

Lemma. Let $X$ and $Y$ be second countable. If $A\subset X$ and $B\subset Y$, then $A\times B$ is meager iff at least of $A,B$ is meager. Assume $f\colon \mathbb R\to \mathbb R$ and $D$ be a meager ...
user avatar
  • 2,153
1 vote
0 answers
52 views

Why does creating the basis of any vector space using dense order instead of well order fail in general case?

This problem occurred to me when I was solving problem 112 in A. Shen and N. K. Vereshchagin, Basic Set Theory (AMS 2002)), just as in this post Can this proof of existence of a Hamel basis using ...
user avatar
0 votes
1 answer
65 views

Continuous function by transfinite induction

Let $A$ and $B$ subsets of $\mathbb R$ such that both have cardinality $\mathfrak c.$ I want to construct a noncontact function $f\colon A\to B$ by transfinite induction such that $f$ is ...
user avatar
  • 2,153
0 votes
1 answer
35 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 $(\...
user avatar
  • 1,064
0 votes
2 answers
75 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 ...
user avatar
1 vote
0 answers
83 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)&...
user avatar
  • 2,153
0 votes
2 answers
122 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 ...
user avatar
2 votes
1 answer
62 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$ ...
user avatar
1 vote
0 answers
56 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 ...
user avatar
1 vote
0 answers
100 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. ...
user avatar
  • 2,153
3 votes
1 answer
358 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 ...
user avatar
  • 2,153
0 votes
1 answer
137 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$...
user avatar
  • 2,153
1 vote
1 answer
66 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 ...
user avatar
  • 2,153
6 votes
1 answer
169 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 ...
user avatar
  • 3,448
0 votes
1 answer
153 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. ...
user avatar
  • 2,153
0 votes
2 answers
55 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_{\...
user avatar
  • 3,448
0 votes
1 answer
37 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) \...
user avatar
2 votes
0 answers
94 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 ...
user avatar
1 vote
2 answers
167 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 ...
user avatar
  • 3,448
1 vote
1 answer
258 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\ ( \ ∀...
user avatar
  • 53.3k
0 votes
1 answer
117 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: ...
user avatar