Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
53 views

Is $\operatorname{rank}(A)\subseteq\operatorname{TC}(A)$?

This question came to me when I was thinking about rank and transitive closures. Let $A$ be a set of rank $\alpha$ and let $\operatorname{TC}(A)$ denote the transitive closure of $A$. Is it true then ...
Anon's user avatar
  • 448
2 votes
2 answers
91 views

If I have a sequence $a_0, a_1, a_2, \cdots$ , then is expressing the limit of this sequence as $a_\omega$ sensible?

If I have a sequence created by some rule which comes to a limit , then I can express it as $a_0, a_1,a_2,\cdots$. If I said $\lim_{n \to \infty} a_n = a_{\omega} $ , is that a sensible thing to do ? ...
Q the Platypus's user avatar
1 vote
1 answer
33 views

Showing that $\bigcap A$ is the least element for the set $A$ where $A$ is a set of ordinals.

The notes I am reading define a set $x$ to be an ordinal provided $x$ is transitive and every element in $x$ is transitive. Let $A$ be a set of ordinals. I have shown that $\bigcap A$ is an ordinal. I ...
3j iwiojr3's user avatar
1 vote
0 answers
76 views

What is the largest known "computational" ordinal

I am interested in the computational implementation of ordinals. What I mean by that, is a data structure T and a function/algorithm "compare" that takes two arguments of type "T" ...
Ivan's user avatar
  • 11
2 votes
1 answer
85 views

Can $\sf{ST}$ construct an infinite class wellordered ordered by $\in$?

Assume the axioms of Extensionality, Empty Set, and Adjunction (meaning that $S\cup\{x\}$ forms a set for any $S,x$). Notice that we do not have Specification as an axiom, which makes this theory very ...
Jade Vanadium's user avatar
1 vote
0 answers
29 views

A sequence of continuum hypotheses

The continuum hypothesis asserts that $\aleph_{1}=\beth_{1}$. Both it and its negation can be consistent with ZFC, if ZFC is consistent itself. The generalised continuum hypothesis asserts that $\...
Darmani V's user avatar
  • 272
1 vote
1 answer
84 views

Can cardinality $\kappa$ exist where $\forall n\in\mathbb{N} \beth_n<\kappa$,$\kappa<|\bigcup_{n\in\mathbb{N}}\mathbb{S}_n|$,$|\mathbb{S}_n|=\beth_n$

The Wikipedia article on Beth numbers defines $\beth_\alpha$ such that $\beth_{\alpha} =\begin{cases} |\mathbb{N}| & \text{if } \alpha=0 \\ 2^{\beth_{\alpha-1}} & \text{if } \alpha \text{ is a ...
SarcasticSully's user avatar
0 votes
0 answers
65 views

Can the class of ordinals be extended even further? [duplicate]

Is it possible for anything to come after all ordinals? I don't see why not. For example, one can take a non-ordinal set $S$, and then add in all the ordered pairs $(\alpha, S)$ to $ON$, where $\alpha$...
user107952's user avatar
  • 21.5k
0 votes
0 answers
18 views

Ordinal addition with limit ordinals, as in Kunen.

This definition of ordinal adddition is taken from Kenneth Kunens "Set Theory: An Introduction to Independence Proofs": $\alpha + \beta = \text{type}(\alpha \times \{0\} \cup \beta \times \{...
Ben123's user avatar
  • 1,309
2 votes
1 answer
127 views

Is the first-order theory of the class of well-ordered sets the same as the first-order theory of the class of ordinals?

Consider the class $K$ of well-ordered sets $(W,\leq)$. Although that class is not first-order axiomatizable, it has an associated first-order theory $Th(K)$. Now consider the class of ordinals $On$, ...
user107952's user avatar
  • 21.5k
2 votes
0 answers
73 views

Set of ordinals isomorphic to subsets of total orders

Background. Given a poset $(S,<)$ we'll indicate with $\tau(S,<)$ the set of all the ordinals which are isomorphic to a well ordered subset of $(S,<)$. We're in $\mathsf{ZFC}$. Questions. ...
lelouch_l8r4's user avatar
3 votes
1 answer
73 views

Constructible subsets of an ordinal - an alternate definition?

Work over ZFC. Recall the standard definition of $\mathrm{Def}(X)$, the set of constructible subsets of the set $X$. This can be considered as taking all those subsets of $X$ that satisfy some first-...
theHigherGeometer's user avatar
5 votes
1 answer
470 views

Does every ordinal have a well-defined "next" limit ordinal?

I would like to know whether every ordinal $\alpha$ has a well-defined "next limit ordinal", i.e. a least limit ordinal $\beta$ such that $\beta > \alpha$. I understand from this ...
blk's user avatar
  • 281
1 vote
0 answers
46 views

Ordinals multiplication: Does $a^2 b^2=b^2a^2$ imply $ab=ba$? [duplicate]

I found this question in one of set theory past exam: If $\alpha$ and $\beta$ are two ordinals such that $\alpha^2\beta^2=\beta^2\alpha^2$, does it necessarily imply $\alpha\beta=\beta\alpha$? Clearly ...
Ankiiatsy's user avatar
1 vote
1 answer
93 views

Intuition of Ordinal Number

I am learning the concept of ordinal numbers. In the book of Set Theory and Metric Spaces by I. Kaplansky (Sec. 3.2, pg. 55), the author states We attach to every well-ordered set an ordinal number; ...
Mingzhou Liu's user avatar
2 votes
0 answers
29 views

References that give the cofinality of ordinal addition, multiplication and exponentiation

$\newcommand{\cf}{\operatorname{cf}}$ Let $\alpha$, $\beta$ be ordinals. I believe that we have \begin{align*} \cf(\alpha+\beta)=\cf(\beta),\quad\beta\neq 0;\quad\cf(\alpha\cdot\beta)=\begin{cases}\cf(...
Jianing Song's user avatar
  • 1,923
2 votes
1 answer
104 views

Define the sum of transfinite ordinal sequences according to finite ordinal sum.

I know it is possibile to define finite sum of ordinals: if $(\alpha_i)_{i\in n}$ is a sequence of lenght $n$, with $n$ in $\omega$, then the symbolism $\sum_{i\in n}\alpha_i$ has a (formal) meaning; ...
Antonio Maria Di Mauro's user avatar
2 votes
1 answer
63 views

Does $\omega_1^{\text{CK}}$ allow to compute the halting problem of $\alpha$-th-order Turing machines for any $\alpha < \omega_1^{\text{CK}}$?

This page contains the following text (see the section “Higher-order busy beaver functions”): At least, under any reasonable formulation of the notion of a higher-order Turing machine, well-orderings ...
lyrically wicked's user avatar
2 votes
1 answer
157 views

Is this a valid basis for a transfinite number system?

I've been curious about transfinite number systems including infinite ordinals, hyperreals, and surreal numbers. The hyperreals in particular seem particularly appealing for introducing a hierarchy of ...
Aidan Simmons's user avatar
-2 votes
1 answer
57 views

Prove that the order type of $\alpha\cdot\beta$ is the antilexicographic order in $\alpha\times\beta$. [closed]

This question is related to this one, but not a duplicate, since I am struggling with injectivity and monotonicity, rather than proving that $\{\alpha\cdot\eta + \xi:\eta<\beta\textrm{ and }\xi<\...
Antonio Maria Di Mauro's user avatar
6 votes
2 answers
117 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_2$ as an oracle?

Let $\omega^{CK}_1$, $\omega^{CK}_2$ denote the first two admissible ordinals greater than $\omega$. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_2$ as an ...
user23013's user avatar
  • 161
4 votes
1 answer
182 views

Colourful class function

Background. We're in $\mathsf{ZFC}$, and I can use the principle of $\epsilon$-induction, but not (directly) the $\epsilon$-recursion. Problem. Let $F : V \to V$, where $V$ is the class of all the ...
lelouch_l8r4's user avatar
0 votes
0 answers
75 views

How Should I Do the Inductive Case of this Proof on Ordinals?

Question Prove that for all ordinals $\alpha$, $V_\alpha=\{x:\rho (x)<\alpha\}$. Note: The function $\rho$ is a rank function. Attempt I did the proof by induction on ordinals. I started with the ...
Mr Prof's user avatar
  • 451
2 votes
0 answers
137 views

Strictly decreasing function from an ordinal to $\mathbb{R}$

Context: We are working in $\mathsf{ZFC}$. Problem: Given a poset $(P,<)$, let $\text{Dec}(P)$ be the set of all strictly decreasing function $f : \alpha \to P$, where $\alpha$ is an ordinal number....
lelouch_l8r4's user avatar
4 votes
1 answer
127 views

Is there a smarter way to calculate $F(\omega^{15} + 7)$? (Ordinal arithmetic)

Given the function $F : \text{Ord} \to \text{Ord}$ definite by transfinite recursion as it follows: $$F(0) = 0 \qquad F(\alpha + 1) = F(\alpha) + \alpha \cdot 2 + 1 \qquad F(\lambda) = \sup_{\gamma &...
lelouch_l8r4's user avatar
2 votes
1 answer
49 views

How Can I Finish off this Solution on Ordinal Arithmetic (Cantor Normal Form)?

Question Let $\beta = \omega + 3$, and $\alpha = \omega ^42+\omega ^34+6 = \beta ^\gamma \delta +\rho$. Find ordinals $\gamma$ and $\delta$, with $0<\delta<\beta$ and $\rho <\beta ^\gamma$. ...
Mr Prof's user avatar
  • 451
1 vote
1 answer
49 views

Is this Solution on Ordinal Arithmetic Correct (Cantor Normal Form)?

Question Let $\beta=\omega + 3$. Calculate $\beta ^2,\beta ^3$ and $\beta ^4$ in Cantor Normal Form. Attempt Since $\beta = \omega + 3$, then $\beta ^2 = (\omega +3)(\omega +3) = (\omega +3).\omega + (...
Mr Prof's user avatar
  • 451
0 votes
0 answers
39 views

Find necessary and sufficient conditions for ordinal monotonicity.

First of all let's we remember the following result. Theorem Let be $\lambda$ and ordinal: a predicate $\mathbf P$ is true for any $\alpha$ in $\lambda$ when the truth of $\mathbf P$ for any $\beta$ ...
Antonio Maria Di Mauro's user avatar
1 vote
0 answers
75 views

Does the equality $\omega\cdot(\omega+1)=(\omega+1)\cdot\omega$ hold?

By this answer I knkow that the equality $$ (\omega+1)\cdot\omega=\omega^3 $$ holds whereas by the definition of ordinal multiplication I know that the equality $$ \omega\cdot(\omega+1)=\omega^2+\...
Antonio Maria Di Mauro's user avatar
4 votes
0 answers
84 views

Finding the first term of a Goodstein sequence whose expression has maximum exponent

Let $n$ be a natural number. When constructing the Goodstein sequence $(n)_{k}$, we start with $(n)_{1}=n$ written in complete base $2$, and we proceed recursively. That is, if $(n)_{k}$ has been ...
John's user avatar
  • 4,442
1 vote
2 answers
104 views

Transfinite recursion to construct a function on ordinals

I am asked to use transfinite recursion to show that there is a function $F:ON \to V$ (here $ON$ denote the class of ordinals and $V$ the class of sets) that satisfies: $F(0) = 0$ $F(\lambda) = \...
Guest_000's user avatar
  • 839
0 votes
1 answer
117 views

Proving the Weak Goodstein Theorem within $\mathsf{PA}$

In Cichon, E. A., A short proof of two recently discovered independence results using recursion theoretic methods, Proc. Am. Math. Soc. 87, 704-706 (1983). ZBL0512.03028. the following process is ...
John's user avatar
  • 4,442
2 votes
1 answer
67 views

Is possibile to define an exponentiation with respect an ordinal operation?

It is well know the following resul holds. Theorem For any $(M,\bot,e)$ monoid there exists a unique esternal operation $\wedge_\ast$ from $X\times\omega$ into $X$ such that for any $x$ in $M$ the ...
Antonio Maria Di Mauro's user avatar
1 vote
0 answers
72 views

Reference request: monoids on ordinal numbers

It is well-known that $(\text{Ord},+,0)$ and $(\text{Ord},\cdot,1)$ are monoids, but I haven't found references on these structures or other simpler ones (like $(\omega_1,+,0)$). For example, it would ...
Yester's user avatar
  • 414
0 votes
1 answer
67 views

An ordinal $\nu$ is a natural iff there is no injection $f$ of $\nu$ into $X$ in $\mathscr P(\nu)\setminus\{\nu\}$.

Let's we prove the following theorem. Theorem An ordinal $\nu$ is a natural if and only if there is no injection of $\nu$ into $X$ in $\mathscr P(\nu)\setminus\{\nu\}$. Proof. Let's we assume there ...
Antonio Maria Di Mauro's user avatar
1 vote
1 answer
116 views

$\omega$-th or $(\omega + 1)$-th when putting odd numbers after even numbers?

The following clip is taken from Chapter 4 - Cantor: Detour through Infinity (Davis, 2018, p. 56)[2]. When putting odd numbers after even numbers, what should the index for the first odd number ($1$ ...
Yif's user avatar
  • 103
3 votes
1 answer
64 views

A countable ordinal which is $\Sigma_n$-definable in first-order ZFC, but not $\Sigma_m^1$-definable in full second-order arithmetic

Let us say that a $\Sigma_m^1$-formula $\phi$ defines a countable ordinal $\alpha$ if it defines a type-$1$ object (i.e. a real) $x$ that encodes a well-ordering of $\mathbb{N}$ of order type $\alpha$ ...
lyrically wicked's user avatar
3 votes
0 answers
83 views

What is $\epsilon_0 \cdot \omega$?

I'm a bit stuck on telling what the ordinal $\epsilon_0 \cdot \omega$ is. $$\epsilon_0 = \sup \{1, \omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \dots \}$$ so $$\epsilon_0 \omega = \sup \{\omega, ...
Robin's user avatar
  • 3,940
1 vote
1 answer
82 views

How can different representations of the same integer be equivalent?

I recently read about a way to define the set of integers as the set of all equivalence classes for some equivalence relation $\simeq$ satisfying $(a,b)\simeq(c,d)$ for $(a, b),\;(c,d)\in\mathbb{N}\...
Alice's user avatar
  • 508
6 votes
0 answers
216 views

$\varepsilon_0 !$ (ordinal factorial)

Given an ordinal $\alpha$, define $\alpha !$ as it follows: $$ \alpha! := \begin{cases} 0! = 1 \\ (\alpha + 1)! = \alpha ! \cdot (\alpha + 1) \\ \lambda! = \left(\sup_{\gamma < \lambda} \gamma !\...
lelouch_l8r4's user avatar
2 votes
1 answer
105 views

Taking the limit beyond infinity, with the ordinals

Imagine a function $f:X\to X$ and $x\in X$ (keeping $f$ and $X$ vague on purpose) and let's define $u_1 = f (x)$ $u_2=f^2(x)=f(f(x))$ $u_n=f^n(x)$ Let's also assume that $\forall n, u_{n-1} \neq u_n $ ...
KiwiKiwi's user avatar
  • 169
2 votes
1 answer
105 views

Stuck on Jech's Set Theory Exercise 2.3

From Jech's Set Theory: Exercise (2.3). If $X$ is inductive, then $X\cap\text{Ord}$ is inductive. $\textbf{N}$ is the least nonzero limit ordinal, where $\textbf{N} = \bigcap\{X:X\text{ is inductive}\...
Sam's user avatar
  • 5,166
0 votes
1 answer
68 views

Proving $\alpha\subset\beta\implies\alpha\in\beta$ for ordinals $\alpha$ and $\beta$

From Jech's Set Theory: Lemma 2.11. (iii) If $α\ne β$ are ordinals and $α ⊂ β$, then $α ∈ β$. Proof: If $α ⊂ β$, let $γ$ be the least element of the set $β − α$. Since $α$ is transitive, it follows ...
Sam's user avatar
  • 5,166
2 votes
1 answer
200 views

Countable ordinals having a certain property

Which are the countable ordinals $\lambda$ such that, for every sequence of ordinals $\alpha_i\ (i\in\mathbb{N})$ such that $\ $it is strictly increasing for all sufficiently large $i$ $\ $$\alpha_i&...
Marco Farotti's user avatar
3 votes
1 answer
146 views

Is the empty set always an 'implicit member' of all sets under a pure set theory?

Pure set theory, wherein all objects considered are sets —whose elements are themselves sets, and so forth— is usually thought of as building itself up in an ex nihilo fashion off the empty set $\...
Sho's user avatar
  • 532
1 vote
0 answers
68 views

How is transifnite recursion applied?

I've been struggling to understand how ordinal addition, multiplication, and exponentiation, along with the Aleph function $\aleph$, are defined using Transfinite Recursion in Jech's Set Theory or ...
Sam's user avatar
  • 5,166
2 votes
1 answer
90 views

What is cardinality of ordinal exponentiation?

Using von Neumann definition of ordinals, is it true that for all cardinal numbers $a$ and $b$ the following equation holds: $$ a^b = |a^{(b)}| $$ where on the left side is the cardinal exponentiation ...
Iskander's user avatar
0 votes
1 answer
27 views

Find unbounded sequence in an ordinal product of regular uncountable cardinals

I'm a little stuck here (and should mention that I lack experience with unbounded sets in the transfinite): Say we have two uncountable regular cardinals $\kappa$ and $\lambda$ where $\kappa < \...
Nibbler's user avatar
  • 57
0 votes
1 answer
55 views

Ordinal number closed for countable sum

I want to find an ordinal number $\beta$ such that $\sup\{\alpha_1,\alpha_2,\dotsc\}+1<\beta$ for any (countable) sequences $\alpha_1,\alpha_2,\dotsc< \beta$. I know that the least uncountable ...
Gizerst Nanari's user avatar
3 votes
1 answer
80 views

Hessenberg sum/natural sum of ordinals definition

I was given the following definition of Hessenberg sum: Definition. Given $\alpha,\beta \in \text{Ord}$ their Hessenberg sum $\alpha \oplus \beta$ is defined as the least ordinal greater than all ...
lelouch_l8r4's user avatar

1
2 3 4 5
40