Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S_1 and S_2...

Question

Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S_1 and S_2 in C, either S_1 ⊆ S_2 or S_2 ⊆ S_1. What is the maximum cardinality of C?

A. n - 1
B. n + 1
C. 2^(n-1) + 1
D. n!

Accepted Answer

The maximum cardinality of C is n + 1. A collection of subsets where every pair is comparable (one contains the other) is called a chain in the power set lattice. The longest chain in 2^A goes from the empty set through all singletons, pairs, triples, ..., all the way up to A itself — one set of each size from 0 to n. That gives n + 1 subsets.

Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S_1 and S_2 in C, either S_1 ⊆ S_2 or S_2 ⊆ S_1. What is the maximum cardinality of C? A. n - 1 B. n + 1 C. 2^(n-1) + 1 D. n!