1

This is my first post, so if I am doing anything wrong, please notify me.

In predicate logic, can one produce a truth-functional extension of a sentence containing 3 constants for a set containing two constants? For example, is it possible to produce a truth-functional extension of the following sentence : '(∀x)(Px ∨ ¬Px) ∧ ((Pa ∧ Pb) ∧ Pc) for the set for the set {a, b}?

By ''truth-functional extension'' I mean an equivalence without quantifier.

Thanks!

Thrasymaque
  • 81

1 Answers1

0

First realize that the $a,b,c$ in the sentence are constant symbols, while the $a $ and $b$ in the domain are objects, and these are different. That is, an interpretation needs to map each of the constants $a,b,c$ to either one of the objects $a$ and $b$ ...which is a little confusing... But can of course be done. And, once you have decided on such an interpretation(say, constant $a$ maps to object $b$, while constants $b$ and $c$ both map to object $a$), then the truth-functional expansion of your sentence with regard to this interpretation becomes:

$(P(a) \lor \neg P(a)) \land (P(b) \lor \neg P(b)) \land ((P(b) \land P(a)) \land P(a))$

In here, I use a 'new' constant symbol $a$ to refer to object $a$, and 'new' constant symbol $b$ to refer to object $b$, just as you would in any truth-functional expansion.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • This sentence being decidable (since it does not contain any function or relation), we should be able to determine whether it is quantificationally true by building a truth table for the domain {a, b}, am I right? The thing is, by deciding that the constant b and c map to the same object, aren't we presupposing a relation b=c, which would be a binary predicate, thus rendering the sentence undecidable? – Thrasymaque May 09 '17 at 02:50
  • @Thrasymaque Yes, the original quantificational sentence is decidable for the reasons you state ... but looking at its truth-functional expansion for for domain ${ a,b }$ alone may not give you the answer. Now, as it so happens, we can set this particular truth-functional expansion to False, meaning that this truth-functional sentence is not a tautology (I assume that is the decision you consider: is it a tautology or not?), and therefore the original quantificational sentence is not a tautology either (or, as you say, it is not quantificationally true). ... End part I ... – Bram28 May 09 '17 at 03:00
  • ...part II ... But if the TF expansion would have been a tautology, then that would not have told us that the original sentence is quantificationally tue, because all that that would tell us is that the sentence is always true for a domain with 2 objects. But, in order for a sentence to be quantificationally true, it needs to be true in all domains, so you also need to check domains with 3,4,... objects. Which then of course raises the question: how can we cover infinitely many domains? And so how is it decidable whether or not the original sentence is quantificationally true?! End part II – Bram28 May 09 '17 at 03:04
  • ...part III... Well, as it turns out, when you only have monadic predicates, (and thus no identities) then you only need to verify domains of size up to $2^n$ where $n$ is the number of those monadic predicates, and that is because you only have that many kinds of possible objects, because for each predicate, an object either does or does not have that property as expressed by the predicate. And, since you don't have identities, the sentence can't specify that there are multiple such objects. ... End part III – Bram28 May 09 '17 at 03:10
  • You are very helpful. One last thing. I thought that when a sentence is a tautology for a domain containing 2^k objects, where k is the number of distinct one-place predicate, then we could conclude that it was a tautology for every domain. I read in my textbook that this has been proven by Schönfinkel and Bernays. In our case, because the sentence contains only one predicate, P, if it is a tautology for a domain containing 2^1 object, like {a, b} (which it's not), we could conclude it is a tautology for every domain. EDIT : I wrote this comment before reading part III, my bad. – Thrasymaque May 09 '17 at 03:11
  • ... part IV. ... Now, since your sentence has only 1 monadic predicate $P$, if we would have found that the TF expansion would have been a tautology for a domain with 2 objects, then that would have told us that the original sentence is quantificationally true. But, we didn't find that. – Bram28 May 09 '17 at 03:12
  • @Thrasymaque Yes, so you already knew that! :) – Bram28 May 09 '17 at 03:13
  • This helps a lot. My homework is to find out if the set {Ba, Bb, Bc, Bd, Be, Bf, Bg, ¬(∀x)Bx} is consistent. Following your comment, I could produce this extension (by making it a big conjunction) : '(((((((Ba) ∧ Bb) ∧ Ba) ∧ Ba) ∧ Ba) ∧ Ba) ∧ Ba) ∧ ¬(Ba ∧ Bb)'. It turns out this is a contradiction. What's funny is, I think I could build an interpretation that would make it true, thus consistent. [Domain = integers from 1 to 8 ; a = 1 ; b = 2 ; c = 3 ; d = 4 ; e = 5 ; f = 6 ; g = 7 ; Bx = x is less than or equal to 7]. – Thrasymaque May 09 '17 at 03:23
  • I solved it! If I make an interpretation under which b also refers to the same object as a, the extension would be : '(((((((Ba) ∧ Ba) ∧ Ba) ∧ Ba) ∧ Ba) ∧ Ba) ∧ Ba) ∧ ¬(Ba ∧ Bb)' instead of '(((((((Ba) ∧ Bb) ∧ Ba) ∧ Ba) ∧ Ba) ∧ Ba) ∧ Ba) ∧ ¬(Ba ∧ Bb)' and it becomes consistent. – Thrasymaque May 09 '17 at 03:27
  • @Thrasymaque Yes, very good! The trick for that one is to make sure to have an object in the domain that none of the constants a through g denote and that does not have property B – Bram28 May 09 '17 at 11:23