# Thread: A few set theory questions

1. ## A few set theory questions

I have the following questions which i've anwered but want to check the correctness of before moving on with other similar questions.

1. Let A = {0,1} and let B = {2,3}
i. how many ordered pairs are in A x B
ii. Draw the arrow diagrams for all the relations from A to B that contain exactly 2 ordered pairs.
iii. How many of these are functions?

i) 4
ii)

iii) My understanding is a function requires a 1 to 1 relationship for all elements in the domain so the first two would be functions.

2. ## Re: A few set theory questions

another one that I'm not 100% on:
Let A = {0,1,2}. Let R be the relation from A to 2^A (power set) defined as follows: if x is an element of A and X is a subset of A then (x, X) is in R if and only if x is not a subset of X. Draw the arrow diagram of R.

So I'm thinking the arrow diagram would have the A set on the left, the power set of A on the right and arrows going from the elements in A on the left to the sets on the right which don't contain that A. If this is correct every element in A would also point to the empty set? So every A has 4 arrows?

3. ## Re: A few set theory questions

Originally Posted by anonymouse
i) 4
Correct.
Originally Posted by anonymouse
ii)
You missed {(0,2), (0,3)} and {(0,2), (1,2)}.

Originally Posted by anonymouse
iii) My understanding is a function requires a 1 to 1 relationship for all elements in the domain so the first two would be functions.
"1 to 1 relationship" is not a technical term. There are "one-to-one correspondence" and "one-to-one function," which are not the same thing. See the second paragraph here. Neither of those properties is required for a relation to be a function. Your last example is not a function because it maps one element of the domain to two different elements of the codomain.

4. ## Re: A few set theory questions

Originally Posted by anonymouse
Let A = {0,1,2}. Let R be the relation from A to 2^A (power set) defined as follows: if x is an element of A and X is a subset of A then (x, X) is in R if and only if x is not a subset of X.
You probably mean "an element of X."

Originally Posted by anonymouse
So I'm thinking the arrow diagram would have the A set on the left, the power set of A on the right and arrows going from the elements in A on the left to the sets on the right which don't contain that A. If this is correct every element in A would also point to the empty set? So every A has 4 arrows?
Yes, this is correct, though it should say, "Every element of A has 4 outgoing arrows."

5. ## Re: A few set theory questions

Thanks for the corrections and looking over my work emakarov!

6. ## Re: A few set theory questions

Originally Posted by anonymouse
I have the following questions which i've anwered but want to check the correctness of before moving on with other similar questions.

1. Let A = {0,1} and let B = {2,3}
i. how many ordered pairs are in A x B
ii. Draw the arrow diagrams for all the relations from A to B that contain exactly 2 ordered pairs.
iii. How many of these are functions?

i) 4
ii)

iii) My understanding is a function requires a 1 to 1 relationship for all elements in the domain so the first two would be functions.
Yes, those are all correct.

7. ## Re: A few set theory questions

Originally Posted by HallsofIvy
Yes, those are all correct.
What about remarks in post #3?

8. ## Re: A few set theory questions

Originally Posted by HallsofIvy
Yes, those are all correct.
See reply #3. There are four pairs in $\displaystyle A\times B$ so there are $\displaystyle \binom{4}{2}=6$ relations with exactly two pairs.