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

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

 

[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?

 

[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?

 

[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?

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.

 

[honestrosewater]

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 [itex]\xi_0[/itex] mean?

 

[laminatedevildoll]

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 [itex]\xi_0[/itex] 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.
[itex]\xi_0[/itex] actually looks like a curly B; I don't know how to write this symbol in Latex.

[itex]\xi_0(X)[/itex] = {A: A not equal to [itex]\emptyset[/itex] and A [itex]\subseteq[/itex] X}

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

 

[honestrosewater]

{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.
[itex]\xi_0[/itex] actually looks like a curly B; I don't know how to write this symbol in Latex.

Like [tex]\beta[/tex]?
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?

 

[laminatedevildoll]

Right, you just choose one member from each set. I was talking about a general solution.
Like [tex]\beta[/tex]?
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) [tex]\in[/tex] A for all non-empty subsets A [tex]\subseteq[/tex] B}
[tex]\beta[/tex](B)= {A: A not equal to [tex]\emptyset[/tex]`and A [tex]\subseteq[/tex] B}

 

[Hurkyl]

How about [itex]\mathcal{B}[/itex]? Not the curliest, but the same font as [itex]\mathcal{P}[/itex] which I usually use for the power set symbol.

 

[honestrosewater]

It was more like a power set symbol I think.
The definition of a subset is
c(A) [tex]\in[/tex] A for all non-empty subsets A [tex]\subseteq[/tex] B}
[tex]\beta[/tex](B)= {A: A not equal to [tex]\emptyset[/tex]`and A [tex]\subseteq[/tex] 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.

 

[laminatedevildoll]

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 [tex]\subseteq[/tex] B, then c(B) [tex]\notin[/tex] A. But c(B) [tex]\in[/tex] B.

 

[honestrosewater]

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 [tex]\subseteq[/tex] B, then c(B) [tex]\notin[/tex] A. But c(B) [tex]\in[/tex] 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: [itex]c(A \cap B)[/itex] 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 [itex]A \cap B[/itex] = {{0}} ([itex]A \cap B[/itex] has exactly one member). So [itex]c(A \cap B)[/itex] = {0}, and the only subsets of [itex]A \cap B[/itex] 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 [tex]\subseteq[/tex] 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) = ?

 

[laminatedevildoll]

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

 

[honestrosewater]

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

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

 

[laminatedevildoll]

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

 

[honestrosewater]

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?

 

[laminatedevildoll]

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.

 

[honestrosewater]

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?

 

[laminatedevildoll]

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.

 

[honestrosewater]

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.