This tag is intended for questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric,...), composition of relations and similar stuff. More-or-less the things about relations taught in the first elementary set theory or discrete math course.

learn more… | top users | synonyms

0
votes
1answer
20 views

Set Theory - Given 2 sets, are they order-isomorphic

We are given the sets $A=(1,2]\cup ((3,4)\cap \mathbb Q)$ and $B=(1,2)\cup ((3,4)\cap \mathbb Q)$ with the standard order $\leq$ of the reals. Are they order-isomorphic? Meaning, is there a bijective ...
0
votes
1answer
24 views

Simple set theory - Show a set is finite

let $(X, \leq_*)$ be a partially ordered set. Assume there is an isomorphism $f: (X,\leq_*) \to (\mathbb Z, \leq)$ let $A \subseteq X$ be a well ordered subset of $X$ with an upper bound. Meaning ...
0
votes
1answer
152 views

Count number of binary relations between sets

He, I have following questions: We have sets $A$ and $B$, $\left | A \right | = m,\left | B \right | = n$. 1) How many binary relations are there from $A$ to $B$? 2) How many binary relations are ...
1
vote
1answer
496 views

Prove that between every two rational numbers a/b and c/d that there is a rational number and there are an infinite number of rational numbers [duplicate]

So the full problem is Prove that between every two rational numbers $a/b$ and $c/d$ that: There is a rational number There are an infinite number of rational numbers I am having ...
5
votes
1answer
57 views

Question about sets of well-orders and isomorphisms between well-orders

I was thinking about this problem in trying to better get a feel for and understand well-orders (I'm trying to learn some set theory) - right now, I'm not really hoping for anybody to supply me with a ...
1
vote
1answer
24 views

Show that f is a symmetric relation on A

I am learning about relations and I come across this exercise. And I don't understand the problem. Let me first state the problem here: Let $f: A \rightarrow A$ be a function for which $f(f(x))=x$ ...
3
votes
1answer
51 views

Can a relation be transitive when it is not reflexive?

Lets say I have the following set: $$ \{1, 2\}$$ and on it the following relation is given: $$\{(1, 2), (2, 1)\}.$$ Now is the above relation transitive? My confusion: we can see, that it is ...
0
votes
3answers
50 views

Class Transitivity Proof

Prove that a class $T$ is transitive iff $\bigcup_{t \in T},\, t \subseteq T$ iff $a \in t$ whenever $a \in b$ and $b \in T$. I know that I need to begin by proving the first statement implies ...
0
votes
2answers
25 views

Relations & modular artithmetic

Given the following partition on the set N:{ n being natural : n = 7k+p} , where p= 0,1,2,3,4,5,6. 1) Find an equivalence relation ~ on the set N that partitions N into the sets mentioned in the ...
2
votes
1answer
128 views

Is there a name for this property of a binary relation? $\forall x\forall y(x\mathsf{R}y\to\exists z(x\mathsf{R}z\land y\mathsf{R}z)))$

Consider a binary relation $\mathsf{R}$ such that $x\mathsf{R}y$ is the case only if there is some $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case. Is there a well-known name for the ...
0
votes
1answer
28 views

Prove the following $R \subseteq A\times B$ and $S\subseteq B\times C \rightarrow $ $ S \circ R $ is symetric

I want to prove the following $ S \circ R $ is symetric, A,B, C are sets $R \subseteq A\times B$ is Symetric $S\subseteq B\times C$ is Symetric Any Suggestions? Thanks!
1
vote
1answer
39 views

proving antisymmetry of partition refinement

Suppose $P$ is the set of all partitions of some set $S$. $R$ is a binary relation on $P$, the refinement relation, defined as $(\Pi_1,\Pi_2) \in R $ if and only if for every $S_1 \in \Pi_1$, there ...
1
vote
1answer
57 views

On the size of a set of functions such that $f(i)\ne f(i+1)$ for every $i$ (and similar conditions)

For a finite set $A$,let $|A|$ denote the number of elements in the set $A$. (a) Let $F$ be the set of all functions $$f: \{1,2,\ldots,n \} \to \{1,2,\ldots,k\}~~~~~~~~~~ (n\ge 3,k\ge 2)$$satisfying ...
1
vote
0answers
34 views

Prove the following $(R\cap S)^n=R^n \cap S^n$

I would like to prove the following without induction. $$(R\cap S)^n=R^n \cap S^n$$ We can start by take $(a,b)\in (R\cap S)^n$ its represent a path from $a$ to $b$ right? Any hints? Thanks.
-1
votes
1answer
19 views

if a set B has a least upper bound of an on an ordered relation <(a) then will it have least upper bound on an ordered relation <(b)

given a set B ordered by a relation <(a) has a least upper bound property, does B have an least upper bound property if it is ordered by another ordered relation <(b).
0
votes
3answers
51 views

Check the following Relation $R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \}$

I would like to check the following relation: $$R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \},R\subseteq \mathbb{Z} \times \mathbb{Z}$$ Reflexivity Symmetric Transitivity Asymmetric Can I ...
1
vote
3answers
61 views

Given 2 sets (X and Y) is it possible for $f: Y \to X $ to be a relation, or not?

This question is from my Computational Theory course's homework. I completely understand functions and relations (I've taken numerous Calculus courses). Here's a general example of what the question ...
0
votes
1answer
51 views

Shortcut method for proving equivalence relations

Define the relation R on N*N by: (x,y)R(z,w) if and only if x-z = w-y. Check whether R is an equivalence relation. Explain your answer My teacher answer is: Using the shortcut method: ...
0
votes
1answer
41 views

Equivalence class for a relation

Consider the equivalence relation on Z ! Z given by (m, n)R(p, q) if and only if mq = np: (a) Find the equivalence class represented by (2, 5). (b) Describe the set S of the equivalence classes ...
0
votes
1answer
20 views

Question on proving relations

State whether the following statement is true, and either prove it or provide a counter example: Every Relation R on {0,1} satisfies R∘R subset of R. This is a past paper question for an exam I have ...
3
votes
1answer
77 views

$\mathrm{Pol}_m(\mathbb{A})$ viewed as a relation pp-definable from $\mathbb{A}$

First let me recall some (abbreviated, and possibly simplified to suit my situation) definitions: Let $A$ be a finite set and $\mathbb{A}$ some set of relations on $A$. Let $m, n$ be positive ...
-2
votes
1answer
61 views

Determining if $R$ is reflexive, transitive or symmetric on $S$ [closed]

Determine if $R$ is reflexive on $S.$ $S = \mathbb{R}$. Define $R$ by $(a, b)\in R$ if $|a|=|b|.$ $S = \mathbb{R}$. Define $R$ by $(a, b)\in R$ if $a = b + 1.$ $S = \mathbb{R}$. Define $R$ by $(a, ...
0
votes
1answer
46 views

Determining why this is transitive

Why $R_3 = \lbrace (1,2),(3,4)\rbrace$ is transitive? It's like, transitive is said because there's $\{a,b\}$,$\{b,c\}$ then there will be $\{a,c\}$ right? But then, why is that one is said to be ...
0
votes
2answers
50 views

Relations between two functions

Consider the statements (1) "If $f(i) \geq f(j)$ then $q(i) \geq q(j)$", and (2) "If $q(i) < q(j)$ then $f(i) \leq f(j)$". How can we relate these statements? I mean are these related?
1
vote
1answer
56 views

How to prove $R$ is an antisymmetric relation if and only if $R\circ R^{-1}\subseteq\Delta_X$?

$R$ is antisymmetric relation if and only if $R\circ R^{-1}\subseteq\Delta_X$ $\leftarrow$ assume $R\circ R^{-1}\subseteq\Delta_X$. let $(x,y)\in R $ and $(y,x)\in R\rightarrow (y,x)\in R^{-1}$, so ...
0
votes
1answer
40 views

Very Abstract Relation with points

So I have this question on relations, that I really cant understand. I mean, I cant understand the question to be honest. Suppose a set $X$ of points on the plane and we "stabilize" a point $O ∈ X$. ...
0
votes
1answer
61 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
2answers
14 views

$X=\{1,2,\dots,10\},x\rho y\Leftrightarrow x\equiv y(mod\hspace{0.2cm}3)$

$X=\{1,2,\dots,10\},x\rho y\Leftrightarrow x\equiv y(mod\hspace{0.2cm}3)$ i.e $x,y$ have the same reminder when divided by $3$ ( it was actually written in the question). I need to find the number ...
8
votes
3answers
154 views

Can we take images of equivalence relations?

Given a function $f : X \rightarrow Y$, it is well-known that we can take the image under $f$ of any subset $A \subseteq X$, and we can take the preimage under $f$ of any subset $A \subseteq Y$. This ...
0
votes
2answers
37 views

To find $R\circ R^{-1}$ in Discrete mathematics

Today I came across a question in DMS which says: If $R$ is the relation “Less Than” from $A = \{1, 2, 3, 4\}$ to $B = \{1,3,5\}$ then find $R\circ R^{-1}$. Now what is $R\circ R^{-1}$? I know ...
1
vote
1answer
25 views

Number of Relations

I was stacked in one question . It was about number of reflexive relations on set with N elements. I know the solution but i don't know the logic behind it . I know we construct nxn matrix and number ...
0
votes
0answers
40 views

Does a strongly connected relation imply that the relation is also reflexive

Simply want to know if a relation is strongly connected is it also reflexive? Definition of strongly connected $$ R\:is\:strongly\:connected\:in\:A \longleftrightarrow (\forall x)(\forall y)(x,y \in ...
0
votes
1answer
59 views

Calculating a union of 2 relations

I have 2 relations: $$ xSy \Leftrightarrow y = 2x$$ and $$ xTy \Leftrightarrow y = 3x$$ The problem I have is calculating $$x(T \cup S)y$$ and $$xS^+y $$ Could you please help me?
0
votes
1answer
48 views

Does $\neg(x > y)$ imply that $y \geq x$?

Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$ x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x) $$ In accordance ...
2
votes
1answer
42 views

Does(n't) associativity of functional composition follow straightaway from associativity of relational composition?

One thing I find puzzling about the typical way in which associativity of functional composition is proved is that it makes explicit use of the fact that a function is a 'right-unique' relation, i.e. ...
1
vote
1answer
43 views

Rigorous definition of relation composition

Let R be an n-ary multivalued function on A, and let S_1, ..., S_n be a list of length n, each member of which is an m-ary multivalued function on A. How does one rigorously define the composition ...
0
votes
1answer
34 views

$M_1 = (x,y)\quad x²+y²+6y = 7 $ to $x \rightarrow y$

I have two relations: $$M_1 = (x,y)\qquad x²+y²+6y = 7 $$ $$M_2 = (x,y)\qquad x²+y²-6x = 7, \qquad y \ge 0$$ The question is if this relations also reflex functions like $x \rightarrow y$? I ...
0
votes
1answer
36 views

If $E_1$ and $E_2$ are equivalence relations, is $E_1\circ E_2$ an equivalence relation?

I'm given two equivalence relations $E_1$ and $E_2$ over a set A and need to show whether the composition $E_1 \circ E_2$ is reflexive, symmetric and transitive. I only managed to show that $E_1 ...
0
votes
2answers
24 views

Points of a relation

I have the following relation: $M =${$ (x,y), x =$$ {1}\over{t+1}$, $y =$$ {5t + 8}\over{t + 1}$,$t\in\mathbb R$} The task is to sketch the points of M into a coordinate system! But my opinion is ...
2
votes
2answers
44 views

How to find inverse of function $f(x, y)$?

I am aware of the method to find inverse function $f^{-1}(x)$ of $f(x)$, which is Replace $f(x)$ with $y$ Switch $x$'s and $y$'s Solve for $y$ Replace $y$ with $f^{-1}(x)$ the above method ...
1
vote
2answers
16 views

How to show that $|A/R|=|A|/n$.

Suppose $A$ is a finite set and $R$ is an equivalence relation on $A$. Suppose also there is some positive integer $n$ such that for every $x\in A |[x_R]|=n$. Prove that $A/R$ is finite and ...
0
votes
2answers
37 views

What kind of relation is this?

A person can remember himself at different points in the past. Each of 'himself' that he remembers at each point in the past can also remember a person in the past, and so on. So if we have a, b, ...
-1
votes
1answer
38 views

Induced mappings

Suppose $f$ is a mapping from the powerset of $A$ to the powerset of $B$. Let $S$ and $T$ be subsets of $A$. If both $f(\varnothing)=\varnothing$, and $f(S \cup T) = f(S) \cup f(T)$, then is $f$ the ...
5
votes
2answers
123 views

Main Theorems/Techniques for proving Homeomorphism?

General Question: what are the most common Theorems/Methods used to prove Homeomorphism? I encountered: - find the map explicitly - use the Compact-to-Hausdorff Lemma - find cts maps $f$ and $g$ ...
1
vote
1answer
80 views

Equivalence relation question with cardinality and countability $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $

Let $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $ What is the cardinality of $[\pi]_S$ ? Prove that the quotient group $\mathbb R/S$ is uncountable. Well I think that cardinality is ...
1
vote
1answer
86 views

Prove or disprove question with equivalence relation, classes and quotient group

Let $A$ be a set and $R$ an equivalence relation on $A$. Prove or disprove: If $A$ is countable then all the equivalence classes of $R$ are countable. If $A$ isn't countable then the ...
0
votes
1answer
13 views

A criterion for complete lattice.

Is there an infinite partially ordered set $(X,\le)$, in which for each $A\subseteq X$, either $\inf A$ or $\sup A$ exists but for some $A\subseteq X$ either $\inf A$ or $\sup A$ does not exist.
1
vote
1answer
49 views

Quotient group with functions and relations question

For the set $\mathbb Z/5 \mathbb Z $ (the quotient group of $\mathbb Z$ with the relation R that is defined by $xRy$ if $5|y-x$) We'll define the following operations (both are $\cdot, +$ ...
3
votes
3answers
201 views

Equivalence relation question with functions

We'll define on the set: $A=\Bbb R^{[0,1]}$ the relation $R$ by $fRg$ if $f(0)=g(0)$. Make sure it's an equivilence relation. What is $[\cos x]$ ? Describe all the equivalence classes ...
1
vote
3answers
54 views

Proof of equivalence relation on a set

Let $X = \{(a,b) \mid a,b \in \Bbb Z; b \ne 0\}$. We define $(a,b)\mathrel R (c,d)$ iff $ad = bc$. Prove that $R$ is an equivalence relation on the set $X$. Which known set do the equivalence classes ...