Category of infinite ordinals

Logica matematica, teoria degli insiemi, algebre di Boole e di Heyting ...

Moderatore: Moderatori

Category of infinite ordinals

Messaggioda Feanor il dom 1 mag 2016, 12:14

Let $\kappa$ be an infinite regular ordinal. Define $\Delta_\kappa$ to be the category of ordinals strictly smaller than $\kappa$ (i.e. the ordinals which are elements of $\kappa$, in von Neumann definition), with order-preserving maps as morphisms.

Question. Suppose $f\colon \alpha \to \beta$ is a monomorphism (resp. an epimorphism) of $\Delta_\kappa$. Is it true that necessarily $\alpha \leqslant \beta$ (resp. $\alpha \geqslant \beta$)?

Remark. It's easy to prove that monomorphisms are precisely injective order-preserving maps (resp. epimorphisms are precisely surjective oder-preserving maps), so let's assume that.
Feanor
 
Messaggi: 734
Iscritto il: lun 29 set 2008, 20:58

Re: Category of infinite ordinals

Messaggioda ineff il mar 27 giu 2017, 14:57

Let start by proving the first part of the question:
Suppose f \colon \alpha \to \beta is a monomorphism of $\Delta_k$ then $\alpha \leq \beta$.


We know that $f$ is injective and order preserving, by that it is easy to prove the claim: let \gamma be the greater ordinal between \alpha and \beta, clearly we have the two inclusion \alpha \hookrightarrow \gamma and \beta \hookrightarrow \gamma, so we can extend f to a map f' \colon \alpha \to \gamma (by composing f with the embedding of \beta in \gamma).

Clearly f' is still monotone and injective, being the composition of two monotone and injective morphisms, and by construction we know that \alpha \leq \gamma,
that is \alpha is an initial segment of \gamma.

We have to prove that for each \alpha&#39; \in \alpha (i.e. for each \alpha&#39; < \alpha) we have that f&#39;(\alpha&#39;) \geq \alpha&#39;.
We proceed by transfinite induction.

For \alpha&#39;=0 the claim is trivally true: f&#39;(0) \geq 0 because every ordinal is great or equal to 0.

Let assume that for every \alpha&#39;&#39; < \alpha&#39; \in \alpha we have that f&#39;(\alpha&#39;&#39;) \geq \alpha&#39;&#39;. Then we have that for each \alpha&#39;&#39;< \alpha&#39;

    f&#39;(\alpha&#39;) > f&#39;(\alpha&#39;&#39;) \geq \alpha&#39;&#39;
because of the monotonicity of f&#39; and the inductive hypothesis.

Now we distinguish between two cases:

  • if \alpha&#39;=\alpha&#39;&#39;+1 then we have that f&#39;(\alpha&#39;) > f&#39;(\alpha&#39;&#39;) \geq \alpha&#39;&#39; and so f&#39;(\alpha&#39;) \geq \alpha&#39;&#39;+1=\alpha&#39;
  • if \alpha&#39; is a limit ordinal then f&#39;(\alpha&#39;) > \alpha&#39;&#39; for each \alpha&#39;&#39; < \alpha&#39;, hence f&#39;(\alpha&#39;) \geq \sup\{\alpha&#39;&#39; \colon \alpha&#39;&#39; < \alpha&#39;\}=\alpha&#39;
whatever the case we always end up having f(\alpha&#39;) \geq \alpha&#39;, as we wished to prove.

By transfinite induction it follows that f&#39;(\alpha&#39;) \geq \alpha&#39; for every \alpha&#39; \in \alpha.
Since f&#39; has image contained in \beta this proves that for each \alpha&#39; \in \alpha we have that

    \alpha&#39; \leq f&#39;(\alpha&#39;) \in \beta
hence

    \alpha&#39; \in \beta
for each \alpha&#39; \in \alpha, that is \alpha \leq \beta and so by general fact of the ordinal \alpha \leq \beta.
Ultima modifica di ineff il mar 27 giu 2017, 16:15, modificato 1 volta in totale.
Con il giusto funtore si può risolvere ogni problema.
ineff
 
Messaggi: 186
Iscritto il: sab 17 apr 2010, 19:45

Re: Category of infinite ordinals

Messaggioda ineff il mar 27 giu 2017, 15:10

Now back to the second part of the question:

If f \colon \alpha \to \beta is an epimorphism in \Delta_k then \alpha \geq \beta.


By hypothesis f is an epimorphism, hence surjective and monotone. In particular this implies that for every \gamma_1,\gamma_2 \in \beta and every \alpha_1,\alpha_2 \in \alpha such that

  • \gamma_1 < \gamma_2
  • f(\alpha_1)=\gamma_1
  • f(\alpha_2)=\gamma_2
we have that \alpha_1 < \alpha_2: clearly \alpha_1 and \alpha_2 have to be different having different images via f, and if by absurd \alpha_2 < \alpha_1 this would imply that

    \gamma_2=f(\alpha_2) \geq f(\alpha_1) =\gamma_1
against the hypothesis that \gamma_1 < \gamma_2.

So we can consider the family of disjoint sets (f^{-1}(\{\gamma\}))_{\gamma \in \beta}, whose elements are not empty sets since f is surjective by hypothesis.
By axioms of choice we get a mapping

    g \colon \beta \to \bigcup_{\gamma \in \beta} f^{-1}(\{\gamma\}) \subseteq \alpha
such that for every \gamma \in \beta we have g(\gamma) \in f^{-1}(\{\gamma\}).

Whenever \gamma_1 < \gamma_2 we have f(g(\gamma_1))=\gamma_1 and f(g(\gamma_2))=\gamma_2 and so, by the previous remark, it follows that g(\gamma_1) < g(\gamma_2).

This implies that g \colon \beta \to \alpha is a strictly monotone map, i.e. a monomorphism, that by question 1 implies that \beta \leq \alpha.
Con il giusto funtore si può risolvere ogni problema.
ineff
 
Messaggi: 186
Iscritto il: sab 17 apr 2010, 19:45


Torna a Logica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite