This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

1
vote
2answers
43 views

Axiom of choice variants [duplicate]

Is there any good book where the equivalence of AC to the statement "Any surjection has a right inverse" is proved (and maybe other equivalences)? I could do $AC \Rightarrow$ "Any surjection has a ...
0
votes
1answer
28 views

Least upper bound property question

Suppose $E \subset S$ and $S$ does not have the least-upper-bound property. Suppose also that $E$ is bounded above and non-empty. Then we cannot say that $E$ does not have a least-upper bound right? ...
-2
votes
0answers
63 views

Use the Cantor-Schroder-Bernstein Theorem to prove that |Q-{q}|=$\aleph_0$, for every rational number q.

Q-{q} $⊆$ Q: This is my attempt at the proof: First, it is obvious that $N $≤$ (Q-{q})$ since $N $⊆$ Q$. Consider the map $f:N→Q-{q}$ defined by $f(x)=x$ if $x\neq$q and $f(q)=22/7$, then $f$ ...
1
vote
2answers
97 views

Use the Schroder-Bernstein Theorem to prove that |(0,1)|=|[0,1]|.

We know that the Schroder-Bernstein Theorem is useful to show two sets are the same size. Assume $f: A \rightarrow B$ is one-to-one & $g: B \rightarrow A$ is also one-to-one. Then $A$ and $B$ ...
0
votes
3answers
33 views

How many algebras of subsets of $X$ contain exactly four elements?

Let X be a set with five elements. How many algebras of subsets of X contain exactly four subsets? Well $\emptyset, X$ must be in any algebra of subsets of $X$ so that means we have to find two more ...
-1
votes
3answers
113 views

If $A\Delta B=C\Delta D$, must $A\Delta C=B\Delta D$? [closed]

If $A$, $B$, $C$, $D$ are sets and $A\Delta B=C\Delta D$, prove that then it is also $A\Delta C=B\Delta D$
0
votes
1answer
21 views

Collection of all inductive Sets

Is collections of all inductive sets is a set or proper class? And how to prove this? where inductive set is a set given from axiom of infinity
1
vote
3answers
58 views

prove that set of reals numbers and complex numbers are equipotent.

I have to prove that set of reals R and set of complex C are equipotent. " i know that set A and B are equipotent iff there is one to one mapping of A onto B. " please anyone give me answer of ...
0
votes
3answers
49 views

Closure of a subset of a metric space is closed

From definition, if $X$ is a metric space, if $E \subset X$, and if $E'$ denotes the set of all limit points of $E$ in $X$, then the closure of $E$ is the set $\overline{E}=E \cup E'$. I need to ...
0
votes
0answers
15 views

the mean number of fixed points of a finite endomorphism

for some reason i found myself wondering what is the average number of fixed points of an endomorphism of a finite set. after floundering around for a while i obtained a result that surprised me. ...
1
vote
2answers
15 views

Mutually disjoint implying complements in set theory

No homework tag because it is just practice for a final, not for marks: $\text{Let $S, T \subseteq U$. If $S \bigcap T= \emptyset$, then $S$ and $T$ :}$ A) are always complements of each other in ...
1
vote
0answers
24 views

Taking multisets as fundamental

I have heard that it is possible to axiomatize the concept of multisets as a primitive idea. Is there some text where this is actually done?
5
votes
4answers
299 views

Can functions be defined by relations?

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?
2
votes
4answers
149 views

Countably infinite union

Is it the case that $(a,b) \subseteq\bigcup_{n\in \mathbb{N}} (a+\frac{1}{n}, b-\frac{1}{n})$? Seeing as we are only indexing by positive integers? i.e we never reach $\infty$
0
votes
1answer
32 views

Finding the “canonical decomposition” of a function — I don't know if I'm doing it right

I've been told to identify the terms in the canonical decomposition of the function r |-> exp(2*pi*i*r) from R -> C. I've been able to give an answer, but I think i might have misinterpreted the ...
4
votes
1answer
34 views

Using expressions like $ \langle x,y \rangle$ in predicate logic formulas

I don't like how books on set theory write logic formulas when describing complex sets. For example that is how a regular book can show that some set $s$ is not a pair: $$\forall x \forall y (\langle ...
2
votes
1answer
20 views

Existence of families of sets whose elements are incomparable in terms of $\in$

There exist families of sets whose elements are comparable in terms of $\in$, like for example the set of finite von Neumann ordinals, there exist such that their elements are incomparable in terms of ...
0
votes
1answer
64 views

Countability of Sets

I understand that a set A is at most countable if A is finite or countable. I also understand that A is finite if A is equivalent to J(n) for some positive integer n and A is countable if A is ...
2
votes
1answer
74 views

Is there a mathematical concept of fractions using transfinite numbers as numerators and denominators?

http://de.wikipedia.org/wiki/Cantors_erstes_Diagonalargument (German) http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument (English) While looking at Cantors method of proof, which he used to ...
0
votes
1answer
15 views

Set theory - set inclusions and symmetric differences

Let $E,F,E_k,F_k$ be arbitrary sets. I am trying to show the following relations: $$(i) \space (E_k-F_k) \Delta (E-F) \subset (E_K \Delta E) \cup (F_k \Delta F),$$ $$(ii) \space (E_k \cup F_k) \Delta ...
0
votes
1answer
47 views

Proper Set Theory Transformation

I was wondering if i am using the Inverse Laws Correctly in this transformation: 1. $\mathrm{A}\cup(\mathrm{B}\cap(\mathrm{A}\cup\mathrm{C})\cap(\mathrm{A}\cup\neg\mathrm{C}))$ 2. ...
1
vote
1answer
65 views

Set Theory Laws

I have been working on the Inclusion Exclusion Principal and came across a problem where I am having difficulty identifying the transformation. Given Information: $\mid\mathrm{U}\mid = \mathrm{50}$ ...
0
votes
2answers
43 views

Combinaision of two functions

Let us denote $X_0 = \{x, y\}$ and $X_1 = \{a, b\}$ two disjoint sets of variables; let us denote $V$ a set of values. I have two functions $f_0 : X_0 \rightarrow V$ and $f_1 : X_1 \rightarrow V$, ...
1
vote
1answer
63 views

set theory, Incompleteness and axiomatic systems

Is the number of theorems that can be proved (decidable) within a certain set of axioms (for instance ZFC) is finite or infinite ? in other words, are we going to fully exhaust that set of axioms ...
2
votes
1answer
32 views

Proving that this relation is transitive

I have seen this question on a book I am reading and could not figure it out fully. The question is as follows: "Suppose A is a set, and $F\subseteq P(A)$. Let $$R_F=\{ (a,b)\in AxA|\text{ for every ...
19
votes
5answers
3k views

What's wrong with this proof of the infinity of primes?

While reviewing an online textbook in abstract algebra for my website—which I'm hoping will go live by the end of the month—one of the exercises in the book inspired me to produce a simple, set ...
0
votes
0answers
33 views

What does “single set” mean in this context?

I encountered this problem in Munkres topology. Let $X_1 , X_2$ denote a single set in topologies $\tau_1$ and $\tau_2$, respectively; let $Y_1 , Y_2$ denote a single set in the topologies $U_1, ...
1
vote
0answers
22 views

problem with my construction of sequence of sets

This is an exercise from a real analysis book. It has many parts. Assume a) and b) are true: a) Suppose $F$ is closed and $O$ is open subset of $\mathcal{R}$ and $F \subset O$, then there is a ...
0
votes
0answers
22 views

Is there accepted notation and/or terminology for the smallest cover of $S$ with cells from $P$?

Let $X$ denote a set. Then for $S \subseteq X$ and $P$ a partitioning of $X$, define $P \diamond S$ as the smallest cover of $S$ with cells from $P$. Explicitly: $$P \diamond S = \bigcup\{Q \in P ...
2
votes
1answer
30 views

what does the the “set-forming operator” $\{ \cdots \}$ actually do?

the statement $$ S = \{1,3,4\} $$ looks a little like a function. informally the arguments are the three numerals, the function is represented by the brackets $\{$ and $\}$ and the image is the ...
0
votes
0answers
23 views

Product of tuples vs cartesian product of set

If $\left ( X_{i} \right )_{1\leq i\leq n}$ is an ordered n-tuple of sets their Cartesian product is defined as: $$\prod_{i=1}^{n}X_{i}:=\left \{ (x_{i})_{1\leq i\leq n} :x_{i}\in (X_{i}) \; \text{ ...
0
votes
1answer
37 views

Axiom of Unions and its use of the existential quantifier

I'm reading Halmos's Naive Set Theory, and right now I'm on the section about the axiom of unions. As stated in the book, the axiom reads: For every collection of sets there exists a set that ...
1
vote
1answer
49 views

Count of matched items in multiple sets

I do apologize if this is a duplication. I did find a question that appears close to describing something of what I'm looking for, but I'm just not "seeing" the complete picture (maybe): Counting ...
0
votes
0answers
61 views

set theory without venn diagram

Can set theory based questions be solved without venn Diagram? I have shared a link below which shows that some set theory questions can be solved by using lines instead of circles(as in Venn ...
1
vote
1answer
58 views

show that there are $1\leq j_1< j_2< j_3\leq 13$ such that $\left | A_{j1}\cap A_{j2}\cap A_{j3} \right |\geq 3$.

Given $A_i,A_2,...,A_{13}$ $\subset [10]$ when $\left | A_i \right |=5$ for all $i$. Need to show that there are $1\leq j_1< j_2< j_3\leq 13$ such that $\left | A_{j_1}\cap A_{j_2}\cap A_{j_3} ...
1
vote
0answers
41 views

Size of Hom-Sets in A Functor Category

I am trying to prove the following presumably easy fact: if $B$ is a category with small hom-sets and $C$ is a small category, then $B^{C}$ has small hom-sets. I am assuming the standard Z-F axioms ...
2
votes
1answer
55 views

Count amount of pairs $(a,b)$ from two sets $A$ and $B$ such that $a\neq b$

I have two sets $A=\{1,2,3\}$ and $B=\{2,3,4\}$ How do I count the amount of pairs $(a,b)$ where $a\in A$ and $b\in B$, such that $a\ne b$ This problem can easily be done on paper, but how can I ...
2
votes
2answers
78 views

Number of ways to select numbers, each 1 from different lists without repetition

I want the numbers of ways to select numbers each 1 from different lists without allowing repetition. Eg- List 1 : 5, 100, 1 List 2 : 2 List 3 : 5, 100 List 4 : 2, 5, 100 I want to select 1 ...
0
votes
1answer
56 views

let $a,b,x,y$ be cardinal numbers such that $a \le b$ and $x \le y$, prove that $a^x \le b^y$.

let $a,b,x,y$ be cardinal numbers such that $a \le b$ and $x \le y$, prove that $a^x \le b^y$. let $\operatorname{card} A=a$, $\operatorname{card}B=b$, and so on. From the given conditions I know ...
0
votes
1answer
51 views

Cartesian product of sets

Let $a$ be a $2\times 1$ vector where each $i$th element $a_i$ taking value $1$ or $0$. Let $\mathcal{A}$ be the set of all possible values of $a$, i.e. $\mathcal{A}:=\{(0,0), (1,1), (1,0), (0,1)\}$. ...
1
vote
1answer
29 views

Proving $(A \cup B) -C = (A-C) \cup (B-C)$

Proving $(A \cup B) -C = (A-C) \cup (B-C)$ I did it as follows, but I'm not sure about the method. Let me know if there is a fault. Let $x \in (A \cup B) -C $ $$ x \in (A \cup B) \land x \notin C \\ ...
3
votes
1answer
62 views

Proof:"Infinite subset of $\mathbb N$ is countable [duplicate]

I've read a proof of the statement:"An infinite subset of $\mathbb N$ is countable; that is, if $A \subset \mathbb N$ and if $A$ is infinite, then $A$ is equivalent to $\mathbb N$." in Carothers' ...
1
vote
3answers
37 views

Notation: the set of two-element subsets of $\Bbb N$

Let $\{a,b\}\subseteq \Bbb N$. Is there a special name or notation for sets of this type, for example $\Bbb N^{2\ge}$? Any subset size may be used, but the specific size and denoting that order does ...
2
votes
2answers
52 views

Surjectivity of a piecewise function $f:(-1,1)\to \mathbb R$

Function $f$ is defined as $f: (-1, 1) \to \mathbb{R}$. $$ f(x) = \begin{cases} -x/(x-1),&x\geq 0 \\ x/(x+1),&x \leq 0 \end{cases} $$ Let $y \in \mathbb{R}$. How would I prove that there ...
0
votes
0answers
23 views

Infinite sets and natural numbers [duplicate]

Must for every infinite set $S$ there exist an injection $f: \mathbb{N}\rightarrow S$? Thanks!
1
vote
2answers
45 views

Cardinality of the set of multiples of “n”

I've yet another question about the cardinality of sets. Apologies, but I just can't seem to fully grasp it. For what it's worth, I have tried searching the site for a solution to this problem. Let ...
1
vote
3answers
37 views

Help with proof of contrapositive of well-ordering principle

Prove by induction on $n$ that if $A$ is a set of positive integers without a least element, then $\mathbb{N}_n \subseteq \mathbb{Z}^+ - A$ for every $n$ so that $A$ is the empty set. I don't ...
2
votes
1answer
46 views

If $A$ is a set, explain why $A^0 = \{\emptyset\}$

I think I may have this but I think it's best I check as I don't have the solution. Let $A$ be a set. $A^0 = \dfrac{A^1}{A^1}$ $A$ / $B$ is everything in $A$ that isn't in $B$ Therefore $A$ / $A$ ...
1
vote
2answers
72 views

Term for a general subset that does not include infinity

I tried to find the answer to my questions for a while but did not succeed, and I hope that was not only because of deficits in my search terms. My question is as follows: Let $\mathcal{A}$ be a set ...
1
vote
0answers
38 views

How to describe any partition a set

For ignore of a better word, I will use word "partition" try to describe what I mean. How to describe partition(where over lapping subsets are allowed) of a set mathematically? In another word, ...