Calculate the number of increasing properties of subsets of $\Gamma = \{1, 2, 3, 4\}$.
I understand what an increasing property is, but I have no idea how to do this. Any hints would be great. Thanks.
Edit: A graph property $Q$ is called monotonically increasing if $G\in Q$ implies $G+e\in Q$, i.e. adding an edge $e$ to a graph $G$ does not destroy the property. For example, connectivity is a monotonically increasing property.
Connection of $\Gamma$ with graphs: Suppose we have a complete graph $K_{n}$ on $\{1,...,n\}$ and $\Gamma$ is the set of edges of $K_{n}$, then there is a bijection between subsets of $\Gamma$ and subgraph of complete graph $K_{n}$.
Consider cases and count.
But first here is the lattice of subsets of {1,2,3}, on the left, and then, on the right, the lattice of subsets of {1,2,3,4}, for reference (where e stands for the empty set). It also illustrates how the bigger lattice could be obtained by first taking two copies of the old one, then taking the union of every set in the second copy with the new element (i.e. with {4} in our case), shifting the second copy one row up, and adding a few extra lines (for the subset relation).
(Hopefully this would make it easier to follow all the cases listed below. It might conceivably also help think how the solution for {1,2,3,4} could be obtained from the solution for {1,2,3}, recursively, but I need to think about this part. According to Wikipedia the problem quickly becomes computationally difficult, e.g. the so-called Dedekind number M(4) (discissed in the present question and answer) is 168, but M(8) is 56130437228687557907788, and values of M(n) for n>8 are not known. It also just occured to me that the lattice for {1,2,3} looks like a cube, while the lattice for {1,2,3,4} looks like a cube one dimension higher.)
Now do the counting for {1,2,3,4}, to answer the question.
(0) The empty set has P (and hence every subset of $\Gamma$ does).
Total from this case: 1.
(1n0) At least one singleton has P, but the empty set doesn't. Split into subcases as follows.
(1n0e1) Exactly one singleton has P.
First assume {1} has P but none of {2,},{3},{4} does. Then each of the doubletons {2,3}, {2,4} and {3,4} may or may not have P, which makes $2^3=8$ possibilities. If at least one of {2,3}, {2,4} or {3,4} has P then also {2,3,4} must have P. But when none of {2,3}, {2,4} and {3,4} has P then {2,3,4} may or may not have P, so we need to add to our count the possibility that {2,3,4} doesn't have P. Together with the $8$ possibilities counted earlier we get $8+1=9$ possibilities, corresponding to the case when the only singleton that has P is {1}. Since there are four singletons, the total from case (1n0e1) is $9\cdot4=36.$
(1n0e2) Exactly two singletons have P.
First assume {1} and {2} have P but {3},{4} don't. Then doubleton {3,4} may or may not have P, two possibilities. (Note that each doubleton except {3,4} must contain at least one of the singletons {1}, {2}, hence has P.) Next, we have "four choose two"= ${4\choose2}=6$ possibilities to pick two singletons out of four, so total from case (1n0e2) is $6\cdot2=12.$
(1n0e3) Exactly three singletons have P. Then all doubletons and larger sets have P. Total from case (1n0e3) is ${4\choose3}={4\choose1}=4$.
(1n0e4) All four singletons have P, total from (1n0e4) is $1$.
(2n1) At least one doubleton has P, but no singleton does. Split into subcases as follows.
(2n1e1) Exactly one doubleton has P. First assume {1,2} has P. Then each of {1,2,3} and {1,2,4} does have P too, but each of {1,3,4} and {2,3,4} may or may not have P, which is $2^2=4$ possibilities. Next, we have ${4\choose2}=6$ different ways to pick the doubleton that does have P, and that times $4$ results in total $24$ from (2n1e1).
(2n1e2) Exactly two doubletons have P.
(2n1e2disjoint) These two doubletons are disjoint. Could be {1,2},{3,4} have P, or else {1,3},{2,4} have P, or else {1,4},{2,3} have P, total $3$ from (2n1e2disjoint).
(2n1e2intersect) The two doubletons that have P have a common element. First consider the case when {1,2} and {1,3} are the two doubletons that have P. Then {2,3,4} may or may not have P, two possibilities. Next, we could pick two intersecting doubletons by first picking the only element which is not in their union (four choices) and multiply that by ${3\choose2}=3$ ways to pick two doubletons out of the remaining three elements. Altogether we have $4\cdot3\cdot2=24$ total from (2n1e2intersect).
(2n1e3) Exactly three doubletons have P.
(2n1e3common) These three doubletons have an element in common, for example {1,2}, {1,3}, {1,4} have P, and {1} is a subset of each of them. Then {1,2,3}, {1,2,4}, {1,3,4} each must have P, but {2,3,4} may or may not have P, two possibilities. The common element of the three doubletons uniquely determines them, and we have four choices for this common element, resulting in total $4\cdot2=8$ from (2n1e3common).
(2n1e3nocommon) The three doubletons have no element in common. Then all of {1,2,3}, {1,2,4}, {1,3,4} and {2,3,4} must have P. We have ${6\choose3}=20$ ways to pick three doubletons out of six doubletons, but we have to subtract the four ways to pick three doubletons when they have an element in common, already accounted for in the previous case (2n1e3common). Thus we are left with $20-4=16$ in (2n1e3nocommon).
(2n1e4) Exactly four doubletons have P, makes ${6\choose4}=15$ from (2n1e4).
(2n1e5) Exactly five doubletons have P, makes ${6\choose5}=6$ from (2n1e5).
(2n1e6) Exactly six doubletons have P, makes ${6\choose6}=1$ from (2n1e6).
(3n2) Some three-element sets have P but no doubletons do. There are four three-element sets, and $2^4=16$ ways to pick a family of three-element sets, but $16-1=15$ ways if this family is to be non-empty. So, $15$ from (3n2).
(4n3) {1,2,3,4} has P but no three-element set does. Total $1$ from (4n3).
(n4) {1,2,3,4} doesn't have P, total $1$ from (n4).
(Note there are some sligthtly different ways to count, resulting in the same final answer: For example cases (3n2), (4n3) and (n4) could have been counted as $2^4+1=17$ by (a) considering all families of three-element sets, $2^4=16$, and to that adding (b) for the empty family of three-element sets we allow that {1,2,3,4} doesn't have P, accounting for the extra $+1$.)
So, adding up:
(0) $1+$
(1n0e1) $36+$
(1n0e2) $12+$
(1n0e3) $4+$
(1n0e4) $1+$
(2n1e1) $24+$
(2n1e2disjoint) $3+$
(2n1e2intersect) $24+$
(2n1e3common) $8+$
(2n1e3nocommon) $16+$
(2n1e4) $15+$
(2n1e5) $6+$
(2n1e6) $1+$
(3n2) $15+$
(4n3) $1+$
(n4) $1=$
$=1+36+12+4+1+24+3+24+8+16+15+6+1+15+1+1=$
$=168$.
Here is a comment on the relation with antichains. The wikipedia link (in the comment by Lorenzo Najt to the question) defines:
An antichain of sets is a family of sets, none of which is contained in any other set.
For example {{1}} is an antichain, and so is {{1},{2,3}} as well as {{1,2},{2,3}}, but {{1},{1,3}} is not an antichain (since {1} is a subset of {1,3}).
Given any antichain (of subsets of $\Gamma$), there is an "increasing property" P satisfied exactly by those subsets of $\Gamma$ that contain some element of the antichain. For example the antichain {$\emptyset$} corresponds to case (0) in my list of cases above. The antichain {{1}} as well as the antichain {{1},{2,3}} each is included in case (1n0e1) above, and so is the antichain {{1},{2,3},{2,4},{3,4}}, as well as the antichain {{1},{2,3,4}} (among others). The antichain {{1},{2}} as well as the antichain {{1},{2},{3,4}} is included in case (1n0e2) above.
I am also curious why M(3)=20, M(4)=168=(20+1)8 (is there some recursive computation involved). Then M(5) is 7581, and trying to get this close to a multiple of M(4) we have $7567=47\cdot161$ though I do not know how to interpret that, or what to use it for. There ought to be some recursive relation expressing M(n) in terms of M(n-1), or perhaps in terms of M(0),M(1),...,M(n-1), but I need to think of the details. (There is a formula for M(n) on wikipedia, involving summation from 1 to $2^{2^n}$ of certain doubly indexed products, and the floor function is involved, looks scary to me.) No reason to expect that it would be easy, but it might be worth looking.
Here is one more picture to illustrate the case when $\Gamma=\{1,2,3\}$ and the number of "increasing properties" is 20. Each increasing property (i.e. an upper-closed subfamily of the family of all subsets of $\Gamma$) is shown along with the antichain that generates it (and all are numbered from 1 to 20).