The ordered pair $(a,b)$ is defined in formal set theory as the set $\{\{a\},\{a,b\}\}$. Then ordered triples $(a,b,c)$ are defined in this way: $((a,b),c)$. However, can we define ordered triples as the set $\{\{a\},\{a,b\},\{a,b,c\}\}$, and analogously for higher n-tuples. In other words, does such a definition uniquely determine the components of the ordered triple?
117892
releasing a second question concerning ordered stuff and set theory, which is very similar to my first question () which I'm putting here for reference.  The next problem that I'm stuck at in my book is this: we have an ordered triple $(a,b,c)$ and we want to define it using set theory. Why would $\{\{ a\} ,\{ a,b\} ,\{ a,b,c\}\}$ not work? The book requires from me to prove why it is not valid.  Additional info: I don't know how this matters but I'm gonna put it up anyhow. It is written within the book that the correct way to show it is $\{\{ a\} ,\{\{ a\} ,\{\{ b\} ,\{ b,c\}\}\}\}$  EDIT: Now, I consider that the correct case should matter. Besides pointing out why the first case is wrong I'm curious as to why the second one is correct
11200
I need to find the closure of these sets on the ordered square: $$A = \{(1/n)\times 0 | n\in \mathbb{Z}_+\}$$ $$B = \{(1-1/n)\times \frac{1}{2}| n\in \mathbb{Z}_+\}$$ $$C = \{x\times 0 | 0&lt;x&lt;1\}$$ $$D = \{x\times \frac{1}{2}| 0&lt;x&lt;1\}$$ $$E = \{\frac{1}{2}\times y | 0&lt;y&lt;1\}$$ I know that the closure is just the set itself united with its limit points. For $A$, the set of limit points, I imagine, are $\{&lt;1,0&gt;\}$, that is, the $x$ coordinate is $1$ and the $y$ is $0$. But  is says the reverse. What am I getting wrong? Following the same reasoning, $B' = \{&lt;1,\frac{1}{2}&gt;\}$ $C' = \{&lt;0,0&gt;,&lt;0,1&gt;\}$ What am I doing wrong?
40961
So, from what I understand, the axiom of choice is equivalent to the claim that every set can be . A set is well ordered by a relation, $R$ , if every subset has a least element. My question is: Has anyone constructed a well ordering on the reals?  First, I was going to ask this question about the rationals, but then I realised that if you pick your favourite bijection between rationals and the integers, this determines a well ordering on the rationals through the natural well order on $\mathbb{Z}$ . So it's not the denseness of the reals that makes it hard to well order them. So is it just the size of $\mathbb{R}$ that makes it difficult to find a well order for it? Why should that be?  To reiterate:   Is there a known well order on the Reals? If there is, does a similar construction work for larger cardinalities? Is there a largest cardinality for which the construction works?
70700
Is my logic correct/accepted?   Let A be a countable set. Let f:A->B, surjective. $\exists$g:A->N, bijective. Using definition from 1. $\exists$h:N->B, surjective. $\therefore$B is countable by definition using 4.   Am I allowed to assume #4? Does anything need to be cleared up?
29845
Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$.  (a) Prove that $R$ is an equivalence relation.  Here is what I have so far. Is this correct?  Reflexive: $a \sim a$ $\implies$ $a+b=a+b$; $(a,b) R (c,d)$  Symmetric: if $a \sim b$ then $b \sim a$ $\implies$ if $a+d=b+c$ then $c+b=d+a$  Transitive: if $a \sim b$ and $b \sim c$ then $a \sim c$ $\implies$ if $a+d=b+c$ and $c+f=d+e$ then $a+d=d+e$  (b) Find $[(1,1)]$.  I'm not sure how to approach this.
67881
I'm doing the following exercise from Just/Weese:  Show in ZF that (WO) implies (IC) and that (IC) implies (SC).  where  (WO) Every set can be well-ordered.   (IC) For any two sets $X,Y$ either there is an injection $X \hookrightarrow Y$ or $Y \hookrightarrow X$.  (SC) For any two sets $X,Y$ either there is an surjection $X \twoheadrightarrow Y$ or $Y \twoheadrightarrow X$.    (WO) $\rightarrow$ (IC): Let $X,Y$ be two sets. Then by (WO) they can be well-ordered. Therefore each is in bijection with an ordinal $\alpha$ (and $\beta$, respectively):  Claim: Every well-ordered set is isomorphic to an ordinal.  Proof: Let $\langle, X,W \rangle$ be a well-ordered set. Let $\alpha$ be an ordinal with $|\alpha| \ge |X|$. Define an injective map $f: X \hookrightarrow \alpha$ as follows:   (i) Let $x_0$ be the $W$-minimal element. Then $x_0 \mapsto \varnothing$.  (ii) Assume $f$ has been defined for $x \in I_W (x')$. Define $x' \mapsto \sup^+ f(I_W (x'))$.   Let $\tilde{f} = f: X \to \mathrm{im}f$. Then $\tilde{f}$ is a bijection and $\mathrm{im}f$ is an initial segment of an ordinal hence also an ordinal.$\Box$  Either $\alpha \in \beta$ or $\beta \in \alpha$. Hence either $X \hookrightarrow Y$ or $Y \hookrightarrow X$.    (IC) $\rightarrow$  (SC): Let $X,Y$ be sets. Then either $X \hookrightarrow Y$ or $Y \hookrightarrow X$. Given $X \hookrightarrow Y$ it is easy to construct a surjection $Y \twoheadrightarrow X$, similarly for $Y \hookrightarrow X$.     Can you tell me if these proofs are correct? Thanks.  I also wanted to prove (IC) $\rightarrow$ (WO), but I'm stuck. I thought of something like if $X$ is a set and $\alpha$ is an ordinal then either $X \hookrightarrow \alpha$ or $\alpha \hookrightarrow X$ but the latter case seems to be a dead end.
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?
110608
Sometimes one needs two disjoint copies of a given set $X$. This can be canonically done by taking $\{0\} × X$ and $\{1\} × X$. Sometimes we want to identify one of the copies with the original set $X$. So I wonder, is it possible to take a disjoint copy of $X$ straight ahead? And can this be done canonically? More precisely, are the following claims true? $ \def\dom{\operatorname{dom}} \def\rng{\operatorname{rng}} \def\On{\mathbf{On}} $   For every $X$ there is a one-to-one function $f$ such that $\dom(f) = X$ and $\rng(X) ∩ X = ∅$. There is an explicit formula $φ(X, f)$ such that for every $X$ there is exactly one $f$ satisfying $φ(X, f)$ and this $f$ satisfies 1. for $X$.   Since such construction of a disjoint copy is intuitively trivial, I'm interested in proofs of 1. and 2. without using regularity, choice, or infinity.   Some ideas:   We may simply put $f(x) := (x, X)$, but we need regularity to show that $(x, X) ∉ X$. We may consider $α = \sup(X ∩ \On)$ and pair members of $X$ with some ordinals above $α$, but we need AC to well-order $X$, and we need global choice to obtain 2. Let $&lt;$ be the transitive hull of $∈$. If the relation $&lt;$ is narrow, i.e. $\{y: y &lt; x\}$ is a set for every $x$, then we may choose $z ∉ ⋃\{(\leftarrow, x)_&lt;: x ∈ X\}$ and put $f(x) := (x, z)$ since $(x, z) = y ∈ X$ would imply $z &lt; y$. Note that we don't need the axiom of infinity to define $&lt;$, but I don't know how to prove its narrowness without infinity.
43812
Let's say I have numbers each taken in a set $A$ of $n$ consecutive naturals, I ask myself : how can I found what are all the unique multisets, which could be created with $k$ elements of this set $A$?  For example I've got $A=[1,2,\dots,499]$. If I wanted to create unique multiset of 3 elements, I would search all the multisets $\{a,b,c\}$ such as $a\leq b\leq c$ and then have all the unique multisets. As such for each elements $a$ there is $499-(a-1)=500-a$ possibilities for $b$ and $500-b$ possibilities for $c$. Unfortunately I'm stumped here and can't find the number of possible combination, as I didn't do any maths for years. I know that I should have some kind of product, but I don't know how to find the product anymore.  So first, I would like to know if I am right in my original assumption, or if I am looking in the wrong direction. Second I would like to approach that as if I were doing an homework, as I would like to understand the logic behind it: What would be the formula to give the numbers of multisets of $k$ elements from a set $A$ of $n$ consecutive naturals?  P.S. I'm totally new to math.SE, as such, I'm not sure I tagged the post appropriately.
86488
For a finite set $S$ there are $\vert S\vert!$ orderings of its elements.  What is the cardinality of all orderings of $\mathbb{N}$?  What would $$\vert \mathbb{N}\vert!$$ mean?  Is it $\prod_{n\in\mathbb{N}} \aleph_0=\aleph_0^{\aleph_0}=\aleph_1$?   says the "equivalence classes of well-orderings of the natural numbers" has cardinality $\aleph_1$.  But I can't put together in my mind the connection between well-orderings of $\mathbb{N}$ and all orderings of $\mathbb{N}$.  (Are there non well-ordered orderings of $\mathbb{N}$?)  This leads to wondering what the cardinality of all orderings of $\mathbb{R}$ is.  (Actually my thought process went in the other direction, from $\mathbb{R}$ to $\mathbb{N}$.)  I think knowing the answer to the above question will teach how to determine what $$\vert \mathbb{R}\vert !$$ means, if anything.  I will be happy if you assume the continuum hypothesis to be true for the purposes of this question, but any level of completeness is welcome.
25440
Prove that there exist uncountable family of subsets of $\mathbb{N}$ which is linearly (totally) ordered by realtion of inclusion.  I do not know how to prove it. Actually I cannot concieve that such family of set can be uncountable. I would be thankful for help
88618
Let $(X, \leq)$ be an infinite poset. Prove that there is an infinite $X&#39; \subset X$ for which holds one of the following:  1) Induced order on $X&#39;$ is linear.  2) $(X&#39;, \leq_\mathrm{ind})$ is antichain. (Every two elements in $X&#39;$ are incomparable)    My attempt:  Let's start trying to construct a linearly ordered set $(X&#39;, \leq_\mathrm{ind})$ element by element. First we take some element $x_1 \in X$, then we take another $x_2 \in X$ such as $x_1 \leq x_2$ or $x_2 \leq x_1$. Basically, we take an element from $X$, if it is "good" we put it in our chain, otherwise we throw it away. We continue constructing the chain that way. If we do not stop at some finite step, then we are done, we have constructed linearly ordered subset.  If we do stop at some $x_n$ that means that we have finite amount of comparable elements, which means that $X \setminus X&#39;$ is an antichain.    a) I am not sure about the soundness in the last step, could somebody please check it?  b) Can this be proved without a choice function?
84031
Claim  Let A is well-ordered set.  $C \approxeq A$ or $C \approxeq \text{section of } A$ $\forall C$ s.t. $C \subset A$   Proof  If $C=A$, $C \approxeq A$ since a well-ordered set is order-isomorphic to oneself.  If $C \neq A$, there $\exists a \in A$ s.t. $a \notin C$. Then   $A\setminus C = \{a \in A \;|\;a \notin C\}$.  Now, since A is well-ordered, there $\exists$ least element in $A\setminus C$, so let this least element be $m_0$.  Now let $S_{m_o} = \{a \in A \;|\; a&lt; m_0\}$ which is a section of A.  Now define $\phi : C \to S_{m_0}$ s.t. $\forall C_0, C_1 \in C$ if $C_0 \le C_1$ then $\phi(C_0) \le \phi(C_1)$   There $\exists \;\text{such}\;\phi$ since $C$ and  $S_{m_0}$ are all-well-ordered since A is well-ordered.  So by definition $\phi$ is increasing. Also, $\phi$is bijective since the number of element in $C$ and $S_{m_0}$ is equal.  Thus,  $\phi^{-1}$ also exists and it is also increasing and bijective by definition.  Thus $C \approxeq \text{section of } A$
12861
I wonder about the foundations of set theory and my question can be stated in some related forms:   If we base Zermelo–Fraenkel set theory on first order logic, does that mean first order logic is not allowed to contain the notion of sets? The axioms of Zermelo–Fraenkel set theory seem to already expect the notion of a set to be defined. Is there are pre-definition of what we are dealing with? And where? In set theory, if a function is defined as a set using tuples, why or how does first order logic and the axioms of Zermelo–Fraenkel set theory contain parameter dependend properties $\psi(u_1,u_2,q,...)$, which basically are functions?
12731
I asked a similar question yesterday about well ordered sets, now I am having troubles with equivalence relations.   Could someone suggest an injection from a well known set of cardinality $2^{\aleph_{0}}$ to the set of all equivalence relations of $\mathbb{N}$?  Many thanks in advance!
81044
Let $A$, $B$ be sets and denote by $A\leq^* B$ an assertion that if $A$ is non-empty, then there's a surjection from $B$ onto $A$. This might be understood as a dual definition of cardinality. (Typically we use injections to capture the notion of A not being bigger than B. The $\leq^*$ notation is to be read as B not being smaller than A.)  Is this relation trichotomous without using the axiom of choice? Meaning for every two sets $A$ and $B$, it holds $A\leq^* B$ or $B\leq^* A$. (I would be surprised). Would trichotomy imply some interesting extra-ZF axiom?  More broadly, is there anything to be said about $\leq^*$? For example how does it relate to the usual comparisons of cardinality by injections?  I suspect there's no clear answer, since it is somehow reminiscent of Partition Principle ($A\leq^* B \implies A\leq B$) and Weak Partition Principle ($A\leq^* B \implies B\not&lt; A $) which both are independent of ZF.
106936
For a set A with a partially ordering &lt;=, define the following  1)  A subset s(x) of A = {y in A such that y &lt;=x}  2)  A subset S of A with the property that for every x in S then all y in A which are &lt;= x are also in S.  Most references I find call s(x) the initial segment of the element x in A. But in Azriel Levy’s book     he calls s(x) the initial section of x in A and defines S as an initial segment. I can’t find any other reference to a set defined as S is.   Levy goes on to say that every set s(x) has the property of S (which would appear to follow by transitivity).   To me it would appear that even if the ordering is total then it doesn’t necessarily follow that every S has an x where S = s(x): e.g. A is the rationals with normal ordering and S = {rationals that when squared &lt;= 2} .  I chanced on the “initial section” reference reading a proof of transfinite recursion, p.27  of   Can anyone clarify segments and sections, confirm common usage of terminology, and give a hint or reference to the usage of sets like S ?