03:04
Consider some countable limit ordinal $\lambda$ with fundamental sequence $\lambda [n]$. We can then construct a fundamental sequence $\{\lambda, \lambda+1,\lambda 2, \lambda^2,\phi (\lambda,0), \phi \binom{\lambda}{1},\psi (\lambda),\psi'(\lambda),...,f(\lambda),f^2(\lambda),f^3(\lambda),...\}$
where $f$ is the fastest growing ordinal function provided by $\lambda$. Then this sequence is guarantee to exceed $\lambda$
For example: $f$ of any finite ordinal is succession, and the (not necessary unique) fundamental sequence (where the embedding from the next element to the previous is justified by the inductive definition of succession) $\{0,1,2,3,4,...\}$ should produce $\omega$ by definition of a fundamental sequence?
=====
Or maybe I should put it this way: Every countable and computable ordinal should be produceable by only successions and fundamental sequences
Or maybe I should put it this way: Every countable and computable ordinal should be produceable by only successions and fundamental sequences
and given a $\lambda$ we already constructed using all previously constructed ordinals (which the ordering is determined by ultimately how many successions and cartesian product is being used)
Or maybe I should put it this way: Since every countable and computable ordinal should be produceable by only successions, cartesian products and fundamental sequences
and given a $\lambda$ we already constructed using all previously constructed ordinals (which the ordering is determined by ultimately how many successions and cartesian product is being used,
and since at every step the definition of succession as the union $\alpha \cup \{\alpha\}$ should define an embedding $g : \alpha \mapsto \alpha \cup \{\alpha\} by g(\alpha)=\alpha$, and every cartesian product should also define an embedding $h : \prod_{k=1}^n a_k \mapsto \prod_{k=1}^{n+1} a_k$)
04:16
1 hour later…
05:21
$\forall \alpha \in \Bbb{On}, n \in \Bbb{N}, \alpha^n := \prod_{k=1}^n \alpha = (\alpha,\alpha,\alpha,\dots,\alpha)$
$\forall S[|S|=\aleph_0] \land \forall \alpha \in S \subsetneq \Bbb{On} : \lambda :=\sup (n < \omega : S[n]) \in \Bbb{On}$
where $S$ is a woset and $S[n]$ is its nth element (Thus $S$ is a fundamental sequence of $\lambda$)
$\forall \alpha \in \Bbb{On}, n \in \Bbb{N}, \alpha^n := \prod_{k=1}^n \alpha = (\alpha,\alpha,\alpha,\dots,\alpha) \in \Bbb{On}$
$\forall S[|S|=\aleph_0] \land \forall \alpha \in S \subsetneq \Bbb{On} : \lambda :=\sup (n < \omega : S[n]) \in \Bbb{On}$
where $S$ is a woset and $S[n]$ is its nth element (Thus $S$ is a fundamental sequence of $\lambda$)
$g_1 : \alpha \mapsto \alpha \cup \{\alpha\}$ is defined for all $\alpha$ that is constructed from what is already available, by $\forall \beta \in \alpha : g_1(\beta) = \beta$. Thus, $g_1$ injects into $\alpha^+$ from $\alpha$ while it is not surjective because the preimage $g_1^{\leftarrow}(\alpha) = \varnothing$
$g_1 : \alpha \mapsto \alpha \cup \{\alpha\}$ is defined for all $\alpha$ that is constructed from what is already available, by $\forall \beta \in \alpha : g_1(\beta) = \beta$. Thus, $g_1$ injects into $\alpha^+$ from $\alpha$ while it is not surjective because the preimage $g_1^{\leftarrow}(\alpha) = \varnothing$
$g_2 : \prod_{k=1}^n \alpha \mapsto \prod_{k=1}^{n+1} \alpha$ is defined for all $\alpha$ that is constructed from what is already available, by the elementwise pairing of elements in tuples i.e. $\forall k < n, g_2(\alpha^k) = \alpha^k$. Thus, $g_2$ injects into $\prod_{k=1}^{n+1} \alpha$ from $\prod_{k=1}^{n} \alpha$ while it is not surjective because the preimage $g_1^{\leftarrow}(\alpha^{n+1}) = \varnothing$
Alternately, $g_2$ can be defined as the elementwise pairing of tuples i.e. Let $\alpha_k$ be the kth element in the tuple $\prod_{k=1}^n \alpha$. Then $\forall k < n : g_2(\alpha_k) = \alpha_k$
06:16
Now for each $m < \omega$, $g_3 : \bigcup_{k=1}^m S[k] \mapsto \bigcup_{n < \omega} S[n]$ is given by $\forall k < g_3 (\bigcup_{k=1}^m S[k]) =S[m]$. We can see that the maps $g_3$ are injective. However it is not surjective since $g_3^{\leftarrow}(S)=g_3^{\leftarrow}(\bigcup_{n < \omega} S[n])=\varnothing$
$\lambda = \sup (n < \omega : S[n]) = \bigcup_{n < \omega} S[n]$, $S[n]$ are the ordinals in $S$ from the collection constructed so far and with ordering unambiguously determined by $g_1$ and $g_2$ for each pair of ordinals thus $S$ is well ordered/ a woset. Therefore $\lambda$ is a well ordering.
Now for each $m < \omega$, $g_3 : \bigcup_{k=1}^m S[k] \mapsto \bigcup_{n < \omega} S[n]$ is given by $\forall k < g_3 (\bigcup_{k=1}^m S[k]) =S[m]$. We can see that the maps $g_3$ are injective. However it is not surjective since $g_3^{\leftarrow}(\lambda)=g_3^{\leftarrow}(\bigcup_{n < \omega} S[n])=\varnothing$
Therefore $\lambda$ represents an element strictly greater than all elements in $S$ for all $S$ in the collection constructed so far
However, from the above, we also started to see the self referential nature of some limit ordinals. To illustrate, let's begin at $0=\varnothing$
Using succession n times, we constructed $\beta=\{0,1,2,3,4,...,n\}$. By the embedding $g_1$, $\beta$ is indeed well ordered
Suppose we want something bigger. Using the definition of ordinal arithmetic as listed earlier, it seemed sensible to pick out many $\beta$ and form a set (this is always possible without choice since such set has only finitely many elements. We can also start again by picking more $\beta$ or pick every 2nd $\beta$ and so on. But note how no matter how you pick the $\beta$ to try to form a set $S$, it is always finite, which means it will biject to some $\beta$ that is already there.
Now let's turn our attention to the definition of the supremum of ordinals via fundamental sequences:
$$\forall S[|S|=\aleph_0] \land \forall \alpha \in S \subsetneq \Bbb{On} : \lambda :=\sup (n < \omega : S[n]) \in \Bbb{On}$$
$$\forall S[|S|=\aleph_0] \land \forall \alpha \in S \subsetneq \Bbb{On} : \lambda :=\sup (n < \omega : S[n]) \in \Bbb{On}$$
In our context, $S$ is the set we tried to construct. Note the presence of $\omega$ in the definition, which is precisely the ordinal we tried to construct. Therefore, without the axiom of infinity, we can only ever get finite ordinals and the existence of infinite well orderings and infinite ordinals will be unprovable. In particular, in such subtheory of ZF, the lack of $\omega$ means $\Bbb{On}$ will look something like this:
Now, we have the existence of an infinite set, and in particular inductive sets like $\Bbb{N}$ and $\omega$. Since $\omega$, defined by the axiom of infinity (and then extracted from some inductive set by taking the interactions of all possible inductive sets), contains all finite naturals and hence all finite ordinals, it follows by axiom of infinity, $\omega$ is indeed the supremum of all finite ordinals.
Now we want to get some ordinal higher than $\omega +n$ for any $n$. Obviously, the first step is to consider the supremum operation. However, we now ran into trouble:
While we can pick any finite number of ordinals and arrange them in increasing order defined by $g_1$ and the fact that $\omega > n$ for finite $n$, we cannot pick countably many ordinals because we never have finished the succession process and thus for any step, there's always some finite $m$ such that $\omega + m$ is the maximum element we have in our growing collection of ordinals being constructed, which means
we never can obtain a countable sequence from what we have constructed so far without the axiom of specification
Now we might wonder what about cartesian products? Unfortunately, as Kripke–Platek set theory showed us (which is a fragment of ZF), without axiom of replacement, we cannot define it, so we are stuck
Now, with replacement, we have functions that takes a given set $X$ to produce a new set that is smaller than or equinumerous as $X$
Since this whole ordinal essay has predicativity in mind, despite the focus is constructivity, we are not allowed to pick any functions that are not reinfiable. That is the functions $f$ we are allowed to pick here are those that can be specified by an algorithm or program expressed as a string using only the objects and operations we have defined and constructed so far (we will soon see how this restriction prevent us from reaching $\omega_1^{CK}$ soon)
Now, using replacement with the algorithm $\forall n < \omega : f(\omega)=\omega + n$ we are now able to obtain the required countable sequence $\{\omega + n\}$, which then allow us to plug into the supremum operator to construct $\omega 2$, which is bigger than anything we have constructed so far by checking with $g_3$.
With axiom of replacement, cartesian products now exists. We can now construct $\omega n$ for finite $n$ either by literatiely using succession followed by replacement to generate the sets required to compute the supremum, or we can define $\omega n$ as the ordered pair $(\omega,n) = \omega \times n$
07:32
Now this combination of succession, multiplication, and supremum can be iterated forever to generate higher and more complex ordinals such as $\epsilon_n, \zeta_0, \phi(n,0), \Gamma_0, \phi \binom{\alpha}{1}, LVO=\psi (\Omega^{\Omega^{\Omega}}), BHO=\psi (\epsilon_{\Omega+1}), \psi_n(0), \psi'(0), ...$
where predicatively, $\Omega$ can be considered as not an ordinal, but a symbol that determines the number of times some ordinal notation get stuck and need to be extended. More accurately, $\Omega$, ordered in a similar manner like the ordinals all the way to $\Omega^{\Omega^{\Omega^{⋰}}}< \epsilon_{\Omega+1}$ count the number of fixed point mappings (which are themselves recursive functions) that is being introduced into the language based on the existing constructions)
We also knew that any ordinal notation can be abstractly represented in Kleene's O notation, therefore nothing new is being introduced in the definition of the OCF functions $\psi,\psi_n,\psi'$
Now, using replacement with suitable increasing functions in terms of an algorithm (thus such function can always be represented in terms of Kleene's O notation (???)), we can get a countable sequence of computable ordinals in increasing order checked by the embeddings $g_1,g_2,g_3$
It is clear that there is no end to this process. Since every supremum of a countable sequence of computable ordinals already being constructed is going to be some computable ordinal higher up (because its fundamental sequence $S[n]$ consists of computable ordinals, hence the supremum is also a computable procedure)
So regardless of which step we decided to stop, we always have a countable sequence of computable ordinals in our constructed collection and such procedure can be iterated indefinitely. Now here's where our requirement for the functions to be reinfiable is important:
Since at any step after countable applications of replacement, cartesian products and succession, we always end up with a computer ordinal that can be used to construct an even larger computable ordinal, it follows this collection will never be complete. Therefore, if we assume we have an algorithm $f$ that pick out all computable ordinals in order (which is countable because we only have a finite language in ordinal notations)
, we are assuming we already have all the computable ordinals as a set (which we don't because the procedure can go forever even by using supremums, cartesian products and succession of ordinals that already existed so far). Therefore such $f$ can never be proved to be a total function, which means it is unprovable whether an algorithm exists to pick out all computable ordinals.
and therefore the Church Kleene Ordinal $\omega_1^{CK}$ in a sense, cannot be proved to exist as it is unprovable whether the collection of all computable ordinals is a set
(since supremum only guarentee given an increasing countable sequence of ordinals, the union of them all is an ordinal and a set that does not inject into any of the ordinals in the sequence, but the collection of all computable ordinals is much larger than any
supremum can capture (since any supremum of a set of computable ordinals already constructed is still a larger computable ordinal, and this process of supremum and ordinal arithmetic can repeat indefinitely and never generate any ordinal that is not computable))
Therefore we have reach the limit of a predicative $\Bbb{On}$ for the default $ZF$ theory (which I have nuked the powerset axiom for reason to become clear later), which look like this:
We now learnt from an ordinal arithmetic perspective, $\omega_1^{CK}$ is in fact the first ordinal inaccessible by succession, cartesian product and supremum from any computable ordinals. This is why we cannot find a fundamental sequence for it
@LeakyNun @user21820 @SimplyBeautifulArt The above summarise my understanding about the ordinals so far. I am not terribly sure I have got the predicative arguments right. All functions used in the above essay should all be computable and hence should be predicative. But I think everything here should be constructible
For simpleart, I suspect $\Omega$ can be make predicative by being a shorthand for the collapse algorithm that comes with the definition of OCFs
For simpleart, I suspect $\Omega$ can be make predicative by being a shorthand for the collapse algorithm that comes with the definition of OCFs
Put it simply, I think the issue is that given a set of computable ordinals that we have constructed at any stage, since the supremum is also a computable ordinal because the procedure will terminate (replacement on $\omega$ using some algorithm, and then take the supremum) and that we can repeat this forever and still getting computable ordinals,
there is nothing to suggest to us that (at least within the default theory of ZF) there exists an uncomputable ordinal that will bound all computable ordinals
08:42
If we want to go further, we need to introduce some notion of hyper computation such as an infinite time turing machine, or an oracle. For finite $n$ number of oracles, it can get us as far as $\omega_n^{CK}$ for some finite $n$
09:20
> There exists a smallest ordinal that is not a successor ordinal inaccessible from any supremum of ordinals smaller than it
We can then go up the admissible ordinals and their limits by instead having the following axiom schema:
> For every set of ordinals, there exists a smallest ordinal that is not a successor ordinal, and inaccessible from any supremum of ordinals smaller than it
It does, however provide a way to define the admissible ordinals without any reference to computability
$$\Bbb{On}^{\text{ZF-P+sup inaccessible ordinals}} = \Bbb{On}^{\text{Constructive(?)}} = \Bbb{On} \cap [0,\omega_1 )$$
> For every ordinal, there exists a smallest ordinal inaccessible from countably many iteration of the following: iterated constructions of fundamental sequences and application of the Axiom of the existence of smallest supremum inaccessible ordinals.
10:44
Let E,Reg,U,R,I,P,C be the axioms: Extensionality, Regularity, Union, Replacement, Infinity, Powerset, Choice.
\begin{align}
\Bbb{On}^{\text{ZF-E}} & = \text{I have no idea}\\
\Bbb{On}^{\text{ZF-Reg}} & = 0\\
\Bbb{On}^{\text{ZF-U}} & = \{0,1,2\}\\
\Bbb{On}^{\text{ZF-R-I-P}} & = \Bbb{On} \cap [0,\omega)\\
\Bbb{On}^{\text{ZF-I-P}} & = \Bbb{On} \cap [0,\omega 2 )\\
\Bbb{On}^{\text{ZF-P-2nd order definitions}} & = \Bbb{On}^{\text{Predicative}} = \Bbb{On} \cap [0,\Gamma_0 )\\
\Bbb{On}^{\text{ZF-P}} & = \Bbb{On}^{\text{Predicative}} = \Bbb{On} \cap [0,\omega_1^{CK} )\\
\begin{align}
\Bbb{On}^{\text{ZF-E}} & = \text{I have no idea}\\
\Bbb{On}^{\text{ZF-Reg}} & = 0\\
\Bbb{On}^{\text{ZF-U}} & = \{0,1,2\}\\
\Bbb{On}^{\text{ZF-R-I-P}} & = \Bbb{On} \cap [0,\omega)\\
\Bbb{On}^{\text{ZF-I-P}} & = \Bbb{On} \cap [0,\omega 2 )\\
\Bbb{On}^{\text{ZF-P-2nd order definitions}} & = \Bbb{On}^{\text{Predicative}} = \Bbb{On} \cap [0,\Gamma_0 )\\
\Bbb{On}^{\text{ZF-P}} & = \Bbb{On}^{\text{Predicative}} = \Bbb{On} \cap [0,\omega_1^{CK} )\\
$0$ is the smallest ordinal, and the well ordering represented by it is the only one that does not depend on anything except uniqueness
$\omega$ is the first limit ordinal, the first transfinite ordinal, and also the first ordinal inaccessible from below using succession
$\omega 2$ is the first ordinal requiring a supremum to reach ($\omega$ does not count because countable supremum is undefined without the existence of $\omega$ or any infinite inductive set)
$\omega_1^{CK}$ is the first uncomputable ordinal, and also the first ordinal unreachable by supremum and ordinal arithmetic from below. It cannot exists without some axiom to insert it into the system. It is also the first impredicative ordinal
$\Sigma$ is the supremum of all accidentally writable ordinals by an infinite time turing machine (ITTM), which is an admissible ordinal larger than $\omega_n^{CK}$ since those are clockable ordinals (i.e. output after termination at the step$\omega_n^{CK}$ in an ITTM)
$\omega_1$ is the first ordinal not reachable from any countable iteration of creating larger limit ordinals via supremum and the existence of admissible ordinals
$\omega_{\lambda}$ the aleph fixed point, is the first ordinal unreachable from a supremum of any aleph cardinality
Also typo, the final line should be a union, not an intersection since ZF ordinals are often taken without assuming the existence of inaccessible cardinals
Let $S$ be the set valued function $\alpha \mapsto \{\alpha+1,f(\alpha+1),f^2(\alpha+1),...\}$ where $f$ is an algorithm consists of all ordinals $< \alpha$, finitely many cartesian products and successions (i.e. any computable increasing function on the ordinals)
$\forall \alpha \in \text{Computable}, \sup (\alpha+1,\alpha 2, \alpha^2, ...) < \omega_1^{CK}$ (Exists via oracles, ITTM or axiom of inaccessible by supremum ordinals)
11:29
In conclusion: both $\omega_1^{CK}$ and $\omega_1$ are impredicative and they can only be made constructive by manually inserting some axioms to form some models of ZF
in Mathematics, 6 mins ago, by Secret
It also does not help that I am actually procrastinating from writing the final data analysis code for my PhD, which is why I am too guilty to be able to spend time reading the logic textbook called forallx
I think I have rambled and obssessed enough about $\omega_1$ to the point of spending a whole week on it (and annoying everyone else who have to listen to my babbles). Time to really get back to chemistry so that I can do the data analysis and remove the only guilt and obstacle for me to finish forallx
4 hours later…
15:27
If I have a set containing containing propositional variables, say a,b,c, but also contains prop. variables with a super/subscript, say j_a, j_b, j_c, how can I quantify this set using the ∀ and select only the variables that don't have subscript, without explicitly checking whether or not its one of those variables using disjunction.
6 mins ago, by Sektor
@user21820 I do get your point -- that's for me to say, not you. You just add snarky remark at the end of your example ;)
@Sektor I created this room with the express purpose of allowing discussion about (mathematical) logic. Your inquiry was not about logic, because it was not a well-formed question. I attempted to prod you to make your question well-formed, by giving an explicit example of a question in the same vein as yours (from the logical point of view).
in Mathematics, Oct 24 at 17:43, by Semiclassical
Not everything you find annoying needs moderator intervention
17:26
yesterday, by vzn
← admittedly guilty of the heinous crime of vague implications, offers up profuse remorse, awaits extreme sentencing
Anonymous
« first day (225 days earlier) ← previous day next day → last day (332 days later) »
