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 ...

2
votes
1answer
23 views

A Lemma in Transfinite Recursion Theorem

Transfinite Recursion Theorem: Let $G:V\to V$ be a class function. Then there is a unique function $F:\operatorname{Ord}\to V$ such that $$\forall \alpha\in \operatorname{Ord}:F(\alpha)=G(F\...
3
votes
0answers
33 views

A proof of Transfinite Induction

This is my proof of Transfinite Induction by filling the gaps in my textbook. It would be great if someone help me verify if i correctly understand what is meant by the authors! Let $P(\alpha)$ is ...
2
votes
0answers
32 views

Every well-ordered set is isomorphic to a unique ordinal number

Every well-ordered set is isomorphic to a unique ordinal number. This is a well-known and important theorem, so i would like to give it a shot by myself. Does my proof look fine, or contain logical ...
0
votes
0answers
11 views

Let $X$ be a set of ordinals. Then $\bigcup X$ is the supremum of $X$

Does my proof look fine or contain mistakes? Any suggestion is appreciated! Let $X$ be a set of ordinals. Then $\bigcup X$ is the supremum of $X$. Lemma: Let $X$ be a set of ordinals. Then $\...
0
votes
0answers
15 views

Suppose that $\alpha,\beta$ are ordinals and that $\alpha\neq\beta$. Then $\alpha$ and $\beta$ are not isomorphic

Does my proof look fine or contain mistakes? Any suggestion is appreciated! Suppose that $\alpha,\beta$ are ordinals and that $\alpha\neq\beta$. Then $\alpha$ and $\beta$ are not isomorphic. My ...
2
votes
1answer
25 views

Suppose that $X$ is a set of ordinals. Then there exists an ordinal $\beta\notin X$

Does my attempt look fine or contain gaps? Thank you so much! Suppose that $X$ is a set of ordinals. Then there exists an ordinal $\beta\notin X$. My attempt: Lemma: Let $X$ be a set of ...
0
votes
0answers
10 views

Let $X$ be a set of ordinals and $\alpha=\bigcup X$. Then $\alpha$ is an ordinal

Does my attempt look fine or contain gaps? Thank you so much! Let $X$ be a set of ordinals and $\alpha=\bigcup X$. Then $\alpha$ is an ordinal. My attempt: Lemma 1: Let $\alpha$ be an ordinal. ...
2
votes
2answers
34 views

Injection from cardinal $\lambda$ to cardinal $\kappa$ implies $\lambda\leq\kappa$

I'm trying to prove that if there is an injection $f:\lambda\to\kappa$ (for $\lambda$,$\kappa$ cardinal numbers) then $\lambda\leq\kappa$. This is not true if they are just ordinal numbers, for ...
3
votes
0answers
18 views

Suppose that $X$ is a set of ordinals. Then $\bigcup X$ is transitive

Suppose that $X$ is a set of ordinals. Then $\bigcup X$ is transitive. Please help me verify my attempt! Many thanks for you! My attempt: Suppose that $\alpha\in\beta\in\bigcup X$. Then $\alpha\in\...
1
vote
1answer
32 views

Every set of ordinals is well-ordered with respect to $\in$

Does my attempt look fine or contain gaps? Thank you so much! Theorem: Every set of ordinals is well-ordered with respect to $\in$. Lemma 1: Every nonempty set of ordinals has a least element ...
0
votes
0answers
13 views

If $\alpha$ and $\beta$ are ordinals. Then $\gamma=\alpha\cap\beta$ is an ordinal

Does my attempt look fine or contain gaps? Thank you so much! Theorem: If $\alpha$ and $\beta$ are ordinals. Then $\gamma=\alpha\cap\beta$ is an ordinal. Proof: $\gamma$ is well-ordered Since $\...
5
votes
0answers
49 views

Are ordinals greater than $\varepsilon_0$ used outside Ordinal Analysis?

I know of Conway's use of ordinals to exhibit the algebraic closure of $\mathcal{F}_2$. I also read a document about the Cantor Bendixson rank of some family of groups. But I found no applications of ...
6
votes
1answer
82 views

What is the cardinality of the set of equivalence classes of countable order types under bi-embeddability?

Two ordered sets have the same order type if there exists an order isomorphism between them. Now the set $X$ of all order types of countable totally ordered sets has cardinality $2^{\aleph_0}$; see ...
0
votes
0answers
17 views

Proof of Tartan's Theorem?

I have read only one proof online that shows that the Sprague-Grundy value of a position in an impartial game, denoted by say $g(x,y)$, is equal to $g_1(x) \otimes g_2(y)$, where $\otimes$ denotes Nim-...
1
vote
1answer
28 views

Is there a standard ordering of non-ordinal order types?

Two ordered sets have the same order type if there exists an order isomorphism between them. The order type of a well-ordered set is called an ordinal number. There is a standard ordering of the ...
0
votes
3answers
23 views

Sequential compactness of $S_\Omega$ and unbounded sequences.

I'm currently trying to prove that The space $S_\Omega$ is sequentially compact. where $S_\Omega$ is the first uncountable ordinal (i.e. it is well ordered, uncountable and all proper sections are ...
2
votes
1answer
33 views

Linearity of ordinals

Ordinals are defined as a set which is transitive and all its elements are transitive. In the proof of linearity of ordinals i.e. $$\forall a \forall b : a<b \vee a>b \vee a=b $$ We assume ...
0
votes
1answer
33 views

The intersection of a class of ordinals belongs to that class

In Jech's Set Theory he claims (p. 20, new millennium edition): If $C$ is a nonempty class of ordinals, then $\cap C$ is an ordinal, $\cap C \in C$ and $\cap C = \inf C$ Jech does not give a proof,...
0
votes
1answer
43 views

Show that $\omega + \omega$ is countable.

Two sets are equinumerous if there exists a bijection between them. A set is finite if it is equinumerous to some $n \in \omega$ and a set is countable if it is equinumerous to $\omega$. $\omega$ is ...
0
votes
1answer
33 views

Given an ordinal $(\alpha,\in)$, how do I find a subset of rationals which is isomorphic to it? [duplicate]

How do I find a subset $E$ of the rationals such that $(E,<) \cong (\alpha,\in)$ where $<$ is the usual ordering of the rationals and $\alpha$ is an ordinal? $(E,<) \cong (\alpha,\in)$ means ...
0
votes
1answer
50 views

Why does $1+\omega=\omega$ with ordinal addition

In my notes, it says that $1+\omega=\omega \neq \omega+1$. I understand why the two expressions are not equal, but why does this equality holds: $$1+\omega = \cup\{1+n:n\in\omega\}=\omega$$
0
votes
1answer
29 views

Is there a standard notation for an ordinal number with cardinality of the continuum?

Under ZFC, the real numbers can be well-ordered. So, there is some ordinal number whose cardinality is that of the continuum. Is there a standard notation for this number? For example, the first ...
2
votes
2answers
62 views

What are the order types of all the total orders on $\mathbb{N}$?

Two ordered sets have the same order type if there exists an order-preserving bijection between them whose inverse is also order-preserving. My question is, what are the order types of all the total ...
0
votes
0answers
31 views

$\log(b,a_1)\in\log(b,a_3) \land \log(b,a_2)\in\log(b,a_3) \implies a_1+a_2\in a_3$?

Let $a,b$ be ordinals. Define $\log(b,a)$ as the biggest ordinal such that $b^{\log(b,a)}\subseteq a$, i.e. for all ordinals $c$ with $b^c\subseteq a$ holds $c\subseteq \log(b,a)$. Question: Given ...
1
vote
2answers
65 views

What are possible ways to refer to a particular (unique) real number that encodes a copy of a chosen large countable ordinal?

Let $E$ denote a particular (arbitrarily chosen, but fixed) method of representing ordinals as real numbers. Let $\alpha$ denote any large countable ordinal. Suppose that we want to refer to a ...
5
votes
1answer
82 views

Does there exist a strict numeric measure of the strength for any set theory (relative to a corresponding proof-theoretic ordinal)?

I have found the following quote ( source ): The proof-theoretic ordinal of any theory is less than $\omega_1^{CK}$. But if all these proof-theoretic ordinals are recursive and below $\omega_1^{...
0
votes
1answer
34 views

Understanding a proof about regular cardinals from “Set Theory for the Working Mathematician”

Consider the following proposition: If $\lambda$ is regular cardinal, $A \subseteq \lambda$ and $|A| < \lambda$ then there is $\alpha < \lambda$ such that $A \subseteq \alpha$. Here's its ...
1
vote
2answers
34 views

A cofinal function into a limit ordinal

Let $\alpha$ be a limit ordinal. Let $f\colon\beta\to\alpha$ be a cofinal function, that is, a function so that $f(\beta)$ is unbounded in $\alpha$. That is, we have $(\forall \gamma < \alpha)(\...
0
votes
1answer
58 views

Why can the set of all natural numbers and omega be put in one-to-one correspondence with natural numbers? [closed]

If $\omega$ comes literally after we've run out of all natural numbers, then why can the set of all natural numbers and omega be put in one-to-one correspondence with natural numbers? I feel the ...
0
votes
1answer
38 views

Function with an ordinal domain: an ambiguity between a notation for a value and for an image

Let $f\colon\alpha\to\beta$ be a function from an ordinal $\alpha$ into an ordinal $\beta$. Since ordinals are transitive sets (i.e. a set $x$ so that $\forall y(y \in x \Longrightarrow y \subseteq x))...
2
votes
2answers
34 views

Proving that if $\kappa$ is a limit ordinal, then $\alpha+\kappa=\bigcup_{\gamma\in\kappa}\left(\alpha+\gamma\right)$

Let $\alpha$ be an ordinal and let $\kappa$ be a limit ordinal. I want to prove that $$\alpha+\kappa=\bigcup_{\gamma\in\kappa}\left(\alpha+\gamma\right).$$ Here I define the sum of ordinals not using ...
0
votes
1answer
38 views

Applying transfinite recursion

Let $f\colon\alpha\to\beta$ be a function between ordinals $\alpha,\beta$. I want to define a function $g\colon\alpha\to\gamma$ for some ordinal $\gamma$ so that $(\forall \eta < \alpha)(g(\eta) =...
1
vote
1answer
18 views

A variant of the definition of an ordinal number

A set is an ordinal if it is transitive and well-ordered by $\in$. How do the transitive sets linearly ordered by $\in$ look like? Are they again just ordinals by the regularity axiom?
1
vote
1answer
32 views

Proper initial segment $X$ of a von Neumann ordinal $Y$ has different order-isomorphism class from $Y$

I mean for von Neumann ordinal a $\in$-transitive set well-ordered by $\in$, I proved that the class of such ordinals is well ordered by $\in$ (or equally by inclusion), and so different von Neumann ...
0
votes
1answer
30 views

Does $\{x \in \mathcal X:x>a \land x<b+1 \}$ give $(a,b+1)$ or $(a,b]$?

Ordinal numbers:- An ordinal number is a set $\alpha$ with the following properties: (1) If $x,y \in \alpha$, then either $x\in y, y\in x, $ or $y=x$ (2)If $y \in \alpha$ and $x\in y$, then $...
1
vote
1answer
113 views

Is it possible to base the slow-growing hierarchy on the ordinal defined as “the height of the minimal model of ZFC (assuming it exists)”?

Let $\alpha$ denote the ordinal described in section 2.24 of the book “A zoo of ordinals” [David A. Madore]: 2.24. The smallest ordinal $\alpha$ such that $L_{\alpha} \models {\text{ZFC}}$ (...
1
vote
2answers
71 views

How exactly does the oracle for a well-order of order type $\omega_1^\text{CK}$ operate?

The concept of an oracle for Turing machines assumes that the oracle answers Yes/No to a particular question $Q$, assuming that $Q$ is formulated as a bitstring on the oracle tape (instead of ...
2
votes
1answer
75 views

Simple ordinal question

Sorry I asked this question as a comment on other thread. I thought I would better ask it as a separate question since I have seen this notation more than few times now and I am not quite certain what ...
2
votes
1answer
31 views

Sets definable by $\Sigma_2$ parameters

Say that a formula $\phi$ defines a set $x$ from parameters $a_1, \dots, a_n$ if $\phi(a_1, \dots, a_n, x)$ holds (in $V$) but for $y \neq x$ $\phi(a_1, \dots, a_n, y)$ does not hold. Is it true that:...
0
votes
1answer
53 views

What does a hyperreal version of the Cantor Set look like?

I would like to construct a hyperreal version of the Cantor set. Let $X_0$ be the interval $[0,1]$ in the hyperreal line, and for any $n$, let and let $X_{n+1}$ be the set of hyperreal numbers ...
1
vote
1answer
94 views

Is it possible to construct a model of oracle Turing machines that correspond to $\omega_n^\text{CK}$, where $n$ is greater than $1$?

I have found the following quotes. Quote $1$ ( source ): In computability theory, Turing Machines+BB oracles correspond to the same ordinal as ordinary Turing Machines ($\omega_1^\text{CK}$). In ...
0
votes
0answers
23 views

Proving the Pressing down lemma [duplicate]

I'm having troubles in finding how to use the first part to prove the second Here is the link to my question about part 1 that was already answered Prove that if: $g: \omega_1\rightarrow\omega_1$ ...
2
votes
1answer
74 views

Given an ordinal with a particular cofinality, can we find other cofinal subsets with order type and cofinality at least that large?

Followup to: If $\omega^\alpha$ has cofinality $\omega^\beta$, and $\beta\le\gamma\le\alpha$, does it also have a cofinal subset of order type $\omega^\gamma$? Say we have an ordinal $\omega^\alpha$ ...
1
vote
1answer
32 views

If $\omega^\alpha$ has cofinality $\omega^\beta$, and $\beta\le\gamma\le\alpha$, does it also have a cofinal subset of order type $\omega^\gamma$?

Here's a question I'm having some trouble answering: Say we have an ordinal $\omega^\alpha$ and suppose it has cofinality $\omega^\beta$, i.e., $\omega^\beta$ is the smallest order type of a cofinal ...
1
vote
2answers
55 views

Prove that if: $g: \omega_1\rightarrow\omega_1$ then for some $\alpha<\omega_1$: $\forall \beta<\alpha: g(\beta)<\alpha$

Prove that if $g: \omega_1\rightarrow\omega_1$ then for some $0<\alpha<\omega_1$, $\forall \beta<\alpha: g(\beta)< \alpha$ How should I prove this theorem. I don't even know how to start
0
votes
1answer
37 views

$\omega_1$ is a limit point of the subset $[0,\omega_1)$

In the Wiki of order topology, I encounter the following statement. $\omega_1$ is a limit point of the subset $[0,\omega_1)$ even though no sequence of elements in $[0,\omega_1)$ has the element $\...
1
vote
0answers
42 views

Is it possible to construct order types using sets?

It's possible to construct a "function" $f$ from the class of well-ordered sets to the class of all sets where for any well-ordered sets $A$ and $B$, we have $f(A)=f(B)$ if and only if $A$ and $B$ are ...
3
votes
3answers
89 views

How to formally use transfinite recursion to construct a sequence for a proof of Zorn's lemma

I'm trying to get my head around how to prove that the axiom of choice implies Zorn's lemma using transfinite recursion: Transfinite recursion I Let $G$ be a class function. Then there is class ...
5
votes
2answers
123 views

Finding a well-ordering of the natural numbers of a given order type

Let $X$ be the set of all well-orderings of the set of natural numbers, and let $O$ be the set of countable ordinals, i.e. the set of ordinals that are order types of the well-orderings in $X$. Then ...
-1
votes
1answer
58 views

When does an injective function $\omega^{<\omega}\to\Bbb N$ have positive density in the integers? [closed]

Under what minimal conditions must the range of a definable, injective function $\omega^{<\omega}\to\Bbb N$ have positive density in the integers? I'm very inexperienced in such matters but it ...