# How to build linear order on $\mathcal P({\bf N})$ [duplicate]

How to build linear order on $\mathcal P({\bf N})$?

Had idea about inclusion relation, but it does not satisfy linearity.

• What about starting with a filter $D$ on $\omega$, then ordering the functions $\omega \to 2$ by $f<g \iff${$f<g$}$\in D$. Sort of like an ultrapower. If $D$ is an ultrafilter the order should be linear (total). – Forever Mozart Jul 24 '13 at 0:51
• – MJD Jul 24 '13 at 1:26

Hint:

Given two sets of natural numbers, $A,B$ we can say that $A\prec B$ if the minimal element of $A\triangle B$ is a member of $A$.

Another alternative is to find an injective function from $\mathcal P(\Bbb N)$ into $[0,1]$ and use that to define the order.

A third alternative is to think about it as infinite binary sequences, and order them lexicographically.

• can you give more details for third variant, please – Vadik May 26 '13 at 10:56
• @Vadik Every element $X \in \mathcal{P}(\mathbb{N})$ naturally corresponds to a function $f_X \,:\, \mathbb{N} \to \{0,1\}$ where $f_X(n) = 1$ exactly if $n \in X$. You may think of such a function as a sequence $f(0),f(1),\ldots$ – fgp May 26 '13 at 11:01
• @fgp It is about second variant, isn't it? – Vadik May 26 '13 at 11:12
• @Vadik: No, fgp wrote about the third variant. And you can see that the third variant is very close to the first variant, and by choosing the injection correctly also to the second variant. – Asaf Karagila May 26 '13 at 11:20
• @Asaf Karagila I understood. But i can't understand this moment "where fX(n)=1 exactly if n∈X.". And X∈p(ℕ) is any subset of p(N) in this context , isn't it? – Vadik May 26 '13 at 11:25