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

Reposting Question about Schroder-Bernstein

Assume there exists a 1-1 function f:X→Y and another 1-1 function g:Y→X. Follow the steps to show that there exists a 1-1, onto function h:X→Y and hence X∼Y. a) The range of f is defined by ...
0
votes
1answer
9 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 ...
1
vote
1answer
19 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
33 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
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
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
110 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
31 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
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 ...
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 ...
3
votes
3answers
194 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
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
219 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
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?
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
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
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
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
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 ...
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
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$ ...
-1
votes
1answer
37 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
95 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
738 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
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}$. ...
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 ...