Results 1 to 2 of 2

Math Help - countable & uncountable sets

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    94

    countable & uncountable sets

    Prove that the set of all grammatical sentences of English is denumerable.(Hint: Every grammatical sentence of English is a finite sequence of English words. First show that the set of all grammatical sentences is countable, and then show that it it infinite)???????
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mathsohard View Post
    Prove that the set of all grammatical sentences of English is denumerable.(Hint: Every grammatical sentence of English is a finite sequence of English words. First show that the set of all grammatical sentences is countable, and then show that it it infinite)???????
    How much do you know? There is a common theorem which states that the set of all finite subsets of an infinite set is equipotent to the full set. Thus, \mathcal{N}=\left\{E\subseteq\mathbb{N}:|S|<\infty  \right\} has cardinality of \aleph_0. Then, if \mathcal{G} is the set of all grammatical sentences we can clearly inject \mathcal{G}\to\mathcal{N}. Then, assuming that I understand a grammatical sentence the sentences \text{hi},\text{hi hi},\text{hi hi hi},\cdots form an infinite subset of \mathcal{G}. It clearly follows that |\mathcal{G}|=\aleph_0.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 07:14 AM
  2. Countable and Uncountable sets
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: October 21st 2010, 12:58 PM
  3. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 02:59 PM
  4. countable and uncountable sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2009, 01:40 PM
  5. Replies: 4
    Last Post: October 11th 2008, 02:42 PM

Search Tags


/mathhelpforum @mathhelpforum