Two ordinal problems

Printable View

April 30th 2010, 04:47 AM
Ester

Two ordinal problems

I have this kind of problems:
1) Let $A$ be a set and let $\alpha = \{ \beta \mid \beta \mbox{ is ordinal and } \beta \preceq A \}$ .
Show that a) $\alpha$ is a cardinal number, b) $card(A) < \alpha$

2) Let A and $\alpha$ be the same as above. Show that $\alpha$ is the smallest cardinal, which is greater than $card(A)$ .

I have no idea how to solve these problems. Any help would be nice.. Thanks!
April 30th 2010, 08:20 AM
MoeBlee

Let's do one at a time.

a = {b | b is an ordinal and b is dominated by A}.
Show a is a cardinal.

So where do you start? Start with the definition of

'a is a cardinal'.

Spell that definition out, then work to show that a meets all the requirements in the definition.

Show me what you get doing that.
May 2nd 2010, 02:20 AM
Ester

Quote:

Originally Posted by MoeBlee

Let's do one at a time.

a = {b | b is an ordinal and b is dominated by A}.
Show a is a cardinal.

So where do you start? Start with the definition of

'a is a cardinal'.

Spell that definition out, then work to show that a meets all the requirements in the definition.

Show me what you get doing that.

I have this kind of definition for cardinals:
Let $A$ be a set. Now $card(A) = \mbox{ "the smallest ordinal so that }A \approx \alpha$ ".

So, does this mean I have to find a set B whom $\alpha$ is the smallest ordinal? In this case, is my set $B = \{\beta \mid \beta \mbox{ is ordinal and }\beta \preceq A \}$ ?
May 2nd 2010, 10:17 AM
MoeBlee

Your definition of 'card' is fine.

card(A) = the least ordinal a such that A equinumerous with a

But then we need to define the predicate 'a is a cardinal'.

So, we define:

a is a cardinal <-> there exists an A such that a = card(A)

And we derive:

a is a cardinal <-> (a is an ordinal & a is not equinumerous with any ordinal less than a)

So now you have to prove:

(1) {b | b is an ordinal & b is dominated by A} is an ordinal

(2) {b | b is an ordinal & b is dominated by A} is not equinumerous with any lesser ordinal

For this, of course, you need to refer to your definition of 'ordinal'.

Let me see what you come up with, and I'll help you if you get stuck.
May 2nd 2010, 10:21 AM
MoeBlee

Quote:

Originally Posted by Ester

So, does this mean I have to find a set B whom $\alpha$ is the smallest ordinal?

In this sense you have to find a set X such that a is equinumerous with X and no ordinal less than a is equinumerous with X, but also you still have to show that a is an ordinal.

But it's just as easy to say you need to prove a is an ordinal and that a is not equinumerous with any ordinal less than a (since then the set X can be taken to be a itself).
May 3rd 2010, 04:08 AM
Ester

Quote:

Originally Posted by MoeBlee

Your definition of 'card' is fine.

card(A) = the least ordinal a such that A equinumerous with a

But then we need to define the predicate 'a is a cardinal'.

So, we define:

a is a cardinal <-> there exists an A such that a = card(A)

And we derive:

a is a cardinal <-> (a is an ordinal & a is not equinumerous with any ordinal less than a)

So now you have to prove:

(1) {b | b is an ordinal & b is dominated by A} is an ordinal

(2) {b | b is an ordinal & b is dominated by A} is not equinumerous with any lesser ordinal

1) Let's choose arbitrary $\beta \in \alpha$ and assume that $\gamma \in \beta$ . $\beta \preceq A$ , so there exists an injection $f:\beta \rightarrow A$ . $\gamma \in \beta$ so $\gamma < \beta$ . There for function $g:\gamma \rightarrow A$ is also injection. That means that $\gamma \preceq A$ , so $\gamma \in \alpha$ . $\alpha$ is a set of ordinals and it is transitive, so $\alpha$ is ordinal.

2) I have only ideas for this. I thought, I could begin like this:
Let's choose arbitrary $\beta < \alpha$ . That means $\beta \in \alpha$ , so $\beta \preceq A$ .
Counterexample: $\beta \approx \alpha$ .

I can't get any further here...
May 3rd 2010, 06:43 AM
MoeBlee

Quote:

Originally Posted by Ester

1) Let's choose arbitrary $\beta \in \alpha$ and assume that $\gamma \in \beta$ . $\beta \preceq A$ , so there exists an injection $f:\beta \rightarrow A$ . $\gamma \in \beta$ so $\gamma < \beta$ . There for function $g:\gamma \rightarrow A$ is also injection. That means that $\gamma \preceq A$ , so $\gamma \in \alpha$ . $\alpha$ is a set of ordinals and it is transitive, so $\alpha$ is ordinal.

Very good.

I would put it this way:

Suppose g in b in a. So there is an injection from b into A. Also, the identity function on g is an injection from g into b. So, by composition of functions, we have an injection from g into A. And g is an ordinal. So g in A. So a is epsilon-transitive. So, since a is an epsilon-transitive set of ordinals, we have that a is an ordinal.

Quote:

Originally Posted by Ester

2) I have only ideas for this. I thought, I could begin like this:
Let's choose arbitrary $\beta < \alpha$ . That means $\beta \in \alpha$ , so $\beta \preceq A$ .
Counterexample: $\beta \approx \alpha$ .

You've almost got it (except, I don't see why you use the word 'counterexample' there).

These are the relevant items now:

1. b is equinumerious with a
2. b is dominated by A
3. a is an ordinal
4. I don't want to tell you this one (but you know it) since telling you would give away the answer.
5. Another simple fact I don't want to give away.

So now just draw a contradiction from 1-5. Let me know what you come up with ...
May 3rd 2010, 09:39 AM
Ester

Quote:

Originally Posted by MoeBlee

You've almost got it (except, I don't see why you use the word 'counterexample' there).

Sorry, English is not my native language. :) I think the word what I was thinking was counterassumption (?).

Quote:

Originally Posted by MoeBlee

These are the relevant items now:

1. b is equinumerious with a
2. b is dominated by A
3. a is an ordinal
4. I don't want to tell you this one (but you know it) since telling you would give away the answer.
5. Another simple fact I don't want to give away.

So now just draw a contradiction from 1-5. Let me know what you come up with ...

This is what I came up with:

$\beta \approx \alpha$ and $\beta \preceq A$ , so there for $\alpha \preceq A$ . $\alpha$ is an ordinal, so $\alpha \in \{\beta \mid \beta \mbox{ is an ordinal and } \beta \preceq A\} = \alpha$ . That means that $\alpha \in \alpha$ , which is contradiction. There for the counterassumption is false and orginal statement is true.
May 3rd 2010, 09:45 AM
MoeBlee

Quote:

Originally Posted by Ester

$\beta \approx \alpha$ and $\beta \preceq A$ , so there for $\alpha \preceq A$ . $\alpha$ is an ordinal, so $\alpha \in \{\beta \mid \beta \mbox{ is an ordinal and } \beta \preceq A\} = \alpha$ . That means that $\alpha \in \alpha$ , which is contradiction. There for the counterassumption is false and orginal statement is true.

Perfect. Now, let's see how far you can get with the next part of the exercise you posted.
May 4th 2010, 05:31 AM
Ester

So, I have to show that $card(A) < \alpha$ .

Using the definition of cardinals, I get that card(A) is an ordinal and $card(A) \approx A$ , so $card(A) \preceq A$ . That means that $card(A) \in \{\beta \mid \beta \mbox{ is ordinal and } \beta \preceq A\} = \alpha$ . $card(A) \in \alpha$ , so $card(A) < \alpha$ .

I was also thinking the second problem which I have (Show that $\alpha$ is the smallest cardinal which is greater than card(A)), and this is what I came up with:

Counterassumption: There exists a cardinal $\kappa$ such that $card(A) < \kappa < \alpha$ . We have $\kappa < \alpha$ , which means $\kappa \in \alpha$ . So $\kappa$ is an ordinal and $\kappa \preceq A$ . $card(A) < \kappa$ , so $A \prec \kappa$ .
Now we have $A \prec \kappa \preceq A$ , which leads to $A \prec A$ . This is contradiction.

So the orginal statement is true.

Is this right?
May 4th 2010, 08:13 AM
MoeBlee

Quote:

Originally Posted by Ester

Using the definition of cardinals, I get that card(A) is an ordinal and $card(A) \approx A$ , so $card(A) \preceq A$ . That means that $card(A) \in \{\beta \mid \beta \mbox{ is ordinal and } \beta \preceq A\} = \alpha$ . $card(A) \in \alpha$ , so $card(A) < \alpha$ .

Very good. A couple of notes:

(1) We have that card(A) is equinumerous with A by virtue of the numeration theorem (derived from the axiom of choice and the axiom schema of replacement). (Though, by the Fregean method, this particular proof will work even without numeration theorem.)

(2) Just remember that card(A) in a implies that card(A) is cardinal-less-than a by the fact that both card(A) and a are cardinals (as opposed to merely ordinals, since for certain ordinals we have k in j and k equinumerous with j).

Here's another version (basically the same as yours):

Suppose it is not the case that card(A) < a. So a is less than or equal card(A). (This does not require the axiom of choice, since we're not relying on domination trichotomy holding among all sets but rather only that cardinal less-than trichotomy holds among all cardinals.) So a is dominated by A. So a in a, which is a contradiction, since a is an ordinal (also contradicts axiom of regularity).

Quote:

Originally Posted by Ester

Counterassumption: There exists a cardinal $\kappa$ such that $card(A) < \kappa < \alpha$ . We have $\kappa < \alpha$ , which means $\kappa \in \alpha$ . So $\kappa$ is an ordinal and $\kappa \preceq A$ . $card(A) < \kappa$ , so $A \prec \kappa$ .
Now we have $A \prec \kappa \preceq A$ , which leads to $A \prec A$ . This is contradiction.

Very good. Note that the numeration theorem was used to infer "A is strictly dominated by k" from "card(A) is cardinal-less-than k".