$$P = NP$$
is unlikely but still possible.
To explain it to a child, you could ask if it's easier to:
- check the definition of a word in a wordbook
- or find a word in the wordbook given its definition
It seems obvious that the former is easier than the latter, $P = NP$ would mean that both are equally easy.
In both propositional and predicate logic, the truth value of a formula is always either true or false, once an interpretation has been given. The set $\{true, false\}$ is not something you choose; it is a fixed part of how the logic works.
However, in predicate logic, formulas are not everything there is. Predicate logic also has terms, which are expressions that can be the arguments of relation symbols. (For example, in the language of arithmetic $2>3$ or $5=x+2$ are formulas; $2\cdot 3$ or $x+2$ are terms).
An interpretation in predicate logic tells you
- A set that the value of terms can be drawn from. (This is implicitly also the set that variables have their values in).
- An interpretation of each of the function symbols in the logical language. (For example, $+$ in the language of arithmetic).
- An interpretation of each of the predicate symbols -- that is a set of ordered tuples of values that make the predicate true when given as argument.
In propositional logic there are no terms, no functions, and predicates. All of the atomic formulas are propositional letters. Seen from the predicate-logic end we can view a propositional letter as a "predicate symbol" that takes no operands. Thus, if we apply the above sense of interpretation, such as symbol should be represented either by the set $\{()\}$ that contains the (unique) tuple of length 0, or by the empty set.
But this corresponds to a choice of whether the propositional letter is true or false -- so an "interpretation" for propositional logic is effectively the same as a map from the propositional letters to $\{true, false\}$. All we need to do is to write $true$ and $false$ instead of $\{()\}$ and $\varnothing$.
Since there are no terms, there is no need for an interpretation to specify which kind of values the terms would have if there were any.
Best Answer
First of all, before we can callthis an integer, we can only call it a blob of ink or a bunch of pixels. How are some buches of pixels integers and others are not? Well, the are not integers, they represent integers. For example MMXV, and $2015$, and
0x7DFare distinct representations of the same integer, and all given with enough "context" to allow us to conclude (more or less easily) what representation scheme was used and that integers "behind" these notations are in fact the same.I won't go into details of the other two representation, but concentrate on the decimal one. How do we know which number it represents? While the answer seems to be "two thousands and fifteen" obviously, it is not really that obvious. The convention(!) behind the notation is that a finite sequence of digit symbols $d_1d_2\ldots d_k$ represents the number $\sum_{i=0}^{k-1}10^{i}d_{k-i}$ (with a bit of ignoring the distinction between a digit symbol and its numerical value). Your candidate does not match this convention because it is not a finite sequence. We cannot even read the value of $k$ from it. Admittedly, there are other ways to formulate the convention of deimal representation, but they all fail in some way or other with an infinite digit string (it may be appropriate to consider left-infinite sequences of digits and view the natural numbers as a subset of the "numbers" obtained this way (by prependingthem with infinitely many zeroes), but beware - the realm of Archimedes-Plutoniumism lurks behind that; and this does not apply to your right-infinite string).
To put it differently: Asking what integer an ill-formed (because infinite) sequence of decimal digits represents is not much better than asking what integer the ill-formed "roman numeral" MQLXXRT represents.