Arbre (teoria de conjunts)

Archiu:Infinite set-theoretic tree.png

Una branca (resaltada en vert) d'un arbre teòric de conjunts. Els punts representen elements, les fleches representen la relació d'orde i les elipses i fleches discontínues representen elements i relacions no representats.

En teoria de conjunts, un arbre (A, ${<}_r$) és un conjunt parcialment ordenat constituït per una série d'elements i una relació d'orde parcial transitiva, ${<}_r$, definida sobre A, de tal modo que, per a cada q ∈ A, el conjunt de predecessors de q en A, $\{p\in A:p{<}_{r}q\}$, està ben ordenat. Els elements d'un arbre A solen denominar-se nodos.

Archiu:Finite set-theoretic trees.png

Eixemples finitos: Els tres conjunts parcialment ordenats de l'esquerra són arbres (en blau); una branca d'un dels arbres està resaltada (en vert). El conjunt parcialment ordenat de la dreta (en roig) no és un arbre perque x₁ < x₃ i x₂ < x₃, pero x₁ no és comparable x₂ (llínea discontínua taronja).

Típicament, s'assumix que els arbres tenen un sol element mínim, al que se li denomina raïl o nodo raïl. Els arbres en una sola raïl poden considerar-se arbres arbre (teoria de grafos) o com un grafo trivialmente perfecte. En el primer cas, el grafo és el diagrama de Hasse no dirigit del conjunt parcialment ordenat. En el segon cas, el grafo és simplement el grafo subjacent (no dirigit) del conjunt parcialment ordenat.

Una branca de l'arbre és una cadena màxima en l'arbre (és dir, un subconjunt tal que dos elements de la branca són comparables, i qualsevol element de l'arbre no contingut en la branca és incomparable en, a lo manco, un element de la branca).

Vore també

• Arbre (teoria de grafos)
• Arbre (programació)

Referències

• Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs, North-Holland. ISBN 0-444-85401-0. Capítul 2, Secció 5.