2
$\begingroup$

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 😊

$\endgroup$
4
  • $\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$
    – Calvin Khor
    Commented Aug 3, 2020 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
    Commented Aug 3, 2020 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$
    – Dan Christensen
    Commented Aug 3, 2020 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$
    – David Graham
    Commented Aug 4, 2020 at 5:02

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .