A(x) is a predicate logic formula. A is a property (predicate), x is a variable. ∃!A(x) would mean that exactly one x exists which has the property A.

First thing that comes up is: ∃x( A(x) ∧ ∀y( A(y) → (x=y) ),

where y is a variable, but my assignment forbids the use of functional symbols such as =.

How do I rewrite this without using any functional symbols? Only the use of →, ⇔, ¬, ∨, ∧, ∃, ∀, variables, formula A(x) and brackets are allowed.

My idea was to simply write this: ∃x( A(x) ∧ ∀y( A(y) → (A(x)⇔A(y)) )

not sure if it's correct, though.

Thank you in advance.

By the way, the question is not a duplicate, as I'm trying to rewrite this without the use of =.

  • $\begingroup$ Is the use of equality forbidden? It is not a functional symbol. In most current versions of first-order logic, it is a basic logical symbol. I do not understand $A(x)=A(y)$, that is not a well-formed formula. $\endgroup$ – André Nicolas Apr 5 '16 at 20:08
  • $\begingroup$ As André said, the second version is incorrect since you said $A$ is a predicate and not a function; however, the first one should be correct. BTW, you say $=$ is forbidden yet you use it in the second version? $\endgroup$ – Graffitics Apr 5 '16 at 20:45
  • $\begingroup$ Also, $=$ is a binary predicate, not a function (a function returns an object, so you can write things like $f(x) = y$, while $(x=y) = z$ makes no sense). $\endgroup$ – Graffitics Apr 5 '16 at 21:01
  • $\begingroup$ I'm sorry, I meant to write ⇔ instead of =. Well in my course, we were told that equality (=) is a basic binary functional symbol. We use it as =(x,y) .... which basically translates to x=y. Would ∃x( A(x) ∧ ∀y( A(y) → (A(x)⇔A(y)) ) be correct, then? $\endgroup$ – P. Lance Apr 5 '16 at 21:05
  • $\begingroup$ @P.Lance No - in fact, what you've written is exactly equivalent to $\exists x A(x)$; can you see why? $\endgroup$ – Steven Stadnicki Apr 5 '16 at 21:20

You could possibly write it out in second order logic, encoding the following:

$$\forall B~(|A| \ge 0) \land ((A \cup B = \emptyset) \lor (A \subseteq B))$$

If $A$ is empty, then $|A| \ge 0$ fails.

If $|A| = 1$ then $\forall B$ can be partitioned into two cases,

  • $A \cup B = \emptyset$, in which case the proposition holds
  • $A \cup B \ne \emptyset$, in which case the proposition holds ($A$ only has 1 element, that element must be in $B$ if they have an intersection)

If $|A| > 1$, then presumably there is a $B$ where $|A \cup B| = 1$ and $A \not \subseteq B$, such as $A = \{X, Y\}$ and $B = \{X\}$. So the proposition doesn't hold.

So the proposition only holds when $|A| = 1$, and always holds when $|A| = 1$. Encoded it is:

$$\exists ! x~A(x) \equiv \forall B()~\bigg(\exists y ~ A(y) \land \bigg(\bigg(\forall z ~ \lnot A(z) \lor \lnot B(z)\bigg) \lor \bigg(\forall w ~ A(w) \implies B(w)\bigg)\bigg)\bigg)$$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.