a) Given a set $S$ with the $n$ elements, find the number of ordered pairs $(A,B)$ such that i) $A \subseteq B \subseteq S$ ii) $A \subset B \subseteq S$ b) Let n be a positive integer and S a set of size n. How many relations $\approx$ on S are there that are: i. an equivalence relation and a partial ordering? ii. an equivalence relation and a total ordering? Normally the topic that I ask about I have a general understanding of (Calculus) but I am having a really tough time with Discrete Maths... Any idea what I should do here?
122680
Find total number of relations that are equivalence as well as partial order set. Assume set contains total $n$ elements.     My attempt:  As equivalence relation has property reflexive, symmetric and transitive and POSET has property reflexive, antisymmetric and transitive.  Symmetric and antisymmetric will cancle each other except reflexive relation and transitive relation can case antisymmetric, so it's also absent on resultant relation.  Therefore, all diagonal element should be present to satisfy conditions of equivalence as well as POSET.  So, it's independent of number of total number of element of set and answer will be $1$.     Can you explain in formal way, please?
102859
Theorem Let be $(X,\le)$ a totally ordered set: then for any not empty finite subset $A$ of $X$ there exist the maximum  element and minimum element. proof. Let be $(X,\le)$ a totally ordered set and we prove by induction that any not empty finite subset $A$ of $X$ has a minimum element. Since $X$ is a totally ordered set, previously we observe that any its subset $Y$ (finite or infinite) is a chain. Obviously any subset $A$ of one element $a$ has trivially a minimum. So we suppose that any subset of $n$ elements has a minimum element and then  we consider a subset $A$ of $n+1$ elements: since $A$ is finite there exists a bijection $\phi$ from $A$ onto some natural number $m$, that is the successor of $n$, and so we can organize the elements of $A$  in a finite succession, that is $A=\{a_1,...,a_{n+1}\}$. Now we consider the subset $B=\{a_h\in A:h\le n\}$: obviously $X$ is a subset of $A$ that has $n$ element and so it has a minimum element $b$; so since $A=B\cup\{a_{n+1}\}$ and since $A$ is a chain (remember what before we observed), it must be or $a_{n+1}\le b$ or $b&lt;a_{n+1}$ and so for the transitivity property of the order relation $\le$ in any case $A$ has a minimum element. So now we only have to prove that any not empty finite subset $A$ of $X$ has a maximum element. So we consider the inverse relation $\preccurlyeq$ defined as $x\preccurlyeq y\iff y\le x$ for any $x,y\in X$: clearly $\preccurlyeq$ is a total order, since indeed $\le$ is a total order, and any minimum in $\preccurlyeq$ is a maximum in $\le$ and so since any not empty finite subset $A$ has a minimum in $\preccurlyeq$ it follows that any not empty finite subset in $\le$ has a maximum element. So we concluded the proof.  Is my proof correct? If not how prove the theorem? Could someone help me, please?
103528
There is a set $x = \{A,B,C,D,E,F,G\}$ and the question ask for counting the number of subsets which contain $D$. And the answer is $2^6$. why would it be $2^6$? I know the total number of subsets is $2^{|x|}$ is it realated?
75532
The question is to find an example of a set $S$ and three relations $R_1$, $R_2$, and $R_3$ on it, such that $R_1$ is reflexive but not transitive, $R_2$ is transitive but not symmetric and $R_3$ is symmetric but not reflexive.  This is what I have done:  Let set $S=\{a,b,c,d\}$ and the three realations are as follows:   $R_1 = \{(a,a),(b,b),(c,c),(d,d)\}$ $R_2 = \{(a,b),(b,c),(c,d)\}$ $R_3 = \{(a,b),(b,a),(c,d),(d,c)\}$   If there is a set which is wrong and not satisfying what is needed can anyone help?
59796
This is from a class question, not looking for someone to do homework for me, just seeking clarification.  Let the set X=(a,b,c)  How many distinct total orders can be defined on this set? Why?  I did search around a bit and from , someone said that for a set of N elements the number of total orders is N!  My question is: is this correct, and why? My class notes define a "total order" as a partial order which is comparable, with a partial order being a relation that is Reflexive, Transititve and Antisymmetric. I get all that, but I'm confused as to how this relates to the question given.
54541
A relation is a subset of the Cartesian product of two sets, if "have the same cardinality", denoted as $R$, is a relation, then there must exist set $A, B$, such that $R \subset A \times B$. What are $A, B$ then? They cannot be "set of all sets", because there is no such set according to axiom of regularity (ZFC set theory).  Did I miss something?  Thanks.
79181
I would like to find a way to construct uncountably many non-isomorphic linear (total) orderings of natural numbers (as stated in the title).  I've already constructed two non-isomorphic total orderings. They are $$ 1 &lt; 2 &lt; 3 &lt;\ldots\\ 1 &gt; 2 &gt; 3 &gt;\ldots $$ where "$&lt;$" and "$&gt;$" are  strict total ordering relations.  Thanks in advance for your help.
88963
Assume I have a set $S$ of $N$ elements and I create subsets with $k$ elements from it. With no additional property the number of possible such subsets will be $N \choose k$. Now I want my subsets to satisfy some additional rules $R_i$: Given a set $X$ of subsets of $S$ with $k$ elements (i.e. $\forall A \in X, A \subset S , \#A=k$), $X$ satisfies $R_i$ if and only if for all $A$ and $B$ in $X$, $A$ and $B$ share at most $i$ elements, i.e. $\forall A , B \in X, \#(A \cap B) \le i$. Let's call $S_i$ the set of all such $X$ satisfying $R_i$. I want to know how large a set satisfying $R_i$ can be, i.e. what is $M_i = \max_{X \in S_i} \#X $ For example if $N=1000$ and $k=10$, trivially we have $M_9 = {1000 \choose 10}$: the largest ensemble of subsets of $10$ elements that share at most $9$ with one another is exactly the set of all possible combinations of $10$ elements out of $1000$. Similarly at the other extreme, still for $N=1000$ and $k=10$, we have $M_0 = 1000/10=100$. Is there a formula or clever (not brute force) algorithm to compute other less trivial cases for $i=1,2,\dots8$? BTW even if there is a nice formula, I'll ultimately want to implement a way to get a maximal $X$...
86628
On my assignment, one of the questions ask to list all equivalence relations on S and count how many are of partial orders.   Let S = {u, v, w}. List all equivalence relations on S. How many of these are also partial orders?   Am I to assume the equivalence relations are the possible combinations of each pair S x S ({}, {{u, u}}, {{u, u}, {u, v}} ...) or should their always be a given relation?
81046
What does it mean when you have a set like A = {1, {2}, 3, 4}? Is {2} a subset within A?  Say I have the following:  A = {1, {2}, 3, 4}, B = {1, 2, {3}}, C = {1, 2}  How many elements are in $A \cap B \cap C$? 1 or 2?  What if I want to find $A \times B$, is there 6 elements or 12?
41015
How many subsets of $\{1,2,...,n\}$ have no two consecutive numbers ?  Here is the solution :  The subsets are interpreted as $n$-words from the alphabet $\{0,1\}$. Let $a_n$ be the number of words with no consecutive ones. Then, a word can start from $0$ and proceed in $a_{n-1}$ ways or start with $10$ and proceed in $a_{n-2}$ ways. Therefore, $a_{n} = a_{n-1} + a_{n-2}$. $a_1 = 2, a_2 = 3$. So, $a_n = F_{n+2}$.  I have no trouble understanding the part of the argument linking $a_n$ with the Fibonacci numbers. But, I have trouble understanding the bijective argument.  What is a $n$ word ? And, how is the bijective constructed here ? How is $a_n$ linked to the question ?
92322
Given a set of N elements, compute the number of subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively.  Any hints would be appreciated.  Thanks!
33430
Is the set of partial order relations over $ \mathbb{N}$ countable? I think it's uncountable but don't know how to prove this. I would be very helpful if someone could also give some kind of a strategy for proving uncountability, in particular how to find injective or surjective functions that help proving this.
61114
I have a set with $N$ members $\{1,2, \dots, N\}$. I would like to know number of set partitions in which each subset is either of size $1$ or $2$, i.e., cardinality of each subset in the partition is maximum $2$. For example with $N=3$, we have the set partitions of maximum size $2$ are $\{1,2,3\}, \{(1,2),3)\}, \{1,(2,3)\}, \{(1,3),2\}$. However I am not interested in $\{(1,2,3)\}$ since it is of length $3$. Kindly tell me number of such set partitions for a set with $N$ members.
78567
Can someone please explain to me how to deal with equivalence relations on classes instead of sets? Is there some sort of generalisation of relations?  Thank you
122875
How many ordered pairs $(A,B)$ they are if $A$ and $B$ are subsets of $\{ 1,2,3,4,5 \}$ such that $A \cap B = \{1\}$?  If 1 is in both sets :  Size of $A$ is $&gt;1$ and size of $B$ is $&gt;1$.  $\Rightarrow$ Size of $A \cup B =4$  $$5 \cdot (3 \cdot 3 \cdot 3 \cdot 3) = 405$$ is not correct.  What am I missing here?
84132
How do I find find out how many non reflexive relations X on the set P = {1, 2, 3}?  I know $2^{n^2 - n}$ returns how many reflexive relations there on a set. Do I subtract that from something to get my result?