A hierarchy of chains is a transfinite sequence of linear orderings such that each chain in the sequence order-embeds into all chains following it but not in those preceding it. We construct a $c^+$-long hierarchy of chains that order-embed into the lexicographic power $(R^ω,>_\lex)$. Each linear ordering L in this hierarchy is such that there exists a tree representation of L, which is an R-branching tree with no infinite branches. The existence of such a hierarchy sheds some light on the hidden complexity of $(R^ω,>_\lex)$.

A hierarchy of chains embeddable into the lexicographic power $R^\omega_\lex$

GIARLOTTA, Alfio;
2013-01-01

Abstract

A hierarchy of chains is a transfinite sequence of linear orderings such that each chain in the sequence order-embeds into all chains following it but not in those preceding it. We construct a $c^+$-long hierarchy of chains that order-embed into the lexicographic power $(R^ω,>_\lex)$. Each linear ordering L in this hierarchy is such that there exists a tree representation of L, which is an R-branching tree with no infinite branches. The existence of such a hierarchy sheds some light on the hidden complexity of $(R^ω,>_\lex)$.
2013
Lexicographic ordering; Representability number; Utility representation; Hierarchy of chains
File in questo prodotto:
File Dimensione Formato  
hierarchy_order_2013.pdf

solo gestori archivio

Licenza: Non specificato
Dimensione 544.08 kB
Formato Adobe PDF
544.08 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/11792
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact