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
0answers
9 views

Show that every infinite set in N is countable

So, Im learning about countability and I'm having a difficult time understanding how to prove this: A set E is countable if there exists a bijection (I) Show that every infinite set is countable ...
0
votes
3answers
23 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
0answers
4 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
2answers
11 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 ...
5
votes
6answers
121 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 ...
15
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
1answer
42 views

Let $A, B$ and $X$ be sets. Prove that if $A ∪ B ⊆ X$ then $A ⊆ X$.

I have just started learning set theory and I've been trying to learn how to do proofs, however I really can't figure out I've been trying to answer a simple one: Let $A, B$ and $X$ be sets. Prove ...
-1
votes
1answer
26 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
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
1answer
11 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 ...
3
votes
1answer
36 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'=\{\ ...
1
vote
1answer
21 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
61 views

Existence of a map $\phi \colon \mathbb N\cup \{0\} \rightarrow \mathbb N\cup \{0\}$ that holds the property $\phi (ab) = \phi(a)+ \phi(b)$

Does there exist a map $\phi \colon \mathbb N\cup \{0\} \rightarrow \mathbb N\cup \{0\}$ that holds the following property? $$\phi (ab) = \phi(a)+ \phi(b)$$ If they do what do they ...
3
votes
3answers
67 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}$. ...
0
votes
1answer
44 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
1answer
42 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 ...
0
votes
2answers
38 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
111 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
3answers
59 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
2answers
39 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 ...
3
votes
3answers
197 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 ...
4
votes
1answer
109 views

Interpretation of a tail event

I am currently reading about tail events wikipedia. And I was wondering: Where does the interpretation come from that events in this sigma algebra are independent from the behaviour of any finite set ...
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$ ...
1
vote
1answer
35 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?
4
votes
2answers
220 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$ ...
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
24 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 ...
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
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 ...
3
votes
1answer
19 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 ...
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 ...
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 ...
3
votes
1answer
158 views

Similarity of Infinite Direct Sums Vs. Infinite Direct Products Accross Categories

Let $|R|=|S|=\infty$. In many concrete categories, I know $R^S$ can be identified as the set of all functions from S to R, and the much "smaller" $R^{\oplus S}$ can be identified as the subset of ...
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 ...
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) ...
-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 ...
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 ...
3
votes
0answers
61 views

How can functions be written as ordered triples?

In a function $ \langle f,A,B \rangle $, I know that the domain $ A $ and the co-domain $ B $ are not restricted to being sets. They can be proper classes. In that case, how can we write functions as ...
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 ...
7
votes
3answers
740 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 ...
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
64 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 ...
3
votes
1answer
31 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
79 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$ ...