Thread: 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?

My answers:
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.

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?

Originally Posted by anonymouse

My answers:
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.

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

Thanks for the corrections and looking over my work emakarov!

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?

My answers:
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.

Originally Posted by HallsofIvy

Yes, those are all correct.

What about remarks in post #3?

Originally Posted by HallsofIvy

Yes, those are all correct.

See reply #3. There are four pairs in so there are relations with exactly two pairs.