Subsets of N are Countable (3.3.6)

Hrbacek and Jech Introduction to Set Theory, chapter 3, section 3, exercise 6:

Let $X⊆ℕ$; prove there exists a one-to-one sequence $f$ onto $X$.

Proof: Let $X$ be nonempty; then let $a∈X$ be the least element of $X$. We define the sequence $f$ by$$f_0 = a$$$$f_{n+1}=g(f_n,n)$$where $g(x,n)$ is the least element of $\{y∈X~|~y > x\}$ when it exists (cf. 3.3.5). Now, we let $P(n)$ be the proposition: if $n∈X$, then $n=f_m$ for some $m∈ℕ$. We shall prove it by total induction. Let $k∈X$. If $X∩k$ is empty, then $k$ is the least element of $X$ and $k=f_0$; otherwise let $p$ be the largest element of this bounded subset. We see $k > p$, and if $r > p$ then $r∉X∩k$ and hence either $r ≥ k$ or $r∉X$, implying $k$ is the least element of $\{y∈X~|~y > p\}$, i.e. $k=g(p,n)$ for all $n∈N$. Since $k > p$ we have $p=f_m$ for some $m$ and now $k=f_{m+1}$. Hence $\text{ran }f=X$.

We shall now prove by double induction (cf. 3.2.13) that $m < n$ and $f_m,f_n$ existing implies $f_m < f_n$, so $f$ is one-to-one. If $n = 0$ then the case is vacuous, so let $n=k+1$ with $m≤k$. If $m=k$ then $f_m < f_n = f_{m+1}$ by the definition of $f$. If $m < k$ then by inductive assumption $f_m < f_k < f_{k+1} = f_n$ and now $f_m < f_n$. This completes the induction and the proof.$~\square$

Minimal Characterization of N (3.3.2)

Hrbacek and Jech Introduction to Set Theory, chapter 3, section 3, exercise 2:

Let $(A,\prec)$ be a linearly ordered set. For $p,q∈A$ we say $q$ is the successor of $p$ if $q$ is the $\prec$-least element of the set of elements greater than $p$, if it exists. Assume $A$ is nonempty and the following properties hold:

1. Every $p∈A$ has a successor.
2. Every nonempty subset of $A$ has a $\prec$-least element.
3. Every $p∈A$ which is not the $\prec$-least element of $A$ is a successor to some $q∈A$.

Show $(A,\prec)≅(ℕ,<)$. Show that the the condition may not hold if one of (a)-(c) is not assumed.

Proof: We shall show the conditions of Theorem 3.4 hold. 3.4(a) holds because $p \prec S(p)$, 3.4(b) is exactly the same here, and to observe 3.4(c) let $B⊆A$ be nonempty with nonempty set of upper bounds $C$; then $C$ has a $\prec$-least element $c$, and if $c$ is the $\prec$-least element of $A$, then $c$ can be the only element of $B$ and $c$ is also the $\prec$-greatest element of $B$. So we can assume $c=S(d)$ for some $d$, where if we assume $c∉B$ we cannot have $d \prec b$ for any $b$ or else either $c$ is the $\prec$-greatest element of $B$ or we have $d \prec b \prec c$ and $c$ is not the successor of $d$. Hence $d$ is an upper bound of $B$ strictly smaller than $c$, a contradiction.

Now, we will present examples $(A,\prec)$ not isomorphic to $(ℕ,\prec)$ each failing exactly one of the properties (a)-(c). $¬$(a) Let $A=\{∅\}$ with $∅ \not \prec ∅$; then $∅$ is the $\prec$-least element of the only nonempty subset of $A$, and (c) is vacuous. $¬$(b) One may examine $(ℤ,<)$ as an example, though it has not been constructed yet; we will imitate it with the set $A=\{+,-\}×ℕ-\{(-,0)}$ where $+,-$ are any two distinct sets, under the relation $a \prec b$ as in $ℤ$ (formalize this by setting the relation $\prec '$ on $\{+\}×ℕ$ as in $(ℕ,<)$, the relation $\prec ''$ on $\{-\}×ℕ-\{(-,0)\}$ as that on $(ℕ,>)$, and take their union under the relation $a \prec b$ where every element of $\{-\}×ℕ-\{(-,0)\}$ is less than all of $\{+\}×ℕ$). We see that every element in $ℤ$ has a successor, and every element is a successor to another, yet is not isomorphic to $ℕ$ as it does not have a least element. $¬$(c) Take the set $N×N$ under the relation $(a,b) < (c,d)$ if $a < c$ or $a=c$ and $b < d$. This is seen to be a linear order, where the successor of $(a,b)$ is $(a,b+1)$ and where the least element of a nonempty subset $A$ is the element $(x,y)$ where $x$ is the least element of $\{n∈ℕ | ∃m, (n,m)∈A\}$ and $y$ is the least element of $\{m∈ℕ | (x,m)∈A\}$. Yet $(1,0)$ is clearly seen not to have a least element and not to be the least element of $ℕ×ℕ$, hence an isomorphism cannot be constructed.$~\square$

Axiomatic System Number Two (3/18/14-Current)

Let $\_∘\_\{\_\}$ be a trinary relation, pronouncing $a∘b\{c\}$ as "$a$ is essential to $b$ in universe $c$," or "$a$ essential to $b$ in $c$." Accept the following axioms:

1. (Axiom of Equality) Define $a\text{~} b\{c\}:⇔∀z(z∘a\{c\}⇔z∘b\{c\})$ ($a$ similar to $b$ in $c$), which is seen to be an equivalence relation in any fixed universe $c$. Then the axiom is $∀a,b(∃x,y[x≠y∧a\text{~} b\{x,y\}]⇒a=b)$, i.e. two objects $a$ and $b$ are equal (where equality can be formally expanded as the property that any trinary relation containing an instance of $a$ can be rewritten with that $a$ replaced by $b$, and vice versa) if $a\text{~} b$ in two distinct universes $x,y$.
2. (Axiom of Iteration) $∀x∃\overline{x}∀a,b(a∘\overline{x}\{b\}⇔[a∘x\{b\}∨a=x])$, i.e. for every $x$ there exists an iteration $\overline{x}$ such that $\overline{x}$'s essentials are the essentials of $x$ in that particular universe plus the additional essential of $x$ itself (if it were not already essential).
3. (Axiom of Existence) $∃∅∀a,b(¬[a∘∅\{b\}])$. Combining the axioms of iteration and existence, we see that for "any" (uniqueness not yet established) $∅$, we have $\overline{∅}≠∅$ as $∅∘\overline{∅}\{∅\}$ yet $¬(∅∘∅\{∅\})$, so there are in fact at least two distinct objects. Now statements defining explicitly the essentials of an object in any given universe (like the existence of $∅$ and $\overline{x}$) can be taken as unique existences.
4. (Axiom of Tensors) $∀x,y∃z(z\text{~} x\{y\}∧z\text{~} y\{x\})$, i.e. there exists an object imitating $x$ in $y$ and $y$ in $x$. When $x≠y$, we see this $z$ is unique by the axiom of equality, so we define $x⊗y$ to be this unique $z$ when $x≠y$ and we define $x⊗x=x$. Note $⊗$ is commutative.

Lemma 1 (Description of Trivial Tensors): $x⊗y=x⇔x\text{~} y\{x\}$. Proof: ($⇒$) We observe $x=(x⊗y)\text{~} y\{x\}$. ($⇐$) We observe $(x⊗y)\text{~} x\{y\}$ and $(x⊗y)\text{~} y\text{~} x\{x\}$, so when $x≠y$ we have $x⊗y=x$; when $x=y$ we definitionally observe $x⊗x=x$.$~\square$

Lemma 2 (Description of Tensor Injectivity): When $y≠z$, we have $x⊗y=x⊗z⇔x⊗y=x⊗z=x⇔x\text{~} y\text{~} z\{x\}$. Proof: The second logical equivalence is an application of the first lemma, so we prove now the first equivalence: ($⇐$) This is trivial. ($⇒$) We have $(x⊗y)\text{~} x\{y\}$ and also $(x⊗z)\text{~} x\{z\}$. Since these two tensors are equivalent, when $y≠z$ we observe this tensor must be equivalent to $x$.$~\square$ This lemma generalizes the first, and interpreted conceptually says that $x⊗\_$ is "injective" on the collection of objects not similar to $x$ in its own universe (with e.g. $x$ appended to this collection). Unfortunately, it is not enough to know the fixed similarity class of an object $y$ defined explicitly in the universe of $x$, if wanting to uniquely determine $x⊗y$.

Proposition 3 (Nonassociativity of $⊗$): Generally, we do not have $x⊗(y⊗z)=(x⊗y)⊗z$. Proof: We show particularly that $∅⊗(∅⊗\overline{∅})≠(∅⊗∅)⊗\overline{∅}=∅⊗\overline{∅}$. Assume the contrary and apply lemma 2 (after showing $∅⊗\overline{∅}≠\overline{∅}$ by appealing to lemma 1) to particularly obtain $∅⊗\overline{∅}=∅$. Apply lemma 1 to obtain $\overline{∅}\text{~} ∅\{∅\}$, even though $¬(∅∘∅\{∅\})$ but $∅∘\overline{∅}\{∅\}$.$~\square$

Axiomatic System Number One (Inconsistent) (3/17/14)

Let $·$ be a binary relation, and accept the following axioms:

1. (Axiom of Existence) $∃X∀y(y·X⇔y=X)$, i.e. there exists "existential $X$" such that it itself is the one and only thing essential to it.
2. (Axiom of Equality) $∀x,y(x=y⇔∀z[z·x⇔z·y])$, where here $x=y:⇔∀z([x·z⇔y·z]∧[z·x⇔z·y])$. This should be familiar from set theory.
3. (Axiom of Transitivity) $∀a,b,c(a·b·c⇒a·c)$, i.e. $·$ is transitive.
4. (Axiom of Antitheses) $∀x∃A(x)∀y(y·A(x)⇔¬[y·x])$, i.e. $A(x)$ flips all the essential relations toward $x$. $A(x)$ is unique according to the second axiom.
5. (Axiom of Agreement) $∀x∃y(x,A(x)·y)$. This $y$ (called an agreement of $x$) may not be unique for any given $x$, and by $x'$ we denote any particular agreement that remains fixed throughout the proof in question.

This system is inconsistent.

Proof: We see $X≠A(X)$ as $X·X$ yet $¬(X·A(X))$ by the definition of $A(X)$. As well, $X≠X'$ seeing as $A(X)·X'$ yet $¬(A(X)·X)$ since we just proved $X≠A(X)$. Therefore $¬(X'·X)$, hence we have $X·X'·A(X)$ implying $X·A(X)$, a contradiction.$~\square$

This system wasn't getting interesting enough to make it worth repairing. Originally there was a second binary relation, but there wasn't enough interplay between the two relations, and the second was just generally neglected, hence it didn't appear in the proof of inconsistency so its axioms weren't included.