# Tagged Questions

34 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 ...
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 ...
285 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.
63 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 ...
77 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 ...
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 ...
59 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 ...
254 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 ...
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\}$ ...
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)? ...
34 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.
604 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 ...
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)$?
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 ...
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 ...
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 ...
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 ...
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 ...
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$.
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 ...
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?
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 ...
389 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$, ...
353 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 ...
689 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 ...
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 ...
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\}$ ...
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 ...