# A few set theory questions

• August 5th 2012, 08:45 PM
anonymouse
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) 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.
• August 5th 2012, 09:02 PM
anonymouse
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?
• August 6th 2012, 01:35 AM
emakarov
Re: A few set theory questions
Quote:

Originally Posted by anonymouse
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.
• August 6th 2012, 03:58 AM
emakarov
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."
• August 7th 2012, 01:04 PM
anonymouse
Re: A few set theory questions
Thanks for the corrections and looking over my work emakarov!
• August 7th 2012, 02:08 PM
HallsofIvy
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?

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.
• August 7th 2012, 02:18 PM
emakarov
Re: A few set theory questions
Quote:

Originally Posted by HallsofIvy
Yes, those are all correct.

What about remarks in post #3?
• August 7th 2012, 02:39 PM
Plato
Re: A few set theory questions
Quote:

Originally Posted by HallsofIvy
Yes, those are all correct.

See reply #3. There are four pairs in $A\times B$ so there are $\binom{4}{2}=6$ relations with exactly two pairs.