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
2answers
27 views

Show that f is surjective

So im having a little trouble proving this. Can anyone help me out? Let $A$, $B \subseteq E$. Moreover, let $$f: \mathscr{P}(E) \to \mathscr{P}(A) \times \mathscr{P}(B)$$ be defined by $$f: X ...
0
votes
2answers
27 views

Linear independent sets

Let $S_1\in\mathbb{R}^{n}$ and $S_2\in\mathbb{R}^{n}$ be two subspaces of $\mathbb{R}^{n}$ Suppose $x_1\in S_1$, $x_1\notin S_1\cap S_2$. $x_2\in S_2$, $x_2\notin S_1\cap S_2$. Show that $x_1$ and ...
0
votes
2answers
38 views

How to express open interval in roster notation?

For example, an open interval such as $(a, b)$ means $a$ and $b$ are not included. If I have $[a, b)$ I know $a$ is included but $b$ is not. I need to express this in roster notation, which is a list ...
0
votes
1answer
32 views

About proof writing in axiomatic set theory

I meet question as following: i) Show that the mappings $f: X \rightarrow Y$ from one given set $X$ into another given set $Y$ themselves form a set $M(X, Y)$. ii) Verify that if $R$ is a set ...
3
votes
3answers
173 views

Is $\aleph_0 = \mathbb{N}$?

Some very wise people here have just told me that $\aleph_0 = \mathbb{N}$, i.e. that the cardinality of the set of natural numbers is just the set of natural numbers itself. Is this now the general ...
0
votes
1answer
20 views

Terminology - “Sample space” vs “sample set”?

Given that a "sample space" is defined as the set of possible outcomes of a given random experiment, is there a fundamental reason to use the term "sample space" instead of "sample set" in probability ...
1
vote
1answer
36 views

proving $|X|<|Y|$, $|Y|<|Z| \Longrightarrow |X|<|Z|$ without CSB

how to prove that if $|X|<|Y|$, $|Y|<|Z|$ then $|X|<|Z|$ without CSB theorem? it is immediate that $|X|\leq |Z|$ so I tried to assume that $|X|=|Z|$ and reach a contradiction but so far I ...
1
vote
1answer
27 views

How do we call a pair of sets $A,B$ such that there is some injection $f: A \to B$?

Let $A,B$ be sets and let $f: A \to B$. If $f$ is a surjection, then we may simply write $f(A) = B$ or say in a more laborious way that $f$ maps $A$ onto $B$, to mean the same thing. However, if $f$ ...
4
votes
2answers
210 views

How do we call a pair of sets between which there is a bijection that need not have additional property?

Let $A,B$ be sets and let $f: A \to B$. Then we say that $A,B$ are isomorphic under $f$ if $f$ is a linear function that maps $A$ onto $B$ in a one-to-one manner; that $A,B$ are homeomorphic under $f$ ...
1
vote
1answer
32 views

If $A = \{x\mid12 < x < 15\}$ and the universal set is the set of positive real numbers less than $15$, what is the complement of $A$?

I have to answer in set builder notation. I put $A^c = \{x\mid 0 \lt x \le 12\}$. I feel that was too easy. Am I missing something?
2
votes
0answers
49 views

What's wrong with this proof of Schröder-Bernstein theorem?

In V. A. Zorich's Mathematical Analysis I there is an exercise to Analyze the following proof of the Schröder-Bernstein theorem: $(\operatorname{card} X \leq \operatorname{card} Y) \land ...
3
votes
2answers
23 views

$X \cap (Y \setminus Z) = (X \cap Y) \setminus (X \cap Z)$

As the title suggests, what is the easiest way to see that$$X \cap (Y \setminus Z) = (X \cap Y) \setminus (X \cap Z)?$$
0
votes
3answers
39 views

$|(a,b)| = |\Bbb R|$ ? Cardinality of any open interval

I want to prove that any open interval $(a,b)$ has the same cardinality of the real numbers: $|(a,b)| = |\Bbb R|$. Do I have to find an function to prove it? Or is there a theorem to prove it ...
0
votes
2answers
45 views

Weird question about natural numbers. Obvious or not?

Given any subset $A,C \subset \Bbb{N}$, there exists a maximal subset $B \subset \Bbb{N}$ such that for all $b \in B, a \in A, \ |b - a| \in C$. For instance $A = \{3,5\}$, $C = \{2,4\}$, then ...
0
votes
3answers
58 views

Showing a function $f$ cannot be surjective

Good day all! So I have a question about the problem: Let $E$ be a set, and $f$ be a mapping from $E$ to $P(E)$. Consider a set $A$ such that $x$ is in $E$ but $x$ in NOT in $f(x)$ Show $f$ ...
0
votes
1answer
29 views

Show a function's inverse is injective iff the function is surjective

Can anyone help me with this question? Let $f:E\to F$. Consider $f^{-1}:\mathcal{P}(F)\to\mathcal{P}(E)$ as a function from $\mathcal{P}(F)$ to $\mathcal{P}(E)$. Show $f^{-1}$ is injective if and ...
3
votes
1answer
16 views

Indicator Function Distributive Property Proof

This is my first post(: I'm trying to understand how to prove the distributive property using the indicator function. I have made the truth tables and understand how this is proved using set ...
2
votes
1answer
269 views

Probability or Set

I'm really good at probability, but this time I seems like I'm not. My friends asked me a very tricky question, and I want to see if there's anyone who can find out the answer. Here's the ...
0
votes
3answers
55 views

Prove a function's injectivity and surjectivity

Good day all! I am new to set theory and I need some help on the question. Can anyone show me how to start this proof? Problem: Let $A$ and $B$ be subsets of a set $E$. Let $f$ be a mapping from ...
0
votes
2answers
13 views

How to determine right set after set complement operation

Let's say that we have an interval $[-5, 5]$. How then will look intervals $[-5, 5]\setminus (-1, 1)$ $[-5, 5]\setminus [-1, 1]$ My answer is that (1) will be $[-5, -1] \cup [1, 5]$ and (2) ...
0
votes
2answers
39 views

Why Should $A = \{x | x^2 = 16\ \mbox{and}\ x+6=6\}$ Be An Empty Set?

We have the following set $$A = \{x | x^2 = 16\ \mbox{and}\ x+6=6\}$$ From $x+6=6$ we know that $x$ is $0$, but the square of $0$ is not $16$ as $x^2 = 16$ says. Similarly, $\pm4+6 \neq 6$. Therefore ...
-1
votes
3answers
49 views

Injective function $g:B \to A$ from a surjective function $f:A \to B$

I wish to prove the existence of an injective function $g:B\to A$ given a surjective function $f:A\to B$. This sounds simple enough, however I'm having trouble writing a formal proof for it. Thanks ...
1
vote
0answers
22 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
50 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
30 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
64 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
78 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
33 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
35 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
20 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
77 views

Does there exist a function $g\in \mathbb{N}^\mathbb{N}$ s.t. $\{f\mid 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
16 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
35 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
51 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
94 views

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

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
57 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
733 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
31 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
35 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
55 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
38 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
143 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
42 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
30 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
63 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
45 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
728 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 ...