Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Prove we have 2^(aleph-0) "Valuations" [Mathematical logic question]

  1. #1
    Member Mathelogician's Avatar
    Joined
    Jun 2010
    From
    Iran
    Posts
    89
    Thanks
    1

    Prove we have 2^(aleph-0) "Valuations" [Mathematical logic question]

    Hi everybody,
    In VanDalen's "Logic and structure" he defines a valuation to be a function v:PROP->{0,1} such that for example v(phi ^ psi)=min(v(phi),v(psi))
    and similar properties you know all, for other connectives.
    then he discusses a theorem that lets us to extend an "atomic valuation"(A function h:ATOMS->{0,1}) to a valuation on PROP.Indeed to have a unique valuation on PROP for any atomic valuation.
    Later he asks to prove that [the number of valuations is 2^(aleph-0)].
    I have questions now:
    1- Is ATOMS equinumerous to PROP?(Or it is only dominated by PROP?)
    I am asking this beacause i want to know if they are not equinumerous, then which "valuations" does he mean; Atomics valuations or The valuations on PROP?(Note that he asks the number of valuations just after he calls Atomic valuations also valuations)
    2- What is Card(ATOMS) ? Because if we prove that ATOMS is equinumerous to natural numbers(i.e, has cardinality of (aleph-0))then we will have 2^aleph-0
    (atomic)valuations.
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Prove we have 2^(aleph-0) "Valuations" [Mathematical logic question]

    Quote Originally Posted by Mathelogician View Post
    2- What is Card(ATOMS) ? Because if we prove that ATOMS is equinumerous to natural numbers(i.e, has cardinality of (aleph-0))then we will have 2^aleph-0 (atomic)valuations.
    To be sure about the answer you should refer to the definition of ATOMS and the language of PROP. Most likely, ATOMS is a countably infinite set such as \{p_0,p_1,\dots\}. One rarely considers finite or uncountable sets of atoms (an exception that comes to mind is the Löwenheim–Skolem theorem).

    Quote Originally Posted by Mathelogician View Post
    1- Is ATOMS equinumerous to PROP?(Or it is only dominated by PROP?)
    If ATOMS is infinite, then Card(PROP) = Card(ATOMS). Of course, if ATOMS is finite, then PROP is countably infinite.

    Quote Originally Posted by Mathelogician View Post
    I am asking this beacause i want to know if they are not equinumerous, then which "valuations" does he mean; Atomics valuations or The valuations on PROP?
    In fact, even if ATOMS is not equinumerous with PROP, as is the case when ATOMS is finite, the sets of valuations on ATOMS and on PROP are equinumerous. This is because the mapping that extends a valuation from ATOMS to PROP is a bijection.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Mathelogician's Avatar
    Joined
    Jun 2010
    From
    Iran
    Posts
    89
    Thanks
    1

    Re: Prove we have 2^(aleph-0) "Valuations" [Mathematical logic question]

    To be sure about the answer you should refer to the definition of ATOMS and the language of PROP. Most likely, ATOMS is a countably infinite set such as \{p_0,p_1,\dots\}. One rarely considers finite or uncountable sets of atoms (an exception that comes to mind is the Löwenheim–Skolem theorem).
    Thanks. I think the key answer would be this....
    And by ATOMS i meant the set of all atoms. and by PROP i meant the set of all propositions.


    If ATOMS is infinite, then Card(PROP) = Card(ATOMS).
    Why then?

    This In fact, even if ATOMS is not equinumerous with PROP, as is the case when ATOMS is finite, the sets of valuations on ATOMS and on PROP are equinumerous. This is because the mapping that extends a valuation from ATOMS to PROP is a bijection
    What do you mean?!
    If ATOMS is considered to be finite, then it would have n elements for some n in N. therefore we would have 2^n valuations on ATOMS. But as you know PROP is infinite.
    How do you explain this?
    And at last, why for every valuation on PROP do we have a valuation in ATOMS(even for ATOMS to be infinite)?[However the converse holds]
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Prove we have 2^(aleph-0) "Valuations" [Mathematical logic question]

    Quote Originally Posted by emakarov View Post
    If ATOMS is infinite, then Card(PROP) = Card(ATOMS).
    Quote Originally Posted by Mathelogician View Post
    Why then?
    Below I'll use some facts about cardinal arithmetic. I'll write |X| for Card(X) for any set X, A for ATOMS and P for PROP. Also, let L be the set of symbols besides atoms that can occur in a formula (logical connectives and parentheses), and let V = A ∪ L. Then L is a finite set, so |V| = |A|. Obviously |A| ≤ |P|. On the other hand, |P| \le |\bigcup_{n=1}^\infty V^{\bar{n}}| where \bar{n}=\{1,\dots,n\}. This is because V^{\bar{n}} is the set of all strings of length n in the alphabet V. We have |V^{\bar{n}}|=|V| and |\bigcup_{n=1}^\infty V^{\bar{n}}|\le\aleph_0\times |V|=|V| because \aleph_0\le|V|. Thus, |P| ≤ |V| = |A|.

    In particular, if A and V are countable, then the set of strings of length n in alphabet V is countable, and the union of a countable number of countable set is also countable.

    Quote Originally Posted by emakarov View Post
    In fact, even if ATOMS is not equinumerous with PROP, as is the case when ATOMS is finite, the sets of valuations on ATOMS and on PROP are equinumerous. This is because the mapping that extends a valuation from ATOMS to PROP is a bijection.
    Quote Originally Posted by Mathelogician View Post
    What do you mean?!
    If ATOMS is considered to be finite, then it would have n elements for some n in N. therefore we would have 2^n valuations on ATOMS. But as you know PROP is infinite.
    How do you explain this?
    Not every function from PROP to {0, 1} is a legal valuation on PROP. A valuation, as I understand, must interact in a certain way with logical connectives (as you write, v(phi ^ psi)=min(v(phi),v(psi)), etc.). We have the following fact, which is proved by induction on formulas.

    If two valuations coincide on atoms, then then coincide everywhere. (*)

    Since ATOMS ⊆ PROP, every valuation v on PROP restricted to ATOMS is a valuation v' on ATOMS. Moreover, when extended to PROP, this v' generates v: if it generated some other v1, then v and v1 would coincide with v' on atoms and therefore v = v1 by (*). Therefore, the mapping that extends a valuation from ATOMS to PROP is a surjection. In other words, a valuation on PROP is completely determined by its restriction on ATOMS, so there are no more valuations on PROP than there are valuations to ATOMS. On the other hand, the extension mapping is an injection because if two valuations on PROP coincide, then their restrictions to ATOMS also coincide. Thus, the extension mapping is a bijection.
    Thanks from Mathelogician
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: April 2nd 2012, 07:06 PM
  2. Replies: 1
    Last Post: September 16th 2011, 01:08 AM
  3. Replies: 4
    Last Post: June 3rd 2011, 08:46 AM
  4. Replies: 1
    Last Post: September 28th 2010, 07:25 PM
  5. logic: expressing "or" in terms of "implies not"
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 29th 2007, 06:55 AM

Search Tags


/mathhelpforum @mathhelpforum