How many possible relations between two sets?

In summary, a relation between sets A and B is a subset of AxB, and with n elements in A and m elements in B, there are 2nm possible relations between them. However, this also includes the null set of ordered pairs, so the actual number may be 2nm-1. The definition of a relation between sets may vary and may exclude certain cases such as a null set or subsets that do not include all elements in A.
  • #1
Battlemage!
294
45
Say you have set A with n elements and set B with m elements. If I recall, there are a total of 2nm relations between them. But my question is, does this count redundancies? What I mean is, if in the relation A~B = B~A. I don't want to count identical relations twice. Thanks!
 
Physics news on Phys.org
  • #2
In principle A~B = B~A can never be correct because A~B means to for EVERY element in A there is a UNIQUE element in B to which is supposed to be related. And so is the fact with B~A means for EVERY element in B there is a UNIQUE element in A to which is supposed to be related. So they cannot be equal.
 
  • #3
Okay well what I mean is, say the relation is multiplication in a subset of R. Then 3*2 = 2*3. And so on.
 
  • #4
Multiplication is not a relation, it is an operation.
 
  • #5
Battlemage! said:
Say you have set A with n elements and set B with m elements. If I recall, there are a total of 2nm relations between them. But my question is, does this count redundancies? What I mean is, if in the relation A~B = B~A. I don't want to count identical relations twice.Thanks!

A relation between sets A and B is by definition a subset of AxB. If A has n elements and B has m elements, AxB has nm elements. Such a set has 2nm subsets, therefore there are 2nm relations between A and B.
 
  • #6
micromass said:
Multiplication is not a relation, it is an operation.
I thought all operations were types of relations. It appears i mixed some stuff up. Let's just rephrase the question as multuplication instead.
 
  • #7
Battlemage! said:
I thought all operations were types of relations. It appears i mixed some stuff up. Let's just rephrase the question as multuplication instead.
So what is the new question?
 
  • #8
Mark44 said:
So what is the new question?
Im sorry I haven't slept in 38 hours that last post was nonsense.

But as a test, a specific example:

Say I have a set with 6 elements and a set with 4 elements. Call them set A=[a1, a2, a3, a4, a5, a6] and set B=[b1,b2,b3,b4] Each of the 6 elements can be matched with one of the 4 elements, but each of the 4 elements can be matched to any number of the 6. So you can end up with all 6 of set A being associated with the first element of set B, or a1 and a2 being mathed woth b1, a3 being matched with b2, a4 and a5 being mathed with b3, and a6 being matched with b4. And so on. Any combination as long as all 6 from set A are matched with elements from set B and
 
  • #9
I am sorry the definition which I wrote was that of a function and not of relation. Every function is a relation but every relation is not a function.
 
  • #10
What is the difference between mapping and relation? You have to consider this question as well. I think mapping involves every element of say A whereas relation does not if its definition is any subset of AXB. Are the sets AXB and BXA identical I do not think so. That partly answers your self imposed equation A~B = B~A?
 
  • #11
Battlemage! said:
Say you have set A with n elements and set B with m elements. If I recall, there are a total of 2nm relations between them.

To investigate the correctness of that statement, we would need an clear definition for the statement "##R## is a relation between set ##A## and set ##B##".

For example, if ##R =\{(1,4), (2,4)\}## then is ##R## a relation between the sets ##A =\{1,2,3\}## and ##B=\{4\}##?

It looks to me like your result of ##2^{mn}## would count ##R## as being among the relations "between" ##A## and ##B##.

However, doesn't ##2^{mn}## also count the null set of ordered pairs as a relation? Are we going to count a null set of ordered pairs as a relation ? Is it a relation "between" ##A## and ##B## ?
 
  • #12
That means there is no relation between the sets A and B is also a relation! Because that is the meaning of null set being the sub set of AXB and defining a relation between them. Or is teh total number [{2^(nm)} -1]
 
  • #13
Let'sthink said:
Are the sets AXB and BXA identical

Yes, if ##A=B##.
 
  • #14
Stephen Tashi, thanks for responding. What is the correct or appropriate statement of the following:
1. The set A is related to set B.
2.The set B is related to set A.
3. There is a relation between the sets A and B.

The definition given by Cruz Martinez favors the third option. There is a relation between A and B means A is related to B and B is related to A.
 
  • #15
Let'sthink said:
Stephen Tashi, thanks for responding. What is the correct or appropriate statement of teh following:
1. The set A is related to set B.
2.The set B is related to set A.
3. There is a relation between the sets A and B.

I don't know of any standard mathematical definition for a relation "between" sets.

So let's look at your post #8 and consider what you want the statement "##R## is a relation between ##A## and ##B##" to mean.

I think you want each element of ##A## to in at least one of the ordered pairs of ##R##.
With that requirement, we would not consider ##R = \{(a1,b1), (a2,b4)\}## to be a relation between ##A## and ##B## because some of the elements of ##A## are missing in the first members of the ordered pairs of ##R##.

Now let's consider ##R = \{ (a1,b1),(a1,b2), (a3,b4), (a4,b4) ,(a5,b4), (a6,b4)\}##. Do you want ##R## to be a relation between ##A## and ##B## or do you want to disqualify it because it contains both ##(a1,b1)## and ##(a1,b2)## ?
 
  • #16
I think Stephen Tashi is confusing between the definitions of function and relation, which I also did!
 
  • #17
Stephen Tashi said:
I don't know of any standard mathematical definition for a relation "between" sets.

I've seen it in some books, e.g. Lee, Topological Manifolds, Appendix A. The other definition I've seen for a relation is that R is a relation if whenever z ∈ R, z is an ordered pair.
 
  • #18
Cruz Martinez said:
I've seen it in some books, e.g. Lee, Topological Manifolds, Appendix A. The other definition I've seen for a relation is that R is a relation if whenever z ∈ R, z is an ordered pair.

Yes, you're right. But you and Stephen are talking about something else. You are talking about a relation with codomain and domain a set. In this case, two elements of the sets can be related. Stephen seems to be talking about the case where two sets themselves are related. Of course you can define such a relation, but there is no standard one like the OP thinks.
 
  • #19
Folks, here is the standard set theoretic definition of a relation:

$$R~\text{ is a relation}~\Leftrightarrow~\forall r(r \in R~\rightarrow~\exists x \exists y(r~=~<x,y>)~)$$

This definition leave open the possibility that some members of relation ##R## are not ordered pairs.

However, the cross product, ##A~\times~B##, of two sets, ##A## and ##B##, is certainly a relation since it satisfies the definition given above.

The minimum number of possible relations between sets ##A## and ##B## would then be the number of sets in the power set of ##A~\times~B##, but the maximum number of relations is infinite.
 
  • #20
xxxx0xxxx said:
This definition leave open the possibility that some members of relation ##R## are not ordered pairs.

Then it is not the standard definition.
 
  • #21
Ok, if you want to be picky :), the definition leaves open the possibility that some elements of the relation ##R## are not ordered pairs taken from ##A## and ##B##.
 
  • #22
xxxx0xxxx said:
Ok, if you want to be picky :), the definition leaves open the possibility that some elements of the relation ##R## are not ordered pairs.

No. A relation by definition consists only of ordered pairs.
 
  • #23
xxxx0xxxx said:
Ok, if you want to be picky :), the definition leaves open the possibility that some elements of the relation ##R## are not ordered pairs taken from ##A## and ##B##.

You haven't yet stated a definition for "##R## is a relation between sets ##A## and ##B##".

I think the definition you are using implicitly is:

##R## is a relation between sets ##A## and ##B## if and only if ##R## is a subset of ##A \times B##.

That's a reasonable definition for some purposes, but I wouldn't say that its a standard definition.

To answer the question in the original post, we need to know what definition Battlemage wants to use. Perhaps Battlemage's doesn't really want to know about relations. Perhaps his question is:

"How many distinct functions are there that have a domain consisting of set ##A## with cardinality is ##n## and an image that is a non-null subset of set ##B##, where ##B## has cardinality ##m## ?"
 
  • #24
Stephen Tashi said:
You haven't yet stated a definition for "##R## is a relation between sets ##A## and ##B##".

I think the definition you are using implicitly is:

##R## is a relation between sets ##A## and ##B## if and only if ##R## is a subset of ##A \times B##.

That's a reasonable definition for some purposes, but I wouldn't say that its a standard definition.

To answer the question in the original post, we need to know what definition Battlemage wants to use. Perhaps Battlemage's doesn't really want to know about relations. Perhaps his question is:

"How many distinct functions are there that have a domain consisting of set ##A## with cardinality is ##n## and an image that is a non-null subset of set ##B##, where ##B## has cardinality ##m## ?"

Thank you for asking.

Here is what I'm getting at. I have two sets. The first set A is smaller than the second set B. Each element from A must be linked with one and only one element from B, but any element from B can be linked to as many elements of A as there are in A (or as few as zero).

How many possible configurations are there?

I hesitate to use the word "pair" because in this scenario one element from B can have multiple elements from A associated with it, while each element from A can only have one element from B associated with it.

Also if B were smaller than A but the same rules applied (each element of A must be linked to an elememt of B, while each element of B can be linked with as few as zero elements to as many as are in A.).

I do apologize for not using correct technical verbiage here.

Edited to add: the motivation for this came from me thinking about a training problem i had at my new job. We were to categorize documents by how confidential they were. There were a few categories of confidentiality but many types of documents. Being quickly bored of the exercise I was wondering at how big the possible number of arrangements could be, and how that question could be answered in general. I realize most people would question my sanity over such idle curiosity...One more edit- my first estimate was 2 nm where n and m are the size of the two sets, as was suggested, but I doubt it is correct and only have intuition to go by (and mine is quite lacking).
 
Last edited:
  • #25
A relation is a set of pairs. which would include the empty set. So if A has a elements (a not = 0) and B has b elements (b not = 0) then the set of relations between A and B is the set of subsets of A x B This tells you all the ways of matching elements of A with elements B including not matching any.
 
  • Like
Likes Battlemage!
  • #26
Battlemage! said:
Here is what I'm getting at. I have two sets. The first set A is smaller than the second set B. Each element from A must be linked with one and only one element from B, but any element from B can be linked to as many elements of A as there are in A (or as few as zero).

If A has ##n## elements and B has ##m## elements then there are ##m^n## ways of doing what you want.
 
  • Like
Likes Battlemage!

1. What is a relation between two sets?

A relation between two sets is a connection or correspondence between the elements of the two sets. It specifies how the elements of one set are related to the elements of the other set.

2. How many possible relations are there between two sets?

The number of possible relations between two sets depends on the sizes of the two sets. If one set has m elements and the other set has n elements, then there are 2^(mn) possible relations between them.

3. What is the difference between a function and a relation?

A relation is a general concept that describes a connection between two sets, while a function is a specific type of relation where each element of the first set is related to exactly one element of the second set.

4. Can a relation be both reflexive and symmetric?

Yes, a relation can be both reflexive and symmetric. A reflexive relation is one where every element is related to itself, while a symmetric relation is one where if a is related to b, then b is also related to a.

5. How can we represent relations between two sets?

Relations between two sets can be represented in various ways, including tables, graphs, ordered pairs, and arrow diagrams. These representations help to visualize and understand the connections between the elements of the two sets.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
990
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
33
Views
2K
  • Set Theory, Logic, Probability, Statistics
2
Replies
62
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
965
Back
Top