# Proof that if $n\in N$ and $\emptyset \ne X \subset \mathcal{P}(n)$ then $X$ has a $\subset$-maximal element

I'm trying to prove the theorem, if $n\in N$ and $\emptyset\ne X\subset\mathcal{P}(n)$ then $X$ has a $\subset$-maximal element. Here $N$ is the intersection over all inductive sets. I have already proved that $N=\{0,1,...\}$ where $0=\emptyset$ and $m+1 = m\cup \{m\}$. I'm a little confused about whether an argument by induction is legitimate given that it's not exactly an axiom. It's a valid logical principle but I think part of the rigorously stated rule is that the claim must be of a countable set of objects and that seems like it's getting ahead of the current material.

My best attempt at an argument without induction: If $n = 0$ the claim is trivial. If $n\ne 0$ then for contradiction suppose $\forall u\in X\,\,\exists v\in X$ such that $u\subset v \land u\ne v$ (my book uses the old-school notation where $\subset$ is a weak ordering). We may consider the sequence of subsets $x_0\subset x_1\subset ...$ where for each $i$ we have both $x_{i+1}\ne x_i$ and $x_{i+1}-x_i\ne \emptyset$. If $y_{i+1}=x_{i+1}-x_i$ then $y_1, y_2, ...$ forms a sequence such that $y_{r}\cap y_s=\emptyset$ for each $r\ne s$. Then we may form a function $f$ mapping $i$ to any arbitrary choice in $y_i$ and guarantee that $f$ will be injective.

At this point I seem to have used the Axiom of Choice which has not yet been introduced officially in my book (by Jech) although perhaps it's smuggled in through the Axiom of Separation. If that's legit then I might be able to then use the existence of a bijection of $n$ with $n$ to get a contradiction, but at this point I'm a little uncertain of the whole approach.

[Edit: Actually I might be able to avoid the issue of the axiom of choice since I have already proved that every non-empty subset of $N$ has a $\in$-minimal element so I could just choose this rather than making the choice arbitrary. Further edit: Actually I don't think that does fix the problem because I've only shown that one exists, not that it's unique, so this amounts to another arbitrary choice of a set, the set of $\in$-minimal elements in $y_i$.]

• I'm confused as to what $X$ has to do with anything, in the statement of the problem in the title (which should also be included in the body, by the way). – Asaf Karagila Oct 18 '16 at 21:15
• Sorry, had mistakes in the title, fixed now. – Addem Oct 18 '16 at 22:52

First note that asking for the existence of a minimal element is the same as asking for a maximal element: $X$ has a maximal element if and only if $\{n\setminus A\mid A\in X\}$ has a minimal element.

Now it's easy, as long as you know that if $A\subseteq n$, then there is some $m\in n$ such that there is a bijection between $A$ and $m$. Given $X$ consider the function $f(A)=|A|$, and pick the minimal element, as you suggested using the fact that $N$ is well-ordered.

(This can be skipped if you've proved that a finite subset of $N$ is bounded, has a last element, that $\mathcal P(n)$ is finite and that the image of a finite set under a function is finite.)

You are correct, however, that constructing a sequence like this will amount to using the axiom of choice, at least in the generality that this proof can work. You can avoid choice by using the fact that $N$ is well-ordered, allowing you to choose the least possible candidate at each step of the way. But you need to know this, first.