How do you do First order models here?

38 Views Asked by At

So I have a question as follow:

Question 1

And I wonder if e.g. $\exists x[R(x,x)]$ means that there are things like , or does it mean that there are the same things (like twice in R) that are e.g. $<a,a>$ and $<a,a>$?

Also, my next question is if there is $\exists x\exists y[R(x,y)]$, does it mean there exist things in R like e.g. $<a,b>$?

I would appreciate any help as I'm really confused about what it actually means and I can't find any resources online.

1

There are 1 best solutions below

1
On

(I'll first note that there appears to be a couple of errors in this question - presumably the functions listed should be $\delta_1$ through $\delta_4$, rather than having two copies of $\delta_2$ and no $\delta_4$.)

$\exists x [R(x, x)]$ means "There is an element $x$ in our domain such that $R(x, x)$ holds, i.e. it is in a relation to itself.

Outside of this kind of problem, an example would be if we're working in real numbers and $R(a, b)$ means "$b$ is equal to the square of $a$". In this case, $\exists x [R(x, x)]$ is true, because we can take, for example, $x = 1$ and note that $1^2 = 1$, so $R(1, 1)$ is true.

For the ones with two qualifiers, always work from the outside in, reading as "[There exists / for all] $x$, such that [there exists / for all] $y$, R(x, y) holds". For example, $\forall x \exists y [R(x, y)]$ means "For every $x$ in the domain, there exists a $y$ such that $R(x, y)$ holds", i.e. "Every value in the domain is represented as the first member of at least one pair". By comparison, $\exists x \forall y [R(x, y)]$ means "there is an element $x$ in the domain such that $R(x, y)$ holds for every $y$ in the domain", i.e. there's a single element that pairs with every element in the domain.

Again going outside this problem, if $R(x, y)$ is "$y$ is the square of $x$" then $\forall x \exists y [R(x, y)]$ is true because given any real value $x$ we can find a $y$ such that $y = x^2$, but $\exists x \forall y [R(x, y)]$ is definitely false because there isn't one single value of $x$ such that every $y$ is its square. On the other hand, if $R(x, y)$ represented "$x$ is less than the square of $y$", then $\exists x \forall y [R(x, y)]$ is true because we can pick, for example, $x = -1$ and it is true that it is less than the square of every real number.