# Choice Functions

1. May 10, 2005

### 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.

2. May 10, 2005

### honestrosewater

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?

3. May 11, 2005

### laminatedevildoll

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?

4. May 11, 2005

### laminatedevildoll

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.

#### Attached Files:

• ###### test_12_96dpi.jpg
File size:
31.6 KB
Views:
63
5. May 12, 2005

### honestrosewater

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: May 12, 2005
6. May 12, 2005

### laminatedevildoll

{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}

7. May 12, 2005

### honestrosewater

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?

8. May 13, 2005

### laminatedevildoll

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: May 13, 2005
9. May 13, 2005

### Hurkyl

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

10. May 13, 2005

### honestrosewater

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.

11. May 16, 2005

### laminatedevildoll

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: May 16, 2005
12. May 17, 2005

### honestrosewater

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) = ?

13. May 17, 2005

### laminatedevildoll

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

14. May 18, 2005

### honestrosewater

1) What makes you think that's correct? Seriously.

15. May 18, 2005

### laminatedevildoll

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

16. May 18, 2005

### honestrosewater

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?

17. May 20, 2005

### laminatedevildoll

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.

18. May 20, 2005

### honestrosewater

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: May 20, 2005
19. May 22, 2005

### laminatedevildoll

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: May 22, 2005
20. May 22, 2005

### honestrosewater

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.
Yeah, it would be nice if logic was taught to more people and sooner.