Set Theory proof on well ordered sets

• oliphant
In summary, if A is a well-ordered set and f : A -> B is a surjection to any set B then there exists an injection B -> A.
oliphant

Homework Statement

Without using the Axiom of Choice, show that if A is a well-ordered set and f : A -> B is a surjection to any set B then there exists an injection B -> A.

The Attempt at a Solution

I was wondering if the existence of the surjection from a well ordered set A implies that B is well ordered, and if so how would I prove this? Is this even the right way to start? I'm pretty lost on this so any starting hints would be appreciated.

You can always find a total ordering by just saying that given

$$x, y \in A, x \ge y$$

define a total ordering in B,

$$f(x) \ge f(y)$$

Now you have to show that that's also a well-ordering. That should be pretty straightforward too. Just take a nonempty subset of B and show that it has a smallest element. Since f is a surjection, for every point in the subset there's a corresponding point in a subset of A so you should be able to find it.

You have to show that relation is an ordering first. It's not: here's a counterexample:

A = {1, 2, 3}
B = {x, y}
f(1) = f(3) = x
f(2) = y

$$x \leq y \leq x$$​
without having
$$x = y$$​

So, more care is needed...

I think basic algebra will help. You know pretty much nothing about A and B, aside from the existence of a surjection f:A-->B.

So, if we cross our fingers and hope that we don't have to do something convoluted, if we were to go about defining a function g:B-->A, what are the only reasonable possibilities for g(b)? (For any particular b in B) Is there anything at all about A that relates to b?

Of course, you shouldn't just do it my way. Your idea can be made to work too. It's better to do things both ways -- you get more experience that way!

P.S. how would you do the problem if you assumed the axiom of choice?

We were actually given a proof using the Axiom of Choice by applying it to the set {f^-1 (b) | b \in B} and defining g(b) = c(f^-1(b))

What if I was to define $$g(b) = \{a \in A | f(a) = b\}$$? Then $$g(b)$$ would be a subset of A and so well ordered, and I think I can finish the proof from there.

What is a well ordered set?

A well ordered set is a collection of objects in which there is a specific ordering or ranking among the elements. This means that every element in the set has a unique predecessor (an element that comes before it) and a unique successor (an element that comes after it).

What is the purpose of a proof on well ordered sets?

The purpose of a proof on well ordered sets is to show that a given set is well ordered and to demonstrate the properties and characteristics of well ordered sets. This is important in understanding the behavior and properties of mathematical structures and their applications in various fields of science and engineering.

How do you prove that a set is well ordered?

In order to prove that a set is well ordered, you must show that every non-empty subset of the set has a least element. This means that for any subset, there is always an element that is smaller than all other elements in the subset. This can be done through a process of mathematical induction, where you show that the least element exists for the smallest subset and then use that to prove it exists for larger subsets.

What are the properties of a well ordered set?

Some key properties of a well ordered set include the existence of a least element for every subset, the transitivity of the ordering (if a < b and b < c, then a < c), and the uniqueness of the predecessor and successor of each element. Additionally, every non-empty subset has a first element and every non-empty bounded subset has a maximum element.

What are some examples of well ordered sets?

Some common examples of well ordered sets include the set of natural numbers (ordered by numerical value), the set of positive integers (ordered by numerical value), and the set of alphabetical letters (ordered by alphabetical order). Other examples include the set of positive rational numbers (ordered by numerical value), the set of days in a week (ordered by chronological order), and the set of positive real numbers (ordered by numerical value).

• Calculus and Beyond Homework Help
Replies
1
Views
668
• Calculus and Beyond Homework Help
Replies
9
Views
649
• Calculus and Beyond Homework Help
Replies
4
Views
617
• Calculus and Beyond Homework Help
Replies
3
Views
694
• Calculus and Beyond Homework Help
Replies
1
Views
673
• Calculus and Beyond Homework Help
Replies
1
Views
696
• Calculus and Beyond Homework Help
Replies
2
Views
977
• Calculus and Beyond Homework Help
Replies
13
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
11
Views
451