# Solving Choice Functions: Axioms, X={1,2,3}, Finding c:P(X)--->X

• laminatedevildoll
In summary, the conversation discusses the concept of choice functions on a class of sets, specifically focusing on the subset of sets with non-empty members. The conversation also delves into the Axiom of Choice and its implications on choice functions. The question of finding multiple choice functions on a given set is raised, but it is ultimately concluded that there is no general solution. The conversation also mentions the concept of subsets and their relationship to choice functions. Ultimately, the conversation highlights the complexity and intricacies of choice functions and the Axiom of Choice.
laminatedevildoll
I am really confused about this subject matter, as a matter of fact, anything having to do with axioms.

For instance,

If X={1,2,3}

How do I find at least three different choice function c:P(X)--->X?

Is the number of different choice functions in {c:P(X)--->X} 7 since it is without the empty set?

I'd be very grateful for any feedback.

A choice function on a class X of sets S is a function c with dom c = X, such that c(S) is in S for every S in X. If X contains the empty set, can there be a choice function on X? If S is the empty set, can there be some c(S) in S?
Does P(X) always contain the empty set?

Okay, I think I understand it now. I must list all the possible sets, and find out that there are 24 different sets to chose from right?

laminatedevildoll said:
Okay, I think I understand it now. I must list all the possible sets, and find out that there are 24 different sets to chose from right?
Herewith attached is an assignment that I did. It relates to choice functions. I am not sure if I 've done it right, but I don't know how to prove or give counterexamples to the last two statements. Note that the subsets are supposed to have an equal sign underneath.

#### Attachments

• test_12_96dpi.jpg
30.8 KB · Views: 405
laminatedevildoll said:
Okay, I think I understand it now. I must list all the possible sets, and find out that there are 24 different sets to chose from right?
You meant P(X) to be the power set of X, right? The empty set {} is a subset of every set, so the empty set is a member of P(X). If P(X) could be the domain of a choice function c, what would be the value of c({})? The definition says that c({}) is in {}. But this isn't possible, since {} has no members! So P(X) can't be the domain of a choice function; IOW, there exists no choice function on P(X). So the answer to your question, "How do I find at least three different choice function c:P(X)--->X?" is you can't. Unless I've missed something- and I can't imagine what. Note the Axiom of Choice, as stated in my book, reads, "If S is a set of non-empty sets, then there exists a choice function on S."
Of course, you could use P(X) minus the empty set. I think this is called the difference between P(X) and {{}}, denoted P(X)\{{}}. But I'm not sure how to solve your problem now. I'll look at it and offer whatever I can if no one else responds. :)

Edit: Finding the number of choice functions from P(X)\{{}} to X is beyond me. It involves binomial coefficients which I'm not familiar enough with.
For the other problems, what does $\xi_0$ mean?

Last edited:
honestrosewater said:
Edit: Finding the number of choice functions from P(X)\{{}} to X is beyond me. It involves binomial coefficients which I'm not familiar enough with.
For the other problems, what does $\xi_0$ mean?

{1} ---> 1
{2} ---> 2
{3} ---> 3
{1,2} ---> 1 2 2 possibilties
{1,3} ---> 1 3 2 possibilities
{2,3} ---> 2 3 2 possibilities
{1,2,3} ---> 1 2 3 3 possibilities

For the choice functions I thought this was how to do that. So, the different choices would be 24.

For the second part.
$\xi_0$ actually looks like a curly B; I don't know how to write this symbol in Latex.

$\xi_0(X)$ = {A: A not equal to $\emptyset$ and A $\subseteq$ X}

Axiom of Choice: Let X be a set. Then there exists a function c:$\xi_0(X)$ $\rightarrow$ so that c(A) $\in$ for all non-empty subsets A $\subseteq$ X}

laminatedevildoll said:
{1} ---> 1
{2} ---> 2
{3} ---> 3
{1,2} ---> 1 2 2 possibilties
{1,3} ---> 1 3 2 possibilities
{2,3} ---> 2 3 2 possibilities
{1,2,3} ---> 1 2 3 3 possibilities

For the choice functions I thought this was how to do that. So, the different choices would be 24.
Right, you just choose one member from each set. I was talking about a general solution.
For the second part.
$\xi_0$ actually looks like a curly B; I don't know how to write this symbol in Latex.
Like $$\beta$$?
It seems like the problems sometimes mean to say {c(A)} instead of c(A), but I guess you must go by exactly what's stated.
(g) should be false. counterexample: A = B = {{}} so c(A) = c(B) = {}.
(h) is true- your proof is just definitions. You know c(A) is in A, so what is the definition of subset?

honestrosewater said:
Right, you just choose one member from each set. I was talking about a general solution.
Like $$\beta$$?
It seems like the problems sometimes mean to say {c(A)} instead of c(A), but I guess you must go by exactly what's stated.
(g) should be false. counterexample: A = B = {{}} so c(A) = c(B) = {}.
(h) is true- your proof is just definitions. You know c(A) is in A, so what is the definition of subset?

It was more like a power set symbol I think.
The definition of a subset is
c(A) $$\in$$ A for all non-empty subsets A $$\subseteq$$ B}
$$\beta$$(B)= {A: A not equal to $$\emptyset$$and A $$\subseteq$$ B}

Last edited:
How about $\mathcal{B}$? Not the curliest, but the same font as $\mathcal{P}$ which I usually use for the power set symbol.

laminatedevildoll said:
It was more like a power set symbol I think.
The definition of a subset is
c(A) $$\in$$ A for all non-empty subsets A $$\subseteq$$ B}
$$\beta$$(B)= {A: A not equal to $$\emptyset$$and A $$\subseteq$$ B}
I mean just regular subsets. A is a subset of B if every member of A is also a member of B. The problem says A is a subset of B, so every member of A is also a member of B. c(A) is a member of A, so c(A) is also a member of B.

I mean just regular subsets. A is a subset of B if every member of A is also a member of B. The problem says A is a subset of B, so every member of A is also a member of B. c(A) is a member of A, so c(A) is also a member of B.
I think that I was wrong before; is e. false too? If so, is the proof that I already put under there correct? For f. I think that I need a counter example. Is it okay if I put if A $$\subseteq$$ B, then c(B) $$\notin$$ A. But c(B) $$\in$$ B.

Last edited:
laminatedevildoll said:
I think that I was wrong before; is e. false too? If so, is the proof that I already put under there correct? For f. I think that I need a counter example. Is it okay if I put if A $$\subseteq$$ B, then c(B) $$\notin$$ A. But c(B) $$\in$$ B.
I don't understand your proofs; You would need to include some explanation between formulas (at least "implies", "equals", etc.).
e) Does your theory include individuals (or urelements, i.e., objects that aren't sets (or classes)) or do you just have sets? If you have individuals, your proof is easier: $c(A \cap B)$ may be an individual, so it wouldn't be a subset because it wouldn't be a set. If you just have sets, let 0 denote the empty set and let $A \cap B$ = {{0}} ($A \cap B$ has exactly one member). So $c(A \cap B)$ = {0}, and the only subsets of $A \cap B$ are {{0}} and 0. Generally, a set with exactly one member has two subsets: itself and 0. So choose a set S with exactly one member m such that m is neither S nor 0; Then c(S) = m is not a subset of S. Of course, there are other ways, but I think this is the simplest.
f) Does $$\subseteq$$ mean proper subset? Let A be a proper subset of B. Then there exists some x in B such that x is not in A. Counterexample: c(B) = ?

C(B)=B, therefore C(B) is a member of B.

laminatedevildoll said:
C(B)=B, therefore C(B) is a member of B.
1) What makes you think that's correct? Seriously.

because x is not in A. I thought that's what you meant.

laminatedevildoll said:
because x is not in A. I thought that's what you meant.
Right. c(B) is just any member of B. If A is a proper subset of B, then there exists some x in B that isn't in A, so c(B) can be that x. But you said:
"C(B)=B, therefore C(B) is a member of B."
1) c(B) doesn't necessarily equal B - it doesn't follow from anything else stated. c(B) is a member of B. The only way c(B) could equal B is if B were a member of itself.
2) It doesn't follow that for any sets A and B, if A = B, then A is a member of B. If that were so, since every set is equal to itself, every set would be a member of itself! So, for instance, you couldn't have the empty set, which I already know you have.
3) Sets usually aren't allowed to be members of themselves. Do you have the Axiom of Foundation (a.k.a Axiom of Replacement) (you probably do)? If so, your theory doesn't allow sets to be members of themselves. So c(B) couldn't equal B.
4) You already know that c(B) is a member of B- it's part of the definition, so you don't need to derive it. Your counterexample is just the case that A is a proper subset of B and c(B) is the member of B that isn't in A.
Do you fully understand all of this, because it's very important?

honestrosewater said:
Do you fully understand all of this, because it's very important?

I understand it quite well, but I am a bit shaky on coming up with counterexamples. I need to really sit down and go over with what you've said to see if I can understand it much better. I appreciate your kind help.

laminatedevildoll said:
I understand it quite well, but I am a bit shaky on coming up with counterexamples. I need to really sit down and go over with what you've said to see if I can understand it much better. I appreciate your kind help.
Do you understand what a counterexample is?
If not, here's the basics: An argument consists of a set of premises and a conclusion; Each premise can be either true or false (but not both true and false); Same for conclusions- true or false. A counterexample to an argument is a case where all the premises are true and the conclusion is false. For example:

Premise 1: a < b.
Premise 2: b < c.
Conclusion: a < c.

Is there a case where all the premises are true and the conclusion is false? Well, if a = b, Premise 1 is true. If b = c, Premise 2 is true. But then a = c, so the conclusion is false. So a = b = c is a counterexample.
A hint for finding counterexamples: Make the conclusion false. Then ask if all the premises could still be true. For the above example, a < c is false when a = c or a > c. So could a = c, a < b, and b < c all be true together? Could a > c, a < b, and b < c all be true together?

Last edited:
honestrosewater said:
A hint for finding counterexamples: Make the conclusion false. Then ask if all the premises could still be true. For the above example, a < c is false when a = c or a > c. So could a = c, a < b, and b < c all be true together? Could a > c, a < b, and b < c all be true together?

a = c, a < b, and b < c is not true together because if c < b then b < c is false because it's a contradiction.

a > c, a < b, and b < c is false too.

I thought I knew what a counterexample was before. But, I never knew the barebones of it.

Last edited:
laminatedevildoll said:
a = c, a < b, and b < c is not true together because if c < b then b < c is false because it's a contradiction.
a = c, a < b, b < c, and b > c can all be true if a = b = c. For every a and b, exactly one of the following is true:
a = b or a < b or a > b.
a < b is just short for a < b or a = b. If a < b is false, there is only one possibility left: a > b. So the negation of a < b is a > b; When one is false, the other is true. You can find other negations the same way.
Anywho, where did "if c < b " come from? You just want to figure out if a = c, a < b, and b < c can all be true. You aren't adding anything else to the argument; You're finding out if this is a counterexample to the original argument. If you add new premises, you're testing a different argument. The original conclusion was a < c. You know a counterexample to an argument is a case where all the premises are true and the conclusion is false. So if you make the conclusion false and all the premises can still be true, then you've found a counterexample to the original argument.
One case where a < c is false is when a = c is true. If a = b is true, then a < c is false- only one of them can be true. So saying that a = c is true is saying that a < c is false. See? So can a = c and the premises a < b and b < c all be true? If so, a < c can be false while the premises are all true. a = c, a < b, and b < c can all be true- this was the counterexample I gave: a = b = c.
I thought I knew what a counterexample was before. But, I never knew the barebones of it.
Yeah, it would be nice if logic was taught to more people and sooner.

## 1. What is a choice function?

A choice function is a mathematical concept used to make a selection from a set of options. It takes in a non-empty set of options and outputs a single element from that set. It can also be thought of as a rule for choosing one option from a set of options.

## 2. What are axioms in relation to choice functions?

Axioms are statements or principles that serve as the foundation for a mathematical theory. In the context of choice functions, axioms are a set of rules or criteria that a choice function must satisfy in order to be considered a valid choice function.

## 3. How do you solve for a choice function?

In order to solve for a choice function, you must first define the set of options (X) and the set of outcomes (P(X)). Then, you must identify a rule or set of rules that satisfies the axioms for choice functions. This rule will be your choice function, and it will map each subset of X to a single element in X.

## 4. What is the purpose of finding c:P(X)→X in relation to choice functions?

The purpose of finding c:P(X)→X is to determine if the choice function satisfies the axioms for choice functions. This mapping represents the rule that the choice function follows, and by checking if it satisfies the axioms, we can determine if it is a valid choice function.

## 5. Can the set of options (X) be any size in a choice function?

Yes, the set of options (X) can be any size in a choice function. As long as the set is non-empty, a choice function can be defined for it. However, the larger the set, the more complex the choice function may become.

Replies
7
Views
1K
Replies
6
Views
2K
Replies
4
Views
3K
Replies
11
Views
5K
Replies
2
Views
2K
Replies
2
Views
957
Replies
1
Views
1K
Replies
73
Views
10K
Replies
22
Views
4K
Replies
4
Views
4K