0
$\begingroup$

I have following facts

  1. No set is an element of itself.

  2. A set x is a subset of a set y iff every element of x is an the element of y

  3. Something is an element of the union of two sets x and y iff it is an element of x or an element of y

I have represented the above fact in fol as follows

  1. $\forall x \neg Elt(x,x)$
  2. $\forall x \forall y \forall z \ Sub(x,y) \equiv (Elt(z,x) \rightarrow Elt(z,y))$
  3. $\forall x \forall y \forall z \ Elt(z,u(x,y)) \equiv (Elt(z,x) \vee Elt(z,y))$

We called the above fact as T

As nonlogical symbols, use Sub(x, y) to mean "x is a subset of y," Elt(e, x) to mean "e is an element of x," and u(x, y) to mean "the union of x and y."

I am not able to interpret following statement in FOL.

  • Show using logical interpretations that T does not entail that the union of x and y is equal to the union of y and x.

  • Let A be any set. Show using logical interpretations that T entails that there is a set z such that the union of A and z is a subset of A.

Question from Knowledge Representation and Reasoning. To understand Knowledge Representation and Reasoning, I am trying to solve the problem set of that book.

$\endgroup$
6
  • $\begingroup$ Your language is mimicking elementary set theory. In it, the equality of sets is defined through the subset relation: $A=B \text { iff } A \subseteq B \land B \subseteq A$. $\endgroup$ – Mauro ALLEGRANZA Oct 12 '17 at 6:20
  • $\begingroup$ In your knowledge Base there is not that information... $\endgroup$ – Mauro ALLEGRANZA Oct 12 '17 at 6:21
  • $\begingroup$ But how to prove fact 1: "not entail" ? Finding a suitable interpretation of the "objects" and predicates that satisfy the theory $T$ and does not satisfy $un(x,y) = un(y,x)$. $\endgroup$ – Mauro ALLEGRANZA Oct 12 '17 at 6:27
  • $\begingroup$ Consider the wrong example: domain $\mathbb N$ and interpret $El$ with $<$. Clearly: $\forall n \lnot (n < n)$ and thus the first axiom is satisfied. This is the way to interpret the theory. $\endgroup$ – Mauro ALLEGRANZA Oct 12 '17 at 6:29
  • $\begingroup$ $un$ is a function symbol: $un(x,y)$ denotes an object of the domain. In order to find the suitable interpretation, we have to think at non-symmetrical operations. Arithmetical ops like $x+y$ and $xy$ are symmetrical; thus, they will not do. $\endgroup$ – Mauro ALLEGRANZA Oct 12 '17 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.