Infinite set ordering convention

[0rthodontist]

I was reading the electronic notes for my class on finite automata and the professor defines something as the smallest set having certain properties. The thing is that all sets having those properties are countable infinite. But there is a potential ordering, because all sets having those properties are supersets of the minimal set intended. Is this worth mentioning to him?

 

[AKG]

That is what is meant by "the smallest set." My book introduces two notions that have to do with strict partial orders: upper bounds and maximal elements. Given a set A with strict partial order <, an element c of A is an upper bound for a subset B of A if for every b in B, either b < c or b = c. A maximal element m of A is an element such that for all a in A, m < a never holds. Note that this does not mean that for all a in A, either a < m or a = m holds, since < is a partial order, and so comparability is not guaranteed. We can form analogous concepts of lower bounds and minimal elements. In your case, you have a collection C of sets with a certain property, and a special set m in C. m is a minimal element of C, in that for all c in C, c < m never holds (that is, c is never properly contained in m). m is also a lower bound of the subset C of C, since for every c in C, either m = c or m < c (i.e. every other set with the property is a superset of this special set m). The fact that m is a lower bound of the subset C of C implies that m is a minimal element of C. In fact, in your case m is the lower bound of C, and is the minimal element of C. This is normally what is meant by "the smallest set".

Coincidentally, this smallest set will also have cardinality less than (or equal to) all other elements in C as a result of being contained in all of them, but this is a mere consequence of being the smallest set, it is not what your professor means when he says it's the smallest.

 

[0rthodontist]

I talked to him and he clarified that he meant "smallest under inclusion" which is what you said.