6
$\begingroup$

I know that I can say ∃x(P(x)) which means there is at least one x for P(x), but how do I express for exactly one?

Here's the questions:

(a) Not everyone in your class has an internet connection. (b) Everyone except one student in your class has an internet connection.

So for the first one I wrote:

(a) ∀x∃x(¬I(x))

"For all x there exists an x (or more) such that an x does not have an internet connection" (where I is the state of having an internet connection)

(b) Don't know how to express

I could be wrong please correct me since i'm pretty new to expressing this all mathematically

Thanks for help

$\endgroup$
1
12
$\begingroup$

You are correct that "There exists ..." means that there exists at least one. To say that there is exactly one you need to say the following:

$$\exists x(\varphi(x)\land\forall z(\varphi(z)\rightarrow z=x)).$$

Namely, there exists $x$ satisfying whatever, and whenever $z$ satisfies whatever, $z$ has to be equal to $x$. Also note the scope of the existential quantifier is over the entire statement.

(As a mathematical example, There exists a natural number which is larger than $1$; but there exists exactly one natural number which is smaller than $1$ (here we take $0$ to be a natural number))

$\endgroup$
6
  • 3
    $\begingroup$ Some publications use $\exists !$ as a shorthand to say there is exactly one. I imagine that is not appropriate for this question. True, though. $\endgroup$
    – Will Jagy
    Sep 30 '15 at 23:08
  • 2
    $\begingroup$ Yes, but this is really a shorthand. Just like $\exists x<n\ldots$ is a shorthand for $\exists x(x<n\land\ldots)$ (or similarly for universal quantifiers). $\endgroup$
    – Asaf Karagila
    Sep 30 '15 at 23:09
  • $\begingroup$ Am I allowed to say ∃x(I(x) -> x = 1) ? Where I(x) are if the students have NO internet connection. If there exists one or more students without an internet connection, then x is one. So for example, if we test it, and x is 2, T -> 2 = 1 which is false. in every other case it's true. $\endgroup$
    – Andrew Kor
    Sep 30 '15 at 23:52
  • 1
    $\begingroup$ Your expression can also be simplified to $\exists x\forall z(\varphi(z)\leftrightarrow z=x)$, or in set theory $\exists x\{z\mid\varphi(z)\}=\{x\}$. $\endgroup$ Sep 30 '15 at 23:52
  • 5
    $\begingroup$ @AjeetKljh You can write the expression "$\exists x(I(x)\implies x=1)$", but it doesn't mean what you want it to: it means, "There is some student such that, if that student has internet, then that student is the number "1".' Presumably none of your students are numbers. :P $\endgroup$ Sep 30 '15 at 23:56
6
$\begingroup$

For part (a), that's not right - "for all $x$, there is an $x$" should immediately strike you as sounding weird (why is $x$ showing up twice?). You're almost there, though - think a bit more about what you're trying to say.

For (b), let me give a hint: Try to express (b) as a conjunction of two simpler statements:

  • There is some student in the class without an internet connection.

  • It is not the case that there are two students in the class without internet connection.

$\endgroup$
8
  • 2
    $\begingroup$ Note: for (b), my answer and Asaf's answer will look different, but are really the same. It's a good exercise to figure out why they're the same! $\endgroup$ Sep 30 '15 at 22:56
  • $\begingroup$ but why does the first one not make sense? Let me replace x with "students": For all students, there exists some students who do not have an internet connection. I might be confusing "for" with "of"? I guess it's wrong because it's like saying "For each student in the class, there is at least another without an internet connection" $\endgroup$
    – Andrew Kor
    Sep 30 '15 at 23:01
  • 1
    $\begingroup$ That sentence still is unnatural, even in natural language - what is the "for all students" doing there? It's basically a dummy clause (=not meaning anything). If you really want, you could write "$\forall x\exists y(\neg I(y))$," but wouldn't it be nicer to just write "$\exists y(\neg I(y))$"? Now, in symbolic logic, you can't even write "$\forall x\exists x(\neg I(x))$" - you're overloading the variable "$x$," and you're not allowed to do that. Think about this example: "There is no largest number." Written as "$\forall x\exists y(x<y)$" - great! As "$\forall x\exists x(x<x)$" - bwah? $\endgroup$ Sep 30 '15 at 23:09
  • $\begingroup$ i get so discouraged because i know what i want to say but i don't know how to express it $\endgroup$
    – Andrew Kor
    Sep 30 '15 at 23:12
  • $\begingroup$ so for the second one isnt it just the same except instead of (¬I(x)), it's (¬I(x) = 1)? or do I have to make it (¬I(x) < 2) $\endgroup$
    – Andrew Kor
    Sep 30 '15 at 23:17
1
$\begingroup$

Expressing "exactly one" close to natural language:

There is someone (∃x) without Internet (¬I(x)) and (∧) everyone else (∀y (y≠x→..) has Internet (I(y)):

∃x(¬I(x)∧∀y(y≠x→I(y)))

With bounded quantifiers the same could be expressed a little simpler, and incorporating "in your class" clauses.

There is someone in your class (∃(x∈C)) without Internet (¬I(x)) and (∧) everyone else in your class (∀(y∈C\{x})) has Internet (I(y)):

∃(x∈C)((¬I(x)∧∀(y∈C\{x})I(y))

(a) Not everyone in your class has an internet connection.

∃x(¬I(x))

b) Everyone except one student in your class has an internet connection.

∃y∀z(y≠z→I(z))

$\endgroup$
-1
$\begingroup$

Umm... when I studied math logic back there in my uni, we had exact quantification, expressed as $∃!$

So, let $I(x)$ === "x has internet connection", $P$ === "pupils". Then, a) is represented as

$$ \exists x(x \in P \land \neg I(x)) $$

and b) is represented as $$ \exists!x(x \in P \land \neg I(x)) $$

Difference between them is only in exactness of second statement: it's not just "not everyone", it's "exactly one" who does not have internet.

We, however, used slightly different notation:

$$ x \in P $$ $$ \exists ! x : I(x) = false $$

which, arguably, reads more naturally.

$\endgroup$

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.