the number of set T

75 Views Asked by At

A={1,2,3...,n} and let T is subset of P(A)

then T satisfies following properties

(1) empty set is element of T

(2) If Y is element of T then Y^c is also element of T

(3) if X,Y are elements of T then union of X,Y is also element of T

How many T's are there?

I have done some calculations, 1 for n = 1, 2 for n = 2, 5 for n = 3, 15 for n = 4

and I try to use recurrence formula..but fail..

How do I get a closed-form??

1

There are 1 best solutions below

1
On

Each and every $T$ corresponds to a partitioning of $A$. Namely, if $S\subseteq P(A)$ is a partitioning, then $$T = \{\cup S'\ : S' \subseteq S\}$$ is the corresponding subset of $P(A)$, and there are no others (for arbitrary $T$, consider its nonempty elements that are minimal with respect to inclusion - these form a partitioning of $A$, and this idea is already in the comments). So you're seeking for these numbers.