Xem mã nguồn của Tập có hướng

{{Short description|SẮp xếp trong toán học khi có cận trên}}
Trong [[toán học]], '''tập có hướng''' (hay '''tiền thứ tự có hướng''' hay '''tập bị lọc''' và đôi khi '''tập được định hướng''') là một [[tập hợp (toán học)|tập hợp]] khác rỗng <math>A</math> kèm theo một [[quan hệ hai ngôi]] có tính [[quan hệ bắc cầu|bắc cầu]] và [[quan hệ phản xạ|phản xạ]] <math>\,\leq\,</math> (tức là [[tiền thứ tự]]), và kèm theo một tính chất khác là mọi cặp phần tử phải có [[cận trên]].<ref>Kelley, p. 65.</ref> Nói cách khác, cho bất kỳ <math>a</math> và <math>b</math> thuộc <math>A</math> thì phải tồn tại <math>c</math> thuộc <math>A</math> sao cho <math>a \leq c</math> và <math>b \leq c.</math> Tiền thứ tự của tập có hướng được gọi là '''hướng''' của tập hợp đó.

Khái niệm trên đôi được gọi trên là '''{{visible anchor|tập hướng lên}}'''. '''{{visible anchor|Tập hướng xuống}}''' được định nghĩa tương tự như vậy,<ref>{{chú thích sách|author=Robert S. Borden|title=A Course in Advanced Calculus|year=1988|publisher=Courier Corporation|isbn=978-0-486-15038-3|page=20}}</ref>, nghĩa là mọi cặp phần tử đều có cận dưới.<ref name="Brown-Pearcy">{{chú thích sách|author1=Arlen Brown|author2=Carl Pearcy|title=An Introduction to Analysis|url=https://archive.org/details/introductiontoan0000brow|url-access=registration|year=1995|publisher=Springer|isbn=978-1-4612-0787-0|page=[https://archive.org/details/introductiontoan0000brow/page/13 13]}}</ref> 
Một số tác giả (và ngay cả bài viết này) sẽ giả định trước rằng tập có hướng sẽ hướng lên, trừ phi nhắc trước trong bài. Một số tác giả khác gọi một tập là tập có hướng khi nó vừa hướng lên vừa hướng xuống.<ref name="CarlHeikkilä2010">{{chú thích sách|author1=Siegfried Carl|author2=Seppo Heikkilä|title=Fixed Point Theory in Ordered Sets and Applications: From Differential and Integral Equations to Game Theory|year=2010|publisher=Springer|isbn=978-1-4419-7585-0|pages=77}}</ref>

Tập có hướng là dạng tổng quát của các [[tập hợp sắp thứ tự toàn phần]] khác rỗng. Do vậy, mọi tập sắp thứ tự toàn phần là tập có hướng (trái ngược với đó. các [[tập hợp sắp thứ tự riêng phần]] không nhất thiết phải có hướng. [[Nửa dàn có nối]] (và cũng là tập sắp thứ tự riêng phần) cũng là tập có hướng, nhưng không phải ngược lại. Tương tự như vậy, [[dàn (lý thuyết thứ tự)|dàn]] là các tập có hướng lên vừa hướng lên vừa hướng xuống.

Trong [[tô pô]], các tập có hướng được dùng định nghĩa [[lưới (tô pô)|lưới]], lưới được dùng để dùng tể tổng quát hoá cho khái niệm [[dãy số]] và nhiều khác niệm khác của [[giới hạn (toán học)|giới hạn]] được dùng trong [[giải tích toán học|giải tích]]. Bên cạnh đó, từ tập có hướng còn sinh ra khái niệm [[giới hạn trực tiếp]] trong [[đại số trừu tượng]] và tổng quát hơn là trong [[lý thuyết phạm trù]].

==Định nghĩa tương đương==

Bên cạnh định nghĩa ở trên, có một định nghĩa khác tương đương như sau: '''Tập có hướng''' là tập hợp <math>A</math> đi kèm [[tiền thứ tự]] sao cho mọi tập con hữu hạn của <math>A</math> bị chặn trên. Trong định nghĩa này, sự tồn tại của cận trên của [[Tập rỗng|tập con rỗng]] sẽ suy ra <math>A</math> khác rỗng.

==Ví dụ==

Tập hợp các [[số tự nhiên]] <math>\N</math> đi kèm thứ tự thông thường <math>\,\leq\,</math> là một trong những ví dụ quan trọng về tập có hướng (và cũng về [[tập hợp sắp thứ tự toàn phần]]). Theo định nghĩa, {{em|[[Lưới (toán học)|lưới]]}} là một hàm số từ tập có hướng đi từ tập có hướng, còn [[Dãy (toán học)|dãy số]] là hàm từ tập các số tựn hiên <math>\N.</math> Mỗi dãy số đều chính tắc trở thành một lưới bằng cách đi kèm với <math>\N</math> thêm quan hệ <math>\,\leq.\,</math> 

Một ví dụ dễ gặp về tập sắp thứ tự riêng phần nhưng '''{{em|không}}''' có hướng là tập <math>\{a, b\},</math> cùng với hai quan hệ thứ tự duy nhất <math>a \leq a</math> và <math>b \leq b.</math>

Nếu <math>x_0</math> là một [[số thực]] nào đó thì tập hợp <math>I := \R \backslash \lbrace x_0 \rbrace</math> có thể biến đổi thành tập có hướng bằng cách định nghĩa <math>a \leq_I b</math> if <math>\left|a - x_0\right| \geq \left|b - x_0\right|</math> (để các số "lớn hơn" sẽ gần hơn với <math>x_0</math>). Khi đó ta nói rằng các số thực đang '''hướng về <math>x_0.</math>''' Đây là ví dụ về một tập có hướng nhưng {{em|không}} sắp [[poset|thứ tự riêng phần]] hay [[loset|toàn phần]]. Lý do nó như vậy là bởi vì [[quan hệ phản đối xứng|tính phản đối xứng]] không còn đúng cho mọi cặp <math>a</math> và <math>b</math> có cùng khoảng cách với <math>x_0,</math> và <math>a</math> và <math>b</math> ở hai bên của <math>x_0.</math> Cụ thể, nó xảy ra khi <math>\{a, b\} = \left\{x_0 - r, x_0 + r\right\}</math> cho một số thực <math>r \neq 0,</math> Khi đó sẽ có <math>a \leq_I b</math> và <math>b \leq_I a</math> mặc dù <math>a \neq b.</math> Nếu tiền thứ tự này được định nghĩa ngay trên <math>\R</math> thay vì <math>\R \backslash \lbrace x_0 \rbrace</math> thì nó vẫn sẽ lập thành tập có hướng nhưng đồng thời nó sẽ có phần tử lớn nhất (duy nhất) chính là <math>x_0</math>; tuy nhiên, kể cả vậy nó vẫn sẽ không phải là tập sắp thứ tự toàn phần. Ví dụ này có thể tổng quát hoá cho [[không gian mêtric]] <math>(X, d)</math> bằng cách định nghĩa trên <math>X</math> hay <math>X \setminus \left\{x_0\right\}</math> tiền thứ tự <math>a \leq b</math> khi và chỉ khi <math>d\left(a, x_0\right) \geq d\left(b, x_0\right).</math>

Sử dụng ví dụ "các số thực hướng về <math>x_0</math>" ở trước nhưng đổi sao cho luật sắp xếp chỉ áp dụng với các cặp phần tử ở cùng một bên của <math>x_0</math> thì tập đó sẽ không có hướng nữa (bởi vì, nếu ta lấy  <math>a</math> ở bên trái của <math>x_0,</math> và <math>b</math> ở bên phải, thì <math>a</math> và <math>b</math> [[tính so sánh được|không so sánh được với nhau]], và do vậy, tập con <math>\{ a, b \}</math> không có cận trên).

===Phần tử tối đại và phần tử lớn nhất===

Phần tử <math>m</math> của tập sắp tiền thứ tự <math>(I, \leq)</math> là ''[[Phần tử tối đại và tối tiểu|phần tử tối đại]]'' nếu cho mọi <math>j \in I,</math> <math>m \leq j</math> suy ra <math>j \leq m.</math><ref>Tư đây sẽ suy ra <math>j = m</math> nếu <math>(I, \leq)</math> [[tập hợp sắp thứ tự riêng phần]].</ref>
Nó là ''[[Phần tử lớn nhất và nhỏ nhất|phần tử lớn nhất]]'' nếu với mọi <math>j \in I,</math> <math>j \leq m.</math>

Bất kỳ tập sắp tiền thứ tự đi cùng với một phần tử lớn nhất đều là tập có hướng với cùng tiền thứ tự đó.
Ví dụ chẳng hạn, trong [[poset]] <math>P,</math> mọi [[Tập trên#Bao đóng trên và dưới|Bao đóng dưới]] của một phần tử (bao đóng dưới là các tập con có dạng <math>\{a \in P : a \leq x\}</math> trong <math>x</math> là phần tử cố định được cho trước từ <math>P,</math>) là tập có hướng. 

Mọi phần tử tối đại của tập sắp tiền thứ tự có hướng đều sẽ lớn nhất.  Thật vậy, tập sắp tiền thứ tự có hướng có đặc trưng là tập các phần tử tối đại (có thể rỗng) và tập các phần tử lớn nhất bằng với nhau,

===Tích của các tập có hướng===

Gọi <math>\mathbb{D}_1</math> và <math>\mathbb{D}_2</math> là hai tập có hướng. Khi đó, [[tích Descartes]] của chúng <math>\mathbb{D}_1 \times \mathbb{D}_2</math> có thể biến thành tập có hướng bằng cách định nghĩa <math>\left(n_1, n_2\right) \leq \left(m_1, m_2\right)</math> khi và chỉ khi <math>n_1 \leq m_1</math> và <math>n_2 \leq m_2.</math> Tương tự với [[thứ tự tích]], đây là hướng tích của tích Descartes. Ví dụ chẳng hạn, tập hợp <math>\N \times \N</math> của các cặp số tự nhiên có thể biến thành tập có hướng bằng cách định nghĩa thêm quan hệ <math>\left(n_0, n_1\right) \leq \left(m_0, m_1\right)</math> khi và chỉ khi <math>n_0 \leq m_0</math> and <math>n_1 \leq m_1.</math>

===Bao hàm tập hợp===

Quan hệ [[bao hàm tập hợp]] <math>\,\subseteq,\,</math> cùng với [[Đối ngẫu (lý thuyết thứ tự)|đối ngẫu]] của nó <math>\,\supseteq,\,</math> định nghĩa [[thứ tự riêng phần]] trên bất kỳ [[họ tập hợp|họ các tập hợp]]. Họ khác rỗng của các tập hợp là tập có hướng tương ứng thứ tự riêng phần (hoặc ngược lại <math>\,\subseteq\,</math>) khi và chỉ khi phần giao (ngược lại là phần hợp) của bất kỳ hai trong số chúng chứa (ngược lại, là tập con của) một phần tử thứ ba nào đó. Viết dưới ký hiệu họ <math>I</math> của các tập hợp là tập có hướng theo quan hệ <math>\,\supseteq\,</math> (hoặc, <math>\,\subseteq\,</math>) khi và chỉ khi 
:với mọi <math>A, B \in I,</math> tồn tại một số <math>C \in I</math> sao cho <math>A \supseteq C</math> và <math>B \supseteq C</math> (ngược lại, <math>A \subseteq C</math> và <math>B \subseteq C</math>) 
hoặc tương đương, 
:với mọi <math>A, B \in I,</math> tồn tại một số <math>C \in I</math> sao cho <math>A \cap B \supseteq C</math> (ngược lại, <math>A \cap B \subseteq C</math>).

Nhiều ví dụ quan trọng của tập có hướng có thể định nghĩa bằng cách sử dụng các thứ tự riêng phần. Ví dụ chẳng hạn, theo định nghĩa, [[bộ lọc (lý thuyết thứ tự)|{{em|tiền bộ lọc}}]] hay {{em|cơ sở lọc}} là [[họ tập hợp]] khác rỗng và là tập có hướng tương ứng với [[thứ tự riêng phần]] <math>\,\supseteq\,</math> và bên cạnh đó cũng không chứa tập rỗng (điều kiện này ngăn chặn tính tầm thường, bởi nếu kèm vào thì tập rỗng sẽ trở thành [[phần tử lớn nhất và phần tử nhỏ nhất]] tương ứng với <math>\,\supseteq\,</math>). 
Mọi [[Pi-hệ thống|{{pi}}-hệ thống]] ({{pi}}-hệ thống là học tập hợp khác rỗng đóng dưới phép giao bất kỳ hai phần tử trong tập hợp) là tập có hướng tương ứng <math>\,\supseteq\,.</math> Mọi [[Hệ Dynkin |λ-hệ thống]] (hay ''hệ thống λ) là tập có hướng tương ứng với <math>\,\subseteq\,.</math> Mọi [[bộ lọc (lý thuyết tập hợp)|bộ lọc]], [[Tô pô (cấu trúc)|tô pô]], và [[σ-đại số]] là tập có hướng tương ứng với <math>\,\supseteq\,</math> và <math>\,\subseteq\,.</math> 
Nếu <math>x_{\bull} = \left(x_i\right)_{i \in I}</math> là bất kỳ [[lưới (toán học)|lưới]] từ tập có hướng <math>(I, \leq)</math> thì cho bất kỳ chỉ số <math>i \in I,</math> tập hợp <math>x_{\geq i} := \left\{x_j : j \geq i \text{ với } j \in I\right\}</math> được gọi là đuôi của <math>(I, \leq)</math> bắt đầu từ <math>i.</math> Họ <math>\operatorname{Tails}\left(x_{\bull}\right) := \left\{x_{\geq i} : i \in I\right\}</math> của tất cả các đuôi là tập có hướng tương ứng với <math>\,\supseteq;\,</math> thậm chí, nó còn là tiền bộ lọc.

Nếu <math>T</math> là [[không gian tô pô]] và <math>x_0</math> là một điểm trong <math>T,</math> thì tập tất cả các [[lân cận tô pô|lân cận]] của <math>x_0</math> có thể biến đổi thành tập có hướng bằng cách viết <math>U \leq V</math> khi và chỉ khi <math>U</math> chứa <math>V.</math> Với mọi <math>U,</math> <math>V,</math> và <math>W</math>{{hairsp}}:
* <math>U \leq U</math> bởi <math>U</math> chứa chính nó.
* Nếu <math>U \leq V</math> và <math>V \leq W,</math> thì <math>U \supseteq V</math> và <math>V \supseteq W,</math> suy ra <math>U \supseteq W.</math> Do đó <math>U \leq W.</math>
* Bởi <math>x_0 \in U \cap V,</math> và vì đồng thời <math>U \supseteq U \cap V</math> và <math>V \supseteq U \cap V,</math> nên <math>U \leq U \cap V</math> và <math>V \leq U \cap V.</math>

Tập hợp <math>\operatorname{Finite}(I)</math> chứa tất cả tập con hữu hạn của tập <math>I</math> là tập có hướng tương ứng với <math>\,\subseteq\,</math> bởi cho bất kỳ hai <math>A, B \in \operatorname{Finite}(I),</math> hợp của chúng <math>A \cup B \in \operatorname{Finite}(I)</math> là cận trên của <math>A</math> trong <math>B</math> in <math>\operatorname{Finite}(I).</math> Tập có hướng này được dùng để định nghĩa tổng <math>{\textstyle\sum\limits_{i \in I}} r_i</math> của [[Chuỗi đã tổng quát (toán học)|chuỗi đã tổng quát]] của họ đánh chỉ số <math>I</math> của các số <math>\left(r_i\right)_{i \in I}</math> (hoặc tổng quát hơn là, tổng của [[Chuỗi (toán học)#Nhóm tô pô giao hoán|các phần tử]] trong một [[nhóm tô pô giao hoán]], ví dụ như [[Chuỗi (toán học)#Nhóm tô pô giao hoán|các vectơ]] trong [[không gian vectơ tô pô]]) là [[giới hạn của lưới]] các [[tổng riêng phần]] <math>F \in \operatorname{Finite}(I) \mapsto {\textstyle\sum\limits_{i \in F}} r_i;</math> nghĩa là:
<math display=block>\sum_{i \in I} r_i ~:=~ \lim_{F \in \operatorname{Finite}(I)} \ \sum_{i \in F} r_i ~=~ \lim \left\{\sum_{i \in F} r_i \,: F \subseteq I, F \text{ finite }\right\}.</math>

==Trái với nửa dàn==
[[Tập tin:Directed_set,_but_no_join_semi-lattice.png|thumb|x100px|Ví dụ về tập có hướng không phải nửa dàn có nối]]

Tập có hướng là khái niệm tổng quát hơn so với nửa dàn (có nối): mọi [[Nửa dàn|nửa dàn có nối]] là tập có hướng, bởi nối hay cận trên nhỏ nhất của hai phần tử bất kỳ là phần tử <math>c.</math> cần tìm. Tuy nhiên, cái ngược lại chưa chắc đã đúng, xét tập có hướng {1000,0001,1101,1011,1111} [[Thứ tự từng toạ độ|sắp thứ tự theo từng bit]] (ví dụ <math>1000 \leq 1011</math> đúng, nhưng <math>0001 \leq 1000</math> thì không, bởi bit cuối 1 > 0), trong đó tập con {1000,0001} có ba cận trên nhưng không có cận trên {{em|nhỏ nhất}}, xem hình vẽ. (Đồng thời lưu ý rằng nếu bỏ 1111 đi, thì tập hợp này sẽ mất hướng)

==Tập con có hướng==
Quan hệ thứ tự trong tập có hướng không được yêu cầu là phải [[Quan hệ phản đối xứng|phản đối xứng]], và do vậy tập có hướng không nhất thiết phải là [[thứ tự riêng phần|sắp thứ tự riêng phần]]. Song, thuật ngữ {{em|tập có hướng}} được dùng nhiều trong ngữ cảnh của tập sắp thứ tự riêng phần. Trong bối cảnh này, tập con <math>A</math> của tập sắp thứ tự riêng phần <math>(P, \leq)</math> được gọi là '''tập con có hướng''' nếu nó là tập có hướng theo cùng thứ tự riêng phần đó: nói cách khác, nó không phải [[tập rỗng]], và mỗi cặp hai phần tử phải cận trên. Ở đây, vì quan hệ thứ tự trên <math>A</math> lấy từ <math>P</math>; nên không cần phải nhắc đến tính phản xạ và bắc cầu.

Tập con có hướng của tập sắp thứ tự riêng phần không nhất thiết phải [[Tập dưới|đóng dưới]]; Tập con của tập sắp thứ tự riêng phần là tập có hướng khi và chỉ khi bao đóng xuống của nó là [[ideal (lý thuyết thứ tự)|ideal]]. Trong khi định nghĩa (trong bài này) là cho tập "hướng lên", ta cũng có thể định nghĩa một tập hướng dưới sao cho mọi cặp phần tử đều có chung một cận dưới. Tập con của tập sắp thứ tự riêng phần là tập hướng xuống khi và chỉ khi bao đóng trên của nó là một [[bộ lọc (lý thuyết tập hợp)|bộ lọc]].

Tập có hướng cũng được dùng trong [[lý thuyết miền]], dùng để nghiên cứu các [[thứ tự riêng phần đầy đủ|thứ tự riêng phần đầy đủ có hướng]].<ref>Gierz, p. 2.</ref> Đây là các tập hợp sắp thứ tự riêng phần trong đó mỗi tập hướng lên được yêu cầu phải có [[cận trên nhỏ nhất]]. <!--Trong ngữ cảnh này, một lần nữa các tập con có hướng tổng quát hoá cho các dãy hội tụ{{explain|reason=Again? Convergent sequences are never mentioned in this article.|date=December 2020}}-->

==Xem thêm==

* {{annotated link|Tập có tâm}}
* {{annotated link|Phạm trù bị lọc}}
* {{annotated link|Bộ lọc trong tô pô}}
* {{annotated link|Tập có liên kết}}
* {{annotated link|Lưới (toán học)}}

==Chú thích==

{{tham khảo|group=note}}
{{tham khảo}}

==Tham khảo==

* J. L. Kelley (1955), ''General Topology''.
* Gierz, Hofmann, Keimel, ''et al.'' (2003), ''Continuous Lattices and Domains'', Cambridge University Press. {{ISBN|0-521-80338-1}}.

{{Lý thuyết thứ tự}}

[[Thể loại:Quan hệ hai ngôi]]
[[Thể loại:Tô pô tổng quát]]
[[Thể loại:Lý thuyết thứ tự]]