• Source: Almost disjoint sets

In mathematics, two sets are almost disjoint if their intersection is small in some sense; different definitions of "small" will result in different definitions of "almost disjoint".




Definition


The most common choice is to take "small" to mean finite. In this case, two sets are almost disjoint if their intersection is finite, i.e. if





|

A
∩
B

|

<
∞
.


{\displaystyle \left|A\cap B\right|<\infty .}


(Here, '|X |' denotes the cardinality of X, and '< ∞' means 'finite'.) For example, the closed intervals [0, 1] and [1, 2] are almost disjoint, because their intersection is the finite set {1}. However, the unit interval [0, 1] and the set of rational numbers Q are not almost disjoint, because their intersection is infinite.
This definition extends to any collection of sets. A collection of sets is pairwise almost disjoint or mutually almost disjoint if any two distinct sets in the collection are almost disjoint. Often the prefix 'pairwise' is dropped, and a pairwise almost disjoint collection is simply called "almost disjoint".
Formally, let I be an index set, and for each i in I, let Ai be a set. Then the collection of sets {Ai : i in I } is almost disjoint if for any i and j in I,





A

i


≠

A

j




⟹



|


A

i


∩

A

j



|

<
∞
.


{\displaystyle A_{i}\neq A_{j}\quad \implies \quad \left|A_{i}\cap A_{j}\right|<\infty .}


For example, the collection of all lines through the origin in R2 is almost disjoint, because any two of them only meet at the origin. If {Ai } is an almost disjoint collection consisting of more than one set, then clearly its intersection is finite:





⋂

i
∈
I



A

i


<
∞
.


{\displaystyle \bigcap _{i\in I}A_{i}<\infty .}


However, the converse is not true—the intersection of the collection




{
{
1
,
2
,
3
,
…
}
,
{
2
,
3
,
4
,
…
}
,
{
3
,
4
,
5
,
…
}
,
…
}


{\displaystyle \{\{1,2,3,\ldots \},\{2,3,4,\ldots \},\{3,4,5,\ldots \},\ldots \}}


is empty, but the collection is not almost disjoint; in fact, the intersection of any two distinct sets in this collection is infinite.
The possible cardinalities of a maximal almost disjoint family (commonly referred to as a MAD family) on the set



ω


{\displaystyle \omega }

of the natural numbers has been the object of intense study. The minimum infinite such cardinal is one of the classical cardinal characteristics of the continuum.




Other meanings


Sometimes "almost disjoint" is used in some other sense, or in the sense of measure theory or topological category. Here are some alternative definitions of "almost disjoint" that are sometimes used (similar definitions apply to infinite collections):

Let κ be any cardinal number. Then two sets A and B are almost disjoint if the cardinality of their intersection is less than κ, i.e. if





|

A
∩
B

|

<
κ
.


{\displaystyle \left|A\cap B\right|<\kappa .}


The case of κ = 1 is simply the definition of disjoint sets; the case of




κ
=

ℵ

0




{\displaystyle \kappa =\aleph _{0}}


is simply the definition of almost disjoint given above, where the intersection of A and B is finite.
Let m be a complete measure on a measure space X. Then two subsets A and B of X are almost disjoint if their intersection is a null-set, i.e. if




m
(
A
∩
B
)
=
0.


{\displaystyle m(A\cap B)=0.}


Let X be a topological space. Then two subsets A and B of X are almost disjoint if their intersection is meagre in X.




References

Kata Kunci Pencarian:

• Disjoint sets
• Almost disjoint sets
• Disjoint union
• Disjoint-set data structure
• Almost
• Fuzzy set
• Set theory
• Maker-Breaker game
• Zermelo–Fraenkel set theory
• Universal set