6

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

Andrew Kor
  • 398

4 Answers4

12

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))

Asaf Karagila
  • 393,674
  • 3
    Some publications use $\exists !$ as a shorthand to say there is exactly one. I imagine that is not appropriate for this question. True, though. – Will Jagy Sep 30 '15 at 23:08
  • 2
    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). – Asaf Karagila Sep 30 '15 at 23:09
  • 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. – Andrew Kor Sep 30 '15 at 23:52
  • 1
    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}$. – Mario Carneiro Sep 30 '15 at 23:52
  • 5
    @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 – Noah Schweber Sep 30 '15 at 23:56
  • @NoahSchweber The statement is still true as long as at least one student doesn't have Internet access. – user253751 Oct 01 '15 at 05:30
6

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.

Noah Schweber
  • 245,398
  • 2
    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! – Noah Schweber Sep 30 '15 at 22:56
  • 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" – Andrew Kor Sep 30 '15 at 23:01
  • 1
    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? – Noah Schweber Sep 30 '15 at 23:09
  • i get so discouraged because i know what i want to say but i don't know how to express it – Andrew Kor Sep 30 '15 at 23:12
  • 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) – Andrew Kor Sep 30 '15 at 23:17
  • What does "$(\neg I(x)=1)$" mean? "$\neg I(x)$" is a statement, and "=" applies to objects, and certainly we don't want a statement to equal a number! Try to say "there are not two students with $\neg I(x)$" just using quantifiers, variables, and connectives. – Noah Schweber Sep 30 '15 at 23:18
  • The amount without a connection is 1. Ugh , yeah i just remembered that ¬I(x) is just true or false – Andrew Kor Sep 30 '15 at 23:18
  • I think you are having some confusion about what is and what isn't a well-formed formula, and how to interpret well-formed formulas; it would be a good idea to talk to your instructor about this. – Noah Schweber Sep 30 '15 at 23:21
1

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))

abuzittin gillifirca
  • 111
-1

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.

hijarian
  • 99