Help needed with first-order logic semantics: true or false

Question

I'm having some difficulties on solving the tasks below. I would really appreciate some help.

Here is the tasks:

For each of the following formulas, give a model which makes the formula true. Let the domain be $\{$$1, 2$$\}$. It is sufficient to provide the interpretation of the relation symbols $R$.

1. $\forall x \forall y Rxy$

2. $\exists x \forall y Rxy$

3. $\forall x \exists y Rxy \land \lnot \exists xRxx$

4. $\exists x \exists y (Rxy \land \lnot Ryx) \land \forall xRxx$

I would appreciate if someone could show me or help me on how I can solve these tasks.

Thank you.

Answer 1

Some hints to help you on your way

One preliminary point. None of the wffs involve free variables, so the question title is either misleading, or betrays a misunderstanding. So (A) first make sure you understand why no variable is bound.

You have a two-element domain. (B) What are some examples of a relation $R$ on this two element domain? [You can specify a relation by specifying which pairs of object it holds between.]

Supplementary question: (C) How many different relations on a two element domain can there be [assuming that we count $R$ and $S$ as the same relation if they obtain between just the same pairs of objects]? Don't forget the relation which never holds, and the relation which always holds!

OK, you've now got some examples to play with. (D) Can you now see how to choose relations which make (1) and (2) true?

(E) Do you see how to parse the wffs (3) and (4)? What is the main logical operator? Do you see they are both conjunctions of simpler wffs. So try tackling the simpler parts first ... and seeing if you can get them to be simultaneously true.

Answer 2

Since the OP asked that I answer, I'll give it a try. Here are my notes (i'll try to latex this later):

The graphs (top-bottom) correspond to formulas (1-4). Here is a procedure for generating them:

1. Given the domain consisting of 1 and 2, we start by drawing two circles labeled '1' and '2'.

2. Then draw the arrows (the relation R) depending on what each formula says. Lastly:

3. Either find a nice natural relation on numbers that gives us those arrows,

4. Or define an ugly relation by simply gathering the related pairs into a set.

Example 1. Formula (1) says: $\forall x \forall y Rxy$, i.e., there is an arrow linking any two objects. So we draw arrows from 1 to 2, from 2 to 1, and also we must not forget to draw arrows from 1 to 1 and from 2 to 2 (because x and y can be the same object). Once this is done, you get the first graph shown above. I have written 'A' instead of a solution so that you can try to solve it.

Example 2. Formula (2) says: $\exists x \forall y Rxy$, i.e., there is some circle that has an arrow going to every circle (including itself!). This corresponds to the second graph above. (Note that there could be arrows going out of 2 to 1 or to itself, but we don't care about those, because the arrows from 1 already satisfy formula (2).) Again, once the graph is drawn, either find a nice formula (I've called it 'B') or define R as an ugly set.

I'll let you make sense of graphs 3 and 4, but let me just point out what makes graphs 2 and 4 different: formula (4) forces R to be asymmetric and reflexive, while (2) doesn't care about symmetry and doesn't impose reflexivity (that's why there is no need for an arrow, in graph 2, from 2 to 2).

Your task. Is to find the nice numerical relations A, B, C, and D (hint: they're all very simple). If you're having trouble, Peter Smith's post contains very helpful hints; for example, he talks of a relation that always holds (hint: can you think of a natural reflexive relation between numbers?). If the hints don't help, let me know and I'll tell you what I have come up with for A, B, C, and D.

---

$$\fbox{Answers}$$

For the A graph, I have: $Rxy \equiv (x = x)$. Notice that there is an arrow going from every point to every point. This means that the relation, in this model, holds everywhere. So any relation that always holds will do the job of R. I have chosen '$x = x$'. You can test it out: plug in any pairs of {1,2} for x and y into Rxy. Since the value of y is not used inside the relation, there are two possibilities: $(1 = 1)$ and $(2 = 2)$, and both hold.

For the B graph, I have: $Rxy \equiv (x \le y)$. Had there been no reflexive loop on 1, we could just use less than, but since we also need to satisfy $(1 R 1)$, we have to add the case where x and y are identical.

For the C graph, I have: $Rxy \equiv (x \not= y)$. I chose this because of the fact that there is an arrow only between any two distinct objects.

For the D graph, I have chosen one of the other three answers. I'll let you figure out which. After you do, just edit the answer into this post, or leave a comment and I'll update it.