Partial order on sets and application of Zorn's Lemma to construct well-ordered subset

Question

I would appreciate help with the following question:
Let $(A,<)$ a linear ordered set.

a. Let $F\subseteq P(A)$. Prove that the following relation is a partial order in $F$: $X\lhd Y$ for $X,Y\in F$ if and only if $X$ is initial of $Y$.
b. Using Zorn's lemma, prove that there exists a well-ordered subset $B\subseteq A$, such that for all $a\in A$ exists $b\in B$ such that $a\leq b$.

Edit:
Regarding (a), my lecturer defined in the course a partial relation as an antireflexive relation and a transitive relation.
Also we defined initial of $A$ as $A_x = \{a\in A: a<x \}$

Having saying that, I need to show that for any $X\in F$,$X \not\lhd X$, and for any $X,Y,Z\in F$, such that $X\lhd Y$, $Y\lhd Z \Rightarrow X\lhd Z$.

I intuitively understand why these things are true, but have difficulty in formal and convincing formulation. In a certain sense, the initial of a set necessarily has one element that does not exist there, the element that defines the initial, so obviously a set cannot be its own initial because all the members are there, and from the definition of the initial there should be one member that does not exist, but this does not feel like a good wording to me and convincing.

Regarding transitivity, I also have difficulty with the convincing and formal explanation, if $X\lhd Y$, $Y\lhd Z$ then from initial's definition exists $a\in Y, b\in Z$ such that $X=Y_a=\{y\in Y: y<a \}$ and $Y=Z_b=\{z\in Z: z<b \}$. I think I should eventually say that $X=Z_a=\{z\in Z: z<a \}$ but I am not quite sure how to get there.

Regarding (b), I learned that Zorn's lemma states:
Suppose a partially ordered set $P$ has the property that every chain in $P$ has an upper bound in $P$. Then the set $P$ contains at least one maximal element.

I know I need to define a set with a partial order relation and show that each chain has an upper bound, but I don't really know which set to define. I thought about the set of all well-ordered subsets of $A$ such that for every $a\in A$ there exists $b$ in the subset such that $a\leq b$, but this is what needs to be proved and it feels like a circular and incorrect argument.

Answer 1

To me, it seems like the main issue here is not with the concepts involved, but rather with basic proof-writing skills: unpacking the definitions and seeing how to turn your intuitions into a structured proof.

Let me give you some pointers on getting started.

Part (a): The first step is to make sure you know the definition of partial order and "initial" (which I would call an "initial segment"). You've included the definitions in the question and correctly identified that you need to prove antireflexivity and transitivity.

Antireflexivity: Let $X\in \mathcal{P}(A)$. We need to prove that $X$ is not an initial segment of itself. You've described good intuition: an initial segment of $X$ fails to contain some element, the element defining the initial segment, so $X$ can't possibly be an initial segment of itself.

Ok, how to write this more carefully? One natural way to prove that $X$ is not an initial segment of itself is to assume $X$ is an initial segment of itself and obtain a contradiciton. So assume $X\triangleleft X$. Then there exists $x\in X$ such that $X = \{y\in X: y<x\}$. Do you see how to finish from here?

Transitivity: From the assumption $X\triangleleft Y$ and $Y\triangleleft Z$, you have correctly concluded that there is $a\in Y$ and $b\in Z$ such that $X = \{y\in Y:y<a\}$ and $Y = \{z\in Z: z<b\}$. Now you want to show that $X = Z_a$. There are actually two things to show here: (1) $a\in Z$, so $Z_a$ makes sense. (2) $X = \{z\in Z\mid z<a\}$.

Try to prove (1) yourself. For (2): A very common way to show that two sets are equal is "double containment". Can you show that every element of $X$ is in the set $\{z\in Z\mid z<a\}$ and every element of the set $\{z\in Z\mid z<a\}$ is in $X$?

Part (b): You say you don't know what poset to apply Zorn's Lemma to. Well, in part (a), you defined a partial order on $\mathcal{P}(A)$, so you could apply Zorn's Lemma to that. The problem is, you already know a maximal element of $(\mathcal{P}(A),\triangleleft)$, namely $A$, and $A$ may not be well-ordered.

So your idea to restrict the partial order to just the well-ordered subsets of $(\mathcal{P}(A),\triangleleft)$ is a good one. You don't want to build in the requirement of cofinality (for every $a\in A$ there exists $b$ in the subset such that $a\leq b$) - this would indeed be circular, since you don't know that any such sets exists. Instead, the goal is to obtain a maximal well-ordered element in $(\mathcal{P}(A),\triangleleft)$ by Zorn's Lemma and use maximality to prove that it's cofinal.

Ok, so let $W$ be the set of well-ordered subsets of $A$. Is it clear to you that the partial order $\triangleleft$ restricts to a partial order on $W$?

To apply Zorn's Lemma, you need to check that every chain in $(W,\triangleleft)$ has an upper bound. Can you do that?

Now given a maximal element $M$ in $(W,\triangleleft)$, you need to check it's cofinal. Suppose not: then there exists $a\in A$ such that for all $m\in M$, $m<a$. Can you use this to build a new $M'\in W$ such that $M\triangleleft M'$, contradicting maximality?