Let $P_{\aleph_{0}}(\mathbb{N}) = \{x\in P(\mathbb{N}):|x|=\aleph_{0}\} $

we'll define the following relation on $P_{\aleph_{0}}(\mathbb{N})$ for $A, B \in P_{\aleph_{0}}(\mathbb{N})$:

$A\preccurlyeq B$ if for every $b_1, b_2 \in B \longrightarrow\left(b_1 < b_2 \longrightarrow\vert [b_1, b_2] \cap A\vert\geq2\right)$

$ \left\langle \preccurlyeq,P_{\aleph_{0}}(\mathbb{N})\right\rangle $ is a Partially ordered set.

prove/ disprove: there exist a maximum element on the order $\preccurlyeq$

my attempt:

I'd like to disprove that argument by contradiction.

suppose there exist a maximum element on the order $\preccurlyeq$, Let it be $A$.

by a definitio; $|A| = \aleph _0$ . therefore by the Well -ordering principle,I'll define $A$ as following $ A = \{ a_i \in A \vert i \in \mathbb{N}\}:$ $$a_1 < a_2 < a_3 < \cdots < a_n < \cdots$$

let $B = \{ a_{2i} \in A \vert i\in \mathbb{N} \}$, hence $ B $ is the even elements of $A$. that means that for every $${b_i} \in B;$$ $$ b_1 < b_2 < \cdots < b_n < \cdots $$ therefore, for every $i$, $a_i < b_i = a_{2i}$ let $b_k, b_j \in B \ $ WLOG $ \ b_k < b_j \ $ and also $ \ b_k = a_{2k}, \ b_j = a_{2j} \ $ for some $ \ k, j \in \mathbb{N}$ $ |b_j - b_k| = |a_{2j}- a_{2k}| > 2$ and of course, $|b_j - b_k| = |a_{2j}- a_{2k}| > |a_j - a_k| $

this is a contradiction to the assumption that $A$ is the maximum element, as we found a bigger element then $A$. therefore. there exist no maximum element.

is that correct?


Let $A\leq B$.

suppose there exist a maximum element, $B$.

$$B = \{ b_{1},b_{2},b_{3},\cdots\}$$

such that: $i<j\ \Longrightarrow\ b_{i}<b_{j}$.

Let $A = \{ n\in\mathbb{N}\vert n<b_{3}\vee n<b_{4}\}$

hence, for a given $b_3 , b_4 $:


Therefore $$ 0 = \vert\emptyset\vert=\vert A\cap[b_{3},b_{4}]\vert<2$$

which contradicts the assumption that $A\leq B$. that means that for every $B$ there exist some $A$ which doesn't maintain the order $ A\leq B$, thus there exist no maximum element $B$.

  • $\begingroup$ Presumably OP meant "element without an element strictly above it", rather than "element above everything". $\endgroup$ – Mees de Vries Sep 3 '18 at 12:31
  • $\begingroup$ I don't know what you refer in "OP" $\endgroup$ – Jneven Sep 3 '18 at 12:33
  • $\begingroup$ you mean PO? partially ordered? $\endgroup$ – Jneven Sep 3 '18 at 12:34
  • $\begingroup$ Oops, I didn't realize you were the same person. "OP", or "original poster", refers to the person who asked the question. I thought your notion of "max element" was a $B$ with no $A$ such that $A > B$; but now you are answering as if you are looking for a $B$ such that for all $A$ we have $B \geq A$. $\endgroup$ – Mees de Vries Sep 3 '18 at 12:35
  • $\begingroup$ this is question of a uni course - you are of course right but this is essentially a notaion - so it could be be represented by $R$. I think a part of the "challenge" is that it says $ A \leq B$ but actually it is the other way around. maybe my professor didn't notice that this is the wrong way - which is interesting for someone who's expertise ARE set theory $\endgroup$ – Jneven Sep 3 '18 at 12:52

I'd prove by contradiction that there exist no maximum element in the order $\preccurlyeq$.

Suppose there exist an object in $P_{\aleph_{0}}(\mathbb{N})$ on the order $\preccurlyeq$, Let it be $X$.

$X \in P_{\aleph_{0}}(\mathbb{N}) \Longrightarrow |X| = \aleph_0$

I'll define a function $$f:\mathbb{N} \to X$$ such that $f$ is well ordered function (on the order < over $\mathbb{N}$) and onto.

let the set $$B = \{ f(n) \vert n\in \mathbb{N}_{even} \}$$ clearly, $B \subseteq X$, therefore $|B| \leq \aleph_0$.

I'll define a function $$g:\mathbb{N}_{even} \to B$$ such that $g(n) = f(n)$ for every $n \in \mathbb{N}_{even}$. $f$ is one-to-one therefore $g$ is also one-to-one, $\Longrightarrow \aleph_o = |\mathbb{N}_{even}| \leq |B| $, thus $|B| = \aleph_o$.

$B \subseteq X \subseteq \mathbb{N}$, hence $B \in P_{\aleph_{0}}(\mathbb{N}$.

Let $n_1, n_2 \in B$ such that $n_1 < n_2 $.

because $B \subseteq X$ then $n_1 , n_2 \in X $ so $$|[n_1 , n_2 ] \cap X \geq 2$$ consequently, $B \preccurlyeq X$, which contradicts the assumption that $X$ is the maximum element in the order.

lemma I'll prove that the function $f$, which is defined to be a well ordered and invertible function exist.

I will define $f$ in recursion: $$f(0) = Min (X) $$

$$f(n+1) =_{ \ <} \ \left( X \ / \bigcup_{0 \leq i \leq n} f(i)\right) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.