1
vote
2answers
46 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 ...
0
votes
1answer
44 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 ...
1
vote
1answer
16 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 ...
2
votes
3answers
50 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 ...
1
vote
1answer
54 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$. ...
5
votes
1answer
104 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. ...
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\}$ ...
1
vote
0answers
26 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 ...
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.
0
votes
5answers
84 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
0
votes
1answer
161 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 ...
1
vote
2answers
581 views

Number of equivalence relations

How many different equivalence relations can be defined on a set of five elements?
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
2answers
94 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 ...
1
vote
2answers
538 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 ...
0
votes
2answers
782 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$ ...
1
vote
0answers
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)$. ...
4
votes
2answers
198 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 ...
2
votes
2answers
176 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 ...
2
votes
1answer
150 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 ...
1
vote
1answer
60 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
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
229 views

The number of equivalence classes of finite symmetric difference relation

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 ...