# Upper and lower bounds for the cardinalities

• MHB
• mathmari
In summary, we have discussed the upper and lower bounds for the cardinalities of various relations formed from two given relations $M$ and $N$. These include the union, product, intersection, set difference, natural join, and left outer join. The upper bound for the cardinality of the union is $m+n$, while the lower bound is $0$ if the relations are not compatible. The cardinality of the product is $m\cdot n$. The intersection has a lower bound of $0$ and an upper bound of the minimum of $m$ and $n$. The set difference has a lower bound of $0$ and an upper bound of $m$. The natural join combines tuples on their common attribute and has a
mathmari
Gold Member
MHB
Hey! :giggle:

Let two relations $M$ and $N$ be given with the cardinalities $m$ and $n$ respectively. Determine and justify the upper and lower bounds for the cardinalities of the following relations:
- $M\cup N$ :
- $M\times N$ :
- $M\cap N$ :
- $M\setminus N$ :
- $M\Join N$ :
- $M\ltimes N$ : I have done the following : - $M\cup N$ :

If the two relations are compatible then the cardinality is equal to $m+n$,whixh is the upper bound, and if the two relations are not combatible then the union is the empty set and so the cardinality is $0$ which is the lower bound.

- $M\times N$ :

The result is a tuple with both elements so the is the cardinality $m\cdot n$?

- $M\cap N$ :

The intersection contains tuples which are both in $M$ and $N$.Therefore if there no tuple in both then the cardinality is $0$, which is the lower bound. the upper bound is the minimum of $m$ and $n$, or not?

- $M\setminus N$ :

If $M$ and $N$ are two union-compatible relations,then their difference is a relation which contains tuples which are in $M$ but not in $N$. So the cardinality is $0$ if $M=N$ and $m$ if $M\cap N=\emptyset$.

- $M\Join N$ :

It is like a concatenation from $M$ and $N$, so is the cardinality the $m+n$ ?

- $M\ltimes N$ :

This contains all tuples from $M$ but only the lines that are also in $N$. So the cardinality is $0$ as lower bound and $n$ as upper bound, or not?
Is my attempt correct? :unsure:

mathmari said:
- $M\cup N$ :

If the two relations are compatible then the cardinality is equal to $m+n$,whixh is the upper bound, and if the two relations are not combatible then the union is the empty set and so the cardinality is $0$ which is the lower bound.

What if the two relations have a couple of tuples in common? Then the cardinality is not $m+n$ is it? (Worried)

Is the union an empty set if they are not compatible? Or is the union undefined? :unsure:

mathmari said:
- $M\times N$ :

The result is a tuple with both elements so the is the cardinality $m\cdot n$?

Yep. (Nod)

mathmari said:
- $M\cap N$ :

The intersection contains tuples which are both in $M$ and $N$.Therefore if there no tuple in both then the cardinality is $0$, which is the lower bound. the upper bound is the minimum of $m$ and $n$, or not?

Correct. (Nod)
mathmari said:
- $M\setminus N$ :

If $M$ and $N$ are two union-compatible relations, then their difference is a relation which contains tuples which are in $M$ but not in $N$. So the cardinality is $0$ if $M=N$ and $m$ if $M\cap N=\emptyset$.

What if $M \subset N$? That does not seem to be covered.

And what if $M\cap N\ne\varnothing$?

mathmari said:
- $M\Join N$ :

It is like a concatenation from $M$ and $N$, so is the cardinality the $m+n$ ?

Nope. (Shake)

The natural join ($\Join$) combines the tuples on their common attribute, or leaves them out if there is no match.
It implies that the cardinality cannot be $m+n$.

mathmari said:
- $M\ltimes N$ :

This contains all tuples from $M$ but only the lines that are also in $N$. So the cardinality is $0$ as lower bound and $n$ as upper bound, or not?

Suppose $N$ contains only 1 tuple.
And suppose $M$ contains $m$ tuples that each match the tuple in $N$ on their common attribute.
Then we get more than $n=1$ tuples, don't we? (Wondering)

Last edited:
Klaas van Aarsen said:
What if the two relations have a couple of tuples in common? Then the cardinality is not $m+n$ is it? (Worried)

The union is only defined when all columns are the same? :unsure:
Klaas van Aarsen said:
Is the union an empty set if they are not compatible? Or is the union undefined? :unsure:

So what can we say about the lower bound? :unsure:
Klaas van Aarsen said:
What if $M \subset N$? That does not seem to be covered.

And what if $M\cap N\ne\varnothing$?

Ah is the set difference also defined when $M\subset N$? What would then be the result? Would it be the empty set? :unsure:
Klaas van Aarsen said:
The natural join ($\Join$) combines the tuples on their common attribute, or leaves them out if there is no match.
It implies that the cardinality cannot be $n$.

So is the maximum cardinality equal to the minimum of m and n? :unsure:

Klaas van Aarsen said:
Suppose $N$ contains only 1 tuple.
And suppose $M$ contains $m$ tuples that each match the tuple in $N$ on their common attribute.
Then we get more than $n=1$ tuples, don't we? (Wondering)

Ah do we get the number of elements as in $M$? :unsure:

mathmari said:
The union is only defined when all columns are the same?

Yes. So suppose all columns are the same and suppose both M and N have the same tuple.
mathmari said:
So what can we say about the lower bound?

If the union is not defined, then the lower bound is also undefined.
mathmari said:
Ah is the set difference also defined when $M\subset N$? What would then be the result? Would it be the empty set?

Yep. (Nod)
mathmari said:
So is the maximum cardinality equal to the minimum of m and n?

Yes. (Nod)

mathmari said:
Ah do we get the number of elements as in $M$?

In this example we would yes.
And generally $m$ is an upper bound.

Klaas van Aarsen said:
Yes. So suppose all columns are the same and suppose both M and N have the same tuple.

So it must be $m=n$ and this is also the cardinality of the union, or not? :unsure:
Klaas van Aarsen said:
If the union is not defined, then the lower bound is also undefined.

Ahh ok :unsure:
Klaas van Aarsen said:
In this example we would yes.
And generally $m$ is an upper bound.

Ok! And what about the lower bound? Do we get the lower bound if no column of $M$ matches to $N$ ? :unsure:

mathmari said:
So it must be $m=n$ and this is also the cardinality of the union, or not?

Erm... what was the question again? :unsure:
mathmari said:
Ok! And what about the lower bound? Do we get the lower bound if no column of $M$ matches to $N$ ?

Erm... what was the question again? :unsure:

When we say $M$ has cardinality $m$ we don't mean that $M$ is a relation of $m$-tuples, do we? :unsure:

mathmari said:
When we say $M$ has cardinality $m$ we don't mean that $M$ is a relation of $m$-tuples, do we?

The cardinality of a set is the number of elements in the set.
If that number is infinite, some extra rules apply, but in our case I believe we are just talking about finite sets.
The cardinality of the relationship $M$ is the number of tuples in $M$, which is regardless of how many members are in any particular tuple.

So no, the cardinality of $M$ does not depend on the number of members in any particular tuple. (Shake)

Do we have tosuppose that $M$ and $N$ are compatible?

- $M\cup N$ :
So that the union is defined we have to suppose that $m=n$, or not?
The union contains all tuples of $M$ and all tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m+n=2m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
That means a lower bound is $m$ and an upper bound is $2m$. Is that correct? :unsure: - $M\times N$ :
The cartesian product contains all possible combinations of the tuples of $M$ with the tuples of $N$.
So we get $m\cdot n$ elements, which is an uppoer bound.
Is that also the lower bound? :unsure: - $M\cap N$ :
So that the intersection is defined we have to suppose that $m=n$, or not?
The intersection contains all tuples of $M$ that are also tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $0$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
That means a lower bound is $0$ and an upper bound is $m$. Is that correct? :unsure: - $M\setminus N$ :
So that the difference is defined we have to suppose that $m=n$, or not?
The difference contains all tuples of $M$ that are not tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $0$ elements.
That means a lower bound is $0$ and an upper bound is $m$. Is that correct? :unsure: About $M\Join N$ and $M\ltimes N$ I don't have an idea yet... :unsure:

mathmari said:
Do we have tosuppose that $M$ and $N$ are compatible?

- $M\cup N$ :
So that the union is defined we have to suppose that $m=n$, or not?

No. (Shake)
Instead we have to suppose that the $M$ and $N$ have the same columns.
Let's assume each of them has tuples with $k$ members.
Then that is independent of how many tuples each of them has, which is $m$ respectively $n$.

mathmari said:
The union contains all tuples of $M$ and all tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m+n=2m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
That means a lower bound is $m$ and an upper bound is $2m$. Is that correct?

Why would we have $m+n=2m$ elements if all are different? Shouldn't it just be $m+n$? :unsure:

If all tuples in $M$ and $N$ are the same, we reach indeed a lower bound.
And if one of them has a couple more tuples, then the union will have a couple more tuples.

mathmari said:
- $M\times N$ :
The cartesian product contains all possible combinations of the tuples of $M$ with the tuples of $N$.
So we get $m\cdot n$ elements, which is an uppoer bound.
Is that also the lower bound?

Yep. (Nod)

mathmari said:
- $M\cap N$ :
So that the intersection is defined we have to suppose that $m=n$, or not?
The intersection contains all tuples of $M$ that are also tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $0$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
That means a lower bound is $0$ and an upper bound is $m$. Is that correct?

No. Instead we have to suppose that each of them has $k$-tuples with matching columns.

mathmari said:
- $M\setminus N$ :
So that the difference is defined we have to suppose that $m=n$, or not?
The difference contains all tuples of $M$ that are not tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $0$ elements.
That means a lower bound is $0$ and an upper bound is $m$. Is that correct?

Again no. To be defined we merely need that both $M$ and $N$ have $k$-tuples with matching columns.

mathmari said:
About $M\Join N$ and $M\ltimes N$ I don't have an idea yet...

Ok. Let's consider them when we have addressed the others then.

Klaas van Aarsen said:
Instead we have to suppose that the $M$ and $N$ have the same columns.
Let's assume each of them has tuples with $k$ members.
Then that is independent of how many tuples each of them has, which is $m$ respectively $n$.

Ah yes. I confused the number of elements with the number of columns.
Klaas van Aarsen said:
Why would we have $m+n=2m$ elements if all are different? Shouldn't it just be $m+n$? :unsure:

If all tuples in $M$ and $N$ are the same, we reach indeed a lower bound.
And if one of them has a couple more tuples, then the union will have a couple more tuples.

The union contains all tuples of $M$ and all tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m+n$ elements, which is the upper bound.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements, which is the lower bound.
So let $C$ be the carcinality of the union, then we have that $\min \{m,n\}\leq C\leq m+n$, or how do we write the left side? Or cannot we not write that in that form? :unsure:
Klaas van Aarsen said:
No. Instead we have to suppose that each of them has $k$-tuples with matching columns.

The intersection contains all tuples of $M$ that are also tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $0$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
So let $C$ be the carcinality of the intersection, then we have that $0\leq C\leq \min \{m,n\}$, or how do we write the right side? Or cannot we not write that in that form? :unsure:
Klaas van Aarsen said:
Again no. To be defined we merely need that both $M$ and $N$ have $k$-tuples with matching columns.

The difference contains all tuples of $M$ that are not tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $0$ elements.
So let $C$ be the carcinality of the difference, then we have that $0\leq C\leq m$. Or cannot we not write that in that form? :unsure:

mathmari said:
The union contains all tuples of $M$ and all tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m+n$ elements, which is the upper bound.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements, which is the lower bound.
So let $C$ be the carcinality of the union, then we have that $\min \{m,n\}\leq C\leq m+n$, or how do we write the left side? Or cannot we not write that in that form?

We can say that the lower bound is $\max \{m,n\}$ and that the upper bound is $m+n$.
mathmari said:
The intersection contains all tuples of $M$ that are also tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $0$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
So let $C$ be the carcinality of the intersection, then we have that $0\leq C\leq \min \{m,n\}$, or how do we write the right side? Or cannot we not write that in that form?

That is quite correct. (Nod)

mathmari said:
The difference contains all tuples of $M$ that are not tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $0$ elements.
So let $C$ be the carcinality of the difference, then we have that $0\leq C\leq m$. Or cannot we not write that in that form?

That seems fine to me. It shows both the lower and upper bound as requested. (Nod)

Klaas van Aarsen said:
We can say that the lower bound is $\max \{m,n\}$ and that the upper bound is $m+n$.

We take the max because either all tuples are the same or the one has some more elements than the other one? :unsure:

mathmari said:
We take the max because either all tuples are the same or the one has some more elements than the other one?
The union contains at least the $m$ tuples of $M$.
And it also contains at least the $n$ tuples of $N$.
That is $\max(m,n)$.
It happens if all tuples of the one are included in the other or vice versa, giving us a lower bound.

Klaas van Aarsen said:
The union contains at least the $m$ tuples of $M$.
And it also contains at least the $n$ tuples of $N$.
That is $\max(m,n)$.
It happens if all tuples of the one are included in the other or vice versa, giving us a lower bound.

Ahh ok! :geek:

Last edited by a moderator:
As for $M\Join N$ :
The natural union of $M$ and $N$ consists of all combinations of the tuples of the two relations, but only those tuples are listed which have the same values in each column of the two relations.
The Cartesian product is thus formed from which only those tuples are selected whose column values are the same for columns of the same name in the two relations. These columns with the same name are only included once in the result.

Upper bound: $m \cdot n$ (if there is no connecting column, i.e. if we have a Cartesian product)
Lower bound: $0$ (if there are connecting columns but they have no common values)

Let $C$ be the cardinality of the natural join, then we have that $0 \leq C \leq m \cdot n$.

As for $M\ltimes N$ :
The result contains all tuples from $M$ in unchanged form that have a link partner in $N$.

Upper bound: $m$ (if all the tuples of $M$ are the same as the tuples of $N$)
Lower bound: $0$ (if there is no tuple in $M$ that is also in $N$)

Let $C$ be the cardinality of the semi join, then we have that $0\leq K\leq m$.
Is everything correct? :unsure:

mathmari said:
Is everything correct?

All correct. (Sun)

Klaas van Aarsen said:
All correct. (Sun)

Great! Thank you!

## 1. What are upper and lower bounds for the cardinalities?

Upper and lower bounds for the cardinalities refer to the maximum and minimum possible values for the number of elements in a set or collection. These bounds provide a range of possible values and can help determine the size or complexity of a problem.

## 2. How are upper and lower bounds determined?

Upper and lower bounds are determined by analyzing the characteristics and properties of a set or collection. For example, in a set of integers, the upper bound would be the largest integer in the set, while the lower bound would be the smallest integer in the set.

## 3. What is the significance of upper and lower bounds in mathematics?

Upper and lower bounds play a crucial role in mathematics as they provide a way to estimate the size or complexity of a problem. They also help in proving the existence of certain mathematical objects and in determining the efficiency of algorithms.

## 4. Can upper and lower bounds be equal?

Yes, it is possible for upper and lower bounds to be equal. This means that the exact value of the cardinality is known and falls within the given range. However, in most cases, upper and lower bounds are not equal and provide a range of possible values.

## 5. How are upper and lower bounds used in real-world applications?

In real-world applications, upper and lower bounds are used in a variety of fields such as computer science, economics, and physics. They help in analyzing and predicting the behavior of complex systems, as well as in optimizing processes and solving problems efficiently.

• Set Theory, Logic, Probability, Statistics
Replies
3
Views
4K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
428
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
• Calculus
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
13
Views
2K
• Topology and Analysis
Replies
2
Views
214
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Topology and Analysis
Replies
1
Views
764
• Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K