# Axiom of Choice to prove two propositions

• erogard
In summary, we discussed the implications of the AC and now are tasked with proving two statements using the AC or its equivalent. The first statement states that every uncountable set has a subset of cardinality \aleph_1, which can be easily shown using a choice function. The second statement states that if B is an infinite set and A is a proper subset of B, then the cardinality of the complement of A in B is equal to the cardinality of B. This can be proven using the fact that the product of two cardinals is their maximum and applying Schroder-Bernstein.
erogard
Hi everyone,

we recently covered some implications of the AC and are now to prove the followings statements with the help of the AC or one of its equivalent:

(1) Every uncountable set has a subset of cardinality $$\aleph_1$$ (the least initial ordinal not less or equal than $$\aleph_0$$, the latter being the cardinality of the set of natural numbers, i.e. $$N$$ itself)

(2) If B is an infinite set and A is a subset of B such that |A| < |B|, then |B - A| = |B|

I have mostly thought about (1) and to fix f as a choice function for such an uncountable set; then the image of this set under f is an element of it, of cardinality less or equal than that of the uncountable one (call it A).

(well I just realized that it is possible to edit the post so I'll be back with my full post in the proper form with my main attempts on (1) )

Last edited:
Are you allowed to use the fact that AC is equivalent to the well-ordering theorem (every set can be well-ordered, i.e. is in bijection with some ordinal)? If so, (1) becomes downright trivial.

How difficult (2) is depends on what assumptions you're allowed to use - you're essentially asked to prove that the sum of two cardinals is their maximum. The proof that I'm familiar with proceeds by first demonstrating that the product of two cardinals is their maximum. A maximo-lexicographical ordering will prove useful.

Last edited:
Hi and thanks for taking a look at my question. Yes indeed I may use the AC or any of its equivalent including the Well-OP; I figured out (1) btw with its application.

I am going to try and think about the way you suggested for (2) which I know requires the AC. I will keep you updated on my progresses.

Edit 1: OK first of all we have shown in class that the product of two cardinals is their maximum, so I can readily use this fact to keep going.

Edit 2: I am basically allowed to use any theorem that follows more or less readily from the AC as we have covered in class most of its equivalent (Zorn's Lemma, Parliamentary axiom, WellOP etc.) You suggest a use of maximo-lexicographic ordering, may you explain a little bit more? I.e. how this could be useful and at what stage this should be used.

Last edited:
erogard said:
Edit 1: OK first of all we have shown in class that the product of two cardinals is their maximum, so I can readily use this fact to keep going.
Ok, so you probably also know $$|B|+|A|=\max(|B|,|A|)=|B|$$.

It's obvious (inclusion is injection) that $$|B-A|\leq|B|$$. Also, we have $$|B|\leq|(B-A)+A|$$, i.e. $$|B|+|A|\leq |B-A|+|A|$$, so $$|B|\leq|B-A|$$.
With Schroder-Bernstein we get $$|B|=|B-A|$$.

## 1. What is the Axiom of Choice?

The Axiom of Choice is a mathematical principle that states that given any collection of non-empty sets, it is possible to choose one element from each set in the collection.

## 2. How is the Axiom of Choice used to prove two propositions?

The Axiom of Choice can be used to prove two propositions by allowing for the creation of a function that maps elements from one set to elements in another set. This function can then be used to show that the two propositions are equivalent.

## 3. What are the benefits of using the Axiom of Choice in mathematical proofs?

The Axiom of Choice can simplify complex mathematical proofs by allowing for the selection of elements from infinite sets, which may otherwise be impossible. It also allows for the creation of new mathematical objects and structures.

## 4. Are there any criticisms of the Axiom of Choice?

Yes, there are some criticisms of the Axiom of Choice. Some mathematicians argue that it leads to counterintuitive results, such as the Banach-Tarski paradox, which states that a solid sphere can be divided into a finite number of pieces and reassembled into two identical copies of the original sphere.

## 5. Can the Axiom of Choice be proven to be true?

No, the Axiom of Choice cannot be proven to be true or false. It is an independent axiom, meaning that it cannot be derived from other axioms in set theory. Its validity is accepted by most mathematicians, but it remains a topic of debate and research in the mathematical community.

• Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
14
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
10
Views
3K
• Set Theory, Logic, Probability, Statistics
Replies
21
Views
11K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
10
Views
4K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K