2
votes
3answers
36 views

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subests of A cannot all be distinct [closed]

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subsets of A cannot all be distinct. for when does this not continue to hold up ( ie instead of 12 , its ...
0
votes
1answer
65 views

How many symmetric and transitive relations are there on ${1,2,3}$?

I'm trying to count the number of relations on ${1,2,3}$ that are symmetric and transitive. I know how to count the symmetric relations but I can't seem to find the method for this one. I've counted ...
6
votes
2answers
288 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
1
vote
0answers
64 views

General (Set Builder) definition for a relation composed with itself n times

Questions What does the set builder notation for $S\circ R$ look like? I'm having the most trouble knowing when there is too much information or not enough information on either side of the 'such ...
0
votes
1answer
78 views

Finding the number of different relations and functions

This must be a very stupid question. Let set $A=\lbrace{a,b\rbrace}$ and $B=\lbrace{1,2,3\rbrace}$. The total number of relations from $A$ to $B$ is $6$. We can calculate this as a has $3$ choices and ...
0
votes
1answer
35 views

What is the number of inclusive relations?

A binary relation on a set T is inclusive if every element in T relates to at least one element. As an example we can say that {(2, 3), (3, 4)} is not inclusive since 4 does not relate to any ...
0
votes
1answer
60 views

Find the number of subsets $S$ of $X$ (of any size) that satisfy the following property

Let $X=\{1,2,\dots,10\}$ define the relation $R$ on $X$ by: for all $a,b\in X$, $a\mathrel{R}b \iff ab$ is even. 1) Find the number of subsets $S$ of $X$ (of any size) that satisfy the ...
0
votes
2answers
262 views

Number of asymmetric relation

Let $A$ be a set of $n$ elements. How can we calculate number of asymmetric relations on $A$? I googled for it and got the answer that the number is given by $3^{(n^2-n)/2}$, But I don't know how to ...
1
vote
1answer
45 views

how many elements does Ia have?

Let $A=\{1,2,3,4\}$. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by $f,g \in F$ $f R g \Leftrightarrow |f(A)|=|g(A)|$ $f(A)=\{f(x): x\in A\}$ ...
0
votes
2answers
76 views

Let S = {1,2…10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S),

Let S = {1,2....10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S), XRY <=> X∩Y=∅ is it true that ∀X∈P(S),∃Y∈P(S) so that (X,Y)∈R? I dont know what is (X,Y)? ...
0
votes
0answers
35 views

How does Dilworth’s Theorem apply to the set {0, 2, 6, 7}?

I'm having some serious problems with Dilworth's Theorem. My question is 'how does Dilworth’s Theorem apply to the set {0, 2, 6, 7}?'. Any help is appreciated.
4
votes
1answer
614 views

How many transitive relations on a set of $n$ elements?

If a set has $n$ elements, how many transitive relations are there on it? For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but ...
-2
votes
1answer
44 views

How many symmetric relations have (x,y)

Set $w = \{x,y,z,w\}$. How many symmetric relations contain $(x,y)$. I know how to calculate the number of symmetric relations. But how do you calculate how many of those contain $(x,y)$?
0
votes
2answers
139 views

Max value of Anti-symmetric Relation

Here is the question: Let A be a set with |A| = n and R be a relation on A that is anti-symmetric. What is the max value for |R|? How many antisymmetric relations can have this size? So I'm not sure ...
1
vote
2answers
2k views

How to find the number of anti-symmetric relations?

I know that given a set $A = \{1, 2, 3, ... , n\}$, the total number of relations on $A$ is $$2^{n^2}$$ The number of reflexive relations is $$2^{n^2 - n}$$ The number of symmetric relations is ...
0
votes
1answer
38 views

Number of (equivalence) relations fulfilling some additional conditions

let say I have $A=\{1,\dots,8\}$ I want to know the following things: what the number of relations on $A$? what the number of reflexivity relations on $A$? what the number of equivalence relations ...
1
vote
1answer
99 views

Confusion regarding transversal for a partition in Smith Introductory Mathematics: Algebra and Analysis

In Smith's Introductory Mathematics: Algebra and Analysis, I came across the definition of a transversal for a partition along with examples. Either I don't understand one of the examples, or it is ...
4
votes
2answers
95 views

Counting non-isomorphic relations

On a set $X$ of $n$ elements, how many non-isomorphic relations are there? The number of relations on a set of $n$ elements is $|\mathcal{P}(X \times X)|=2^{n^2}$, but is there any way to give a ...
2
votes
2answers
28 views

Determine the number of pairs $(a,b) \in [(1,4)]$ which satisfy $|a|,|b|≤40$

Define an equivalence relations on $Z\times(Z-\{0\})$ by letting $(a,b)\sim (c,d)$ if $ad=bc$. Determine the number of pairs $(a,b)\in\mathbb[(1,4)]$ which satisfy $|a|,|b|\leq40$.
1
vote
2answers
221 views

How many total order relations on a set $A$?

Let's define a set $T_A$ which is the set of all total order relations on $A$. This set is a subset of the set of all $2$-adic relations on $A$: $$T_A \subset \mathcal P(A^2) $$ 1-Which is the ...
2
votes
1answer
64 views

Determining if a Relation is a Partial Order

Consider the following relation on all pairs of real numbers $(x, y): (x, y) \preccurlyeq (x′, y′)$ if $x ≤ 0$ and $y ≤ y′$. Is it a partial order?
3
votes
3answers
1k views

Number of equivalence relations on a finite set

I need a hint for computing the number of ways in which all the equivalent classes on a set of $n$ elements can be realized. For example, if the set has 2 elements ${a,b}$, then there are 2 possible ...
1
vote
1answer
390 views

Warshall's algorithm multiple choice…

Here's a question given to us for practice. Can anyone help me through the steps of solving it? The algorithm itself is confusing to read, so I'm just looking for a concise way to calculate $W_1$, ...
0
votes
1answer
358 views

Multiple choice questions on relations and some of their properties

I'm confused about these 3 selected problems. I have the solutions for each, if necessary, but I'm much more interested in understanding the material. If anyone can offer a clear, concise, and ...
1
vote
3answers
694 views

Trouble understanding equivalence relations and equivalence classes…anyone care to explain?

What exactly are equivalence relations and equivalence classes? The latter is giving me the most trouble; I've tried to read multiple sources online but it just keeps going over my head. Example ...
1
vote
3answers
136 views

Intuitive understanding of relations and their basic properties

Can anyone explain relations and the four basic properties of them (reflexive, symmetric, antisymmetric, transitive)- or direct me to a source that does. Particularly, are these statements ...
1
vote
2answers
292 views

Combination Problem With Relations?

The question is, "How many nonzero entries does the matrix representing the relation $R$ on $A = \{1,2,3,...,100\}$ consisting of the first $100$ positive integers have if $R = \{(a, b)|a>b\}$ ...
4
votes
5answers
5k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...