1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinite set ordering convention

  1. Feb 22, 2006 #1

    0rthodontist

    User Avatar
    Science Advisor

    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?
     
  2. jcsd
  3. Feb 22, 2006 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Feb 22, 2006 #3

    0rthodontist

    User Avatar
    Science Advisor

    I talked to him and he clarified that he meant "smallest under inclusion" which is what you said.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Infinite set ordering convention
  1. Infinite set (Replies: 8)

  2. Infinite Sets (Replies: 2)

  3. Infinite set (Replies: 11)

Loading...