0
votes
2answers
19 views

Relations on set A and conditions of existence of descending chains

I am reading through the Elements of Set theory by Herbert Enderton and even though I have passed this exercise long ago,the more I look at my solution the less I believe it. Problem goes like this: ...
2
votes
1answer
38 views

Terminology on pullbacks

I'm quite confused with the use of pullbacks, and in particular I wonder which terminology I shall use in the following examples. Let $X$ and $Y$ be arbitrary sets. Suppose that $f,g:X\to Y$ and I ...
1
vote
2answers
26 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
3
votes
3answers
37 views

An example of symmetric transitive relation that is not reflexive on a set of natural numbers $\mathbb{N}$ [duplicate]

An example of symmetric transitive relation that is not reflexive on a set of natural numbers $\mathbb{N}$. My guess is that such relation does not exist, but I don't know how to prove it.
1
vote
1answer
30 views

A question on relations

Problem Statement: Let $A$ and $B$ be sets. Many books define a relation $\mathcal R$ from $A$ to $B$ to be a subset $ \mathcal R \subseteq A \times B $. Show that such an R is a ...
0
votes
3answers
61 views

What would make a function reflexive, transitive, and/or symmetric?

A binary relation $R$ is a subset of the Cartesian product between two sets $X$ and $Y$, containing a set of ordered pairs $\{(x,y) : x \in X, y \in Y\}$. $R$ is a function if each element of $X$ is ...
1
vote
3answers
20 views

How many reflexive binary relations there are on a finite countable set?

We know that binary relation is subset of Cartesian product made by set on to itself. let's say we have a set with two elements $A=\{0,1\}$ So Cartesian product is $C=A\times A = ...
0
votes
1answer
40 views

Understanding the difference between relations and functions.

$R=\{(1,2),(1,3)\}$ is a relation but not function. The logic for this is that if the first element of every ordered pair must remain different, then it is said to be function. Otherwise, it's just ...
1
vote
1answer
28 views

Finding the cardinality of $\{X\in \mathcal P(\mathbb R)| |X|=\aleph_0 \}$

Let $S$ be a relation over $\mathcal P(\mathbb R)$ such that $A,B\subseteq\mathbb R: \exists f:A\to B, \exists g: B\to A$ and $f,g$ are injections. Find the cardinality of $\{X\in \mathcal ...
1
vote
1answer
54 views

Showing $ (R ∪ R^{-1})^∗ = R^∗ ∪ R^{−1∗} $ is false by giving a counterexample.

Show that $$ (R ∪ R^{-1})^∗ = R^∗ ∪ R^{−1∗} $$ is false by giving a counterexample. I tried the following, but every time it keeps coming out as true (instead of false): If $R = \{(a,b), ...
0
votes
1answer
71 views

How can we prove these equivalence relations [closed]

We have this relation $A= (\mathbb Z_{\geq0})\times(\mathbb Z_{\geq0})\times\ldots\times(\mathbb Z_{\geq0})$. And we have the relation $R$ on $A$ such that: $(a , b)R(c , d)\iff a+d=c+b$ and ...
1
vote
1answer
17 views

Antisymmetric relation (“strong” vs “weak”)

Defining: "weak antisymmetric relation": $\forall a, b \left< a,b \right> \in R \land \left< b,a \right> \in R \Rightarrow a=b$ "Strong antisymmetric relation": $\forall a, b \left< ...
1
vote
1answer
23 views

Name for a generalized relation to be a multiset?

A relation between two sets $A$ and $B$ is a subset of $A \times B$. If taking a multiset subset of $A \times B$, e.g. allowing $(a,b)$ appears twice in the subset, is there a name for such a ...
0
votes
0answers
10 views

For which sets, $X$ the relation is a partial function

Given $T=\left\{\ \left<A,B\right> \in (P(X))^2 | A\subseteq B \right\}$ For which sets, $X$, the relation $(P(X))^2-T \cap (P(X))^2-T^{-1}$ is a partial function? Here's my solution: ...
0
votes
2answers
29 views

Greatest lower and least upper bounds for a set of pairs

Had some trouble with this question in an exam recently, and wanted to make sure I reasoned correctly. The question was: $X$ is a set of pairs of real numbers $(x,y)$, with absolute values less than ...
0
votes
2answers
31 views

Reflexive/Symmetric/Antisymmetric/Transitive

I am having issues identifying if the following are reflexive/symmetric/antisymmetric/transitive. Could anybody help me out? I have the book definitions but I'm confused on really the application of ...
1
vote
0answers
28 views

Prove/disprove questions on equivalence relations and ordered sets

If $R$ is an equivalence relation and a partial order over $A \neq \emptyset$ then every equivalence class contain at least one element. If $(A,\le)$ an ordered set, and $a\in A$ is a single ...
-1
votes
3answers
32 views

AntiSymmetric help

So I understand Symmetric = (a,b) > (b,a) so e.g. A = {(1,2), (2,1) = Symmetric And Anti symmetric = {(1,2), (1,1) = Anti symmetric since the (1,2) is present but no (2,1). But what if we have ...
0
votes
0answers
20 views

Relations that are closed to union and intersection

Let's define that sets are closed to union if for every relation $R,S$ that have certain traits $R\cup S$ have the same traits as well. Likewise for intersection. Determine if the following ...
0
votes
4answers
28 views

Let $(A,<_A)$ and $(B,<_B)$ be two partially ordered sets. Show that $(A,<_A)$ is not isomorphic to $(B,<_B)$.

Let $(A,<_A)$ and $(B,<_B)$ be two partially ordered sets, where $A=\{a,b,c\}$ and $<_A=\{(a,b),(a,c)\}$; $B=\{x,y,z\}$ and $<_B=\{(x,y),(y,z),(x,z)\}$. How to show $(A,<_A)$ is not ...
1
vote
1answer
37 views

state the relations of a set

Consider the following relations: ...
0
votes
1answer
25 views

Need help with compositions of relations

Prove that given relations $R_1 \subseteq A \times B$, $R_2 \subseteq B \times C$, $R_3 \subseteq C \times D$ then $(R1 \circ R2) \circ R3 = R1 \circ (R2 \circ R3)$ I don't know where exactly to ...
1
vote
1answer
33 views

List all elements of the relations

The task is to List all elements of the relations (d) S`, S-1 and S ₀T. ...
0
votes
1answer
39 views

Relations between sets

I have a mutiple choice question on finding the relation but I seem to be blanking. Can someone explain to me how this works? Let $X = \{2,3,4\}$ and $Y = \{0,1,2,3,4\}$. If a relation $P$ ...
1
vote
1answer
121 views

Exercise in Well Orderings

Prove that if $\prec$ is a well-ordering on a set X and if $Y \subseteq X$, then $\prec_Y=\{(x,y) \mid (x \in Y) \wedge (y \in Y) \wedge (x \prec y)\}$ is a well ordering on Y. I am a little ...
0
votes
1answer
54 views

Proving a relation is transitive

I am trying to understand transitive relations. I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive. But for longer sets I am getting confused in ...
1
vote
1answer
54 views

Prove that if the relation (R) is symmetric and antisymmetric on the set X, there exists a Y subset of X such that R is the = relation on Y.

Prove that for any relation R on a set X that is both symmetric and antisymmetric, there is subset Y \subseteq X for which R is the relation = on Y. I will tell you what I know. I know that ...
1
vote
2answers
38 views

How to show properties of a given relation?

I am given that R is a relation on the given set X, and I have to show if the relation is (i) reflexive, (ii) symmetric, (iii) transitive, (iv) asymmetric, and (v) give an example of an element of ...
1
vote
1answer
47 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor ...
0
votes
1answer
31 views

questions about a proof to a question (about relations)

1) $R,S,T$ are relations on the same set. Prove that $R(S\cup T)=RS\cup ST$ The proof that I stumbled upon was the following: $(a,b)\in R(S\cup T)⇒((a,x)\in R)∧((x,b)\in S∨(x,b)\in T)⇒(a,b)\in ...
1
vote
1answer
81 views

Determine if R is an equivalence relation

I've got this question: Consider the relationship $R$ between ordered pairs of natural numbers such that $(a, b)$ is related to $(c, d)$ (denoted by $(a, b) R (c, d)$) if and only if $ad = bc$. ...
0
votes
2answers
33 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
1
vote
2answers
63 views

understanding reflexive transitive closure

Suppose I have the following relation $$R = \{(1,1), (2,3), (3,1)\}$$ To make it reflexive we add the following missing pairs: $$ \{(2,2), (3,3)\}$$ Now I wonder how to find the reflexive transitive ...
0
votes
1answer
40 views

Help determining relations on the set {1, 2, 3}

I'm studying for a midterm and I just want to make sure that my understanding of these 2 problems that my teacher gave is logically sound. If you could take a look and give me some feedback I would ...
0
votes
2answers
37 views

If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite.

If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite. My work: As $A_1$ and $A_2$ are countably infinite, there exists a ...
2
votes
1answer
60 views

Problems with the definition of transitive relation

Recently I found this problem, which made me realize I have some problems with relations that are vacuously transitive. Problem: Assume that $R$ is a relation on $A$ and define the relation $S$ as ...
2
votes
1answer
27 views

Union of Cartesian squares

I am trying to find sufficient and necessary conditions for a relation to be representable as a union of Cartesian squares: $\bigcup_{i\in I}(X_i\times X_i)$ for some family $X_i$ of sets. One ...
1
vote
2answers
31 views

How do you call this feature and property of relation?

If an operator can be defined for $k$ operands, $k \in \mathbb N$, how do you call this feature of the operator? For example, "+" is such an operator. Similarly, for a relation $R$ on a set $X$, $R$ ...
0
votes
1answer
25 views

Are all relations that are symmetric and anti-symmetric a subset of the reflexive relation?

Simple question, but I can't seem to find a guaranteed answer. A symmetric set contains (a, b) if it contains (b, a), but an ...
0
votes
1answer
59 views

Help understanding a theorem on transitivity of a relation

The theorem states this: The relation R on a set A is transitive if and only if $R^n \subseteq R$ for n = 1, 2, 3,... What I'm reading is that the nth power of that set is transitive if the set ...
1
vote
1answer
60 views

Bijection on a component of a cartesian product

I have been recently studying relations and mappings and I have come across the following problem. Consider two non empty finite sets $I,J$ and their cartesian product $I\times J$. Let $f\colon ...
1
vote
4answers
68 views

I do not understand the definition of antisymmetric relations

OK, let A be a set and let R be a binary relation on A. In my class we say that R is antisymmetric if and only if for every a, b in A, if (a, b) in R and (b, a) in R then a = b. Fair enough, but what ...
1
vote
1answer
36 views

prove a set relation R is transitive?

I have been thinking this problems all the evening, please help Let R be a relation on A. Prove that if Dom(R)∩ Range(R) = Ø, then R is transitive. Oh my god, how to prove this???
2
votes
2answers
1k views

How many equivalence relations on a set with 4 elements.

Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there? So I started by making a list of the possible relations: ...
0
votes
1answer
45 views

Reflexive relation on set of $n$ elements

How many reflexive relations are there on a set of $n$ elements? I did the problem and I got the answer $2 ^ {n ^ 2}$. Is it correct? Thanks for the help..!!
0
votes
1answer
25 views

Partial order up to equivalence

In certain contexts one runs into something like a partial order, but the antisymmetry property is weakened as follows: if $x \preceq y$ and $y \preceq x$ then $x \simeq y$, where $\simeq$ is a given ...
1
vote
3answers
64 views

How to write this set?

I hope someone can help me out here :) We have to sets : STUDENTS » All the students of the school CLASSES » All the classes of the school And the relation : STUDENTSCLASSES » Relates the students to ...
0
votes
1answer
23 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
25 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
194 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 ...