1

The question is the following:

(a) Specify a sentence in which the following are all true:

∀x¬Rxx, ∀x∃yRxy, ∀x∀y∀z((Rxy ∧ Ryz) → Rxz).

====

For (a), I believe this structure requires an infinite domain, in which case the structure looks like this:

DA = {0, 1, 2,...}

|R|A = {<0, 1>, <1, 2>, <2, 3>...}

Improve this question

3 Answers 3

Reset to default
1

For b):

Assuming you cannot have an empty domain (otherwise, all sentences would be vacuously true, and thus true in a finite domain after all), you need at least one object. This object needs to relate to something, but that something cannot be itself, so you need a second object b. b needs to relate to something as well, but that cannot be b itself, and also not a, otherwise by transitivity b relates to b after all. So, b needs to relate to an object c. Etc.

And to make that 'Etc.' a little more hard: Note that any model can never have a cycle of aRb, bRc, cRd, ... yRz, zRa, for once you have such a cycle, then by transitivity, all opjects in that cycle end up relating to each other, including themselves, thus contradicting irreflexivity. But if there is no cycle in your structure, then it is possible to 'line' up all objects from 'left' to 'right', such that any R relation goes from 'left' to 'right' as well. But with a finite number of objects, that means that you end up with a 'rightmost' element ... which therefore does not relate to anything, and that contradicts the ∀x∃yRxy

So, you can indeed not have any finite model

For c) No, you can't just negate the statement to force a finite model. We showed that in order to satisfy the sentences, we need an infinite domain, but all that that means is that in a finite domain, the negation of the statement is indeed true. However, that does not rule out having infinite domains where the negation is also true. Indeed, it is easy to create an infinite model of the negation: just have infinitely many objects, and have them all relate to each other (i.e. define R to be reflexive)

Improve this answer
4
  • Thank you. For b) in my proof thus far, I've gotten to the part where we must assume a third element, a2, since two elements will violate statement 1 (ie, ∀x¬Rxx). Now to the "hard" part. I understand the "cycle" thing in a kind of abstract way, but I don't know how to put this down in a proof. How can I show that for any elements a0...an, this formula eventually produces a cycle.
    – vundabar
    Jun 1, 2018 at 21:54
  • @vundabar well, if you don't have a cycle, then you can line up all objects with relations depicted as arrows going from left to right and then the rightmost one has no outgoing arrow ... which contradicts AxEy xRy ... so in order for Ax Ey xRy to be true, you must have a cycle, but now of course you have a problem with transitivity and irreflexivity. I think that's proof enough ....
    – Bram28
    Jun 1, 2018 at 22:00
  • Unfortunately, it seems that one of the drawbacks of not knowing how to proof very well is not knowing when I've done enough! Could I also say something like the following: as per statement 3, since all pairs in the domain have a transitive relation, then any structure allowing b>a allows the relation R(a, b) and R(b, a), producing R(a, a), in violation of statement 1. To be clearer, what I'm trying to do is show in a more concrete way what it is that produces these cycles.
    – vundabar
    Jun 1, 2018 at 22:26
  • @vundabar It is not true that for all pairs you have Rab and Rba ... you have that if Rab and Rbc, then Rac. But if you have a cycle of, say, Rab, Rbc, Rcs, and Rda, then by that transitivity, you have Rac because of Rab and Rbc, and since you also have Rcd, by transitivity again you have Rad, and since you have Rda, that gives Raa. So yes, cycle +Transitivyty -> reflexivity
    – Bram28
    Jun 2, 2018 at 0:24
0

In a), you essentially want all pairs $(n,m)$ with $n < m$ in your relation.

For b), consider the following process: Start with some element $a_0$. Then pick some $a_1$ such that $R(a_0,a_1)$ - you can do this by Sentence 2. Then pick $a_2$ such that $R(a_1,a_2)$, etc. In a finite structure, there would need to be a repetition at some point, meaning that there are $i < j$ with $a_i = a_j$ (Pidgeon hole principle). Then you use Sentence 3 (possibly very often) to obtain a contradiction to Sentence 1.

Improve this answer
7
  • The formatting looks a bit funky. Could you edit that please?
    – vundabar
    May 31, 2018 at 23:57
  • 1
    This requires mathjax browser extension to see it normally. @vundabar
    – rus9384
    Jun 1, 2018 at 7:27
  • mathjax is not available on philosophy.stackexchange.com, which is nothing I can fix.
    – Arno
    Jun 1, 2018 at 7:49
  • I was able to translate the text on the mathjax website. Thanks. @Arno you say: "In a finite structure, there would need to be a repetition at some point. Then you use Sentence 3 (possibly very often) to obtain a contradiction to Sentence 1." What exactly do you mean by "repetition"? Do you mean a repetition such that we would need to derive R(a1, a1), which we could then say is illegal because of the sentence ∀x¬Rxx? How do I show the necessity for this repetition?
    – vundabar
    Jun 1, 2018 at 10:38
  • I've clarified what "repetition" here means, and given a hint on how to argue its necessity. We don't necessarily get R(a1,a1) though, but some R(ai,ai).
    – Arno
    Jun 1, 2018 at 11:38
0

As a pedantic point, your relations would also work if the domain (and hence the interpretation of R) was the empty set, so your assertion that the domain needs to be infinite isn't quite right. An existential addition to this (for example, there is an element 0) would do the trick there if you wanted to require an infinite domain.

Improve this answer

You must log in to answer this question.

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