All Questions
22
questions
1
vote
1
answer
67
views
What exactly is the $\in$-Induction Principle?
Throughout the post $\mathcal{L}_\text{ZF}$ is the language of $\text{ZF}$, while $\text{fld}(R)$ is the field of the relation $R$, and $\text{wf}(R)$ means the relation $R$ is well-founded i.e.
$\...
- 5,166
0
votes
0
answers
40
views
How is the following theorem the princple of *complete* induction?
The following is from page $19$ of Holz' Introduction to Cardinal Arithmetic.
As I understand it (see here), ordinary and complete induction (on $\omega$) work as follows:
Ordinary Induction: if $P(...
- 5,166
2
votes
0
answers
71
views
What does it mean that we need $𝜖_0$ induction to prove PA consistency?
I have started to learn about Peano Arithmetic, and also about ordinals.
In particular, I have seen that the Goodstein theorem is an example of a statement that can be expressed in PA but that ...
- 785
0
votes
1
answer
62
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
...
- 5,057
1
vote
1
answer
101
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 ...
- 4,906
1
vote
1
answer
120
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:...
- 12k
1
vote
1
answer
159
views
Does an inductive set contain all the finite ordinals; and a more general definition of inductive sets?
Definition. A set $I$ is called inductive if
$$(\emptyset\in I)\wedge\forall x\in I(x\cup\{x\}\in I)$$
This concept appears in the Axiom of Infinity (in ZF), which claims such a set exists. According ...
- 49
1
vote
1
answer
70
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 ...
- 1,779
0
votes
1
answer
78
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 ...
- 9,299
0
votes
2
answers
100
views
Double induction on ordinals (If $\ \alpha+1=\beta+1$ then $\alpha=\beta$)
Iv'e encountered the following exercise:
Show that for any $\alpha,\beta\in\text{Ord}$ if $\alpha+1=\beta+1$ then $\alpha=\beta$
I think the way to prove this is by induction on, say, $\alpha$. Base $...
- 256
0
votes
2
answers
254
views
if $\alpha<\beta$ then $\omega^\alpha+\omega^{\beta}=\omega^{\beta}$
Prove that if $\alpha<\beta$ then $\omega^{\alpha}+\omega^{\beta}=\omega^{\beta}$
Proof: I'm not too sure what to start with to attempt this, I was thinking that I would need to perform ...
user395952
1
vote
1
answer
340
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 ...
- 4,223
3
votes
0
answers
188
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?...
- 381
0
votes
1
answer
165
views
Is there a key difference between the principle of transfinite induction and the principle of transfinite induction for ordinals?
In a recent question I was asked to prove the principle of transfinite induction for ordinals but I mistakenly proved the principle of transfinite induction, since I have a only a vague understanding ...
- 103
30
votes
6
answers
11k
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 ...
- 11.4k