This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

2
votes
1answer
11 views

For a finite character set $\Sigma$, what would be a formal proof that $\Sigma^{+} = \Sigma^{*}\Sigma$?

Let there be a finite character set $\Sigma$, as in computer science convention. $\Sigma^{*}$ is defined as in Kleene star notation (https://en.wikipedia.org/wiki/Kleene_star) with $\Sigma^{+}$ ...
10
votes
2answers
55 views

Does there exist a function $g\in \mathbb{N}^\mathbb{N}$ s.t. $\{f\circ f=g\}$ is not empty and finite?

I'm struggling with this question and can't figure it out. The question was too long for the title so I will write it once more: Does there exist a function $g : \mathbb{N} \longrightarrow ...
-1
votes
0answers
11 views

Is total substring well-ordering of a set containing $\omega_0$-length string possible? [duplicate]

I originally asked the quesiton here: http://math.stackexchange.com/questions/1411731/can-a-set-containing-a-string-of-infinite-length-be-well-ordered-by-substring-to and Can a set containing a ...
0
votes
1answer
11 views

Equivalence of definitions of the axiom of induction.

Definition 1: $(0\in S, n\in S \implies n+1\in S) \implies n\in S \forall n≥0$. Definition 2: $(P(0), P(n)\implies P(n+1)) \implies P(n) \forall n≥0$. To prove the equivalence of these ...
0
votes
1answer
24 views

Can a set containing a string of length $\omega_0$ be well-ordered by substring total order?

I originally asked the quesiton here: http://math.stackexchange.com/questions/1411731/can-a-set-containing-a-string-of-infinite-length-be-well-ordered-by-substring-to But right after posting the ...
1
vote
0answers
42 views

Problem requiring Zorn's lemma

Let $R$ be a relation from $A$ to $B$ and let the domain of $R$ be $A$. Use Zorn’s Lemma to show that there is a subset $f$ of $R$ such that $f$ is a function from $A$ into $B$. I am having ...
0
votes
2answers
55 views

Which axioms of ZFC are required to prove the existence of $\aleph _ 0$?

At Wiki, we have: The cardinality of the natural numbers is $\aleph_0$. Also from Wiki, we have: In mathematics, cardinal numbers, or cardinals for short, are a generalization of the ...
1
vote
5answers
50 views

Countable/Uncountable collections

I'm asked to produce an example of a countable collection of disjoint open intervals. At first I had trouble seeing how this is possible since open intervals are not countable. My idea is to have ...
4
votes
3answers
421 views

Proof for the theorem that the empty set is a subset of every set

I'm new in here. Considering my person: I am physics student (BSc.) who has finished 2 semesters by now. Within the first two semesters, I discovered that mathematics is beautiful and that I want to ...
3
votes
2answers
30 views

Proving a function $F$ is surjective if and only if $f$ is injective

Problem: Let $X$ and $Y$ be non-empty sets and let $f: X \rightarrow Y$ be a function. Then we can define $F: P(Y) \rightarrow P(X)$ by \begin{align*} F(B) = f^{-1}(B) \qquad \text{for all} \ B \in ...
0
votes
3answers
30 views

Clarification regarding function

I have been reading Velleman's How to prove book and this is one of the paragraphs written in the Functions chapter: For every $a \in A$ and $b \in B$, $b = ...
3
votes
3answers
51 views

If a set is countable and infinite, there is a bijection between the set and $\mathbb{N}$

I'm trying to show that if a set $S$ is infinite and countable then there is a bijection $\varphi : S\to \mathbb{N}$. Since $S$ is countable, we know that there is an injection $f: S\to \mathbb{N}$. ...
2
votes
1answer
34 views

Cantor's diagonal argument modified version

I have the following doubt regarding Cantor's diagonal argument. First of all, the "usual case" is quite clear for me. If $X$ is some set, then we can show there is no surjection from $X$ onto the set ...
0
votes
1answer
9 views

Proving $F . G$ is the greatest lower bound

This is one of the problem I have been solving from Velleman's How to Prove book: Suppose $A$ is a set. If $F$ and $G$ are partitions of $A$, then we'll say ...
4
votes
4answers
132 views

Is it true that $A \in A$?

I defined the set $A$ as follow: \begin{align} A_0 & =\varnothing \\ A_1 & =\{A_0\}=\{\varnothing\} \\ A_2 & =\{A_1\}=\{\{\varnothing\}\} \\ A_3 & =\{A_2\}=\{\{\{\varnothing\}\}\} \\ ...
1
vote
2answers
40 views

Prove that no set can contain everything (or every other set)

Prove that there cannot exist a set that contains everything. Ill put my proof in the answer so please check it there. Also if there is a more creative way to do this(using the basic axioms) if it's ...
0
votes
1answer
28 views

Couple of questions on the Axiom of Extensionality

I understand that the axiom of Extensionality says that two sets are equal iff they have the same elements. Which is clear enough. But take a look the definition for this axiom given by ...
2
votes
0answers
55 views

Chance of Drawing All of a Subset

I have a simple question but I can't seem to find the answer anywhere. Say that I have a set $\mathbb Z$ and a subset of that $\mathbb X$. I want to draw elements from $\mathbb Z$ until there is at ...
-1
votes
2answers
43 views

$A \subseteq B$ if and only if $B^c \subseteq A^c$ [on hold]

How to prove without using Venn diagram that $A \subseteq B$ if and only if $B^c \subseteq A^c$?
7
votes
4answers
718 views

As of August 2015, is the “set” of all gold medalists in the 2016 Olympics a set?

As of August 2015, is the "set" of all gold medalists in the 2016 Olympics a set? I think it is since the defining property is very clear. However, given any $x$, we do not know if $x$ is in this ...
1
vote
1answer
22 views

Prove that $R$ is anti-symmetric

This is one of the problem I have been solving from Velleman's How to Prove book: Suppose $A$ is a set. If $F$ and $G$ are partitions of $A$, then we'll say ...
0
votes
1answer
44 views

Proving well-ordering property of natural numbers without induction principle?

In Munkres, Topology, he has this way of proving the well ordering property for the natural numbers: He assumes he can work with the real numbers from the for the real numbers Then he defines an ...
13
votes
1answer
1k views

True or false: {{∅}} ⊂ {∅,{∅}}

Note: Actually there's no error in the book and the manual. I actually misread it. The answer is of a different question : True or False: {0} ⊂ {0} This question is from Discrete Math Book by Rosen. ...
0
votes
0answers
25 views

Mathematical notation for first and second maximum

I have a vector $f_x = f_{x_1}, f_{x_2},\cdots, f_{x_n} $ having the frequencies for bin $x = x_1,x_2,\cdots,x_n$. Now I want to address two bins having highest frequencies. I address the highest ...
1
vote
1answer
62 views

Example to show that $f(A-B)$ is not necessarily a subset of $f(A) - f(B)$

Suppose f : X→Y is a function and A,B ⊆ X. I am trying to come up with counterexample to show $f(A-B)$ is not always a subset of $f(A) - f(B)$ and this is what I have so far: $A = \{1,2,3\}$ $B = ...
1
vote
0answers
32 views

Basic Set-Theoretic Properties from Halmos

I've been backtracking lately to make sure that I have a solid set-theoretic background before taking measure theory this fall. Here's a few facts I've come across today, and my attempted proofs. Let ...
2
votes
3answers
154 views

Average of points on an xy plane

I was at a family reunion yesterday which required a bit of travel. Most of that part of the family lives near one another, so I am the outlier. I can't reasonably expect them to have the next reunion ...
1
vote
2answers
42 views

Can I do instantiation like this?

Suppose, if I have been given this: $\forall x \in A(P(x))$ and $\exists y \in A(Q(y))$. Now from $\forall x \in A(P(x))$ using universal instantiation, I get $P(c)$ where $c$ is an arbitrary element ...
1
vote
2answers
56 views

Why is it called a “multiset”?

According to Wolfram MathWorld, "A set is a finite or infinite collection of objects in which order has no significance, and multiplicity is generally also ignored ..." and A multiset is "A ...
0
votes
1answer
23 views

To prove $(A-B) \cup (B-C) \cup (C-A) = A \cup B \cup C - A \cap B \cap C$.

To prove $(A-B) \cup (B-C) \cup (C-A) = A \cup B \cup C - A \cap B \cap C$ It can be done by set operation method. But the process is very lengthy. So I am trying it by showing that each is a subset ...
-3
votes
2answers
40 views

Assume A is a set, prove that {a} ⊆ A if and only if a ∈ A [on hold]

Unsure about proving "if and only if" questions!
1
vote
2answers
36 views

Showing $\bigcup_{k}\{(a_{1},…,a_{k}):a_{j}\in [0,1]\cap \mathbb{Q} ,\sum^{k} a_{j}=1\}$ is countable

Showing $M=\bigcup_{k}\{(a_{1},...,a_{k}):a_{j}\in [0,1]\cap \mathbb{Q} ,\sum^{k} a_{j}=1\}$ is countable. I find this hard to believe because say for fixed k and any $b,c\in [0,1]\cap ...
1
vote
1answer
39 views

The cardinality of the set all symmetric relations on the set of natural numbers is $\mathfrak{c} = | \mathbb{R} | = 2^{\aleph_0}$

Prove that a set of all symmetric relations on the set of natural numbers has cardinality $\mathfrak{c} = | \mathbb{R} | = 2^{\aleph_0}$. Here I think that the $(a,b)b$ - will be every number ...
0
votes
0answers
19 views

What is the best way to map pairs in cartasian product? [closed]

Is there a method for making sure you have all the pair combinations when mapping out pairs in cartasian product, similare to when finding subsets in powersets using binary counting (000, 001 ...) ...
-1
votes
1answer
46 views

Is |AxBxC| = |Ax(BxC)|?

Is the cardinality of AxBxC different to that of Ax(BxC), since AxBxC gives a 3 tuple, but Ax(BxC) gives a two tuple? but in such case, what would be the formula for calculating the cardinality of ...
2
votes
1answer
30 views

Finding a unique relation $T$

This is one question I have been solving from Velleman's How to prove book: Suppose $R$ and $S$ are relations on a set $A$, and $S$ is an equivalence relation. We will say that $R$ is compatible ...
1
vote
1answer
39 views

How to calculate the cardinality of the complement of two countable sets of reals?

Let $A,B\subseteq\Bbb R$ be countable sets. Denote by $A'$ and $B'$ the complements (in $\Bbb R$) of $A$ and $B$ respectively. What is the cardinality of $C=A'\cap B'$? I cant figure this ...
3
votes
1answer
55 views

Anatomy of $\mathcal P(\mathbb{N})$

How many proper subsets of $\mathcal P(\mathbb{N})$ there is that have cardinality of $2^{|\mathbb{N}|}$ ?
1
vote
2answers
38 views

An injection between finite sets of equal size must be a bijection

To me, it seems logical that if I have two finite sets of equal size, and there is an injection between them, then that injection must be a bijection. However, of course, we cannot just claim these ...
1
vote
1answer
53 views

A Proof in Elementary Set Theory

I apologize in advance for any lack of clarity in my mathematical symbols; I'm beginning to learn how to use this site. I'm working through "Introduction to Analysis" by Rosenlicht and he presents an ...
1
vote
1answer
32 views

Has anyone ever suggested a name or notation for this operation on multisets?

A basic multiset identity says: $$A+B = (A \cap B) + (A \cup B)$$ Allowing ourselves to use negative multiplicities and rearranging: $$A-(A \cap B) = (A \cup B)-B$$ But since $A \supseteq (A \cap ...
0
votes
1answer
26 views

Cardinality of a Quotient Set

Let $X = \{1, 2, 3, 4, 5, 6, 7, 8, 9,10\}$ and $P=\{2,3,5,7\}$. In $P(X)$ define the equivalence $A\mathcal{R}B$ if $A\setminus P = B \setminus P$ . Then what is the cardinal of the quotient set? I ...
1
vote
2answers
21 views

Equality of 2 Sets

I'm reading a book that states "If $X$ and $Y$ are sets, then $X=Y$ if and only if, for all $x, x\in X$ if and only if $x\in Y$." Perhaps it's because I learned the equality of two sets being defined ...
11
votes
4answers
722 views

When do two functions become equal?

When do two functions become equal? I have stumbled over this definition of equality of functions in elementary real analysis. Let $X$ and $Y$ be two sets. Let $f:X\rightarrow Y$ and ...
0
votes
1answer
11 views

intersection closure of comparison relations

I am given a set of $n$ integers $X$ and a set of operations $L=\{\geq,\leq,\neq\}$ over $X$. Consider all binary relations $\bf{R}\ $ resulted from any combination of $L$. For example ...
2
votes
3answers
78 views

One-one and onto map from $\mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N} $.

Can you tell any one-one & onto map from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$? I can prove that these have same cardinality but am unable to think of a mapping.
0
votes
0answers
18 views

union of a class of sets which is empty [duplicate]

i came across a concept on set theory in a book on topology and i can't seem to understand it. if $U$ is the underlying universal set and if $\left\{A_{i}\right\}$ is a class of subsets of $U$ for an ...
-1
votes
1answer
27 views

$B$ is a subset of some $s(n)$

Assume that $s$ is a function with domain $\omega$ such that $s(n) \subseteq s(n^+)$ for each $n \in \omega$. Assume that $B \subseteq \bigcup_{n\in\omega}s(n)$ such that for every infinite subset ...
2
votes
2answers
61 views

Questions about definability of truth

Suppose i work in ZFC. Using the recursion theorem, i can define the the truth value of formuals in the language $\mathcal{L}$ of set theory (one predicate symbol $\in$), $Val_\mathcal{M}(\varphi)$, ...
1
vote
2answers
37 views

Question about definition by induction.

I am reading some notes about naive set theory. I know the "definition by induction", but I can't apply it to the following cases directly. Suppose $A$ is a set, let $A^+$ be the set $A\cup \{A\}$. ...