4
$\begingroup$

This question is maybe too broad and probably incredibly trivial. I feel like there must be some resources which answer me on the web but for a long long time I couldn't really find an answer to my question and after asking it to chat, I decided to make a post out of it. If this question is not appropriate, please try to edit.

My question is: Wikipedia says: 'A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true.' How is 'true' in this sentence defined? I know what a model is and the definition of the satisfaction relation etc. But the perspective 'we have some symbol set and created a syntax and now we are interpreting it and if the interpretation of the purely syntactical thing/formula is true in the interpretation(?), then the model satisfies the formula'. So in my mind, we inherit a definition of the truth from some theories which are already build (for example groups, real numbers etc.) and we are using them to define our 'fundamentalist truth'. And a side note, we are in first-order logic (and to be honest, I don't know in which degree this information is relevant).

And for example I don't understand principle of excluded middle because I don't understand in which setting it says a proposition true. I spend hours to understand it, and didn't even come close. I hope that this is a good justification to ask such a question. I hope that someone out there understand my problem and hits me with an explanation. I would really appreciate it.

Thanks!

EDIT: I want to explain my mind. I picture it like this: We have a syntax developed and we define a sequent calculus, and if we start with a list of formulas (taking them as axioms) then we deduce/prove other formulas. I picture this process as "sudden": (Picture)
(1) We have an alphabet and a language, so there is a universe where all the possible combinations lie, empty word and so on.
(2) We define what a formula is, this makes only some words, let's say blue. Now we have some blue things and some colorless.
(3) We choose some blue's as axioms and this is also suddenly make them green.
(4) Then we define a sequent calculus and this makes everything which are reachable from green words suddenly red. Axioms are also now red.
(5) We have done so far just syntactical things. We can for example define consistency and for example if everything is red if and only if the words which were green some time ago were not consistent.
(6) Now this was just one universe with a specific "base" (greens). We can picture now a multiverse structure, for each choose of a base (any subset of blue words), we have a universe. If we choose empty set, then what we get is the smallest universe, which contains "no matter what logically correct statements". If we have too much (like in the example (5)), then suddenly everything becomes red, so lot's of choices of green words makes whole universe blueless (red + colorless). This blueless'ness is equivalent to inconsistency of the base (which prove for a formula $\phi$, both $\phi$ and $\neg \phi$.
(7) I assume that what I wrote is correct (probably not rigorously, but as a "picturing".
(8) Now, some of the universes are bad, for example, everything is red. We want to choose a specific base, and we have some reds, some blues, and we want to also interpret formulas in a logically correct way, and we look if in this universe, what is red and what is blue correspond to the what we know about that mathematics.
(9) The risk is, we could just say that what in our mind blue/red is, should be blue/red, and that is it. This without logic, but we want to minimize the human error, and therefore we restrict to the mathematics we assume to the just bases and rules of sequent calculus.
(10) By the way, is there a theory, where this all things doesn't suddenly happen and there is a notion of "laziness"? I obviously don't know but, and this probably gibberish but maybe take a kind of type theory with a notion of laziness like in haskell? This is a side question, doesn't need to be answered.
(11) We prove some relative consistency results about some specific bases and there is lots of other things we can do of course.
(12) I honestly, don't see how can we break the circularity. We are taking sets as domains to the structures and we are creating set theory. We have functions already, but we are trying to define them properly. Is this actually a circularity? I don't want to ask circularity questions in this sense, because it is not the topic of the question, but still an answer would be appreciated.
(13) We choose a specific universe, than interpret the language in a good, structured way, definition of the satisfaction rule for example is also a piece of mathematics we "assume". We assume that this kind of perspective is good/strong, maybe someone can deny that and that's why there is alternatives to first order logic, like type theory.
(14) Debates about LEM are debates about what kind of a sequent calculus to choice.
(15) If the interpretation is good enough to satisfy the base, then we choose it as a model of our theory, and we are done.
(16) Interpretation part of the theory, make some syntax "true", and sequent calculus part of it make is "provable", and Gödel's first completeness theorem says that they correspond: If we had a green base, and now have some blues/reds, then a formula is in reds (provable) if and only if every interpretation which satisfies the green base also satisfies to this red formula.
(17) Now, let's go back to the LEM. Firstly, a proposition is what we called formula above. So let $\phi$ be a formula, instead of true/false, what should we use to denote false? Is it same thing to be unprovable? I am just about to grasp it, an answer to this questions should finish my endeavors.

So there is two side questions (10) and (12) and two main questions (17) and "Is my thought process correct? Is what I wrote above correct?". Don't consider side questions and this question consist of two questions which are similar. Sorry for the insufficient question in the beginning and I hope that now this question makes sense and opens.

Again, thank you!

$\endgroup$
  • $\begingroup$ "true" means true... Consider a formula $P(c,d)$ and interpret it in a structure $\mathfrak A$ with domain $D= \{ 0,1 \}$ where the constant $c$ is interpreted as $0$, the const $d$ is interpeted as $1$ and the binary relation $P$ is interpreted as $<$. Then $\mathfrak A \vDash P(c,d)$, i.e. the sentence is satisfied in $\mathfrak A$. $\endgroup$ – Mauro ALLEGRANZA May 5 '17 at 5:54
  • $\begingroup$ Consider now the same sentence and a domain $E= \{ \text{John}, \text {Paul} \}$ where $\text{John}$ and $\text {Paul}$ are brothers and the binary relation $P$ is interpreted as $\text {is father of}$. In this "structure" $\mathfrak B$ the sentence is false: $\mathfrak B \nvDash P(c,d)$. $\endgroup$ – Mauro ALLEGRANZA May 5 '17 at 5:56
  • 1
    $\begingroup$ @MauroALLEGRANZA I edited my question and please see my comment to the answer below. I am missing a really trivial and fundamental point, I guess. $\endgroup$ – Konformist Liberal May 5 '17 at 10:22
  • $\begingroup$ The Law of Excluded Middle in classical logic is a "logical law", i.e. a formula true in every interpretation. This means that it holds in every "context". It states that, for every specific "domain of discourse" or interpretation every sentence of the language "suitable" for that doamin has one and only one truth value. In the domain of the natural numbers, either a number is odd or is not odd (i.e. even). In the domain of humans, either a human is married or he is not married. $\endgroup$ – Mauro ALLEGRANZA May 5 '17 at 11:25
3
$\begingroup$

(Main question) Wikipedia says: 'A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true.' How is 'true' in this sentence defined? [...] So in my mind, we inherit a definition of the truth from some theories which are already build [...]

It's defined in the meta-system. Formally, the meta-system is itself a formal system, and modern logicians usually choose ZFC set theory for this. In actual practice the meta-system is seldom stated and proofs about logic are given in informal language, but such that any logician can with enough time and effort mechanically translate such a proof into proof in ZFC* where ZFC* is simply ZFC plus on-the-fly definitorial expansion to prevent exponential blow-up of proof length. $ \def\nn{\mathbb{N}} $

In ZFC* we can easily define $\nn$ as the set that satisfies the axiom of infinity and define the basic arithmetic operations on $\nn$, and prove that these together satisfy the axioms of PA. Then you can define (finite) strings using $\nn$, either via Godel coding or as functions from $\nn_{<n}$ to $\nn$ where $n \in \nn$. Next you can define (classical) first-order logic via its inference rules, in terms of strings. (For now let us stick to having countable many fixed predicate/function/constant-symbols.) Then you can define an interpretation $I$ to be a pair $(U,f)$ where $f$ is a function from first-order formulae to the classical truth values (say $\{0,1\}$ where $0,1$ denote $false,true$ respectively) such that $f$ respects the inference rules (the rules are sound for $f$). Finally, you can define that a formula $φ$ is satisfiable iff there is an interpretation $I = (U,f)$ such that $f(φ) = 1$.

Notice that in the above definition everything can be done formally in ZFC* and there is absolutely no need for any of it to make any sense, in the sense that the rules of the formal system ZFC* allow us to construct the definitions and prove the theorems we need. So there is no absolute notion of truth; it is relative to the meta-system, as you might have thought. If you believe the meta-system is meaningful, and first-order logic is meaningful, then the notion of truth that we define in it is also meaningful and captures our intuitive idea of classical logic. You may have noticed that ZFC itself is a first-order system; there is no escaping the fact that we must already choose some kind of logic to even begin studying logic.

(12) I honestly, don't see how can we break the circularity. We are taking sets as domains to the structures and we are creating set theory. We have functions already, but we are trying to define them properly. Is this actually a circularity? I don't want to ask circularity questions in this sense, because it is not the topic of the question, but still an answer would be appreciated.

Although it may not seem directly related to your question, circularity is probably the core of what you are seeking to grasp. Indeed predicate/function-symbols seem to be the syntactic equivalents of sets and functions, do they not? No wonder that in first-order logic we define an interpretation of them using sets and functions, whose constructability and properties are somewhat already given in the meta-system.

At the minimum, natural numbers have to be assumed somehow in the meta-system, otherwise you cannot even talk about formal systems. And to talk about models of formal systems you need to assume something like sets even if it is much weaker than ZF. For more detail see this post.

(17) Now, let's go back to the LEM. Firstly, a proposition is what we called formula above. So let $ϕ$ be a formula, instead of true/false, what should we use to denote false? Is it same thing to be unprovable? I am just about to grasp it, an answer to this questions should finish my endeavors.

It seems you misunderstood something here. A formula is sometimes unprovable in a first-order theory, when two models of the axioms (a model is an interpretation that satisfies all the axioms) disagree on the truth-value of the formula (one satisfies it and the other does not satisfy it). Firstly, not all formulae are unprovable; "$x = y \land y = z \land z \ne x$" is a formula (not a sentence) but always disprovable.

Secondly, unprovability has nothing to do with LEM. LEM is baked right in to first-order logic in the inference rules, because the rules allow you to derive "$P \lor \neg P$" for any sentence $P$. We can hence say that LEM is a valid rule over first-order logic. This is the case even if $P$ is not provable from the axioms of the theory. LEM is just essentially affirming that if you pick any model $M$ of the axioms, either $P$ is satisfied by $M$ or $\neg P$ is satisfied by $M$.

Thirdly, even if a first-order theory is syntactically complete (proves or disproves every sentence), it may not prove or disprove some formula. For example the theory of dense linear-orders without endpoints is syntactically complete but does not prove or disprove the formula "$x < y$". Sort of just because of the free variables $x,y$.

$\endgroup$
  • $\begingroup$ As for (10) about laziness, I can confidently say "no such thing" simply because there is no way to precisely specify such a thing that doesn't become trivial in some way. If you think very carefully, we cannot avoid paradox or circularity via any sort of laziness. See this response to the common naive attempt of just repudiating assumptions whenever we reach a contradiction. $\endgroup$ – user21820 May 6 '17 at 18:03
  • $\begingroup$ Sorry, what is $U$ in $(U,f)$ here? $\endgroup$ – Koncopd Aug 19 '18 at 18:21
  • $\begingroup$ @Koncopd: $U$ is the domain of the interpretation, as per the conventional interpretation of first-order logic. Sorry I didn't make that clear in my post. For example one interpretation of PA would have $U = \mathbb{N}$ and $f$ be the evaluation function given by the natural interpretation of all the arithmetic operation-symbols as the ordinary arithmetic operations on $\mathbb{N}$. $\endgroup$ – user21820 Aug 20 '18 at 8:48
0
$\begingroup$

What "true" means depends on the interpretation. That is, it is part of the data you specify when you provide an interpretation. For example, for classical propositional logic, you can interpret a formula as a finite function $\{0,1\}^n\to \{0,1\}$ (or the more concrete presentation of such as a truth table) where the formula has $n$ proposition variables. Such an interpretation is "true" if it equals the constantly $1$ function. Alternatively (and equivalently), you could interpret a formula with $n$ proposition variables as a subset of $\{0,1\}^n$ with an interpretation being "true" if it equals $\{0,1\}^n$.

We can give a rather general answer while clearly articulating the data that needs to be provided by using the notion of categorical semantics from categorical logic. In this approach, a predicate $\varphi$ in a context $\Gamma$ is interpreted as a subobject $[\![\varphi]\!] : S \rightarrowtail [\![\Gamma]\!]$ where $[\![\_]\!]$ is the interpretation function. The interpretation of a proposition is "true" in this context when $id_{[\![\Gamma]\!]} : [\![\Gamma]\!] \rightarrowtail [\![\Gamma]\!]$ factors through $[\![\varphi]\!]$ which means there exists a monomorphism $\iota : [\![\Gamma]\!]\rightarrowtail S$ such that $[\![\varphi]\!] \circ \iota = id_{[\![\Gamma]\!]}$. When we interpret into the category of sets and functions, this description gives exactly the description I gave in the first paragraph (most closely related to the "alternative" presentation). More generally, though, when we specify an interpretation, we need to specify (among other things) the category we're going to interpret into which will implicitly specify what "subobject" means concretely and thus what "true" means.

One thing we can do is interpret one logic into another so that an interpretation is "true" when it's provable in this second logic. In some sense, this is all we ever really do.

$\endgroup$
  • 1
    $\begingroup$ I understand that we should inherit some truth form the informal mathematics, and this process of logic is like formalizing the syntactical structure of such information, but then what does logic adds? And what happens if our informal reasoning is false? A critical question for me now: Let's say we define epsilon formulas and create the axioms system ZFC and interpret it in $V_\omega$ and do maybe relativisation, I don't know it is okay. In this case, do the rules of logic (both sequent calculus and interpretation rules) tell us everything which is true? I mean is logic + axioms enough? $\endgroup$ – Konformist Liberal May 5 '17 at 10:14
  • $\begingroup$ I edited my question when it was on hold. You may want to look again and edit your answer accordingly. Thanks! $\endgroup$ – Konformist Liberal May 6 '17 at 12:05

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.