3

So I have been looking at this question: How to convert an English sentence that contains "Exactly two" or "Atleast two" into predicate calculus sentence? And the way I would do this didn't really show up there.

So I would like to write "Exactly two..." like this:

Let $P(x)$ be a predicate, so to say exactly two terms satisfy $P$ I would write: $$\exists x \exists!y((x \ne y) \wedge P(x) \wedge P(y))$$

Now, this would ensure that $x \ne y $ and since $=$ is an equivalence relation, it ensures that there is only one such $x$ and $y$.

Would this be a right way to write it? I'm not a mathematican, so I was unsure If I can provide this as an answer, but it got me curious as my notation is much shorter than the ones proposed in the linked question.

Blue
  • 75,673
Karol Szustakowski
  • 91
  • 1
  • 6
  • 1
    Well, how do you define $\exists!$? – Qi Zhu Jun 14 '20 at 14:49
  • 3
    Instead of using the "exactly one" quantifier $\exists!$ why don't you just use the "exactly two" quantifier $\exists_2$? $$\exists_2xP(x)$$ – bof Jun 14 '20 at 15:04
  • 2
    In the usual formulations of the predicate calculus, the unique-existence quantifier is not a primitive symbol, so you'd have to expand your formula by the expression for $\exists!$ in terms of primitive notation. If, on the other hand, you use an unusual formulation of the predicate caclulus, then you need to say which formulation you want --- presumably including $\exists!$ but not $\exists_2$ as in the comment by @bof. – Andreas Blass Jun 14 '20 at 16:15
  • 1
    Why do all of the answers here have a downvote? What am I missing?!? – user1729 Jun 16 '20 at 15:25
  • 1
    Perhaps the answers were downvoted because none of them attempts to answer the question that was asked, which was "would this be a right way to write it?" Each one all give alternative expressions, which might be taken to imply that OP's proposal is wrong. But it's not wrong, and nobody said this, or discussed OP's proposal. – MJD Jun 16 '20 at 16:05
  • @JCAA MJD's point, I believe, is that none of the answers explain this. They should say: "By predicate calculus I mean this. Under this interpretation the OPs answer is wrong because of this. A correct answer is this". Currently, too much information is contained in the comments. – user1729 Jun 17 '20 at 07:06
  • @MJD I found the OP's formulation to be unconventional and confusing. Its correctness was not immediately apparent to me. I'm guessing that it would also be difficult to work with in formal proofs. It may well be correct. I will try to formally prove it equivalent to my suggestion. – Dan Christensen Jun 17 '20 at 14:43
  • I have been able to show that my formulation follows from that of the OP, but not the converse. To get rid of the $\exists!$ in the OP's formulation, I used $\exists x~ \exists y~ \forall z~ [x\neq y \land P(x) \land P(z) \iff z=y]$ – Dan Christensen Jun 17 '20 at 20:26
  • FYI A mathematician, using the notation of set theory, might simply write instead, $P={ x, y }$, $x\neq y$. Or, more formally, $\exists x ~\exists y~ [x\neq y \land \forall z~[z\in P \iff z=x \lor z=y]]$. – Dan Christensen Jun 18 '20 at 14:02

4 Answers4

2

Your expression translates to something like:

There exists an element $x$, and a unique element $y$ distinct from $x$, such that $P(x)$ and $P(y)$ are true.

This is equivalent to saying that there are exactly two elements making $P$ true, so is correct.

You can generalise your characterisation to define quantifiers $\exists^n$ for $n \ge 1$ meaning 'there exist exactly $n$' in the following way:

  • Define $\exists^1 x\, P(x)$ to mean $\exists! x\, P(x)$;
  • Define $\exists^{n+1}x\, P(x)$ to mean $\exists x\, \exists^n y\, (x \ne y \wedge P(x) \wedge P(y))$

Note that the recursive definition of $\exists^2$ collapses to precisely the definition you made.

Clive Newstead
  • 64,925
  • As I find all answers really helpful this is the only answer that has explicitly tackled my question, so I have marked it as accepted. Thank You. – Karol Szustakowski Jun 17 '20 at 21:53
  • I think you will find this notation is not widely used or understood by mathematicians. – Dan Christensen Jun 18 '20 at 04:13
  • A mathematician might write instead, $P={ x, y }$, $x\neq y$. – Dan Christensen Jun 18 '20 at 13:49
  • @DanChristensen: I don't know of any context where the notions of predicates and sets are conflated in this way. I wouldn't suggest that someone write $\exists^2$ without first defining what their notation means, but I certainly wouldn't suggest identifying $P$ with ${ x : P(x) }$. (I say this not just as a mathematician, but as a logician too.) – Clive Newstead Jun 18 '20 at 16:15
  • @CliveNewstead With predicate $P$, we have $P(a)$ being true is iff $a=x$ or $a=y$ where $x\neq y$. Similarly, with set $P$, we have $a\in P$ being true is iff $a=x$ or $a=y$ where $x\neq y$. Use a different symbol for the set if you find it confusing to use the same one for both. – Dan Christensen Jun 19 '20 at 02:10
  • @DanChristensen: I understand what you meant, but if your quibble with the notation $\exists^2$ is that you'd need to first define it in order for it to be understood, then the same goes for your identification of $P$ with ${ x : P(x) }$ (which is suggested by your comment above, where you write $P = { x,y }$). There is no convention that allows you to replace '$P(x)$' with '$x \in P$' in mainstream mathematics. – Clive Newstead Jun 19 '20 at 02:11
  • @CliveNewstead Why introduce unconventional notation unless absolutely necessary? It isn't in this case. Keep it simple. – Dan Christensen Jun 19 '20 at 02:16
  • @DanChristensen: I think we agree! – Clive Newstead Jun 19 '20 at 04:07
  • @CliveNewstead "There is no convention that allows you to replace 'P(x)' with 'x∈P' in mainstream mathematics." Not in general, but it works in this case. – Dan Christensen Jun 19 '20 at 04:28
  • @DanChristensen: You're missing my point; I'm not saying it doesn't 'work'. It works because you identified $P$ with ${ x : P(x) }$. You can 'always' do this, because $P(x)$ is true if and only if $x \in { x : P(x) }$—so yes, it works in this case and in all cases—what I'm saying is that writing '$x \in P$' is not a standard thing to do when $P$ is a predicate, just like writing $\exists^2 x, P(x)$ is not a standard thing to do. Both $x \in P$ (when $P$ is a predicate) and $\exists^2 x, P(x)$ are nonstandard notations, both would need additional clarification if used. – Clive Newstead Jun 19 '20 at 12:18
  • @CliveNewstead Russell's Paradox has shown us that you cannot always assume that for any unary predicate $P$, we CANNOT assume there exists a set ${ x : P(x)}$. If, however, $x$ and $y$ are elements of a set and $x\neq y$, then we can formally construct (i.e. prove the existence of) set $p$ such that $\exists a~\exists b~[a\neq b \land \forall c ~[c\in p \iff c=a \lor c=b]]$. Now, we can also define unary predicate $P$ such that $\exists a~\exists b~[a\neq b \land \forall c ~[P(c) \iff c=a \lor c=b]]$. (Used different symbols $p$ and $P$ so as not to confuse you.) – Dan Christensen Jun 19 '20 at 14:08
  • @DanChristensen: Sure, but funnily enough, the notation $x \in A$ can be used when $A$ is a proper class. (Set theorists write stuff like '$x \in V$' all the time.) But what 'proper class' usually means is '(meta-)equivalence class of predicates under logical equivalence', so what '$A$' really means when $A$ is a proper class is ${ x : P(x) }$ for some representative $P(x)$ of the equivalence class. So this means you're almost justified in writing $P = { x : P(x) }$, but this still conflates the notions of class (= equivalence class of predicates) and predicate (= representative). – Clive Newstead Jun 19 '20 at 14:37
  • But still, foundational concerns aside, I'm not saying I'm confused by what you mean by $x \in P$, or that you can't use that notation if you define it first—I'm saying that it's not standard, just as $\exists^2$ is not standard. If it were standard, we wouldn't be having this discussion. – Clive Newstead Jun 19 '20 at 14:40
  • @CliveNewstead I am "conflating" nothing. I am just pointing out the similarities in structure of the definitions of the set $p$ and the predicate "P". The only difference is that former has the string "$c \in p$ in the place the latter has "$P(c)$". Neither makes use of any unconventional notation. – Dan Christensen Jun 19 '20 at 14:53
  • @DanChristensen: In that case I don't think we disagree about anything. Your first comment on this answer seems to suggest that "$P = { x, y }, x \ne y$" is another way of writing "$\exists^2 x,, P(x)$", which does conflate the set and the predicate—that might not have been what you meant, but that's the only way I can see to interpret it (since you never said, for instance, that $P$ denotes the set of elements for which $P(x)$ is true). That is what triggered this discussion. Like I said, I don't think we actually do disagree about anything, except the intention of your original comment. – Clive Newstead Jun 19 '20 at 15:13
0

Exactly two terms satify $ P$ can be written as

$$\exists !(x,y) \;:\; x\ne y \wedge P(x) \wedge P(y)$$

or also

$$\exists x\exists y \; : \; x\ne y \wedge P(x) \wedge P(y) \wedge \Bigl( \forall z \; (z\ne x\wedge z\ne y \; \implies \;\lnot P(z))\Bigr)$$

hamam_Abdallah
  • 62,951
0

Perhaps a more standard definition of $P$ (with a biconditional) and easier to work with would be:

For distinct $a$ and $b$, we have $P(c)$ being true if and only if $c=a$ or $c=b$.

$\exists a: \exists b: [a\neq b \land \forall c: [P(c) \iff c=a \lor c=b]]~~~$

FYI: Using the notation of set theory, $P$ might instead be a set such that

$~~~P=\{a, b\}$, $~a\neq b$

Or, more formally,

$~~~\exists a ~\exists b~ [a\neq b \land \forall c~[c\in P \iff c=a \lor c=b]]$

Here, "$c\in P$" has simply replaced "$P(c)$" in this case.

Dan Christensen
  • 14,529
0

Exactly two:

$$\exists x \exists y(Px \land Py \land x \neq y \land \forall z(Pz \implies (z =x \lor z=y)))$$

N. Bar
  • 1,600