# Defining reflexive relations

• MHB
• lemonthree
lemonthree
Question: How many reflexive relations are on set A if A has 4 elements?

I'm thinking that the answer to this question is 4, but I don't know whether it is truly that simple.
I know that a reflexive relation, R, occurs when for all x in A, x R x.
so let's say A = {1,2,3,4}.
1~1
2~2
3~3
4~4.
So there are 4 "relations" here. I believe the answer to this is 4, *or* it could be 1 as A~A. Is it right?

HOI
First, do you know what a "relation" is? You seem to be completely misunderstanding this problem.

A relation on set A is any subset of AxA. In this case, since A has 4 members, say A= {a, b, c, d}, AxA has 16 members, AxA= {(a, a), (a, b), (a, c), (a, d), (b, a), (b, b), (b, c), (b, d), (c, a), (c, b), (c, c), (c, d), (d, a), (d, b), (d, c), (d, d)}. Every such pair may or may not be in a subset of AxA. Since A has 16 pairs there are 16 "yes" or "no" choices to determine whether or not a specific pair is in AxA or not. There are $2^{16}= 65536$ subsets. (In general, if a set contains n members then it has $2^n$ subsets.)

If the only condition is that the relation be reflexive then we are only requiring that the subset contain (a, a), (b, b), (c, c), and (d, d). That leaves 12 other pairs that might of might not be in the set so there are $2^{12}= 4096$ such sets.

Last edited:
lemonthree
Thank you for helping to clear my misunderstanding! It seems to remind me of the power set a little.

Just to make sure I'm understanding it right, I can say that all the 4096 reflexive relations on set A *will* definitely contain the 4 sets (a, a), (b, b), (c, c), and (d, d)?

HOI
Yes, that's what "reflexive" means!