1

I understand most of the rules regarding bound variables, substitution instances etc. (or at least I think I do), but the issue is that I don't seem to be able to take it all the way. For instance, given the interpretation:

Domain: {1,2,3}
a: 1 b: 2 c: 3
F: {1,2}
G: {3}
H: {}
R: {(1,1), (2,1), (1,3), (3,3)}

How does one determine the truth value of the sentence: (Ey)(Ax)Rxy

I understand that in the substitution instance for 'a' we end up with (Ax)Rxa, but I don't know how to take it any farther. Essentially, my textbook explains the rules for getting to this point, but not what the next step is!

Do I end up having to simply evaluate (Ax)Rxa? So: Raa, Rba, Rca, making the substitution instance false since Rca is false and it's a universal quantifier? (And this holds true for the substitution instances for b and c as well, making the whole sentence false, since (Ex) needs at least one instance to be true?)

Another example: (-(Ez)Hz) -> {(Ax)[Fx v (Ey)(-Fy & Rxy)] -> (Az)Gz}

Then (substitution instance for a):
-Ha -> (Ax)[Fx v (Ey)(-Fy & Rxy)] -> (Az)Gz}
-Ha -> {[Fa v (Ey)(-Fy & Rxy)] -> (Az)Gz}
...and so on? Then, once the truth value for substitution instance 'a' has been established, repeat with substitution instance 'b' then 'c'? It seems extraordinarily unwieldy, especially seeing as I would then have to evaluate the "smallest" quantifier by a, b, c first, then do the same with the next largest, and etc.

My final question is regarding a sentence with the form: (Ex)Fx & (Ex)Gx

For substitution instance 'a', would I start with Fa & (Ex)Gx?

Then:
Fa & Ga = F
Fa & Gb = F
Fa & Gc = T

Making the whole sentence true? (due to only needing one instance to be true since it's an existential quantifier). If the sentence was instead (Ax)Fx & (Ex)Gx, I would need to also run the substitution instances for b and c as well (so Fb & Ga, Fb & Gb, etc.).

I've been trying to figure this out for the last couple of days, essentially trying to reverse engineer the process from the examples in my professor's slides and the groundwork rules laid out in the textbook. I hope I'm on the right track, and would greatly appreciate any insight you could help give me!

  • 1
    You might try posting the question to Math.SE, as it's a specific technical question in mathematical logic. – Mozibur Ullah Jan 14 '17 at 3:27
  • When you do, it might be worth adding a reference to the text, and to the the question as the question itself is unclear; have you put in all the relevant information to explain what the textbook question is driving at? There's nothing in the question, for example to say why 'substitution in a' is substituting for y in the formula... – Mozibur Ullah Jan 14 '17 at 3:35
  • Or is the textbook author using a non-standard formalism for set theory? – Mozibur Ullah Jan 14 '17 at 3:36
  • @MoziburUllah I'm afraid I have to admit I don't even really understand what your last comment means, I'm very much a beginner at this. And if you don't understand why "a" is being substituted for "y" in the above sentence, I can only imagine that either I've misunderstood the underlying rules so badly that it's hopeless, or that you aren't familiar with the material. I admit that I did write my question with the idea that the reader would have an understanding of the material, so if that's the case with you please let me know so I can take it back to the drawing board. – DiRekter Jan 14 '17 at 3:46
  • Well, I'd say substitituting a for y in the formula, which explains how your second formula (Ax)Rxa is found from your first, (Ey)(Ax)Rxy. – Mozibur Ullah Jan 14 '17 at 3:56
2

In the case of Ǝy∀x[Rxy], it's not enough to substitute only one value for y, because it's saying that there exists at least one y such that ∀x[Rxy], but it doesn't say which one. That means your first substitution might fail, but there still might be another substitution that will work. For that reason, you have to substitute every value y in the domain to see if there is one that will work for every x.

In terms of the sets, we are looking for a such that {(1,a), (2,a), (3,a)}. However in the set R, there is no ordered pair which satisfies that condition, so the statement is false.

For example, We might think of this in terms of computers being connected to different things:

  • Rxy = x is connect to y

Domain for x: {Sue's computer, laptop, Joe's computer} Domain for y: {modem, printer, UPS}

If Ǝy∀x[Rxy] is true, there exists one connection that all of the computers share, but according to the set R: {(1,1), (2,1), (1,3), (3,3)}:

  • Sue is connected to the modem (item 1 to 1)
  • The laptop is connected to the modem (item 2 to 1)
  • Sue is connected to the UPS (item 1 to 3)
  • Joe is connect to the UPS (item 3 to 3)

There is no connection that is common to all the computers in the domain, so Ǝy∀x[Rxy] is false. It would be true, for instance, if the laptop were also connected to the UPS. In that case, the UPS would be an instance of y to which all the computers would be connected.

I'm hoping that helps you understand your other questions, but I'm not sure how they can be answered in the way you worded them.

Your last question seems to be making some mistaken assumptions about how the truth conditions are satisfied. I don't understand for example how you came to the conclusion that "Fa & Ga = F" and "Fa & Gc = T". Since you have two existential quantifiers in (Ex)Fx & (Ex)Gx, it's not permitted to assume that both are instances of the same variable:

"If you can pick, quite arbitrarily, an element of the domain which is a perfectly typical case just in the sense that you know nothing about that particular individual other than that it is an element of the domain, and you can derive the desired conclusion from a formula about that typical disjunct (TD), then you may infer that same conclusion from the original formula. This gives us a very clear picture of the pattern of inference which any application of the rule EE [existential elimination] encodes." (Paul Tomassi)

If you need to conclude that Fa & Ga, that result has to be arrived at by some other means than simply assuming that both F and G may be predicates of a.

  • +1:I'm just noting that you're reading the binding in a different direction to what I was; it's the reading that I would have used, usually; but for some reason, I thought the formal order would be correct - it's one reason for my comments above; though I suppose I could have been clearer with them. – Mozibur Ullah Jan 14 '17 at 10:19
1

Given the domain

D:={1,2,3}

from which variables are drawn from

We consider the relation

R={(1,1), (2,1), (1,3), (3,3)}, ie a subset of D x D

We now consider the formula

(Ey)(Ax)Rxy

We want to establish its truth value over this domain, ie x & y are both drawn from the domain D.

Now x is bound to A (ie All) first; and y is bound to E (ie There Exists) second (you read bindings from right to left, it matters which direction you read them from and we read them right to left because that is how well-formed formulas are built up in formal grammars).

So the formula reads in English

for all x, there exists a y such that R(x,y) holds

What this means is for each x in all of D there is a y such that R(x,y) holds

Because x is bound first, we must first consider x ranging over D, ie over {1,2,3}

Thus we consider the three substitutions:

EyR(1,y), this is satisfied by both (1,1) & (1,3) in R, so this substitution instance is true

EyR(2,y), this is satisfied by (2,1) in R, so this instance is also true

EyR(3,y), this is satisfied by (3,1) in R, so this is also true.

Since all substition instances have been verified, the forumula holds; ie it is true.

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.