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

1
vote
0answers
20 views

non-countable subset of $\mathbb 2^{\mathbb Z}$ with finite pairwise intersection. [duplicate]

Does a non countable subset of the power-set of $\mathbb Z$ exist so that the intersection of any two elements is a finite set? If we ask for the sets to be pairwise disjoint then the answer is a ...
0
votes
4answers
47 views

An example of why $f(f^{-1}(B))\neq B$

Let $f:X\rightarrow Y$ be a function and $B\subseteq Y$ a subset of $Y$. I know (and have proven) that $f(f^{-1}(B))\subseteq B$. I've also found an example where $f(f^{-1}(B))\neq B$ for $B= ...
3
votes
1answer
29 views

How to prove that if $A$ is infinite and $B$ is finite, then $|A\cup B|=|A|$?

I'm studying logic and unfortunately, I'm a newbie at this, so I don't see the stuff everyone sees at the moment. I want to solve following exercise, but get nowhere: Let $A$ be an infinite set ...
1
vote
2answers
32 views

finite vs infinite set function composition

If there is a set $X$ which is finite with $f : X \rightarrow X$ and $g: X \rightarrow X$, then $f \circ g = 1_X$ iff $g \circ f = 1_X$. How is it true for finite sets? I'm not too sure, but the ...
3
votes
4answers
70 views

Proof of $(A\cup B)-(A\cap B)=(A-B)\cup(B-A)$

I was trying to prove $(A\cup B)-(A\cap B)=(A-B)\cup(B-A)$ and came across issues in translating (pertaining to what I did with $\emptyset$) and got through the proof but was doubting its accuracy so ...
0
votes
1answer
30 views

What's wrong with this proof for all subsets A and B of X, $F(A\cap B)=F(A)\cap F(B)$?

Definition: If $F:X \rightarrow Y$ and $A\subseteq X$, then $F(A)=\{y\in Y|y=F(x)\text{ for some x in A}\}$ Proposition For all subsets A and B of X, $F(A\cap B)=F(A) \cap F(B)$ Let $F$ ...
-1
votes
1answer
34 views

Need help on understanding a theorem on subsets

An example in my textbook for Discrete Mathematics states, that, Let A be a set, and B = {A, {A}} Then A is a included in B, and so is {A} also an element of B. (Understood) Also it states, {A} is a ...
2
votes
1answer
18 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^{+}$ ...
11
votes
2answers
67 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
14 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
14 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
31 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
49 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
79 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
53 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 ...
7
votes
3answers
724 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
33 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
52 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
35 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
138 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 ...
3
votes
1answer
62 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
44 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
724 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
47 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 ...
14
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
64 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
45 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
57 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 [closed]

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
40 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
56 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 ...