Stack Exchange Network

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

2
votes
1answer
35 views

Lowest Unique Ordinal Game

The "lowest unique integer game" is widely-known: Some number of players each pick an integer from the range $[1, n]$ and the winner is the player who chose the lowest unique integer (if such a player ...
0
votes
0answers
25 views

Basic Proposition of Cardinals

Definition. A cardinal is an ordinal which it is not in bijection with any smaller ordinal. Notation. $|X|$ means that cardinal of $X$. Proposition 1. Let $w$ be an ordinal. Then $|w+1|=w.$ ...
1
vote
0answers
98 views

Motivation of the von Neumann definition of ordinals

The von Neumann ordinals are defined in such a way that each ordinal is exactly the set of all smaller ordinals. I am wondering about the origin/motivation for this definition of ordinals (that is, ...
0
votes
1answer
28 views

For ordinals, if $\beta \leq \alpha < \beta + \gamma$ then $\alpha = \beta + \delta$ for some $\delta < \gamma$

I need to show, for ordinals $\alpha, \beta, \gamma, \delta$, that: if $\beta \leq \alpha < \beta + \gamma$ then $\alpha = \beta + \delta$ for some $\delta < \gamma$. I understand this should ...
1
vote
1answer
49 views

Is $L^{n}$ normal, where $L$ denotes the closed long ray?

1.I am trying to prove that $L^{n}$, the $n$-$th$ product of closed long ray is normal, so that I can apply Tietze extension theorem to its closed subset and prove something else. I think I am able to ...
1
vote
0answers
48 views

Can the following lemma about HEP be generalized?

If $(X,A)$ has homotopy extension property (HEP), $A$ closed in $X$, then so does $(X\times I,X\times\partial I\cup A\times I)$ where $I$ is the unit interval. Is this still true if we replace HEP by ...
1
vote
2answers
46 views

Ordinal $\omega_1$ is not compact

Any ordinal number can be turned into a topological space by using the order topology. The topological space $\omega_1$ is sequentially compact but not compact. Why is $\omega_1$ not compact ?
2
votes
0answers
82 views

Computation of Length of Terminating Sequences of Infinite Ordinals

I often enjoy generating terminating sequences for countable (recursive, of course) ordinals. My process is as follows. Say we pick a natural number, in my case, almost always: two. Then we pick a ...
2
votes
1answer
53 views

Intuition behind Covering Axioms

Many concepts in General Topology are the direct abstraction of very profound and natural concepts (think of structures as topology or uniformity themselves, separation axioms, quotient and ...
2
votes
0answers
39 views

Functions between ordinals.

I'm trying to compute the cardinality of a determined set. $$A=\{f\colon \omega_n \to \omega_m | |Supp(f)|=\aleph_k \quad k<n\}$$ As suggested by the exercise, I first tried few elementar cases: $$...
2
votes
1answer
45 views

Well-ordered sets are order-isomorphic to a unique ordinal and proof by induction over the ordinals

I've read through the various threads concerning the proof that every well-ordered set is order isomorphic to an ordinal, and I have a thousand questions. Let me concentrate on one. I'm reading a set ...
1
vote
1answer
34 views

order type of club - cofinality

With $ot(C)$ being the order-type of the club $C$, and $cof(\alpha)$ the cofinality of the ordinal $\alpha$ Show that for every limit ordinal $\alpha$ there is a club $C\subseteq \alpha$ such that $...
1
vote
2answers
60 views

How can I prove that if $\alpha$ is an ordinal, then there is an initial ordinal $\kappa$ such that $|\alpha|=|\kappa|$?

I'm having trouble understanding initial ordinals. In particular, I can't prove a seemingly trivial theorem about them. Def: An ordinal $\kappa$ is an initial ordinal iff $\forall \delta < \kappa \...
1
vote
2answers
27 views

How do I prove the anti-symmetry and there is a minimal element for each subset of $\alpha$

An ordinal number is a set $\alpha$ with the following properties: (a) If $x,y \in \alpha,$ then either $x\in y$, $y\in x$, or $x=y.$ (b)If $y\in \alpha$ and $x\in y$, then $x\in \alpha$. ...
0
votes
1answer
18 views

Subclass of ordinals is a set iff it is bounded

Let $X\subseteq \text{Ord}$. Then $X$ is a set if and only if there exists an ordinal $\beta$ such that for all $\alpha \in X$, $\beta\ge \alpha$. I am really having trouble with proving that ...
0
votes
1answer
42 views

How to prove that the set $C$ is unbounded

My textbook Introduction to Set Theory 3rd by Hrbacek and Jech defines relevant concepts as follows: A set $C \subseteq \omega_1$ is closed unbounded if $C$ is unbounded in $\omega_1$ , ...
1
vote
2answers
40 views

Prove that the set of all closure points of an increasing function is closed unbounded

My textbook Introduction to Set Theory 3rd by Hrbacek and Jech defines some concepts as follows: A set $C \subseteq \omega_1$ is closed unbounded if $C$ is unbounded in $\omega_1$ , i.e.,...
1
vote
2answers
22 views

A decreasing transfinite sequence of subsets of a countable set.

Let $X$ be a countable set and $(S_\alpha)_{\alpha< \rho}$ is a decreasing transfinite sequence of subsets of $X$ in the sense that $$ S_\alpha \supset S_\beta $$ whenever $\alpha<\beta$. Here $\...
1
vote
1answer
42 views

What sets are there with order type $\omega^2$

I’ve recently been thinking about order types of sets, and I can’t come up with a set of natural numbers order type $\omega^2$ or $\omega\cdot\omega$. If someone could help me by giving an example it ...
4
votes
1answer
34 views

Proving (without AC) that there is a surjective function from $\mathcal{P}(\omega)$ to $\omega_1$.

Problem I am working on the following exercise from page 60 of Kunen's Foundations of Mathematics: Prove, without using AC, that one can map $\mathcal{P}(\omega)$ onto $\omega_1$. In my copy of ...
4
votes
0answers
42 views

Does there exist a notion of “growth rate”, big-O notation, etc for ordinal (normal) functions?

Given some $f: \Bbb N \to \Bbb N$, we have various ways to talk about how fast it's growing: big-O notation, little-o notation, and so on. These are a good way to compare growth rates, so we can talk ...
2
votes
1answer
29 views

Can $\kappa$-club is defined for any class of ordinals?

In reading "Proof Theory - The First Step into Impredicativity", I'm stuck at Thm. 3.2.19. 3.2.19 Theorem Let $\kappa$ be a regular ordinal. A class $M\subseteq On$ is $\kappa$-club iff $en_M$ is a ...
-2
votes
1answer
32 views

Unknown notation/omega

What does the 3rd term in $\omega\times\omega\times\omega^{\operatorname*{\omega}\limits_{\smile}}$ with semicircle below the last $\omega$ in definitions 5.3.6 here mean?
2
votes
1answer
39 views

Modifying the “base” of Veblen's hierarchy to exceed $\Gamma_0$

The Veblen hierarchy is usually defined with $\varphi_0(x) = \omega^x$. As a result, we can define the Feferman–Schütte ordinal as the first fixed point of the function $\varphi_\alpha(0) = \alpha$. ...
1
vote
0answers
38 views

What is $\sup \emptyset$ (if exists) w.r.t the usual ordering on ordinals?

My textbook Introduction to Set Theory 3rd by Hrbacek and Jech defines the supremum of a set $X$ of ordinals as follows: Clearly, If $X=\emptyset$, then $\bigcup \emptyset$ is undefined. So I ...
8
votes
1answer
149 views

A particular class which satisfies all ZF axioms except for the axiom of infinity

Suppose we have a non-empty transitive class $\mathcal{C}$, meaning that if $x$ is in the class, then all its elements are also in the class. Suppose also that $\mathcal{C}$ satisfies the axiom schema ...
1
vote
0answers
63 views

What rule allows to determine the symbol on an $i$-th cell of the tape of an Infinite Time Turing Machine at any limit stage?

Assuming that $s$ denotes a particular symbol that can appear on the tape, $\alpha$ denotes any limit ordinal such that $\alpha \ge \omega$ and $C_i[\tau]$ denotes the symbol on the $i$-th cell of ...
1
vote
1answer
52 views

Set of well-orderings of a given ordinal

Let $\alpha$ be an ordinal. Consider the set $$S = \{ \operatorname{type}(\alpha, R) : R \text{ well orders } \alpha \}$$ Clearly $\alpha \in S$. Can anything be said about the relation of an ...
0
votes
0answers
33 views

Prove the existence of transfinite hierarchy of Borel sets by Transfinite Recursion Theorem

The sequence $\langle {\bf \Sigma}^0_\alpha, {\bf \Pi}^0_\alpha \rangle_{\alpha \in \rm{Ord}}$ is the transfinite hierarchy of Borel sets. My textbook only postulates the existence of this sequence. I ...
1
vote
0answers
47 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
55 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
44 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
68 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
93 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
55 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
37 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
100 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
58 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
70 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
19 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
38 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
39 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
37 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
59 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
72 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
50 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
138 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 ...
0
votes
1answer
73 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
64 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 \...