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 [ordinals]

In the ZF set theory ordinals are transitive sets which are well-ordered by $\in$. They are canonical representatives for well-orderings under order-isomorphism. In addition to the intriguing ordinal arithmetics, ordinals give a sturdy backbone to models of ZF and operate as a direct extension of the positive integers for *transfinite* inductions.

1
vote
0answers
40 views

Solution verification: Writing a sum in the Cantor normal form

Can someone please help with the following problem. I need to write the following sum in Cantor normal form: $$\sum_{i ∈ ω\cdot2} \sum_{j ∈ i} (i+j)$$ The result I'm getting is $$ω^2 + w,$$ so I ...
1
vote
0answers
45 views

How to justify the uniqueness and existence of this sequence by Transfinite Recursion Theorem?

For $F \subseteq \Bbb R$, the derived set of $F$, denoted by $F'$, is the set of all limit points of $F$. Prove that there exists a unique transfinite sequence $\langle F_\alpha \rangle_{\alpha \in ...
1
vote
1answer
34 views

Different definition of Veblen functions

Consider the Veblen hierarchy, where $\psi_0(x) = \omega^x$ and $\psi_1(x)$ is the x'th fixed point of $\psi_0$, $\psi_2(x)$ is the x'th fixed point of $\psi_1(x)$, and so on. We eventually get to $\...
1
vote
2answers
37 views

Fixed points of ordinal exponentiation for bases besides $\omega$

The first fixed point of the map $x \to \omega^x$ is the first epsilon number $\epsilon_0$, which is the supremum of $\omega, \omega^\omega, \omega^{\omega^\omega}, ... = \omega^{\omega^{\omega^{.^{.^{...
4
votes
1answer
83 views

Is Halmos' use of the Axiom of Substitution wrong in Ch. 19 Naive Set Theory?

I am trying to work out how the axiom of substitution on the set $\omega $ of all natural numbers can be used to construct the set of all successors of $\omega$ (as in the set {$\omega,\omega^+,(\...
1
vote
1answer
50 views

Isomorphism from limit ordinals to ordinals: is there a fixed point?

Let $\kappa > \omega$ be some limit ordinal, and let $L$ be the set of limit ordinals less than $\kappa$. Since $(L,<)$ is well-ordered, it must be isomorphic to some ordinal $\lambda$ via a map ...
1
vote
2answers
35 views

Set theory ordinal proof practice problem

Prove that for every ordinal $\alpha$ there exists a single $\beta$ and $n$, such that ($\beta$ = $0$ ∨ Lim($\beta$)) $\&$ Nat($n$) $\&$ $\alpha = \beta + n$. I am sorry for tossing ...
4
votes
3answers
93 views

How to use transfinite induction/recursion to construct a dense Hamel Basis of a Banach space?

Here is an excellent answer by David C. Ullrich to my old question. In his answer, he proves the following theorem by doing a transfinite induction on the cardinality of the base of topology. If $X$...
3
votes
0answers
56 views

Does every countable well-order inject into the real numbers? [duplicate]

It is easy to prove that $\omega_1$ does not have an order-preserving injection into $(\mathbb R, <)$: to each $\alpha \in \omega_1$ we could assign the interval between the image of $\alpha$ and $\...
2
votes
1answer
65 views

Where is the theorem related to the construction of countable admissible ordinals by Turing machines with oracles?

Wikipedia contains the following information in the article "Admissible ordinal": By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the ...
0
votes
1answer
18 views

$\operatorname{card}(\bigcup\limits_{n \in \mathbb{N}} \underbrace{A\times…\times A}_{n})=k$ if $\operatorname{card}(A)=k$ infinite.

I was reading a proof of a theorem that goes like this: Let $A$ be an infinite set of cardinality $k$ and $A^{<\omega}$ the set of finite sequences of elements of A. Then $\operatorname{card}(A^{&...
0
votes
1answer
36 views

Proving nicely that $3+\omega=\omega$ where $\omega$ is the smallest limit ordinal.

I just learned about ordinal numbers and I am a bit confused to show things with them. Let $\omega$ be the smallest limit ordinal. I want to show that $3+\omega=\omega$. So the definition I have of $...
-1
votes
1answer
36 views

On proving $\omega^{\epsilon} = \epsilon$

How can I prove that $$\omega^{\epsilon} = \epsilon$$ where $\omega =\{0, 1, 2, 3, 4, ...\}$ and $\epsilon = \{\omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \omega^{\omega^{\omega^\omega}}, ...\}...
1
vote
2answers
35 views

Let $α$ and $β$ be ordinals such that $α>1$ and $β\neq0$. Let $γ$, $ζ$, and $η$ be ordinals st $γ<β$, $ζ<α$, and $η<α^{γ}$. Prove $α^γ ζ+η<α^{β}$.

Let $\alpha$ and $\beta$ be ordinals such that $\alpha>1$ and $\beta\neq0$. Let $\gamma$, $\zeta$, and $\eta$ be ordinals such that $\gamma<\beta$, $\zeta<\alpha$, and $\eta<\alpha^{\gamma}...
-1
votes
1answer
56 views

$\alpha + \beta = \sup_{v<\gamma} (\alpha + \beta_{v})$? [closed]

On page 124 of Introduction to Set Theory, Jech claims that ordinal functions below are continuous in the second variable: If $\gamma$ is a limit ordinal and $\beta= \sup_{v<\gamma} \beta_{v}$ then ...
0
votes
1answer
51 views

A question about a proof of Hausdorff's Formula

My textbook Introduction to Set Theory by Hrbacek and Jech presents Hausdorff's Formula: and its corresponding proof: I am unable to deduce 3. from 1. and 2. as stated in the proof. Each ...
0
votes
0answers
50 views

Is my understanding of this proof about cardinality correct?

In my textbook Introduction to Set Theory by Hrbacek and Jech, there is a theorem: and its corresponding proof: I would like to ask if my understanding of the proof in case $\color{blue}{\...
0
votes
1answer
48 views

Is my understanding of a proof from textbook Introduction to Set Theory by Hrbacek and Jech correct?

3.8 Therorem Let us assume the Generalized Continuum Hypothesis. If $\aleph_\alpha$ is a regular cardinal, then $$\aleph_\alpha^{\aleph_\beta}=\begin{cases} \aleph_\alpha&\text{if }\beta<\alpha\...
1
vote
1answer
123 views

What is the source of formal descriptions for large uncomputable ordinals clockable by Infinite Time Turing Machines?

I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $\alpha$ if $\alpha$ is a computable ordinal: basically, we take the description of some standard Turing ...
1
vote
1answer
67 views

A question regarding Brian M. Scott's proof that $\text{cf}(\aleph_{\omega_1})=\omega_1$

$\text{cf}(\aleph_{\omega_1})=\omega_1$ From here, I quote Brian M. Scott's proof: Suppose that $\langle\alpha_n:n\in\omega\rangle$ is an increasing sequence cofinal in $\omega_{\omega_1}$. For ...
0
votes
1answer
61 views

Let $(\alpha_\xi\mid\xi<\kappa)$ be a sequence such that $\{\alpha_\xi\mid\xi<\kappa\}=\alpha$. Find an increasing subsequence that has limit $\alpha$

Let $\alpha$ be a limit ordinal which is not a cardinal, and $\kappa=|\alpha|$. Then there exists a bijection from $\kappa$ to $\alpha$, or equivalently, a one-to-one sequence $\langle \alpha_\xi \...
0
votes
1answer
46 views

If $\alpha$ is a limit ordinal, then $\operatorname{cf}(\alpha)$ is a limit ordinal [duplicate]

In the textbook Introduction to Set Theory by Hrbacek and Jech, Section 9.2, the authors first introduce the definition of increasing sequence of ordinals: Then they introduce cofinality: My ...
0
votes
0answers
53 views

Is this an equivalent definition of singular cardinal?

In my textbook Introduction to Set Theory, the authors define singular cardinal as follows: I propose an equivalent definition as follows: An infinite cardinal $\kappa$ is called singular if ...
0
votes
1answer
109 views

What exactly does it mean for an Infinite Time Turing Machine to reach stage $\omega$ (and limit ordinal stage)?

The paper “Infinite Time Turing Machines” contains the following information: At each step of computation, the head reads the cell values which it overlies, reflects on its state, consults the ...
0
votes
2answers
38 views

Let $B,C$ be sets, $B\subseteq C$ such that $\forall c∈C,\exists b\in B: c\le b$ then $\sup B=\sup C$.

I had been reading this. In the proof, below lemma is used. I don't know how to go for proving it.Notice that I want to prove this theorem for set of ordinals not real numbers Let $B,C$ be sets, $...
0
votes
0answers
58 views

Boolean algebras/Unknown notation

Does someone know what is meant (in the context of trees and Boolean algebras by Shelah) here on the page 8 right above Remark 1.5: $$\{\langle\rangle\}\cup\{\langle\xi\rangle\otimes_{\zeta(*)}d\eta:\...
0
votes
1answer
71 views

What is the name of a theorem which says that if $\alpha$ and $\beta$ are ordinals, then $\alpha\in\beta$, or $\beta\in\alpha$, or $\alpha=\beta$?

This Math.SE question contains the following information: There is a theorem which says given any two ordinals $\alpha$ and $\beta$, exactly one of the following holds: $\alpha\in\beta$, or $\...
1
vote
1answer
50 views

What is a simple method of combining an infinite (or finite) set of well-orders into one well-order?

Let $$W = \{W_1, W_2, W_3, \ldots\}$$ denote an infinite (or finite) set of well-orders on $\mathbb{N}$ and $\alpha_i$ is an ordinal (order type) that corresponds to $W_i$, assuming that $\alpha_1 \ge ...
1
vote
1answer
113 views

Pardon my ignorance, but isn't TREE(3) a finite number?

Pardon my ignorance, but isn't TREE(3) a finite number? -Dylan Thurston It is my understanding as well that TREE(3) is finite (Proof that TREE(n) where n >= 3 is finite?). However, I have seen ...
0
votes
1answer
43 views

$\leq_{\frak K_\lambda}$-increasing continuous

Here (in the context of Abstract Elementary Classes) on the page 43 at the bottom,-6th line, what does it technically mean $$\leq_{\frak K_\lambda}-\text{increasing continuous}$$ ? I think that this ...
1
vote
1answer
51 views

Beginning a Veblen heirarchy with $1 + x$?

If I define: $$ φ'_0(x)=1+x $$ Enumerating the fixed points of $φ'_0(x)$, one would get: $$ φ_1'(0)=ω φ_1'(1)=ω+1 \cdots φ_1'(ω)=ω+ω \cdots $$ Which is identical to: $$ φ_1'(x)=ω+x $$ The next several ...
1
vote
1answer
30 views

Difference between Kleene's O and the system $S_1$

On pages 207-208, Rogers (Theory of Recursive Functions and Effective Computability) introduces two system of notations for ordinals: the first is what he calls $S_1$ and the second one is Kleene's $\...
0
votes
0answers
66 views

How do you define ordinal exponentiation without induction?

I am writing some notes on introductory set theory, starting from the basic axioms all the way to cardinal arithmetic. Right now I am up to ordinal arithmetic. I have defined ordinal addition and ...
0
votes
0answers
52 views

Proving $\alpha+\beta=\sup\{\alpha+\beta_{\delta}:\delta<\gamma\}$

For ordinals $\alpha$, $\beta$, $\gamma$, if $\gamma$ is a limit ordinal and $\beta = \sup\{\beta_{\delta}:\delta<\gamma\}$, why does below expression hold, $$\alpha+\beta=\alpha + \sup\{\beta_{\...
1
vote
1answer
31 views

If $\aleph_\alpha=\alpha$, then $\alpha$ is a limit ordinal

If $\aleph_\alpha=\alpha$, then $\alpha$ is a limit ordinal. My attempt: Assume the contrary that $\alpha$ is not a limit ordinal. Then $\alpha$ is a successor ordinal and thus $\alpha=\beta+1$ for ...
0
votes
0answers
52 views

Boolean algebras/ Shelah/ Unclear step in the proof

Here on the page $10$, what does the displayed formula in the $6$th line $$\text {lg}(\eta_\ell)<\omega\Rightarrow \bigcup\{\text{Rang}(\nu_\ell(k):k<\text{lg}(\nu_\ell))\}\cap\bigcup_{k<\...
0
votes
1answer
84 views

There are arbitrary large singular cardinals $\aleph_\alpha$ such that $\aleph_\alpha=\alpha$

Definitions: Let $(\alpha_\xi \mid \xi < \lambda)$ be a transfinite sequence of ordinals of length $\lambda$. We say that the sequence is increasing if $\alpha_\nu < \alpha_\mu$ whenever $\nu&...
0
votes
1answer
39 views

If $(A,\preccurlyeq)$ is a linear ordering such that $|\{y\in A\mid y\preccurlyeq x\}| < \aleph_\gamma$ for all $x\in A$, then $|A|\le\aleph_\gamma$

If $(A,\preccurlyeq)$ is a linear ordering such that $|\{y\in A\mid y\preccurlyeq x\}| \le \aleph_\gamma$ for all $x\in A$, then $|A|\le\aleph_\gamma$. Does my attempt look fine or contain logical ...
1
vote
1answer
102 views

Well-Ordering Principle implies Zorn's Lemma

Well-Ordering Principle implies Zorn's Lemma Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help! My attempt: Let $(A,\...
4
votes
2answers
281 views

Axiom of Choice implies Well-Ordering Principle

Axiom of Choice implies Well-Ordering Principle. My textbook only presents the construction of function $F$ and does not provide details on how to define such well-ordering. I try to fill in the ...
4
votes
2answers
93 views

Is there a “solution” to the ordinal game?

Even though I have almost no background in logic, I find the idea of ordinal notation quite interesting. It seems that the idea is to come up with notation to define larger and larger numbers, until ...
0
votes
0answers
24 views

Let $α$ and $β$ be ordinals. Let $(η_{ζ})_{ζ\inβ}$ be a $β$-sequence of ordinals. Then $α\times(\sum_{ζ\inβ}\eta_{ζ})=\sum_{ζ\inβ}(α\times\eta_{ζ})$.

Let $\alpha$ and $\beta$ be ordinals. Let $\left(\eta_{\zeta}\right)_{\zeta\in\beta}$ be a sequence of ordinals indexed by $\beta$. Define the sum $\sum_{\zeta\in\beta}\eta_{\zeta}$ as follows. Let $Z=...
0
votes
2answers
27 views

Is the function sending each set to its corresponding Hartogs number injective?

Let $V$ be the class of all sets, $\text{Ord}$ be the class of all ordinals, $\text{InOrd}$ be the class of all initial ordinals, and $f:V \to \text{Ord}$ be the function that sends each set to its ...
0
votes
0answers
23 views

The Hartogs number of $A$ exists for any set $A$

The Hartogs number of $A$ exists for any set $A$. Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help! My attempt: Let $H=\{(W,\...
0
votes
0answers
52 views

For any set $A$, the Hartogs number of $A$ is an initial ordinal

The Hartogs number of $A$ is the least ordinal which is not equipotent to any subset of $A$. We denote the Hartogs number of $A$ by $h(A)$. Theorem: For any set $A$, $h(A)$ is an initial ordinal. ...
1
vote
1answer
28 views

Each well-orderable set $X$ is equipotent to a unique initial ordinal

Each well-orderable set $X$ is equipotent to a unique initial ordinal. Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help! My ...
1
vote
0answers
29 views

Let $n,k\in\omega$. Then $\underbrace{(\omega+k)+(\omega+k)+\ldots+(\omega+k)}_{n\text{ times}}=\omega\cdot n+k$

Let $n,k\in\omega$. Then $\underbrace{(\omega+k)+(\omega+k)+\ldots+(\omega+k)}_{n\text{ times}}=\omega\cdot n+k$. Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly ...
0
votes
0answers
25 views

Is it true that the class of initial ordinals is proper?

It is well-known that the class of ordinals is the proper class. Is it true that the class of initial ordinals is proper? Thank you for your help!
3
votes
1answer
77 views

Prove that $|\omega+\omega|=|\omega\cdot\omega|=|\omega^\omega|=|\omega|$

$|\omega+\omega|=|\omega\cdot\omega|=|\omega^\omega|=|\omega|$ Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help! My attempt: ...
-1
votes
1answer
66 views

$\omega_2$ is not the countable union of countable sets [closed]

I'm not sure I quite understand the form of the proof in this post '$\omega_2$ is a not countable union of countable sets without AC' and similar ones. Is the idea to firstly show that there is an ...