closure of a subset under relations
Let be a set and be an -ary relation on , . A subset of is said to be closed under , or -closed, if, whenever , and , then .
Note that if is unary, then is -closed iff .
More generally, let be a set and a set of (finitary) relations on . A subset is said to be -closed if is -closed for each .
Given with a set of relations on , we say that is an -closure of if
-
1.
,
-
2.
is -closed, and
-
3.
if satisfies both 1 and 2, then .
By condition 3, , if exists, must be unique. Let us call it the -closure of , and denote it by . If , then we call it the -closure of , and denote it by correspondingly.
Here are some examples.
-
1.
Let , , and be the relation that whenever divides . Clearly is not closed under (for example, but ). Then . If is instead the relation , then .
-
2.
This is an example where is in fact a function (operation). Suppose and is the binary operation subtraction . Suppose . Then . To see this, set . Note that so as well as . This means that if , both and . By induction, . In general, if , where are coprime, then . This is essentially the result of the Chinese Remainder Theorem.
-
3.
If is unary, then the -closure of is just . When every is unary, then the -closure of in is .
Proposition 1.
exists for every .
Proof.
Let be the set of subsets of satisfying the defining conditions 1 and 2 of -closures above, partially ordered by . If , then . To see this, we break the statement down into cases:
-
•
In the case when , we have .
-
•
When , pick any -ary relation .
-
(a)
If , then, since aach is -closed, . Therefore, . So is -closed.
-
(b)
If , pick elements such that . As each for , and is -closed, . Since for every , as well. This shows that is -closed.
In both cases, since for every . Therefore, .
-
(a)
Hence, is a complete lattice by virtue of this fact (http://planetmath.org/CriteriaForAPosetToBeACompleteLattice), which means that has a minimal element, which is none other than the -closure of . ∎
Remark. It is not hard to see has the following properties:
-
1.
,
-
2.
, and
-
3.
if , then .
Next, assume that is another set of finitary relations on . Then
-
1.
if , then ,
-
2.
, and
-
3.
if or .
Title | closure of a subset under relations |
---|---|
Canonical name | ClosureOfASubsetUnderRelations |
Date of creation | 2013-03-22 16:21:26 |
Last modified on | 2013-03-22 16:21:26 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 36 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 08A02 |
Defines | closed under |
Defines | closure property |