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

0
votes
2answers
23 views

Basic set theory

Consider these $3$ sets: $X = \{1,2,3\}$ $Y = \{\{1,2,3\}\}$ $Z = \{\{\{1,2,3\}\}\}$ Is it fair to say: $X$ is an element of $Y$ $Y$ is an element of $Z$ $X$ is NOT an element of $Z$?
-1
votes
1answer
18 views

If A is an infinite set, prove that |A| = |A\F| if F is finite

If A is an infinite set, prove that |A| = |A\F| if F is finite. Can I use a theorem? or must find a bijection between A and A\F? also I have to answer: What happen if F is countable? What happens if ...
0
votes
0answers
27 views

Does this set contain these numbers?

How would I go about proving whether or not every number $n=k^8$ is included in the set of all numbers $m=k^4$ ($n$ and $k$ are integers in both cases)?
0
votes
1answer
27 views

Suppose $f\colon X \rightarrow Y$. Prove that if $A \subset B\subset X$, then $f(A)\subset f(B)$.

I would like to verify that this is a correct, clear and concise solution. I am new to set theory. Problem: Suppose $f\colon X \rightarrow Y$. Prove that if $A\subset B\subset X$, then ...
1
vote
4answers
26 views

a problem on the algebra of sets

trying to prove that $A \cup ( A \cap B) = A $ for any set $A,B$. I am trying to use distributive law for sets, but keep coming to the same form. Is there a way to prove this ?
1
vote
2answers
71 views

What's the disjoint union?

I'm self-studying some analysis, and ran into the term 'disjoint union'. I googled it, and it seems that it's just a normal union of any sets, but where we pair each duplicate with an index ...
1
vote
0answers
15 views

Prove that if $|X|=\aleph _0$ then there exist a family of sets, $\mathcal{F}$, of subsets of $X$, s.t $|\mathcal{F}|=\aleph$ [duplicate]

Let $X$ be a set such that $|X|=\aleph _0$. I need to find a family of sets $\mathcal{F}$, of subsets of $X$ such that $|\mathcal{F}|=|\mathbb{R}|$. I saw a couple of examples of Specific X but I ...
6
votes
3answers
46 views

What phenomenon is this? $(2\Bbb{Z} + 1)\cup 3\Bbb{Z} = 2\Bbb{Z} \cup 3\Bbb{Z} + 3$

$(2\Bbb{Z} + 1)\cup 3\Bbb{Z} = 2\Bbb{Z} \cup 3\Bbb{Z} + 3$ Proof: $$ \begin{align*} 2\Bbb{Z} &= \bullet \circ \bullet \circ \bullet \circ \bullet \circ \dots \\ 3\Bbb{Z} &= \bullet \circ ...
-3
votes
1answer
27 views

prove that f is one-to-one if the sign ⊃ in f^(-1)(f(A))⊃A can be replaced by = for all A ⊂ X [on hold]

I have no clue as to how to go about this problem. I have the proof for $$f^{-1}(f(A)) ⊃ A $$ but i don't know where to go from here
1
vote
4answers
30 views

prove that$ A \backslash (B \backslash C) = (A\backslash B) \cup ( A \cap B \cap C)$ [on hold]

I drew the Venn's diagram and could visualize it, but I am having trouble proving it.
2
votes
2answers
26 views

I am issues with proving the following problem: $f^{-1}(f(A)) ⊃ A$ [duplicate]

I am unsure as to where to start with this problem. The way I read it is that $f^{-1}(f(A)) ⊃ A$ means that $A$ is a subset of the preimage of the image of $A$. But I am unsure.
-1
votes
2answers
38 views

Inclusion exclusion principle in set theory

Can some one help me as i am struck in how to prove inclusion exclusion principle in set theory without using Venn diagrams That is we have to prove: $|A \cup B \cup C|=|A|+|B|+|C|+|A \cap B \cap ...
0
votes
0answers
12 views

Explicit Description for an Equivalence Relation

Given a set function $f : X \to X$ let $\sim$ be the equivalence relation $x \sim f(x)$. Contextually, I am working with the coequalizer of $f$ and $1_X$. I want to have as much information about the ...
0
votes
3answers
29 views

“Either A and B is open, then A + B is open” (typo sense-making, Stein Shakarchi Real Analysis)

Please advise about the most reasonable way to read this statement. My interpretations are below. The authors do not define the set operation A + B; I assume A + B = $A \cup B$. Their statement ...
0
votes
2answers
14 views

Prove that the set of all periodic sequences (from some index) of natural numbers is countable

This exercise is from my course textbook and comes with a bunch of other exercises which practice the theorem that countable union of countable sets is countable. So I started by notating for every ...
6
votes
6answers
175 views

How is $\mathbb N$ actually defined?

I know perfectly well the Peano axioms, but if they were sufficient for defining $\mathbb N$, there would be no controversy whether $0$ is a member of $\mathbb N$ or not because $\mathbb N$ is ...
-1
votes
1answer
38 views

Reposting Question about Schroder-Bernstein

Assume there exists a $1$-$1$ function $f:X\to Y$ and another $1$-$1$ function $g:Y\to X$. Follow the steps to show that there exists a $1$-$1$, onto function $h:X\to Y$ and hence $X\sim Y$. a) The ...
0
votes
1answer
13 views

Product of countably many 1-dimensional spaces does not have cardinality $\aleph_0$

From Bergman's "Universal Algebra: Fundamentals and Selected Topics" page 52, constructing a directly indecomposable algebra (one which does not admit a decomposition into directly indecomposable ...
13
votes
5answers
2k views

How is an empty set truly “empty”?

In a related question, an answerer says: an empty bag is a bag with nothing inside it. Makes sense, but I'm reading a textbook right now that says: The empty set has only one subset (namely, ...
1
vote
1answer
24 views

Set theory: Symmetric Difference properties.

I would like to know if my procedure was correct in proving the next property ($\oplus \equiv$ symmetric difference): $$(A_1\cup A_2)\oplus (B_1\cup B_2)\subset (A_1\oplus B_1)\cup (A_2\oplus ...
3
votes
1answer
37 views

How can you prove the equivalance relation for the following model?

Given two Kripke-frames $M=(W,R)$ and $U=(E,S)$ where $W,E$ are 'possible worlds' and $R,S$ are equivalence relations on $W,E$ respectively. we define $M\otimes U = (W',R')$ as follows: $W'=\{\ ...
0
votes
1answer
45 views

Show equivalence using venn diagram, subset argument, membership table

Show that A \ (B ∩ C) = (A \ B) U (A \ C) Using: a) Venn diagram b) Subset argument c) Membership table I can do the venn diagram, you just draw the shapes and show that the end shape for both ...
0
votes
2answers
40 views

Express as a set

Let the universal set $U$ be the set of all people, let $M$ bet the set of all males, let $C$ be the set of all children, let $H$ be the set of all dutch people. Express as sets: a) boys b) girls ...
4
votes
2answers
113 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
33 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
40 views

How to express open interval in roster notation? [on hold]

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
43 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
202 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
21 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
38 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
31 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
221 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
40 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
55 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
26 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
40 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
46 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
60 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
30 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
20 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
270 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
57 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
40 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
50 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
32 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 ...