2

How to rigorously state that the predicate $P(x)$ is true for all but a finite number of $x\in\mathbb{N}$?

My Attempt

There is a finite set $\mathcal{S}\subset \mathbb{N}$ s.t. $s\in\mathcal{S}\implies \neg P(x)$ and $s\notin\mathcal{S}, s\in \mathbb{N}\implies P(x)$.

But I think there is a much more elegant way to saying the above. Actually, I struggle a lot when formalizing many seemingly super intuitive notion such as the above one.

Andrés E. Caicedo
  • 79,201
Kun
  • 2,496
  • 2
    What about the statement "$P(x)$ is true for all but finitely many $x \in \mathbb{N}$ is not precise enough as is? – Ethan Alwaise May 11 '16 at 03:56
  • Oh, it is precise, but it is not formal enough. When statements are not very formal, it is harder to use the fact in proofs. So I always have to make them formal first the use them – Kun May 11 '16 at 04:09
  • It is very formal, and it shouldn't be harder to use that in a proof, in fact, proofs look extremely more elegant if you use words instead of chunks of logic symbols. – YoTengoUnLCD May 11 '16 at 04:41
  • 1
    @YoTengoUnLCD I know, but it is better for a beginner to write in logic symbols so I really understand what I wrote. I agree that writing in words is more beautiful but it requires you to actually master the logic symbols first. – Kun May 11 '16 at 04:42

2 Answers2

2

$\exists N\forall n(n\gt N\implies P(n))$

André Nicolas
  • 507,029
  • Thank you for the answer. But it seems like this is more of a equivalent statement rather than the original statement. When we deal with finite or infinite, aren't we always talking about sets? Sorry about the misunderstanding. – Kun May 11 '16 at 04:10
  • When one writes a formal sentence in first-order logic, what the quantifiers range over is aways understood. One could instead write a sentence of Zermelo-Frankel (or some other) set theory. I chose not to do that. – André Nicolas May 11 '16 at 04:17
0

You want to say that the cardinality of the set of natural numbers for which the predicate is false is finite.

$$\exists n{\in}\Bbb N~\Big(n=\big\lvert\{x{\in}\Bbb N:\neg P(x)\}\big\rvert\Big) \\ ~ \\ \big(\exists n{\in}\Bbb N\big)\big(\exists^{=n}x{\in} \Bbb N\big)\big(\neg P(x)\big)$$

Something like that.

[The first uses set construction and cardinal measure; the second uses a counting quantifier to say the same thing]

Graham Kemp
  • 129,094