I have some questions:
Is the following proposition is true?
And if it is true, Is my proof is correct?
And another thing, I am not fully able to intuitively comprehend why (4) implies (3), I.e. Why if for some predicate $P(n)$ it is true that $\forall A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\exists n\in A, P(n)$, Then it must be the case that $\exists N\in\mathbb{N},\forall N<n\in\mathbb{N}, P(n)$ ? In words it means that, If we know that for any infinite subset of the natural numbers we take, There exists an element in the subset for which $P(n)$ is satisfied, Then it must be the case that there is some $N$ from which all of the $n$’s that are greater than this $N$ will satisfy $P(n)$ ?
Let $P:\mathbb{N}\to\{True,False\}$ be some predicate, Prove that the following two statements are logically equivalent:
(1) $\forall N\in\mathbb{N},\exists N<n\in\mathbb{N}, P(n)$
(2) $\exists A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\forall n\in A, P(n)$
And use this logical equivalence to prove that the following two statements are logically equivalent too:
(3) $\exists N\in\mathbb{N},\forall N<n\in\mathbb{N}, P(n)$
(4) $\forall A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\exists n\in A, P(n)$
Note: $\mathscr{P}_{\aleph_0}(\mathbb{N})$ denotes the set of all subsets of $\mathbb{N}$ that have cardinallty of $\aleph_0$, I.e. $\mathscr{P}_{\aleph_0}(\mathbb{N}):=\{A\in\mathscr{P}(\mathbb{N})| |A|=\aleph_0\}$.
Proof that (1) implies (2):
Let’s define $A:=\{n\in\mathbb{N}|P(n)\}$, It is clear that $A\in\mathscr{P}(\mathbb{N})$ and that $\forall n\in A, P(n)$, Therefore it is just left for us to show that $|A|=\aleph_0$ to accomplish the proof:
Suppose by contradiction that $|A|\neq \aleph_0$, Then we get that it must be the case that $A$ is finite, And thus $|A|\in\mathbb{N}\cup\{0\}$, Now there are two cases: $|A|\in\{0\}$ or $|A|\in\mathbb{N}$
If $|A|\in\{0\}$, We conclude that $|A|=0$, And thus $A=\emptyset$, Now because of (1), We get that in particular for $N:=1$ we have $\exists N\lt n\in\mathbb{N}, P(n)$, And thus $n\in\mathbb{N}$ is natural number for which the statement $P(n)$ is satisfied, And we conclude by the way we defined the set $A$ that $n\in A$ which contradicts the fact that $A=\emptyset$.
If $|A|\in\mathbb{N}$, Then $A$ is a non-empty finite set of natural numbers, And thus its maximum $\max(A)$ exists and is an element in $A$, Now let’s define $N:=\max(A)$, Then we get that $N\in A$, And thus $N\in \mathbb{N}$, And we can conclude by (1) that $\exists N<n\in\mathbb{N},P(n)$, And thus by the way we defined the set $A$, We conclude that $n\in A$, Which implies that it must be the case that $n\leq \max(A)$, But since $N=\max(A)$, We conclude that $n\leq N$, But this contradicts the fact that $N<n$.
Thus we see that wether $|A|\in\{0\}$ or $|A|\in\mathbb{N}$, We always reach a contradiction, And thus it must be the case that $|A|=\aleph_0$, And we conclude that $A\in\mathscr{P}_{\aleph_0}(\mathbb{N})$ as was to be shown.
Proof that (2) implies (1):
Suppose by contradiction that it is not true that $\forall N\in\mathbb{N},\exists N<n\in\mathbb{N}, P(n)$, I.e. suppose that (#) $\exists N\in\mathbb{N},\forall N<n\in\mathbb{N}, \lnot P(n)$,
We’ll show that (##) $\forall n\in A, n\leq N$:
Suppose by contradiction that $\exists n\in A, n>N$, Then since $A\subseteq\mathbb{N}$ (Because $A\in\mathscr{P}_{\aleph_0}(\mathbb{N})$), We conclude that $N<n\in\mathbb{N}$, And thus by (#) we conclude that $\lnot P(n)$, I.e. $P(n)$ is not satisfied, Also, Since $n\in A$, We get by (2) that it is also the case that $P(n)$ is satisfied, Therefore we got that $P(n)$ is not satisfied and $P(n)$ is satisfied at the same time, And thus we’ve reached a contradiction and it must be the case that $\forall n\in A, n\leq N$ as was to be shown.
Now let’s define $B:=\{i\in\mathbb{N}|i\leq N\}$, We’ll show that $A\subseteq B$:
Let $n\in A$, Then by the fact that $A\subseteq \mathbb{N}$, We get that $n\in\mathbb{N}$, Also by (##) we get that $n\leq N$, And thus we can conclude that $n\in B$ as was to be shown.
Now since $|B|=N\in\mathbb{N}$, We conclude that $B$ is finite, And since $A\subseteq B$, We conclude that it must be the case that $A$ is also finite, But this contradicts the fact that $|A|=\aleph_0$ (as $A\in\mathscr{P}_{\aleph_0}(\mathbb{N})$)) and we’ve reached a contradiction.
Therefore it must be the case that $\forall N\in\mathbb{N},\exists N<n\in\mathbb{N}, P(n)$ as was to be shown.
Proof that (3) and (4) are logically equivalent:
Let’s define a new predicate $Q(n)\equiv \lnot P(n)$, Then by what we’ve just shown, We conclude that:
$$\forall N\in\mathbb{N},\exists N<n\in\mathbb{N}, Q(n)\equiv\exists A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\forall n\in A, Q(n)$$
But this implies that:
$$\lnot\forall N\in\mathbb{N},\exists N<n\in\mathbb{N}, Q(n)\equiv\lnot\exists A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\forall n\in A, Q(n)$$
Now since:
$$\lnot\forall N\in\mathbb{N},\exists N<n\in\mathbb{N}, Q(n)\equiv \\\equiv\exists N\in\mathbb{N},\forall N<n\in\mathbb{N}, \lnot Q(n)\equiv\\\equiv\exists N\in\mathbb{N},\forall N<n\in\mathbb{N}, \lnot\lnot P(n)\equiv\\\equiv\exists N\in\mathbb{N},\forall N<n\in\mathbb{N}, P(n)$$
And since:
$$\lnot\exists A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\forall n\in A, Q(n)\equiv\\\equiv\forall A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\exists n\in A, \lnot Q(n)\equiv\\\equiv \forall A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\exists n\in A,\lnot\lnot P(n)\equiv\\\equiv \forall A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\exists n\in A, P(n)$$
We conclude that:
$$\exists N\in\mathbb{N},\forall N<n\in\mathbb{N}, P(n)\equiv\forall A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\exists n\in A, P(n)$$
as was to be shown.
Note: One example of using this proposition is in the context of limits of sequence:
Let $\{a_n\}_{n=1}^\infty$ be some sequence of real numbers, Inorder to show that $\lim_\limits{n\to\infty}a_n\neq L$, We have to show that $\exists\epsilon\in (0,\infty),\forall N\in\mathbb{N}, \exists N<n\in\mathbb{N}, a_n\notin (L-\epsilon, L+\epsilon)$
(Here $P(n)\equiv a_n\notin (L-\epsilon,L+\epsilon)$)
By the proposition we get that this is equivalent to show that:
$\exists\epsilon\in (0,\infty),\exists A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\forall n\in A, a_n\notin (L-\epsilon,L+\epsilon)$
I.e. It is enough to show that $a_n\notin (L-\epsilon,L+\epsilon)$ for an infinite number of $n$’s.
Also inorder to show that $\lim_\limits{n\to\infty}a_n= L$, We have to show that $\forall\epsilon\in (0,\infty),\exists N\in\mathbb{N}, \forall N<n\in\mathbb{N}, a_n\in (L-\epsilon, L+\epsilon)$
(Here $P(n)\equiv a_n\in (L-\epsilon,L+\epsilon)$)
By the proposition we get that this is equivalent to show that:
$\forall\epsilon\in (0,\infty), \forall A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\exists n\in A, a_n\in (L-\epsilon,L+\epsilon)$
Best Answer
I'll start with the intuition and with fixing the notation because it grates on me.
You have the following:
(1) $\forall N\in\mathbb{N},\exists n\in\mathbb{N} (N<n)\wedge P(n)$
(2) $\exists A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\forall n\in A, P(n)$
(3) $\exists N\in\mathbb{N},\forall n\in\mathbb{N} (N<n) \wedge P(n)$
(4) $\forall A\in\mathscr{P}_{\aleph_0}(\mathbb{N}),\exists n\in A, P(n)$
Now to explain the intuition first. (1) says $P(n)$ is true cofinately often. Consider the converse $\exists N\in \mathbb{N} \forall n\in \mathbb{N} (n>N)\implies \neg P(n)$. That just means that $P(n)$ is only true for finitely many $n$. At some point we've seen all $n$ for which $P(n)$ will hold.
(2) just says there is an infinite set for which $P(n)$ holds. Now for $\omega$ all infinite sets must be cofinal. That is you can't have an infinite set such that all elements of it are smaller than some $N$.
Now (3) says that from some point on $N$ ALL natural numbers satisfy $P(n)$. Now just above I pointed out that no infinite set on the naturals can be bounded above, but that means that for every infinite set $A$ there must be some element of $A$ which is bigger than $N$ so $P(n)$ holds.
(4) says that whenever we choose any infinite set $A$ there will be some $n$ such that $P(n)$. Arguably this really is the trickiest. Why should that mean that all but finitely many (i.e. $\exists N$ $\forall n>N$) satisfy $P(n)$? This reformulation actually gives you the answer. If there were infinitely many $n$ for which $P(n)$ is not satisfied than the set of these $n$ would be a witness of (4) failing.
You also ask whether your proofs are correct. The answer as far as I can see it yes. They are very roundabout in my opinion but it is hard to judge when I don't know what you can get away with.
Just to give my version of the same proofs: (1)$\implies$ (2): Let $A=\{n\in\mathbb{N}:P(n)\}$. If $A$ is not infinite, then it is bounded from above by some $N$ but by (1) we have that for every $N$ there is $n>N$ such that $P(n)$. That is a contradiction thus $A$ is infinite.
(2) $\implies$ (1): Let $N$ be arbitrary. Since $A$ is infinite there is an $n\in A$ such that $n>N$ and $P(n)$. Q.E.D.
The second equivalence is fine though confusing. To me it seems pretty much easier and more interesting to prove it from first principles. Though chasing negations has its uses I guess.