Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am concerned with showing the least element existence in every subset of $\alpha\times\beta$. Below is my attempt. My teacher has used similar argument to show $\mathbb{N}\times\mathbb{N}$ is a well-ordered by some 'given' ordering.


Let $\alpha,\beta$ be ordinals. Show that $\alpha\times\beta$ with the ordering

$(\gamma,\delta)\triangleleft(\lambda,\kappa)\iff[\gamma\cup\delta<\lambda\cup\kappa\vee(\gamma\cup\delta=\lambda\cup\kappa\space\land\space(\gamma<\lambda\vee(\gamma=\lambda\space\&\space\delta<\kappa)))]$ is well-ordered.


Now I show that for every non-empty subset $b$ of $\alpha\times\beta$ we have a least element. We proceed as follows:-

If $\emptyset\neq b\subseteq\alpha\times\beta$ , define $k$ to be the least ordinal in $\{x\cup y\mid (x,y)\in b\}$ with respect to ordering $\in_{Ord}$. The set $\{z\in {Ord}\mid (z,k\backslash z)\in b\}$ is non-empty and if $z_0$ is its least element (again w.r.t $\in_{Ord}$ then $(z_0,k\backslash z_0)$ is the $\triangleleft$ -least element of $b$.

Am I right?

share|cite|improve this question
I have voted to close the question. Different people will have different ideas about what a "correct" homework solution is, and in the end the person that matters is the person who will grade the assignment. Since there isn't an objective answer to the question, it isn't a good fit for this site. Moreover, the question whether this proof is correct is not likely to be of interest to others in the future, making the question "localized" in the jargon used on this site. – Carl Mummert Nov 30 '11 at 14:39
if you think so i will delete it. shall i press above delete button. – user18096 Nov 30 '11 at 14:45
If there is a particular step in the proof that you are worried about, or an issue that you don't feel that you completely understand, you could simply edit the question to focus on that one issue. I think it is likely that people would be able to give helpful answers to that sort of question. – Carl Mummert Nov 30 '11 at 14:49
thanks. I will do that. I do have minor concerns regarding my solution. I will point them out above. – user18096 Nov 30 '11 at 14:52
I wouldn't use $<x,y>$ for a pair when you are working with ordered sets, because that leads to a lot of difficulty reading with the other meanings for $>$ and $<$. Just write $(x,y)$. – Thomas Andrews Nov 30 '11 at 15:02
up vote 2 down vote accepted

The way I would think about it is to take a nonincreasing sequence $(\alpha_i,\beta_i)$ and prove that it is eventually constant. Nonincreasing means $(\alpha_{i+1},\beta_{i+1}) \leq (\alpha_i,\beta_i)$ for all $i$ where $\leq$ means $\triangleleft$ or equal.

First, if we define $\gamma_i = \alpha_i \cup \beta_i$, then the fact that the original sequence is nonincreasing means that $(\gamma_i)$ is non-increasing in the usual ordering of the ordinals. Hence $(\gamma_i)$ is eventually constant. (In fact, the ordinal that $(\gamma_i)$ eventually equals will be exactly the $k$ from your proof sketch.)

Hence, by removing finitely many terms from the beginning of the sequence $(\alpha_i, \beta_i)$, we can assume $\gamma_i$ is constant. That means that the first clause of the definition of $\triangleleft$ will never apply. So move on to the next clause of the definition of $\triangleleft$, and apply the same technique. This will show that $\alpha_i$ is eventually constant. Then move on to the third clause and show that $\beta_i$ is eventually constant.

share|cite|improve this answer
Thank you for answering. – user18096 Nov 30 '11 at 20:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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