If the truth set is identical to it's universal set, then the statement is logically true statement and it's called a tautology.

Can someone please explain the universal set to me in this context? I thought the universal set has to be defined for each problem, so how is it defined, for, say, $\neg (p\wedge q)\iff (\neg p) \vee (\neg q)$

I'm not taking a class, just interested in learning more about math. Thanks 😊

  • $\begingroup$ Hi, I edited a typo (I think!) and made the symbols more pretty. You can learn how to do that yourself here: math.meta.stackexchange.com/questions/5020/… . Please check if the symbols are correct now :) $\endgroup$ Aug 3 '20 at 5:32
  • 3
    $\begingroup$ It would help if you gave a definition of truth set and universal set, I don't think it is common terminology. $\endgroup$
    – Couchy
    Aug 3 '20 at 9:34
  • $\begingroup$ The notions of truth sets or universal sets rarely if ever come up in mathematics. There are only a few basic rules of logic that you need to remember, e.g. if A implies B then not B implies not A (the contrapositive rule). To learn them, you might Google "software to learn the basic methods of proof." $\endgroup$ Aug 3 '20 at 18:53
  • 1
    $\begingroup$ @Calvin, that certainly is attractive! I will take some time to learn this mark-up 😁 thanks for the great resource $\endgroup$ Aug 4 '20 at 5:02

The terms "truth set" and "universal set" aren't really common, but from context it sounds like they mean the following:

Fixing a propositional language $P$, the universal set associated to $P$ is the set of all valuations of propositional formulas built from $P$ (or essentially equivalently, the set of all maps $P\rightarrow\{True, False\}$), and for a formula $\varphi$ built from $P$ the truth set of $\varphi$ is the subset of the universal set consisting of all valuations making $\varphi$ true.

Now you are correct that $\varphi$ alone can't tell us what $P$ is - e.g. if $\varphi$ is $p\rightarrow q$, then $\{p,q\}$ and $\{p,q,r\}$ would each make sense. However, $\varphi$ does have a minimal language associated to it, namely the set of all propositional atoms which actually occur in $\varphi$, so we often default to that language.

Moreover, in this context - and indeed in many contexts - the choice of language doesn't matter:

Suppose $P_1,P_2$ are two languages each of which contains every propositional atom occurring in $\varphi$. Then $\varphi$ is a tautology in the sense of $P_1$ iff $\varphi$ is a tautology in the sense of $P_2$.

This is a good exercise: the key point is that whether or not a valuation $v$ makes a sentence $\varphi$ true is determined entirely by the restriction of $v$ to the propositional atoms actually occurring in $\varphi$. So we don't have to worry about the choice of language issue here.

That said, sometimes the choice of language does matter. For example, in the context of first-order logic it is important to specify the language when talking about the decidability or completeness of a theory: Presburger arithmetic, for example, is complete and decidable as a $\{+\}$-language but not as a $\{+,\cdot\}$-language.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.