Count the number of topological sorts for each partially ordered set $(A,|)$, where (a) $A = (3, 5, 7, 11, 13, 16, 17)$  (b) $A = (1, 3, 9, 27, 81, 243)$   That is, you have to ﬁnd the number of ways to order the elements of the set A so that the partial order imposed by divisibility is preserved.  Edit: I got the answer 7 choose 1 which is 7 for a) and 6 choose 6 which is 1 for b), is that correct?
122810
can someone please explain to me how to count the number of topological sorts  for poset(A|) where A = {2,3,4,8,9,16,27,81} ? Quick example would be nice. Please help...I have an exam in several hours. Thanks !
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?
9446
I found an interesting problem regarding the principle of inclusion and exclusion. Given $1985$ sets, each containing $45$ items, find their total union, if the union of any two is $89$. This is what I did: First, I found out the intersection of any two. Using the principle of inclusion and exclusion, I managed to find out that |$A_{1}$|$\cup$|$A_{2}$|=|$A_{1}$|+|$A_{2}$|-|$A_{1}$|$\cap$|$A_{2}$|. From this, we know that $89=45+45-x$, where $x=1$. The first thing that came to my mind was that this intersection could be the common intersection of all the sets: A solution I found to the entire problem is that there is one element that every set has in common, and 44 elements that each set does not share with no other set. To clarify, one can imagine a flower, whose petals are individual sets, their only common item being the center of the flower. Each and every pair of sets therefore contains the required 89 elements ($44$ elements on one petal $+$ $44$ elements on the other petal $+ 1$ element in the centre), each set also contains $45$ elements. Therefore, the total sum of all the elements, or the union of all the sets, is $1985\times44+1$. But I do not know how to prove this with formulas and expressions. I am also not sure whether this is correct, because of what I found when I tried to solve a similar problem but only with three sets: The rules of this problem are exactly the same as before, only now we have $3$ sets instead of $1985$. I found out two ways to arrange the elements of the sets which satisfy the rules, each of them having a different total union. If we had a three-set Venn diagram, one solution is this: 1 element in the intersection of them all ($A \cap B \cap C$) 44 elements in each individual set but not in any intersection (in $A$,$B$,$C$) The other solution is this: 1 element in each intersection of every pair, but not in the intersection of them all 43 elements in each individual set. Their unions are different, because while in the first solution, the union is $44\times3+1$, while in the second solution, the union is $43\times3+3$. These are different numbers and therefore I am unsure about my solution to the original problem. My question is whether there is an analytical way to solve this problem, or whether I am missing something.
16314
Greetings Community! The above problem you see is a combinatorics problem I could not solve. :( This problem is from ZIO $2010$, P$1$.     Here is what I did: Observe that every graph can be divided into "sub-groups" which may help in solving. We first remove the empty set. Then the singleton set. Consider the bigger but smaller than the sub-parts example:    The singleton sets are $\{4,5,6\}$ which are at the least position in the graph.   The dual sets are $\{2,4\}, \{3,5\}, \{3,6\}$, the bottom - two portions in the graph. The triplet sets are $\{2,4,5\}, \{4,5,6\}$ which we may manually count but for the bigger graphs in the sub-part, this may prove to be difficult and this is where I am stuck.   Any help would be appreciated. Thanks.
90635
Given a well-orderable infinite set $A$, can we always say that the set $$\left\{R\subset A\times A:\langle A,R\rangle\, \text{is a well-ordering}\right\}$$ has cardinality $2^{|A|}$? How much Choice is required for the proof of this? I believe that where $A$ is countably infinite, we can proceed without any use of Choice. Is that correct?
37405
I tried to write a formal proof for the theorem: $A$ subset of $\mathbb R$ well ordered by the normal order $\implies A$ is at most of cardinality $\aleph_0$.  Any suggestions?  Thanks.
67254
a question from my h.w.:  Let $(X,&lt;)$ be a totally ordered set. Lets examine $X$ with the order topology. a. Prove that $\overline{(a,b)} \subseteq [a,b]$ (where the overline denotes closure of the set). Give an example where the inclusion is strict. b. Give necessary and sufficient conditions such that $a\in\overline{(a,b)}$ and such that $b\in\overline{(a,b)}$  So I've managed a. easily enough. I think a proper example of strict inclusion would be a finite set - say $\{1, 2, 3, 4, 5\}$ with the obvious order. Then $(2,4)=\{3\}$ so indeed $ \overline{(2,4)} = \{3\}$ and not $[2,4]$. I'm stumped about the conditions though. Can anyone give me some help? Thanks!
103126
I dont know the concept or how to answer the question.     Suppose there are two sets, $X=\{1,2\}$ and $Y=\{a,b\}$.         What are all the ordered pairs in the form of (element of $X$, element of $Y$)?   What are all the ordered pairs in the form of (element of $Y$, element of $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?
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.
48131
I need to compute the cardinality of the set of all total orders on $\Bbb{N}$.  Now, by definition there is an inclusion of this set into $\mathcal{P}(\Bbb{N}\times\Bbb{N})$, and so has cardinality $\le 2^{\aleph_0}$.  Now, finding an injection from $\mathcal{P}(\Bbb{N})$ to the set in question is much harder. I have the solution below, which I don't really understand and don't intuitively see. It feels like the usual $\le$ with some priority to elements of the set injected, but not quite.  Can anyone extrapolate some meaning from this, or provide a nicer solution?  (apologies for the laziness of not rewriting the solution)
19720
So, to explain the title, I'm referring to the necessity of the axiom of choice in the existence of a well ordering on reals, or any uncountable set.  Now, while tweaking some sets, I came across this :  We start with the natural numbers, $N$. We take the power set of the naturals, $P(N)$.  Then we remove all the finite subsets of $N$ from $P(N)$. Let us call this new set $S$. This set is the set of all infinite subsets of $N$.  It is easy to show that $S$ has uncountable cardinality, same as that of real numbers. This is because the removal of finite subsets only removes a countable number of elements. (Haven't posted this deduction, for it is very easy, but I may post it if it is not so evident)  Now, we seek to find an ordering on the set $S$. Every set in this set is an infinite subset of natural numbers, so each of these sets are well ordered by the natural ordering of $N$.  Taking any two sets in $S$, say $A$, and $B$, we seek to order them by checking their elements lexicographically. We compare the first two elements in $A$, and $B$. Let them be $a_1$, and $b_1$ respectively. If $a_1 = b_1$, then we move on to the second elements in the sets, $a_2$, and $b_2$, and so on. If, at any point, $a_n &lt; b_n$, then $A &lt; B$, or if $b_n &lt; a_n$, then $B &lt; A$.  This order seems to be a well ordering of the uncountable infinity of reals. I don't seem to have invoked the axiom of choice anywhere in the construction of this set $S$.  So, why isn't this a well ordering on the uncountable of reals?
102924
Q.20 What is the number of ordered pairs $(𝐴, 𝐵)$ where $𝐴$ and $𝐵$ are subsets of $\{1,2, . . . ,5\}$ such that neither $𝐴 ⊆ 𝐵$ nor $𝐵 ⊆ 𝐴$?  Ans: 𝟓𝟕𝟎  Hint: Use principle of Inclusion-Exclusion.  Solution: Let $X$ denote the set of all ordered pairs $(A, B)$ when $A ⊆ B$. Similarly let $Y$ denote set of all ordered pairs $(A,B)$ when $B ⊆ A$. The question asks to find $$𝑛(X'\cap Y') = 𝑛(𝑆) − 𝑛(𝑋\cup𝑌) $$$$= 𝑛(S) − 𝑛(X) − 𝑛(Y) + 𝑛(X\cap Y) $$$$= 2^{10} − 3^5 − 3^5 + 2^5 = 570$$.    How did this happen? What is $S$? If $S={1,2,3,4,5}$, shouldn't $n(S)=2^5$? And where do the $3^5$s come from? I cannot understand this.  Also, are there other ways to solve this?
116338
A partially ordered set $(X, \leq)$ is called a lattice if for every pair of elements $x,y \in X$ both the infimum and suprememum of the set $\{x,y\}$ exists. I'm trying to get an intuition for how a partially ordered set can fail to be a lattice. In $\mathbb{R}$, for example, once two elements are selected the completeness of the real numbers guarantees the existence of both the infimum and supremum. Now, if we restrict our attention to a nondegenerate interval $(a,b)$ it is clear that no two points in $(a,b)$ have either a suprememum or infimum in $(a,b)$.   Is this the right way to think of a poset that is not a lattice? Is there perhaps a more fundamental example that would yield further clarity?
6113
Suppose we have a set of $n$ elements. We want to know the maximum number of subsets of $3$ elements we can find of this set such that no two subsets have an intersection with $2$ or more elements.  The question arises from trying to count the number of subgroups isomorphic to $\mathbb{Z}_2\times\mathbb{Z}_2$ in a group with $n$ elements of order $2$ such that the product of any two such elements has also order $2$.
11978
We are given two numbers $a,b$ such that $a&lt;b$. Now we have a set $\{a,a+1,a+2,\ldots, b\}$ (all number between a and b including them). Then, we have to find how many numbers cannot be formed from the above set. The only operation allowed on the set elements is addition.    Note : We can add these number as many times we want. Only addition allowed on these numbers.  Eg : If numbers are 3 and 5, the set is $\{3,4,5\}$ using these we only cannot make $1,2$.  Can anyone help me with that?  I am not getting any idea. I tried the cases when $b-a = 1$.
93883
A set $X$ together with a binary relation $\leq$ such that for all $x,y,z\in X$,  $O1$. $x\leq x$  $O2$. $x\leq y$ and $y\leq x$ then $x=y$  $O3$. $x\leq y$ and $y\leq z$ then $x\leq z$  is called an ordered or sometimes a partially ordered.  An ordered $(X,\leq)$ is called a total order if for all $x,y\in X$, either $x\leq y$ or $y\leq x$.  Question: Show that total orders are maximal orders  My question: is there a typo in the question?  What is a maximal order? How can I prove the question, can you help? Thanks...