1 Attachment(s)

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) Attachment 24435

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.

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?

Re: A few set theory questions

Quote:

Originally Posted by

**anonymouse** My answers:

i) 4

Correct.

Quote:

Originally Posted by

**anonymouse**

You missed {(0,2), (0,3)} and {(0,2), (1,2)}.

Quote:

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.

Re: A few set theory questions

Quote:

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

Quote:

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

Re: A few set theory questions

Thanks for the corrections and looking over my work emakarov!

Re: A few set theory questions

Quote:

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)

Attachment 24435
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.

Re: A few set theory questions

Quote:

Originally Posted by

**HallsofIvy** Yes, those are all correct.

What about remarks in post #3?

Re: A few set theory questions

Quote:

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.