retagged by
6,173 views
41 votes
41 votes
Consider the following first order formula:

$\left ( \matrix{
    \forall x \exists y : R(x,y)
    \\[1em] \Large \land \\[1em]
    \forall x \forall y : \left ( R(x,y) \implies \lnot R(y,x) \right)
    \\[1em] \Large \land \\[1em]
    \forall x \forall y \forall z : \left ( R(x,y) \land R(y,z) \implies R(x,z) \right )
    \\[1em] \Large \land \\[1em]
    \forall x: \lnot R(x,x)
}\right )$

Does it have finite models?

Is it satisfiable? If so, give a countable model for it.
retagged by

4 Answers

Best answer
43 votes
43 votes

Let's break it down. Consider an ordered structure (directed graph).

  1. $\forall x \exists y : R(x,y) \equiv$ Every vertex has at least $1$ outgoing edge.
     
  2. $\forall x \forall y : \left ( R(x,y)\implies \lnot R(y,x) \right)\equiv$ If there is a directed edge from vertex $u$ to vertex $v$, there should not be an edge back from $v$ to $u$. That is, our relation $R(x,y)$ is asymmetric.
     
  3. $\forall x \forall y \forall z : \left ( R(x,y) \land R(y,z) \implies R(x,z) \right )\equiv$ If $u \to v \to z$, then $u \to z$ is also true. That is, our relation $R(x,y)$ is transitive.
     
  4. $\forall x: \lnot R(x,x) \quad \equiv$ We cannot have a self-loop in the graph. That is, $R(x,y)$ is irreflexive.

Now, such a non-trivial $\left(\text{size} > 0\right)$ finite structure cannot exist.

Proof by contradiction:

Assume, for the sake of contradiction, that such a finite structure $\bf{S = (V,E)}$ exists. Since it is finite, let the number of vertices in this structure be $\bf{|V| = n, n \in \mathbb{N}, n>0}.$

Edit: A summarized version of the following proof is in the comments. You can directly skip to that.


Lemma $1$: $v_n$ has an incoming edge from every vertex $v_i, i < n$

Proof by Induction:

Induction Hypothesis: $P(n) = $For every $1 \leq i < j \leq n$, there is an out edge from vertex $v_i$ to vertex $v_j$, that is $v_i \longrightarrow v_j$.

Base Cases:

  • Let $n = 2$.
    $v_1 \longrightarrow v_2$ must be true since there has to be an out edge from $v_1$ (Property A) and the only available vertex is $v_2$ (no self loops allowed - Property D).
    Hence, our hypothesis $P(2)$ is satisfied.
  • Let $n = 3$.
    There must be an out edge from $v_1$ to some vertex. Let's call that vertex $v_2$, that is $v_1 \longrightarrow v_2$.
    Similarly, there must be an out edge from $v_2$. But due to property B, we can't have an out edge from $v_2$ back to $v_1$. Hence, the out edge from $v_2$ must lead us to a new vertex. Lets call that $v_3$.
    Since $v_1 \longrightarrow v_2 \longrightarrow v_3$, due to Property C, we must have $v_1 \longrightarrow v_3$.
    Hence, our hypothesis $P(3)$ is satisfied.

Inductive Step:

For $P(n+1)$: The $n$th vertex $v_n$ must have an out edge. Since $P(n)$ is true, the $n$th vertex has incoming edges from all vertices $v_i, i < n$. Hence, the out edge from $v_n$ cannot be to any of those vertices. Self loops aren't allowed either.

Hence, the out edge from vertex $v_n$ must be to the new vertex $v_{n+1}$. That is, $\substack{\searrow\\[0.5em]\longrightarrow\\[0.5em]\nearrow}\; v_n \longrightarrow v_{n+1}$

Since every vertex $v_i, i < n$ has an out edge to $v_n$, and $v_n$ has an out edge to $v_{n+1}$, due to Property C, we have that $v_i$ has an out edge to $v_{n+1}$. That is, $v_i \longrightarrow v_{n+1}, \forall i \leq n$.

This is exactly what $P(n+1)$ states.

Hence, $P(n) \implies P(n+1)$.

Q.E.D

Since $P(n)$ is true as proven above, every vertex $v_i$ must have an out edge to the vertex $v_n$.


Since the nth vertex has incoming edges from all other vertices (Lemma 1), it cannot have an out edge to any vertex. It can't have self loop either. Thus, it fails to satisfy Property A.

Hence, our assumption that S exists leads to a contradiction.

Q.E.D


The given logic formula can be satisfied by an infinite model.

For example, $R(x,y) \iff x < y, \quad x,y \in S$, where $S$ is any infinite ordered set, satisfies the given formula.

edited by
29 votes
29 votes

Claim 1 : 
If we have a non-empty finite set $A$, then there does not exist any relation $R$ on $A$ which satisfies all the following four properties : 
1. Every element of $A$ is related to some element.
2. Relation R is Asymmetric. 
3. R is transitive.
4. R is irreflexive. (This is redundant because it is covered by "being asymmetric"..So, even if it is Not given, the claim/question remains unchanged)

Proof : 
Proof is simple and idea for the proof is that assume you list all the elements of set A as $a1,a2,a3,....,a_m$
Now, first property says you need to related every element to some element. So, you need to relate $a1$ with some element. Also, Property 2 says that No element is related to itself. So, we need to relate $a1$ with some different element.

Without loss of generality, assume $(a1,a2) \in R.$
 Now you need to relate $a2$ with some different element. But $a2$ can't be related to $a1$ because of second property. So, Without loss of generality, assume $(a2,a3) \in R.$  
 Now you need to relate $a3$ with some element. But $a3$ can't be related to $a1,a2$ because of second, and third property. $a_3$ can’t be related to $a_2$ because of Asymmetric property, and $a_3$ can’t be related to $a_1$ also because If $a_3$ is related to $a_1$ then by Transitive property, $a_3$ will also be related to $a_2$ (because already $a_1$ is related to $a_2.$)

So, Without loss of generality, assume $(a3,a4) \in R.$  
By now you must have observed that if we proceed in this manner, then when we pick element $a_i$ to relate it to some element then we cannot relate it with any of the elements before it i.e. we can't relate $a_i$ with $a1,a2,a3,\dots, a_{i-1}$, so, we need some new element for $a_i$. So, since we have assumed that $A$ is finite, so, at some point we will come to the last element $a_m$ and then we can't relate $a_m$ with any other element, so, it will violate property 1. If we relate $a_m$ with some element then it will violate property $2.$ 
Hence, it claim 1 is proven. 

Now, the given question has four FOL(first order logic) formulas which mean these four properties that we stated in the claim 1. 
So, as long as we have some Non-empty finite set $A$ then we cannot satisfy all these four FOL formulas simultaneously. Hence, we don't have a Finite Model. 
"Model" for a FOL formula F means "some interpretation" for F in which F is True.

We say M is a model of a sentence α if α is true in M. 

Watch @GO Classes Discrete mathematics 2023 course, First order logic, Lectures 17, 18, 19, which cover Model concept in First order logic, as well as in propositional logic. Watch these 3 lectures. It will help you understand many concepts very clearly.

https://www.goclasses.in/s/store/courses/description/2023-Discrete-Mathematics


https://www.cs.umd.edu/~nau/cmsc421/chapter08.pdf


http://www2.imm.dtu.dk/courses/02286/Slides/FirstOrderLogic%20-%20SatisfiabilityValidityLogicalConsequenceTrans.pdf

 

edited by
10 votes
10 votes

consider the figure, draw edges as per the given proposition, there be a state in which you do whatever you want keeping the given conditions in view, you will always violate some, all are not true together.

In this case, shown by the diagram above, the proposition which says that there should not be any self loop is violated. There is no finite model to satisfy this.

3 votes
3 votes

Using https://math.stackexchange.com/questions/2229066/meaning-of-finite-and-hence-infinite-model-in-mathematical-logic as a reference, you could interpret $R$ as $<$, and so, the first predicate means that for all $x$, there is a $y$ such that $x < y$.

With a finite model, or finite domain, this predicate itself is violated. Take $\{1, 2\}$ as an example - there is no number greater than 2. So there is no way you could satisfy the whole set of statements with a finite model.

This is an intuitive answer at best, of course it requires a rigorous proof to show that this is true.

Related questions

20 votes
20 votes
3 answers
2
Akash Kanase asked Apr 18, 2016
3,454 views
Consider the binary tree in the figure below:Give different steps for deleting the node with key $5$ so that the structure is preserved.