Tagged Questions

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.

39 views

29 views

Counting number of relations that are symmetric and reflexive.

I've looked at the other two problems similair to mine but I'm having a bit of an issue understanding as their solutions seems a bit more complex. While I for the most part understand my professors ...
33 views

Equivalence Relations and Cardinality

I'm looking at the question below from a past paper: What is an equivalence relation? Say that two sets $X$ and $Y$ are related via the relation $\rho$ if $X$ and $Y$ have the same cardinality. Prove ...
35 views

20 views

Can you use constants from the domain in a First Order Formula? [closed]

Say I have a First Order Signature defined like so: $N = (\{1,2,3\dots\},T)$ Where T is a binary relation symbol. Can I use values from the domain to define functions over this signature? For ...
20 views

28 views

How to find inverse of a relation if the inverse isn't a function?

I am trying to find the inverse of the following function $f:\mathbb{Z}^+\rightarrow \mathbb{Z}$ given by $f(a)=\frac{(-1)^a(2a-1)+1}{4}$. I switched $x$ and $y$ and then tried solving for $y$. This ...
45 views

define a relation $R$ on $S$?

Let S be the set of humans. 1) Define a relation $R$ on $S$ that is reflexive, symmetric, and transitive but not antisymmetric 2) Define a relation $R$ on $S$ that is symmetric and antisymmetric ...
11 views

Clarification on a reflexive function

$R_1 = \{(a, b) | a ≤ b\}$ is a reflexive function, but I'm confused on why it is. $a≤b$ but doesn't that not necessarily mean that there is an $a$ that will equal $b$? Couldn't all of the $a$ very ...
31 views

Confusion on sets and relations

I'm confused on how the number of subsets equals the number of relations. If set A = {1, 2} then AxA would be {}, {1}, {2}, {1,2}. I'm confused on how there are $2^{n^2}$ subsets of $A$ x $A$ because ...
15 views

Understanding Fuzzy Composition operations

There are two common forms of composition operation in Fuzzy Theory: max–min composition max–product composition Let R be a relation that relates elements from ...
30 views

For a given relation in $\mathbb{N}\times \mathbb{N}$ find the number of elements in it's equivalence class

The whole problem goes like this: We define the relation $R$ in $\mathbb{N}\times \mathbb{N}$ in the following way: $(a,b)R(c,d)$ iff $a-d=c-b$ First find proof the it's a relation of equivalence (...
74 views

A relation that is both reflexive and irrefelexive

I didn't know that a relation could be both reflexive and irreflexive. However, now I do, I cannot think of an example. So what is an example of a relation on a set that is both reflexive and ...
41 views

Why is $x \mid y$ over $\Bbb N$ a partial order but not total order?

I understand why $x \mid y$ is an example of a partial order relation over $\Bbb N$. But can someone explain why its not a total order relation? By definition a total order relation on a set $A$ is a ...
31 views

Why is the Relation R3 Transitive?

Given $A = \{1,2,3,4\}$ in the Relation $\mathcal{R} = \{(1,1),(2,2),(3,3),(4,4)\}$ I understand why $\mathcal{R}$ is Reflexive, Symmetric but why is it also transitive? In my understanding for a ...
25 views

Equivalence relations and composition, intersections of them

I've been having some trouble with this one, I hope someone get's it. Let S and R be equivalence relations within X. Prove that if R∘S is an equivalence relation, then it is equal to the ...
21 views

Binary relations between any two sets

I have some doubts regarding relations and binary relations in particular.This is what I understand : 1) The graph $G_R$ of a relation R on X and Y is the subset of X × Y defined by $G_R$ = {(x, y) ∈...
27 views

Deteremining whether the relation R on the set of all Real Numbers is Reflexive, Symmetric, Antisymmetric, Transitive, and/or Irreflexive

I am attempting to work out a problem from my Discreet Mathematics Textbook and am a little stuck on part of this one question. I was wondering if someone could walk me through (b) and (c) on the ...
20 views

20 views

equivalence class of kernel relation of floor function

By taking particular values of $k$, I found that equivalence class of $k$, $[k]=\{k,k+1,k+2,...,2k-1\}$, equivalence class of $2k$, $[2k]=\{2k,2k+1,2k+2,...,3k-1\}$ and so on, but how to present it ...
70 views

Suppose that R and S are reflexive relations on a set A. Prove or disprove each of these statements.

I am doing this question with my own attempt. Can anyone help me with the formal way of proving? Thanks! Suppose that $R$ and $S$ are reflexive relations on a set $A$. Prove or disprove each of ...
13 views

Determine whether each of these combinations of R 1 and R 2 must be an equivalence relation.

I have this question but not really sure how to do it when there is union and interception symbol. I am easily confuse when this 2 symbol appear. From my understanding I know that equivalence relation ...
35 views

Let $R_1$ and $R_2$ be the “congruent modulo 3” and the “congruent modulo 4” relations, respectively. Find $R_1\cap R_2$ and $R_1 \cup R_2$.

I have this question and would need help on how to find $R_1 \cup R_2$. My working for $R_1 \cap R_2$ is shown below: Let $R_1$ and $R_2$ be the “congruent modulo 3” and the “congruent modulo 4” ...
37 views

Determine whether the relation is reflexive, symmetric, anti-symmetric, and/or transitive?

Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a, b) ∈ R if and only if a) everyone who has visited Web page a has also ...
28 views

What are the values of the sum?

what are the values of $\sum_{j \in S} 1$, where S = {1, 3, 5, 7}. if we have $\sum_{j = 1}^{n} 1$ then the answer will be n. But what happens if this a set?
9 views

Number of symmetric relations

Let set $A=\{1,2,3\}$ Find number of symmetric relations that can be defined on $A$ containing ordered pairs $(1,2)$ and $(2,1)$ is? Can someone give me some hint for this question?
33 views

How Galois connections between powersets correspond to binary relations?

How to show the well-known bijective correspondence between Galois connections (or rather polarities) between two powersets on some (fixed) sets with binary relations between these sets? You can also ...
24 views

Can a tuple be defined as an instance of a relationship?

SO let's say x and y are in relation. Is (x,y) a tuple and an instance of a relation ? Is a n-tuple an instance of a n-relation?
15 views

What is a minimal relation?

I was reading this definition of transitive closure of a relation, where is written that the transitive closure is minimal: the transitive closure of a binary relation R on a set X is the ...
50 views

A book or Source to further study Relations

I have completed a course on Discrete Mathematics and really enjoyed studying the chapter on relations. In fact I went back and finished what we hadn't covered in class. I did basic stuff like n-ary ...
27 views

Having problem with finding the number of ordered pairs.

Y and Z are proper subset of X this means that X is having all the elements of Y and Z and also Y$\ne$X and Z$\ne$X (This is because we are talking about proper subset and not just subset). Let Y={1} ...
3) Define U = {1, 2, 3, 4, 5}. Consider the following subsets of U: P = {2, 3, 5}, O = {1, 3, 5}, E = {2, 4}, S = {3} a) Create the Hasse diagram using $\subseteq$ as the partial order on sets E, ...