# Rewriting ∃! using predicate logic expressions ( “=” excluded)

## 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.

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

• 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. – André Nicolas Apr 5 '16 at 20:08
• 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? – Graffitics Apr 5 '16 at 20:45
• 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). – Graffitics Apr 5 '16 at 21:01
• 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? – P. Lance Apr 5 '16 at 21:05
• @P.Lance No - in fact, what you've written is exactly equivalent to $\exists x A(x)$; can you see why? – 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)$$