[FOM] Question about Congruence

Vaughan Pratt pratt at cs.stanford.edu
Mon Jan 28 16:50:48 EST 2008

hdeutsch at ilstu.edu wrote:
> Is the following fact well known?  It is of some philosophical  
> interest, as explained below.
> (*) Let R be an equivalence relation defined on a set A and let B be a  
> set. Then B is closed under R iff each element E of the partition P of  
> A induced by R is such that if some element of E is in B, then they  
> all are.

("let B be a set" should have been "let B be a subset of A")

The union of a subset of a partition P is a straightforward notion, for 
which the above is easily seen to provide two equivalent 
characterizations.  If either of them are documented somewhere (I've 
never run across either) you can cite that, otherwise "evident" might be 
more appropriate than "well-known."

One generalization would be to the notion of compatibility of a 
subalgebra of an algebra A with a quotient of A, the above being the 
case of an algebra with no operations.

Vaughan Pratt

More information about the FOM mailing list