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

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.

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

Originally Posted by Mathelogician
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).

Originally Posted by Mathelogician
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.

Originally Posted by Mathelogician
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.

3. ## 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]

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

Originally Posted by emakarov
If ATOMS is infinite, then Card(PROP) = Card(ATOMS).
Originally Posted by Mathelogician
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.

Originally Posted by emakarov
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.
Originally Posted by Mathelogician
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.