# Tagged Questions

47 views

### Properties of bijections

If a bijection exists between set A={a1, a2, ...} and set B={b1, b2, ...} such that a1 maps to b1 and a2 maps to b2, etc., does this mean if we find a relationship R between a1 and b1 (i.e. f(b1) is ...
45 views

### How many equivalence relations there are on a set with 7 elements with some conditions

Calculate how many equivalence relations there are on $\{1,2,3,4,5,6,7 \}$ that include the set $\{(2,2),(1,3),(3,6),(7,5)\}$ and are foreign to the set $\{(1,7),(4,7),(4,3)\}$. Well I first drew ...
17 views

### Little equivalence-relation problem

If $U=\{1,2,\ldots,1000\}$ and $A = \mathbb P(U) - \{ \emptyset \}$, the following relation $R$ is defined in $A$ $$XRY \Leftrightarrow (\min X = \min Y) \wedge (\max X = \max Y)$$ Calculate ...
51 views

### Relations and Combinatorics exercise

Be $A=\{1,2,3,\ldots,10\}$ Determine how many equivalence relations can be defined in $A$ with exactly two equivalence classes. Determine how many equivalence relations can be defined in $A$ with ...
61 views

### What is the proper way to format a hypothetical syllogism proof?

Problem: Show that these three statements are equivalent, where $a, b \in R:$ (i) $a < b$, (ii) the average of $a, b,$ is greater than $a,$ and (iii) the average of $a$ and $b$ is less than $b$. ...
112 views

### How to simply show that there are “78 'strict ordinal' 2x2 game matrices”

In "Theory of Moves", Steven J. Brams analyses two-player games with two strategies per player, where each player can totally rank his payoffs, although payoffs need not be comparable among players. ...
46 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\}$ ...
28 views

### Finding equivalence relations containing specific equivalences

"Find the number of equivalence relations on the set $\{1,2,3,\ldots,7\}$ such that: a) $1\sim2$ and $3\sim4$. b) $1\not\sim2$, $1\not\sim3$ and $3\not\sim2$." Solving this problem is equivalent to ...
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.
85 views

### Number of equivalence relations with a fixed size

How can I find the number of equivalence relations R on a set of size 7 such that |R|=29? Any advice would be greatly appreciated! :D
192 views

### Bell numbers proof

Let $p(n)$ denote the number of different equivalence relations on a set with $n$ elements (The number of partitions of a set with $n$ elements). Show that $p(n)$ satisfies the recurrence relation ...
658 views

### Number of equivalence relations

How many different equivalence relations can be defined on a set of five elements?
39 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

### Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
560 views

### Variations : Anti-Symmetric Relations on an $n$-Element Set : Graph Theoretic Elucidation

Question: How many antisymmetric relations are there on an $n$-element set? Guess: I suspect that there are $2^n$ such relations. Discussion: I'm told that anti-symmetric relations on a ...
832 views

### Need help counting equivalence classes.

I am having trouble wrapping my head around the concept of equivalence classes. Here is the question: Let $X$ be the set of all nonempty subsets of the set $\{1,2,3,...,10\}$. Define the relation $R$ ...
51 views

### Simple counting question related to equivalence classes

Let $S = \{1,2,3,...,10\}.$ Define the relation $\mathscr R$ on the power set $\mathscr P(S)$ of all subsets of $S$ by: for all $A,B \in \mathscr P(S),A\mathscr RB$ if and only if $N(A) = N(B)$. ...
203 views

### Counting the number of functions

Let $A$ and $B$ be subsets of the set $\Bbb Z$ for all integers, and let $\mathscr F$ denote the set of all functions $f:A\rightarrow B.$ Assume $A = \{1,2,3\}$ and $B=\{1,2,...,n\}$ where $n\ge 2$ is ...
185 views

### Given a relation $R$, is it reflexive? Symmetric? Transitive?

Define the relation $R$ on the set $\mathbf Z^+$ of all positive integers by: for all $a,b \in \mathbf Z^+,aRb$ if and only if $gcd(a,b)\gt 1$. (a) is $R$ reflexive? Symmetric? Transitive? so here ...
151 views

### find the number of equivalence classes of $\mathbb R$.

Let $\mathscr X$ be the set of all nonempty sub sets of the set $\{1,2,3,...,10\}.$Define the relation $\mathscr R$ on $\mathscr X$ by: for all $A,B \in \mathscr X, A\mathscr RB$ if and only if the ...
62 views

### How many equivalence relations $S$ on $A$ are there for which $R⊆S$ ($R$ is an equivalence relation on a set $A$, with $4$ equivalence classes)

Suppose $R$ is an equivalence relation on a set $A$, with four equivalence classes. How many different equivalence relations $S$ on $A$ are there for which $R⊆S$? Thanks in advance
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 ...
Let $\Sigma$ be an infinite set. Let $A,B \subseteq \Sigma$ be of finite symmetric difference iff they have a finite difference, more formally: $A \sim B$ iff $|A \Delta B| \in \mathbb{N}$ How ...