Math-Wiki - תרומות המשתמש [he]

Postdocs

2019-12-30T21:41:43Z

Ari: /* Your second week in the department */ adding access to electronic databases

<div dir="ltr" class="mw-content-ltr">

Information for Postdocs at the Math department of Bar-Ilan University. See [[Visitors|similar page]] for all academic visitors.

==Obtaining a student Visa==

# Make sure that your passport expiration date is far away.
# Complete and sign the [https://www.gov.il/BlobFolder/service/student_visa_application_type/he/MatanAshratKnisa_4.pdf application form]. Note that you will need an address in Israel; if you will stay at the university dormitories, you can put that on the form.
# Prepare a physical and electronic copy of the following documents before contacting the [https://www.science.co.il/Embassy.php closest embassy of Israel]:
## Two passport pictures.
## Invitation letter with your full name (as it appears on the passport), passport number, and start+end dates of your postdoctoral studies.
## Proof of the financial support/scholarship for the postdoctoral period.
## A travel document that is valid for at least one year, from the start date of the postdoctoral studies, electronic copy of the page with your personal details, and previous entry visas to Israel if you have any.
# Contact the [https://www.embassypages.com/israel closest embassy of Israel], ask for an appointment for [https://www.gov.il/en/service/student_visa_application_type A2 Visa] and ask whether additional documents are needed. The embassy may indeed require for additional documents. e.g. residence permit (in case you are not living in your home country), hotel reservation (contract with the university dormitories, in case you will stay there), flight tickets, Ph.D. diploma, work reference letter, etc'.
# Pay the fee and attend the appointment. They will provide you with the information for the payment, the date and time of the appointment, and the list of documents that you must send in advance via e-mail (scanned). You will be asked to show the originals during the appointment.

Note: the visa is for one year starting the date of the appointment. It is therefore advised to make the appointment as close as possible to your arrival to Israel.

==Extending your student Visa==
Prepare the following documents in advance:

* Certificate of studies of the running academic year

* Print and fill the form "Aplication for extension of permit of residence/change of visa category" [https://biuinternational.com/wp-content/uploads/2018/07/visa-application-form-2018.pdf here].

Bring the documents with your passport, a recent picture and 175 NIS (350 NIS for multiple entrance visa) to the Ministry of Interior in Bialik St 2 in Ramat Gan.

The queuing numbers for visa extension are assigned between 8:00 am and 8:20 am at the entrance, be sure to be there before 8:00 am.

The visa can be extended for at most one year. If paying by cash, be sure to bring the exact amount.

==Your first day in the department==

# Get yourself a local SIM card (you will need it for all the later steps). Here are a couple of options:
## There is a store at the center across the street, called [https://www.d.co.il/80125739/18740/ Blue Phone]; they sell prepaid SIM cards by [https://019mobile.co.il/ 019 mobile]. The SIM card costs 40NIS (one time), and a standard plan (including unlimited calls + 20GB data/month) costs 49NIS/month. The phone number at the store is 03-5259192.
## There is another option with [https://www.golantelecom.co.il/web/ Golan Telecom]. This is more suitable for those who plan to stay at least one year as it involves signing a contract for a year. The plan they offer changes from time to time. At the time of writing they offer 100 GB/month with unlimited calls and SMS at 29 NIS/month. There are one-time connection fee at 30 NIS and one-time SIM fee at 19 NIS. It is highly recommended to check their current offers before deciding. There are many stores, for example there is one on Yigal Alon St 98, Tel Aviv-Yafo (it is inside the building and you need to ask the guard). Bring your passport, the invitation letter and your credit card with you.
## It is possible to order a sim card [https://biuinternational.com/students/sim-card-information/ online] before coming to Israel, and then pick it up at the airport upon your arrival.
# Get yourself a bank account and a debit card. Inside campus, you'll find a branch of [https://www.mizrahi-tefahot.co.il/en Mizrahi Tefahot] ([https://www.boi.org.il/en/bankingsupervision/banksandbranchlocations/pages/israelibanks.aspx bank code # is 20], and the [https://www.mizrahi-tefahot.co.il/en/Bank/Pages/Branch-Locator.aspx#BranchNumber=414 branch code # is 414]). Make sure to bring in your postdoc invitation letter, your passport, an id card from a country where you are a citizen and the number of your local phone. They will need the tax identification number or equivalent from the country where you pay your tax. They may later ask you to e-mail them a copy of the postdoc invitation letter. As soon as you the student status in the system, print the certificate of studies of the running academic year and bring it to the bank to get the student discount on the fees. Note: your very first paycheck is expected to take place around one month after your arrival.
# Fill the four forms:
## [http://www.assafrinot.com/wiki/application260617.PDF Postdoctoral fellowship application form].
## [http://www.assafrinot.com/wiki/registration260617.pdf Registration form for postdocs].
## [http://www.assafrinot.com/wiki/contact.docx Emergency contacts for foreign students] ([http://www.assafrinot.com/wiki/contact.pdf PDF]).
## Policy for postdoctoral fellows: [http://www.assafrinot.com/wiki/policy140817.PDF English], [http://www.assafrinot.com/wiki/נוהל-להשתלמות-בתר-דוקטור.16.3.2017.pdf Hebrew].
Submit them (along with your passport-sized photo, a photocopy of your passport, and a photocopy of the approval of your Ph.D. degree) to [https://math.biu.ac.il/en/node/1196 Rivka Wolberger].
# Get yourself an health insurance. One option is [https://biuinternational.com/students/health-insurance/ Harel Yedidim].
## The daily premium insurance costs around 1.9 USD per day.
## Assuming you have an Israeli bank account, you can pay for the insurance via a bank transfer. For this, you have to submit the filled form and ask for the amount to pay. The payment has to be done to the account IBAN: IL060311260000000185272, Beneficiary: HAREL INSURANCE CO.LTD. After making the transfer, send the confirmation from the bank to the e-mail y_health@yedidim.co.il.
## It is also possible to pay through an international transaction, but you have to pay the commission of the banks.
## Another payment option is to pay for the whole period using any credit card (not necessarily an Israeli one), or ask them to charge you on a monthly basis (in which case, the payment takes place every 9--11 of the month).
## When filling the insurance application form, make sure to set the cover dates to start on the day of signing the form (and not earlier).
# Ask your postdoc advisor to:
## Assign you a room at the department;
## Assign you a P.O. box of the department;
## Show you the [http://sifria2018.lnx.biu.ac.il/F/?func=find-b-0&con_lng=eng library];
## Fill and submit the [http://www.assafrinot.com/wiki/טופס-אשור-מלגות.docx scholarship payment form];
## Provide you the acknowledgement-for-funding string to be included in your research papers.

==Your second week in the department==

# Go to the bank to pick up your debit card.
# Go to [https://math.biu.ac.il/en/node/1196 Rivka Wolberger] to pick up your student card, to create an [https://inbar.biu.ac.il/Live/Login.aspx Inbar] account, and to provide there your bank details, so that you can receive your monthly scholarship.
# Contact [https://math.biu.ac.il/node/582 Doron Kurzberg] to receive username+password for your unix account.
# You can also [http://oren.biu.ac.il/connect-to-bar-ilan-computer-from-home/ connect to Bar-Ilan computer from home]
# [https://math.biu.ac.il/node/460 Access to electronic databases via the BIU Library subscription using the OpenAthens network]

==Email and personal website==

# Your email address is LOGIN@macs.biu.ac.il, where LOGIN stands for the username of your unix account.
## To access your mailbox through the web, click [https://webmail.cs.biu.ac.il here].
## To download your mail using [https://en.wikipedia.org/wiki/Post_Office_Protocol POP3], configure your email client to use the server mailhost.cs.biu.ac.il (port 110).
## To set up mail forwarding, read the [http://help.cs.biu.ac.il/email.htm instructions].
# Your website address is http://u.math.biu.ac.il/~LOGIN, where LOGIN stands for the username of your unix account.
## To set up your webpage, use an [https://winscp.net/eng/download.php SFTP client] to connect to planet.cs.biu.ac.il (port 22), and then set up your website files (e.g., "index.html") on the folder /u/grad/LOGIN/WWW , where LOGIN stands for the username of your unix account.

==Dormitories==

* [https://biuinternational.com/dorms/ About]

* [https://docs.google.com/forms/d/1BZ1hTIx7nS_9Uo5L1Ehv6jZWqNRM7wyppP1i3YUMnbE/ Registration]

* The dormitories do not supply linens, sheets etc. please make sure to bring whatever you need.

* You will need to take a permanent payment form from the [http://barilanmeonot.co.il/ dorms headquarters] and bring it to your bank. This will set up an automatic monthly payment of your rent and water/electricity usage.

* Note that the dorms have a laundry room, and that you can pay in it with cash (the instructions there seem to insist that you download some app to pay with your phone, but in fact you only need to have 9 NIS exact change (maybe times two, for the washer and the dryer)). To use the machines, pay the exact amount on the yellow machine that in the middle, after that press the green button if you want to use the washer and the yellow button if you want to use the dryer, after this you can use the machine you have selected by the buttons. The small machine in the middle only shows the amount of money you have put on and no information about the other machines.

==Campus==

Keep in mind that the Israeli weekend takes place Friday and Saturday.

The open hours of the gates changes from gate to gate. Gate number 2 opens at 6:30 and closes at 00:00 from Sunday to Thursday. Gate number 1 is open 24h. During the weekend only gate number 1 is open, gate number 2 closes at 1pm on Friday
* [http://www.biu.ac.il/Tour/campus-map.pdf Campus map]

* The campus has a free WiFi network + [https://cat.eduroam.org/?idp=1200 eduroam]

* [https://biuinternational.com/ International students portal]

* Note that there is an ATM outside campus nearby gate #2. This ATM accepts international debit cards.

* [https://www1.biu.ac.il/utilities On-campus utilities] (bank/post office/grocery store/etc')

==Conferences and Reimbursements==

* A month (or more) before going on a conference, you will need to submit an [http://www.assafrinot.com/wiki/travel.doc application form] [http://www.assafrinot.com/wiki/travelEN.docx (English version)] together with an invitation letter. Please keep a scan of the form you submitted, as this will be needed for filling the financial report upon your return.

* After coming back from the conference, you have to submit all your boarding passes and receipts and provide a [http://www.assafrinot.com/wiki/travelrprt.pdf financial report] [http://www.assafrinot.com/wiki/travelrprtEN.docx (English version)] and a [http://www.assafrinot.com/wiki/scientificrpt.pdf scientific report] [http://www.assafrinot.com/wiki/scientificrprtEN.doc (English version)].

* To request reimbursements for relevant purchases you've made, fill [http://www.assafrinot.com/wiki/reimbursement.pdf this form].

==Buses==

* List of [http://math-wiki.com/index.php?title=Visitors#Buses Buses]

*Bus card ([https://en.wikipedia.org/wiki/Rav-Kav Rav-Kav card]): you can buy the bus card from the bus driver or at any central bus station. The cards bought from the bus drivers are anonymous cards and are not eligible for the student benefits, the ones bought at the central stations are personal cards and eligible for student benefits. To buy the card at a central bus station you will need to bring your passport. You will need your passport and certificate of studies to change the status of your card to student, this can be done at any central bus station or at the Information and Student Service Center ([https://www.instagram.com/p/BsDEIYgAUa3/ building 502-19]). You can charge the card at the Information and Student Service Center. At the beginning of every academic year cards with student benefits are blocked, you can unblocked at the Information and Student Service Center showing the certificate of studies for the new academic year.
*Alternatively, there is an app called [https://ravkavonline.co.il/en/ Rav Kav Online] that you can download in your phone and you can scan your card with this app to do anything you want (like charging/viewing history/checking balance/applying student discount etc).

==Miscellaneous==

* [https://www1.biu.ac.il/en_calendar Academic Calendar]

* A reasonably accurate description of how [https://en.wikivoyage.org/wiki/Israel#Holidays Shabbat and Jewish holidays] (see [https://en.wikipedia.org/wiki/Jewish_and_Israeli_holidays_2000%E2%80%932050#5780_%282019%E2%80%932020%29 also]) affect public life in Israel

* [https://math.biu.ac.il/en/node/758 Regular Seminars]

* [http://www.assafrinot.com/wiki/Coleman-Soref.doc Coleman-Soref registration form]

*In case you need an Israeli police clearance certificate for a foreigner embassy. International police clearance certificate can be requested at any police station, you only need to tell the police to which embassy they have to send it, the Dizengoff Tel Aviv Police Station is close to many of the embassies. You have to pick it up at the embassy where it was sent.

*To apostille documents, deposit 35 NIS at any post office to the bank account 0-026789, Foreign Ministry. Go to the ministry of foreign affairs in Jerusalem with the document and the receipt of the payment.

==For faculty==

</div>

* [http://www.assafrinot.com/wiki/travelkkmb.doc נסיעה לחו"ל ע"ח תקציב קקמ"ב]

* [http://www.assafrinot.com/wiki/schollarship.docx רישום השתתפות תקציב מחקר בתקציב מלגות]

Postdocs

2019-09-17T22:22:31Z

Ari: /* Miscellaneous */ added link to info about Shabbat and Jewish holidays

<div dir="ltr" class="mw-content-ltr">

Information for Postdocs at the Math department of Bar-Ilan University. See [[Visitors|similar page]] for all academic visitors.

==Obtaining a student Visa==

# Make sure that your passport expiration date is far away.
# Complete and sign the [https://www.gov.il/BlobFolder/service/student_visa_application_type/he/MatanAshratKnisa_4.pdf application form]. Note that you will need an address in Israel; if you will stay at the university dormitories, you can put that on the form.
# Prepare a physical and electronic copy of the following documents before contacting the [https://www.science.co.il/Embassy.php closest embassy of Israel]:
## Two passport pictures.
## Invitation letter with your full name (as it appears on the passport), passport number, and start+end dates of your postdoctoral studies.
## Proof of the financial support/scholarship for the postdoctoral period.
## A travel document that is valid for at least one year, from the start date of the postdoctoral studies, electronic copy of the page with your personal details, and previous entry visas to Israel if you have any.
# Contact the [https://www.embassypages.com/israel closest embassy of Israel], ask for an appointment for [https://www.gov.il/en/service/student_visa_application_type A2 Visa] and ask whether additional documents are needed. The embassy may indeed require for additional documents. e.g. residence permit (in case you are not living in your home country), hotel reservation (contract with the university dormitories, in case you will stay there), flight tickets, Ph.D. diploma, work reference letter, etc'.
# Pay the fee and attend the appointment. They will provide you with the information for the payment, the date and time of the appointment, and the list of documents that you must send in advance via e-mail (scanned). You will be asked to show the originals during the appointment.

Note: the visa is for one year starting the date of the appointment. It is therefore advised to make the appointment as close as possible to your arrival to Israel.

==Extending your student Visa==
See [http://www.assafrinot.com/wiki/Visa%20Extension%20Procedure,%20July%202017.docx here].

==Your first day in the department==

# Get yourself a local SIM card (you will need it for all the later steps). Here are a couple of options:
## There is a store at the center across the street, called [https://www.d.co.il/80125739/18740/ Blue Phone]; they sell prepaid SIM cards by [https://019mobile.co.il/ 019 mobile]. The SIM card costs 40NIS (one time), and a standard plan (including unlimited calls + 20GB data/month) costs 49NIS/month. The phone number at the store is 03-5259192.
## There is another option with Golan Telecom (https://www.golantelecom.co.il/web/). This is more suitable for those who plan to stay at least one year as it involves signing a contract for a year. The plan they offer changes from time to time. At the time of writing they offer 100 GB/month with unlimited calls and SMS at 29 NIS/month. There are one-time connection fee at 30 NIS and one-time SIM fee at 19 NIS. It is highly recommended to check their current offers before deciding. There are many stores, for example there is one on Yigal Alon St 98, Tel Aviv-Yafo (it is inside the building and you need to ask the guard). Bring your passport, the invitation letter and your credit card with you.
## It is possible to order a sim card [https://biuinternational.com/students/sim-card-information/ online] before coming to Israel, and then pick it up at the airport upon your arrival.
# Get yourself a bank account and a debit card. Inside campus, you'll find a branch of [https://www.mizrahi-tefahot.co.il/en Mizrahi Tefahot] ([https://www.boi.org.il/en/bankingsupervision/banksandbranchlocations/pages/israelibanks.aspx bank code # is 20], and the [https://www.mizrahi-tefahot.co.il/en/Bank/Pages/Branch-Locator.aspx#BranchNumber=414 branch code # is 414]). Make sure to bring in your postdoc invitation letter, your passport, an id card from a country where you are a citizen and the number of your local phone. They will need the tax identification number or equivalent from the country where you pay your tax. They may later ask you to e-mail them a copy of the postdoc invitation letter.
# Fill the four forms:
## [http://www.assafrinot.com/wiki/application260617.PDF Postdoctoral fellowship application form].
## [http://www.assafrinot.com/wiki/registration260617.pdf Registration form for postdocs].
## [http://www.assafrinot.com/wiki/contact.docx Emergency contacts for foreign students] ([http://www.assafrinot.com/wiki/contact.pdf PDF]).
## Policy for postdoctoral fellows: [http://www.assafrinot.com/wiki/policy140817.PDF English], [http://www.assafrinot.com/wiki/נוהל-להשתלמות-בתר-דוקטור.16.3.2017.pdf Hebrew].
Submit them (along with your passport-sized photo, a photocopy of your passport, and a photocopy of the approval of your Ph.D. degree) to [https://math.biu.ac.il/en/node/1196 Rivka Wolberger].
# Get yourself an health insurance. One option is fill the form of [https://biuinternational.com/students/health-insurance/ Harel Yedidim] and mail it to [https://biuinternational.com/about/our-team/ Maayan Cohen] at Maayan.cohen1@biu.ac.il.
## The daily premium insurance costs around 1.9 USD per day.
## You can pay for the whole period in one payment (using any credit card, not necessarily an Israeli one), or ask them to charge you on a monthly basis (in which case, the payment takes place every 9--11 of the month). It is also possible to pay through an international transaction, but you have to pay the commission of the banks. If you have an Israeli account you can pay from there.
## When filling the insurance application form, make sure to set the cover dates to start on the day of signing the former (and not earlier).
# Ask your postdoc advisor to:
## Assign you a room at the department;
## Assign you a P.O. box of the department;
## Show you the [http://sifria2018.lnx.biu.ac.il/F/?func=find-b-0&con_lng=eng library];
## Fill and submit the [http://www.assafrinot.com/wiki/טופס-אשור-מלגות.docx scholarship payment form];
## Provide you the acknowledgement-for-funding string to be included in your research papers.

==Your second week in the department==

# Go to the bank to pick up your debit card.
# Go to [https://math.biu.ac.il/en/node/1196 Rivka Wolberger] to pick up your student card, to create an [https://inbar.biu.ac.il/Live/Login.aspx Inbar] account, and to provide there your bank details, so that you can receive your monthly scholarship.
# Contact [https://math.biu.ac.il/node/582 Doron Kurzberg] to receive username+password for your unix account.
# You can also [http://oren.biu.ac.il/connect-to-bar-ilan-computer-from-home/ connect to Bar-Ilan computer from home]

==Email and personal website==

# Your email address is LOGIN@macs.biu.ac.il, where LOGIN stands for the username of your unix account.
## To access your mailbox through the web, click [https://webmail.cs.biu.ac.il here].
## To download your mail using [https://en.wikipedia.org/wiki/Post_Office_Protocol POP3], configure your email client to use the server mailhost.cs.biu.ac.il (port 110).
## To set up mail forwarding, read the [http://help.cs.biu.ac.il/email.htm instructions].
# Your website address is http://u.math.biu.ac.il/~LOGIN, where LOGIN stands for the username of your unix account.
## To set up your webpage, use an [https://winscp.net/eng/download.php SFTP client] to connect to planet.cs.biu.ac.il (port 22), and then set up your website files (e.g., "index.html") on the folder /u/grad/LOGIN/WWW , where LOGIN stands for the username of your unix account.

==Dormitories==

* [https://biuinternational.com/dorms/ About]

* [https://docs.google.com/forms/d/1BZ1hTIx7nS_9Uo5L1Ehv6jZWqNRM7wyppP1i3YUMnbE/ Registration]

* The dormitories do not supply linens, sheets etc. please make sure to bring whatever you need.

* You will need to take a permanent payment form from the [http://barilanmeonot.co.il/ dorms headquarters] and bring it to your bank. This will set up an automatic monthly payment of your rent and water/electricity usage.

* Note that the dorms have a laundry room, and that you can pay in it with cash (the instructions there seem to insist that you download some app to pay with your phone, but in fact you only need to have 11-13 NIS exact change (maybe times two, for the washer and the dryer)). To use the machines, pay the exact amount on the yellow machine that in the middle, after that press the green button if you want to use the washer and the yellow button if you want to use the dryer, after this you can use the machine you have selected by the buttons. The small machine in the middle only shows the amount of money you have put on and no information about the other machines.

==Campus==

The open hours of the gates changes from gate to gate. Gate number 2 opens at 6:30 and closes at 00:00 from Sunday to Thursday. Gate number 1 is open 24h. During the weekend only gate number 1 is open, gate number 2 closes at 1pm on Friday
* [http://www.biu.ac.il/Tour/campus-map.pdf Campus map]

* The campus has a free WiFi network + [https://cat.eduroam.org/?idp=1200 eduroam]

* [https://biuinternational.com/ International students portal]

* [https://www1.biu.ac.il/utilities On-campus utilities] (bank/post office/grocery store/etc')

==Conferences and Reimbursements==

* A month (or more) before going on a conference, you will need to submit an [http://www.assafrinot.com/wiki/travel.doc application form] together with an invitation letter. Please keep a scan of the form you submitted, as this will be needed for filling the financial report upon your return.

* After coming back from the conference, you have to submit all your boarding passes and receipts and provide a [http://www.assafrinot.com/wiki/travelrprt.pdf financial report] and a [http://www.assafrinot.com/wiki/scientificrpt.pdf scientific report].

* To request reimbursements for relevant purchases you've made, fill [http://www.assafrinot.com/wiki/reimbursement.pdf this form].

==Buses==

* List of [http://math-wiki.com/index.php?title=Visitors#Buses Buses]

*Bus card ([https://en.wikipedia.org/wiki/Rav-Kav Rav-Kav card]): you can buy the bus card from the bus driver or at any central bus station. The cards bought from the bus drivers are anonymous cards and are not eligible for the student benefits, the ones bought at the central stations are personal cards and eligible for student benefits. To buy the card at a central bus station you will need to bring your passport. You will need your passport and certificate of studies to change the status of your card to student, this can be done at any central bus station or at the Information and Student Service Center ([https://www.instagram.com/p/BsDEIYgAUa3/ building 502-19]). You can charge the card at the Information and Student Service Center.
*Alternatively, there is an app called Rav Kav Online that you can download in your phone and you can scan your card with this app to do anything you want (like charging/viewing history/checking balance/applying student discount etc).

==Miscellaneous==

* [https://www1.biu.ac.il/en_calendar Academic Calendar]

* A reasonably accurate description of how [https://en.wikivoyage.org/wiki/Israel#Holidays Shabbat and Jewish holidays] affect public life in Israel

* [https://math.biu.ac.il/en/node/758 Regular Seminars]

* [http://www.assafrinot.com/wiki/Coleman-Soref.doc Coleman-Soref registration form]

==For faculty==

</div>

* [http://www.assafrinot.com/wiki/travelkkmb.doc נסיעה לחו"ל ע"ח תקציב קקמ"ב]

* [http://www.assafrinot.com/wiki/schollarship.docx רישום השתתפות תקציב מחקר בתקציב מלגות]

88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7

2016-09-19T13:45:13Z

Ari: /* תרגיל */ תיקון טעות

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

==אריתמטיקה של עוצמות==

'''הגדרה''' יהיו A,B קבוצות אזי <math>A^B:=\{f:B\rightarrow A\}</math>.

===תרגיל===
יהיו A,B קבוצות כך ש <math>|B|>1</math>. הוכח כי <math>|A|<|B^A|</math>.

'''פתרון.'''
נבחר 2 איברים שונים <math>b_0,b_1\in B</math> ונגדיר פונקציה חח"ע <math>g:A\to B^A</math> ע"י <math>g(a)=f_a</math> כאשר <math>f_a(a)=b_1</math> ו <math>\forall a'\not=a :f_a(a')=b_0</math>
ולכן <math>|A|\leq|B^A|</math>.

נניח בשלילה שקיים שיוויון אזי קיימת התאמה חח"ע ועל <math>g:A\to B^A</math>.
נסמן <math>\forall a\in A:g(a)=f_a</math>.

נראה באופן דומה לתירגול קודם כי g איננה על ע"י שנמצא פונקציה f שאין לה מקור:

נבחר 2 איברים שונים <math>b_0,b_1\in B</math>ונגדיר פונקציה באופן הבא <math>f:A\rightarrow B</math> ע"י
<math>f(a)=b_0</math> אם <math>f_a(a)=b_1</math>. ו- <math>f(a)=b_1</math> אחרת.
לפי הבנייה <math>\forall a\in A f\not=f_a</math> כיוון ש <math>f(a)\not=f_a(a)</math>. סתירה לכך ש g על.

===תרגיל===
הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A

'''הוכחה.'''
יש התאמה חח"ע ועל <math>g:P(A)\to \{0,1\}^A</math> ע"י
<math>\forall B\subseteq A : g(B)=f_B=\chi_B</math>

לפי תרגיל קודם <math>|A|<|\{0,1\}^A|=|P(A)|</math>

'''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה

'''הגדרה:'''
יהיו שתי קבוצות '''זרות''' A,B כך ש <math>|A|=a, |B|=b</math>. אזי נגדיר פעולות בין עוצמות:
*<math>a+b:=|A\cup B|</math>
*<math>a\cdot b := |A\times B|</math>
*<math>a^b := |\{f:B\rightarrow A\}|</math>

דוגמא: ראינו בתירגול קודם את הזיהוי <math>[0,1)=\{f:\mathbb{N} \to \{0,1,...9\}\}</math>
לכן <math>\aleph=|\mathbb{R}|=|[0,1)|=|\{f:\mathbb{N} \to \{0,1,...9\}\}|=10^{\aleph_0}</math>

הערות:
*ההגדרות לעיל מוגדרות היטב, כלומר העוצמה נשארת זהה ללא תלות בבחירת הקבוצות המייצגות.
* בידקו שעבור המקרה הסופי מתקיים מה שמצופה.
למשל <math>2+1=|\{1,2\}\cup\{3\}|=3</math>
*'''שימו לב:''' מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:
**<math>a^0=1</math> שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
**<math>0^0=1</math> זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
**<math>a\neq 0 \rightarrow 0^a=0</math> אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.

===תכונות האריתמטיקה===
יהיו a,b,c עוצמות אזי מתקיים
*<math>ab=ba</math>
*<math>(ab)c=a(bc)</math>
*<math>a^ba^c=a^{b+c}</math>
*<math>a^cb^c=(ab)^c</math>
*<math>(a^b)^c=a^{bc}</math>
כלומר מתקיימים חוקי החזקות ה"רגילים"

נוכיח למשל <math>a^ba^c=a^{b+c}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
נגדיר פונקציה מ <math>A^{B\cup C} \to A^B\times A^C</math> ע"י <math>f \mapsto (f|_B,f|_C)</math>. היא חח"ע ועל.

נוכיח למשל <math>(a^b)^c=a^{bc}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
נגדיר פונקציה מ <math>(A^B)^C \to A^{B\times C} </math> ע"י <math>f \mapsto g(b,c)= f(c)(b)</math>. היא חח"ע ועל.

בנוסף אם מניחים את אקסיומת הבחירה אזי מתקיים עבור a,b עוצמות כאשר אחד מהם אין סופי

* <math>a+b=max\{a,b\}</math>
*אם שניהם אינם אפס אזי <math>a\cdot b=max\{a,b\}</math>
*מסקנה: אם <math>2\leq a \leq b</math> אזי <math>a^b=2^b</math>

הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>

===תרגיל===
הוכח כי <math>\aleph_0+\aleph=\aleph</math>

הוכחה: דרך א- ישירות מהגדרה. נבחר <math>A=[\frac{1}{4},\frac{1}{2}],B=\mathbb{N}</math> אזי
<math>\aleph=|A|\leq |A\cup B |\leq |\mathbb {R}|=\aleph</math>

דרך ב- מהנוסחא. <math>\aleph_0+\aleph=max\{\aleph_0,\aleph\}=\aleph </math>

===תרגיל===
הוכח כי <math>\aleph \cdot \aleph=\aleph </math>

הוכחה: <math>\aleph=|\{f:\mathbb{N}\to \{ 0,1\dots 9 \} \}|=10^{\aleph_0}=2^{\aleph_0}</math>

דרך א- ישירות מהגדרה. נבחר <math>A=\{f:\mathbb{N}\to \{0,1\dots 9\}\},B=A\times A</math> אזי
נגדיר פונקציה <math>A\to A\times A</math> ע"י <math>f(n)\mapsto (f(2n),f(2n+1))</math> . זו פונקציה חח" ועל.

דרך ב- אריתמטיקה-
<math>\aleph \cdot \aleph=2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\aleph </math>

דרך ג- מהנוסחא- <math>\aleph \cdot \aleph=max\{\aleph,\aleph\}=\aleph </math>

===תרגיל===

הוכח כי <math>|\mathbb{R}\backslash \mathbb{Q}|=\aleph</math>

פתרון:

כיוון ש <math>\mathbb{R}\backslash \mathbb{Q}</math> מוכל בממשיים עוצמתה לכל היותר אלף. נניח בשלילה כי עוצמתה שווה a קטנה ממש מאלף אזי
<math>\aleph=|\mathbb{R}|=|\mathbb{R}\backslash \mathbb{Q}|+|\mathbb{Q}|=a+\aleph_0=a<\aleph</math>. סתירה

===תרגיל===
תהא <math>A</math> קבוצה אינסופית.

הוכח/הפרך

1. <math>|A\backslash B|=|A|\Rightarrow |B|<|A|</math>

2. <math>|A\backslash B|=|A|\Leftarrow |B|<|A|</math>

פתרון:

1. הפרכה: ניקח את השלמים והטבעיים

2. נכון כי ניתן להציג A כאיחוד זר <math>A=A\backslash B \cup B</math>
ולכן <math>|A|=|A\backslash B| + |B|</math>. אם <math>|A\backslash B|<|A|</math> נקבל סתירה

=== תרגיל ===
תהי <math>\{A_i\}_{i\in I}</math> משפחה של קבוצות הזרות זו לזו כך שעוצמת כל אחת מהן ב<math>a</math>. נגדיר <math>\sum_{i\in I} a = |\bigcup_{i\in I}A_i|</math>.
הוכח כי <math>\sum_{i\in I} a = |I|\cdot a</math>

פתרון:

תהא <math>A</math> קבוצה נוספת מעוצמה <math>a</math>.
לכל <math>i\in I</math> קיימת פונקציה חח"ע ועל
<math>f_i:A\rightarrow A_i</math>.
כעת נגדיר פונקציה <math>g:I\times a\rightarrow\bigcup_{i\in I}A_i</math> ע"י <math>g(k,x)=f_k(x)</math>. מכיוון שהקבוצות זרות ו<math>f_k</math> חח"ע ברור שg חח"ע. מכיוון ש<math>f_k</math> על גם g על ולכן קיבלנו את המבוקש.

===תרגיל ממבחן תשסח מועד א (ד"ר שי סרוסי וד"ר אלי בגנו) ===

תהי A קבוצה אינסופית. נסמן <math>a=|A|,\;B=P(A),\;F=A\times P(A),\; C=P(A)^A,\; H=B^B</math>

:א. מצא את <math>|C|</math>
:ב. מצא את <math>|F\times H|</math>
:ג. מצא את <math>|\{R:|\mathbb{N}/R|=2\}|</math> המוכלת באוסף יחסי השקילות על הטבעיים.

'''פתרון.'''
א. <math>|C|=(2^a)^a=2^{aa}=2^a</math>

ב.<math>|F\times H|=|F||H|=a2^a(2^a)^{2^a}=2^{a2^a}=2^{2^a}</math>

ג. כל יחס שקילות שקבוצת המנה 2 מתאים לחלוקה של <math>\mathbb{N}</math> ל-2 קבוצות זרות.
ולכן יש התאמה חח"ע ועל <math>\{R:|\mathbb{N}/R|=2\} \leftrightarrow W=\{\{A,A^c\}|A\subseteq \mathbb{N}\}</math> ולכן 2 הקבוצות מאותה עוצמה.

ט: <math>|W|=2^{\aleph_0}</math>

ה: נסמן <math>|W|=a</math>. בנוסף <math>\bigcup_{\{A,A^c\}\in W}\{A,A^c\}=P(\mathbb{N})</math>
ולכן <math>2^{\aleph_0}=|P(\mathbb{N})|=2a=a</math>.

===תרגיל ממבחן תשע מועד א (ד"ר שי סרוסי וד"ר אפי כהן)===

יהי S יחס על <math>\mathbb{R}^\mathbb{R}</math> (קבוצת כל הפונקציות הממשיות), המוגדר על ידי <math>(f,g)\in S</math> אם"ם לכל <math>x\in\mathbb{R}</math> מתקיים <math>f(x)-g(x)\in\mathbb{Z}</math>

:1. הוכיחו ש S הינו יחס שקילות

:2. תהי <math>f\in\mathbb{R}^\mathbb{R}</math> מצאו את <math>|[f]|</math>

:3. מצאו את <math>|\mathbb{R}^\mathbb{R}/S|</math>

'''פתרון:'''

1.
*רפלקסיביות: <math>\forall x\in\mathbb{R} f(x)-f(x)=0\in\mathbb{Z}</math>
*סימטריות: <math>f(x)-g(x)\in\mathbb{Z}</math> גורר שגם <math>g(x)-f(x)\in\mathbb{Z}</math> כי יש נגדי לחיבור
*טרנזיטיביות: נובעת בקלות מסגירות לחיבור בשלמים: <math>f-h=f-g+g-h</math>

2.

עבור <math>[f]\in \mathbb{R}^\mathbb{R}/S </math>
נגדיר <math>F:[f] \to \mathbb{Z}^{\mathbb{R}}</math>.
ע"י <math>F(g):=f-g </math> נראה כי היא מוגדרת,חח"ע ועל.

מוגדרת: לפי ההגדרה של יחס השקילות אכן מתקיים <math>f-g\in \mathbb{Z}^{\mathbb{R}}</math>

נראה כי ל F קיימת הופכית. נגדיר <math>G: \mathbb{Z}^{\mathbb{R}} \to [f]</math>. ע"י <math>G(h):=f-h </math>. הפונקציה מוגדרת היטב כי <math>f-(f-h)\in \mathbb{Z}^{\mathbb{R}}</math> וקל לוודא שזוהי ההופכית

חח"ע: נניח <math>F(g)=F(h)</math> לכן <math>\forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x)</math> ולכן h=g.

על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור ש(f-h) במחלקת השקילות של f והיא תהיה המקור.

אם כך, העוצמה של מחלקת השקילות זהה לעוצמה של אוסף הפונקציות מהממשיים לשלמים והוא <math>{\aleph_0}^\aleph</math>. לפי התכונות שלמדנו לעיל מתקיים <math>2^\aleph\leq{\aleph_0}^\aleph\leq 2^\aleph</math> ולכן לפי קנטור מתקיים <math>{\aleph_0}^\aleph=2^\aleph</math>

3.

נזכור בסימון <math>\lfloor x\rfloor</math> שהוא המספר השלם הגדול ביותר הקטן או שווה לx.

נגדיר F פונקציה השולחת את <math>f\in\mathbb{R}^\mathbb{R}</math> לפונקציה <math>F(f):=f-\lfloor f\rfloor\in [0,1)^\mathbb{R}</math>. נראה ש-F מוגדרת היטב (על קבוצת המנה)וההפעלה שלה על קבוצת המנה תהיה חח"ע ועל.

מוגדרות: יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, <math>F(g)-F(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor</math>. מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר שבערכו המוחלט קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס
כלומר <math>F(f)=F(g)</math>. לכן הפונקציה F מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.

חח"ע: נניח <math>F(f)=F(g)</math> אז <math>f-g=\lfloor f\rfloor - \lfloor g\rfloor</math>
כיוון ש <math>\lfloor f\rfloor - \lfloor g\rfloor\in \mathbb{Z}^\mathbb{R} </math> אזי הם נציגים של אותה מחלקת שקילות כלומר <math>[f]=[g]</math>

על: ניקח פונקציה כלשהי r מהממשיים לקטע <math>[0,1)</math>. קל לראות ש <math>F[r]=r</math> שכן
<math>\lfloor r \rfloor = 0</math>. לכן r ישמש מקור ולכן F הינה על.

סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל<math>\aleph^\aleph</math> וזה שווה ל<math>2^\aleph</math> לפי התכונות לעיל.

===תרגיל ממבחן תשע מועד ב (ד"ר שי סרוסי וד"ר אפי כהן)===

א. תהי A קבוצה אינסופית מעוצמה a.

:1. נגדיר עבור :
<math>X=\{(X_1,...,X_n):1<n\in\mathbb{N}\and\Big[\bigcup_i X_i=A\Big] \and \Big[\forall i\neq j: X_i\cap X_j = \emptyset\Big] \and \big[ \forall i X_i \neq \emptyset\big]\}</math>.

כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A
'''הוכח''' <math>|X|=2^a</math>

:2. מצא את <math>|\mathbb{N}\times X|,|\mathbb{N}\cup X|</math> וגם את <math>|X|^{|\mathbb{N}|},|\mathbb{N}|^{|X|}</math>

ב.תהי <math>\{A_i\}_{i\in I}</math> משפחה של קבוצות הזרות זו לזו. נסמן את עוצמת כל אחת מהן ב<math>a_i</math> בהתאמה. נגדיר <math>\sum_{i\in I} a_i = |\bigcup_{i\in I}A_i|</math>.

חשב את <math>\sum_{n\in\mathbb{N}}\aleph</math>

'''פתרון.'''

א.

:1.

נביט באוסף הפונקציות <math>Y=\{f:A\rightarrow\mathbb{N}\}</math>. נגדיר <math>g:X\to Y</math>
על ידי לכל <math>x=(X_1,...,X_n)\in X</math>

נשלח אותו ל <math>g(x)=f_x</math> המוגדר
<math>\forall a\in A :\; f_x(a)=k</math> כאשר <math>a\in X_k</math> כלומר שולחת איבר לאינדקס של הקבוצה שהוא נמצא בה בחלוקה.

נוכיח שהפונקציה מוגדרת וחח"ע.

מוגדרת: כיוון ש x הוא חלוקה של A אזי האיבר a יופיע ויופיע בדיוק באחת מהקבוצות.

חח"ע: נניח <math>(X_1,...,X_n)=x\neq x'=(X'_1,...,X'_m)</math>. אזי קיים <math>X_i\not=X'_i</math>, לכן קיים יהיה <math>a\in X_i/X'_i</math> (או להיפך) ואז <math>i=f_x(a)\not= f_{x'}(a)</math>
כלומר <math>g(x)\not=g(x') </math>

דרך 2- נגדיר פונקציה <math>g:X\to P(A)^{\mathbb{N}}</math> ע"י <math>g((X_1,...,X_n))(i) = \begin{cases}X_i & \text{if } 1\leq i \leq n \\ \emptyset & \text{if } n<i \end{cases} </math>

קל לראות כי הפונקציה חח"ע ולכן <math> |X| =(\leq 2^{|A|})^{\aleph_0} = \leq 2^{|A|\cdot \aleph_0} =2^{|A|}</math>

דרך 3- נציג את X כאיחוד זר <math>X=\cup_{1<n\in \mathbb {N}}Y_n</math> כאשר <math>Y_n</math> זה חלוקות סדורות של A עם n קבוצות. כעת לכל n קיימת פונקציה <math>g:Y_n \to P(A)^n</math>
המוגדרת <math>g((X_1,...,X_n))=X_1 \times \cdots \times X_n</math> קל לראות שהיא חח"ע ולכן <math>|Y_n|=|A|^n =|A|</math> ולכן <math>|X|\leq \sum_{1<n\in \mathbb {N}}|A|=|A|\cdot \aleph_0 =|A|</math>

כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A ל-X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.

לכן <math>2^{|A|} \leq |X| \leq |Y| = \aleph_0^{|A|}</math>, ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת X הינה <math>2^a</math>.

:2.

<math>|\mathbb{N}\cup X|=\aleph_0+2^a=2^a</math>

<math>|\mathbb{N}\times X|=\aleph_0\cdot 2^a=2^a</math>

<math>|X|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a</math>

<math>|\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a}</math>

ב.

בעצם אנו רוצים לחשב איחוד בן מנייה של קבוצות מעוצמת <math>\aleph</math>.
לכל עותק של <math>\aleph</math> נתאים <math>A_n</math> ופונקציה חח"ע ועל
<math>f_n:\mathbb{R}\rightarrow A_n</math>.
כעת נגדיר פונקציה <math>g:\mathbb{N}\times\mathbb{R}\rightarrow\bigcup_{n\in\mathbb{N}}A_n</math> ע"י <math>g(k,x)=f_k(x)</math>. מכיוון שהקבוצות זרות ו<math>f_k</math> חח"ע ברור שg חח"ע. מכיוון ש<math>f_k</math> על גם g על ולכן סה"כ עוצמת הסכום הינה <math>\aleph_0\cdot\aleph=\aleph</math>

88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 4

2016-09-18T13:51:02Z

Ari: /* דוגמאות */ תיקון טעויות

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

==פונקציות==
'''הגדרה:''' יהיו A,B קבוצות וR יחס בינהן. אזי:
*התחום של R הינו <math>dom(R)=\{a\in A|\exists b\in B:(a,b)\in R\}=\{(*,\;),(*,\;)\dots \}</math>
*התמונה של R הינה <math>im(R)=\{b\in B|\exists a\in A:(a,b)\in R\}=\{(\;,*),(\; ,*)\dots \}</math>

'''הערה''': ישירות מהגדרה מתקיים כי <math>dom(R)\subseteq A, Im(R)\subseteq B</math>

'''דוגמא:'''
*אם R יחס מלא על A אזי האיחוד של התמונה והתחום שווה A (כי כל שני איברים ניתן להשוות)
*<math>R=\{(1,a),(2,b),(3,a),(a,1)\}</math> אזי התחום הוא <math>dom(R)=\{a,1,2,3\}</math> והתמונה הינה <math>im(R)=\{1,a,b\}</math>

'''הגדרה:'''
*יחס R מ-A ל-B נקרא '''על''' אם <math>\forall b\in B \exists a\in A:(a,b)\in R</math> כלומר <math>im(R)=B</math>
*יחס R מ-A ל-B נקרא '''שלם''' אם <math>\forall a\in A \exists b\in B:(a,b)\in R</math> כלומר <math>dom(R)=A</math>
*יחס R נקרא '''חד ערכי''' אם <math>[(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b)</math> כלומר אין איבר שנשלח ל-2 מקומות שונים
*יחס R נקרא '''חד-חד ערכי''' אם <math>[(x,b)\in R] \and [(y,b) \in R] \rightarrow (x=y)</math> כלומר איברים שונים נשלחים למקומות שונים (כלומר, היחס ההופכי הינו חד ערכי)

'''הגדרה:'''

יחס חד ערכי ושלם נקרא '''פונקציה'''; נסמן במקרה זה <math>(a,b)\in R\leftrightarrow b=R(a)</math>.
ובאופן כללי <math>f:A\to B \;\; , a \mapsto f(a)</math>.
(A נקרא תחום (הגדרה) של הפונקציה. ו B נקרא הטווח של הפונקציה)

נחזור על הגדרת חח"ע עבור פונקציה:

<math>f</math> חח"ע אמ"מ <math>f(x_1)=f(x_2)\Rightarrow x_1=x_2</math> אמ"מ <math>x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2)</math>

'''הגדרה:'''

תהא A קבוצה. '''פונקציית הזהות''' היא פונקציה <math>f:A \to A</math> המקיימת <math>\forall a\in A: f(a)=a</math>. נהוג לסמנה: <math>id_A</math> פונקציית הזהות היא חח"ע ועל.

===דוגמאות:===
*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p^2</math> (אינה חח"ע ואינה על)
*<math>f:\mathbb{N}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p^2</math> ( חח"ע ואינה על)
*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p</math>. זו פונקציית הזהות.
*<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> כאשר <math>f(x)=x-1</math> ( חח"ע ו על)
*<math>f:\mathbb{N}\rightarrow\mathbb{N}</math> כאשר <math>f(x)=x-1</math> ( לא מוגדר כי <math>f(1)=?</math>)
*<math>f:\mathbb{R}\rightarrow\mathbb{Z}</math> כאשר <math>f(x)=[x]</math> מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע
*<math>f:\mathbb{Z}_2\rightarrow\mathbb{Z}_3</math> כאשר לוקחים את 0 ל0 ואת 1 ל1. זו פונקציה חח"ע שאינה על. (כל פונקציה היא על לתמונה של עצמה.)
*<math>D:\mathbb{R}\rightarrow\mathbb{R}</math> פונקצית דיריכלה: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.
* תהא <math>A</math> קבוצה ו <math>B\subseteq A</math> תת קבוצה. הפונקציה
<math>
\chi_B=
\begin{cases} 1 & \text{ if } x\in B \\ 0 & \text{ otherwise } \end{cases}
</math>
פונקצית האינדקטור. במקרה של דריכלה <math>D=\chi_{\mathbb{Q}}</math>
* תהא <math>f:A\to B</math> אזי <math>g:A\to Im(f) </math> המוגדרת <math>g(a)=f(a)</math> היא על (במילים: פשוט חושבים על הטווח של f להיות התמונה של f)
* תהא <math>A\subseteq B</math> אזי הפונקציה <math>i : A\to B </math> המוגדרת <math>i(a)=a</math> נקראת פונקציה ההכלה (במקרה ש <math>A=B</math> זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.

===תרגיל===
יהיו A ו-B קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מ-A ל-B הינה על אם"ם היא חח"ע

'''הוכחה:'''
נסמן <math>f:A\to B, A=\{a_1,\dots a_n\},B=\{b_1,\dots b_n\} </math> . כאשר כל האיברים ב A שונים זה מזה וכנ"ל ל B

נניח <math>f </math> חח"ע אזי <math>|\{f(a_1),\dots f(a_n)\}|=n</math>
כיוון ש <math>\{f(a_1),\dots f(a_n)\}\subseteq B </math> ובשניהם יש אותו מספר איברים, מתקיים שיוון ולכן <math>f </math> על.

נניח <math>f </math> על. נניח בשלילה ש <math>f </math> אינה חח"ע אזי <math>|\{f(a_1),\dots f(a_n)\}|<n</math> (כי יש שני איברים שנשלחים לאותו מקום)
ואז <math>f </math> אינה על -סתירה.

הערה: הדבר אינו נכון אם A וB קבוצות אינסופיות.

למשל פונקצית הערך השלם <math>f:\mathbb{R} \to \mathbb{Z} </math> המוגדרת <math>f(x) =\lfloor{x}\rfloor</math> היא על ואינה חח"ע

===הרכבת פונקציות===

'''הגדרה:'''
יהיו <math>f:A\to B, g:B\to C </math> שתי פונקציות אזי '''ההרכבה של <math>g</math> על <math>f</math>''' היא פונקציה <math>g \circ f:A\to C </math> המוגדרת על ידי הכלל <math>g \circ f(a)=g(f(a)) </math>

תכונות:
# הרכבה היא קיבוצית. כלומר <math>f_3 \circ (f_2 \circ f_1) = (f_3 \circ f_2) \circ f_1 </math>
# הרכבה '''אינה''' (בהכרח) חילופית כלומר לא מתקיים בהכרח כי <math>f_2 \circ f_1 = f_2 \circ f_1 </math>. למשל <math>f(x) =x^2 , g(x) = x+1</math> אזי <math>f(g(2))=f(3)=9, g(f(2))=g(4)=5</math> ולכן <math>f\circ g \neq g \circ f</math>

====תרגיל====
*נניח <math>g \circ f</math> חח"ע. הוכח/הפרך: g חח"ע, f חח"ע
*נניח <math>g \circ f</math> על. הוכח/הפרך: g על, f על

'''פתרון:'''

נניח <math>g \circ f</math> חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>x,y</math> כך ש <math>f(x)=f(y)</math> אבל <math>x\neq y</math>. אבל, <math>g\circ f (x) = g(f(x))=g(f(y))=g\circ f(y)</math> בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.

לגבי g ניתן דוגמא נגדית: <math>f(x)=e^x ,g(y)=y^2</math> ההרכבה היא <math>h(x)=e^{2x}</math>

נניח <math>g \circ f</math> על. נסמן <math>g \circ f : A\rightarrow B</math> אזי לכל איבר <math>b\in B</math> קיים איבר <math>a\in A</math> כך ש <math>g(f(a))=b</math>. לכן עבור g לכל b קיים <math>f(a)</math> שנותן את b תחת g ולכן g על.

דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם
<math>f(n)=n+1</math>;
<math>\forall n\not=0 g(n)=n-1 , g(0)=0</math>
ההרכבה היא הזהות

(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. <math>f(n)=2n</math>, והפונקציה g מוגדרת כ <math>g(2n)=n</math> ו <math>g(2n+1)=n</math>. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל f אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)

===פונקציות הפיכות===
'''הערה:''' לכל פונקציה <math>f</math> מתקיים <math>f\circ id =f</math> וגם <math>id \circ f =f</math>

'''הגדרה:''' תהי <math>f</math> פונקציה <math>f:A\rightarrow B</math>. פונקציה <math>g:B\rightarrow A</math> תיקרא '''הפונקציה ההופכית ל-<math>f</math>''' אם <math>f\circ g = id_B</math> וגם <math>g\circ f = id_A</math>. במקרה זה נסמן את <math>g</math> על ידי <math>f^{-1}</math>, ונאמר שהפונקציה <math>f</math> היא '''הפיכה'''.

הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.

'''תרגיל.'''

הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.

'''הוכחה:'''

אם f הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע ועל, נובע ש-f חח"ע ועל לפי התרגיל הקודם בדבר הרכבת פונקציות.

אם f חח"ע ועל, אז נגדיר <math>g:B\to A</math> ע"י: עבור <math>a\in A </math> קיים (כי f על) יחיד (כי f חח"ע)
<math>b\in B</math> כך ש <math>f(a)=b</math> . נגדיר <math>g(b):=a</math>. תרגיל: בדקו ש g ההופכית של f.

יחידות: נניח g,h הופכיות של f אזי <math>h= h\circ I_B=h\circ f \circ g=I_A \circ g=g</math>.

דרך אחרת להוכחת יחידות: נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, <math>\exists a\in A:g(a)\neq h(a)</math>. אבל <math>f(g(a))=f(h(a))</math> וזו סתירה לחח"ע של f.

==== דוגמאות ====
1. <math>f:\mathbb{R} \to \mathbb{R}</math> המוגדרת:
# <math>f(x)=x+1</math> הפיכה וההופכית היא <math>f^{-1}(x) = x-1 </math>
# <math>f(x)=x^3</math> הפיכה וההופכית היא <math>f^{-1}(x) = x^{1/3} </math>
# <math>f(x)=\sin (x)</math> אינה הפיכה כי איננה חח"ע למשל <math>\sin(0) =\sin(2\pi k)</math>

2 תהא <math>A</math> קבוצה <math>f:P(A)\to P(A)</math> המוגדרת:
# <math>f(B)= B^c</math> הפיכה וההופכית היא <math>f^{-1}(B) = B^c </math>
# תהא <math>C\subseteq A</math> תת קבוצה <math>f(B)= B \triangle C</math> הפיכה וההופכית היא <math>f^{-1}(B) = B \triangle C </math>

3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר <math>f:P(A)\to \{0,1\}</math> ע"י :

<math>
f(B)=
\begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}
</math>

תקיים כי<math>f(C)=f(A) </math> ואם <math>C\neq A</math> אזי הפונקציה אינה חח"ע ובפרט אינה הפיכה

4. תהא <math>A</math> קבוצה. אזי אפשר (בעזרת חומר שראינו בתירגול על יחסי שקילות)
להגדיר <math>f:\{R \; | \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\}</math> ע"י <math>f(R)=A/R</math> והיא תהיה חח"ע ועל כי ראינו את הפונקציה ההופכית לה

===תרגיל ===
יהיו <math>f_1,\dots f_k:A\to A</math> הפיכות/חח"ע/על. הוכח שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה/חח"ע/על

הוכחה:

חח"ע: נניח <math>(f_k \circ \dots \circ f_1)(x_1) =(f_k \circ \dots \circ f_1)(x_2)</math> אזי מח"ע של <math>f_k</math>
נקבל כי <math>(f_{k-1} \circ \dots \circ f_1)(x_1) =(f_{k-1} \circ \dots \circ f_1)(x_2)</math> באופן דומה נמשיך (או באינדוקציה) ונקבל <math>x_1=x_2</math>

על: יהא <math>y\in A</math> כיוון ש <math>f_k</math> על קיים <math>a_k\in A</math> כך ש <math>f_k(a_k)= y</math>
באותו אופן קיים <math>a_{k-1}</math> כך ש <math>f_{k-1}(a_{k-1}=a_k</math> נמשיך באופן דומה (או באינקודציה)
ונקבל <math>(f_k \circ \dots \circ f_1)(a_1)=(f_k \circ \dots \circ f_2)(a_2)=\dots f_k\circ f_{k-1} (a_{k-1}) = f_k(a_k)=y</math>

הפיכות: נובע מחח"ע+על

===תרגיל ===
הוכח כי אם <math>g\circ f \circ g =id</math> אז <math>f </math> הפיכה

הוכחה:

הרכבה של פונקציה חח"ע <math>(g\circ f) \circ g =id</math> גורר שהשמאלית <math>g</math> חח"ע

הרכבה של פונקציה על <math>g\circ (f \circ g) =id</math> גורר שהימנית <math>g</math> על

ביחד נקבל ש <math>g</math> חח"ע ועל כלומר הפיכה. נכפול ב <math>g^{-1}</math> מימין ומשמאל ונקבל כי <math>f=g^{-1}\circ g^{-1}</math> ואז <math>f</math> הפיכה כהרכבה של הפיכות.

88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 5

2016-09-18T13:39:28Z

Ari: /* תמונות חלקיות */ תיקון טעויות

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

==המשך פונקציות - פונקציות על תת-קבוצות==

===תמונות חלקיות===

'''הגדרה.''' תהי <math>f:X\rightarrow Y</math> פונקציה, ויהיו תת קבוצות <math>A\subseteq X,B\subseteq Y</math>. אזי '''התמונה החלקית של A תחת f''' היא התת-קבוצה <math>f(A)=\{f(a)|a\in A\}</math>, ו'''התמונה החלקית ההפוכה של B תחת f''' היא התת-קבוצה <math>f^{-1}(B)=\{a\in X|f(a)\in B\}</math>.

שימו לב להבדל בין התמונה ההפוכה <math>f^{-1}(B)</math> לבין הפונקציה ההופכית <math>f^{-1}(y)</math>. התמונה ההפוכה איננה מניחה כי הפונקציה f הפיכה. הדרך להבחין בין פונקציה הפיכה לתמונה ההפוכה היא לבדוק האם בין הסוגריים נמצא ''איבר'' של התמונה (בדוגמאות לעיל זהו <math>y \in Y</math>) או שנמצאת ''תת-קבוצה'' של התמונה (בדוגמאות לעיל זו <math>B\subseteq Y</math>).

==== דוגמאות ====
תהא <math>D:\mathbb{R}\to \mathbb{R}</math> פונקצית דריכלה. אזי <math>D(\mathbb{Q})=\{1\},D^{-1}(\{1\})=\mathbb{Q}=D^{-1}((0.5, 18))</math>

תהא <math>f:X\to Y</math> פונקצית . אזי <math>f^{-1}(Y)=X</math>

תהא <math>f:\mathbb{R}\to \mathbb{Z}</math> פונקצית הערך השלם התחתון. אזי <math>f((-0.5,3/4))=\{-1,0\},f^{-1}(\{1\})=[1,2)</math>

==== תכונות ====
# אם <math>A_1\subseteq A_2</math> אזי <math>f(A_1)\subseteq f(A_2)</math>
# אם <math>B_1\subseteq B_2</math> אזי <math>f^{-1}(B_1)\subseteq f^{-1}(B_2)</math>

'''תרגיל.'''
הוכח/הפרך: תהיינה <math>A,B \subseteq X</math> ותהי f פונקציה <math>f:X \to Y</math>. אזי <math>f(A)\cap f(B)=f(A\cap B)</math>

'''פתרון.'''

נפריך על ידי דוגמא נגדית. נניח וf אינה חח"ע, כלומר קיימים <math>x\neq y </math> כך ש <math>f(x)=f(y)</math>. ניקח <math>A=\{x\},B=\{y\}</math> אזי:

<math>f(A)\cap f(B) = \{f(x)\} \neq \phi = f(\{\}) = f(A\cap B)</math>

'''הערה''' תמיד מתקיים <math>f(A\cap B)\subseteq f(A)\cap f(B)</math>

'''הערה''' הטענה נכונה אם <math>f</math> חח"ע. הוכיחו!

===תרגיל===
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הוכח <math>A \subseteq f^{-1}(f(A))</math>. וקיים שיוויון אם <math>f</math> חח"ע

'''פתרון.'''

יהא <math>a\in A</math> אזי <math>f(a)\in f(A)</math> ולכן <math>a\in f^{-1}(f(A))</math>.

נראה את ההכלה בכיוון השני אם <math>f</math> חח"ע:

יהא <math>x\in f^{-1}(f(A))</math> לכן <math>f(x) \in f(A)</math> לכן <math>\exists a\in A : f(x)=f(a)</math>. כיוון ש <math>f</math> חח"ע נובע כי <math>x=a\in A</math>

דוגמא שלא מתקיים שיוויון <math>f:\{1,2\}\to \{1\}</math> (יש דרך אחת להגדיר את הפונקציה). אזי נגדיר <math>A=\{2\}</math> ומתקיים <math> f^{-1}(f(A))=\{1,2\}\neq A</math>

===תרגיל===
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq Y</math>. הוכח <math> f(f^{-1}(A)) \subseteq A</math>. וקיים שיוויון אם <math>f</math> על

'''פתרון.'''

יהא <math>f(x) \in f(f^{-1}(A))</math> כאשר <math>x\in f^{-1}(A)</math> ולכן <math> f(x)\in A </math>.

נראה את ההכלה בכיוון השני אם <math>f</math> על:

יהא <math> a\in A </math> כיוון ש f על <math>\exists x\in X : f(x)=a </math> לכן <math> x \in f^{-1}(A) </math>. ואז <math>a=f(x)\in f(f^{-1}(A)) </math>

דוגמא שלא מתקיים שיוויון <math>f:\{1\}\to \{1,2\}</math> המוגדרת <math>1\mapsto 1</math>. אזי נגדיר <math>B=\{1,2\}</math> ומתקיים <math> f(f^{-1}(B)) =\{1\}\neq B</math>.

===תרגיל ממבחן (קצת משודרג)===

יהיו <math>X,Y</math> שתי קבוצות, ותהי <math>f:X\rightarrow Y</math> פונקציה כלשהי. נגדיר את הפונקציה <math>g:P(Y)\rightarrow P(X)</math> על ידי <math>g(B)=f^{-1}(B)</math>.
בדוק את הקשר בין החח"ע/על של f לבין אלה של g. (כלומר, מה גורר את מה בהכרח).

'''פתרון.'''

1. ''' f על אמ"מ g חח"ע '''
בכיוון אחד- נתון ש f על. נניח <math>f^{-1}(B)=g(B)=g(A)=f^{-1}(A)</math> נפעיל את f על שני הצדדים ונקבל (בגלל ש f על) <math>B=f(f^{-1}(B))=f(f^{-1}(A))=A</math>

בכיוון השני- נתון כי g חח"ע. נניח בשלילה כי f אינה על אזי <math>\exists y\in Y\forall x\in X:f(x)\neq y</math> לכן <math>g(Y)=f^{-1}(Y)=f^{-1}(Y/\{y\})=g(Y/\{y\})</math> בסתירה לחח"ע של g.

2. ''' f חח"ע אמ"מ g על '''
בכיוון אחד- נתון f חח"ע. אזי <math>g(f(A))=f^{-1}(f(A))=A</math> ולכן g על ( עבור A המקור שלה יהיה <math>f(A)</math> )

בכיוון השני- נתון g על. נניח בשלילה ש f אינה חח"ע אזי קיימים <math>x,y \in X</math> שונים כך ש <math>f(x)=f(y)</math>. נביט בנקודון <math>A=\{x\}</math>

כיוון ש g על קיימת <math>B\in P(Y)</math> כך ש <math>f^{-1}(B)=g(B)=A</math>

לכן <math> \{f(x)\}= f(A)= f(f^{-1}(B))\subseteq B </math>

ולכן <math>\{y,x\}\subseteq f^{-1}(\{f(x)=f(y)\})= f^{-1}(\{f(x)\}) \subseteq f^{-1}(B)=g(B)=A=\{x\}</math>

לכן <math>\{y,x\}\subseteq \{x\}</math> כלומר <math>x=y</math>. סתירה.

מכאן ניתן להסיק כי שאר הגרירות אינן מוכרחות:

* '''ייתכן ו-f חח"ע אך g אינה כזו''' (ניקח f חח"ע שאינה על אזי g אינה חח"ע לפי 1)

* '''יתכן ו-g חח"ע אך f אינה כזו'''. (ניקח g חח"ע שאינה על אזי f אינה חח"ע לפי 2)

* '''ייתכן ו-f על אך g אינה כזו ''' (ניקח f על שאינה חח"ע אזי g אינה על לפי 2)

* '''ייתכן ו-g על אך f אינה כזו ''' (ניקח g על שאינה חח"ע אזי f אינה על לפי 1)

אתם מוזמנים לתת דוגמאות למסקנות לעיל

למשל:
יהיו <math>X=\mathbb{Z}, Y=\{0\}</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן <math>g(\{\})\neq g(\{0\})</math> ואלה הקבוצות היחידות בקבוצת החזקה של Y.

===פונקציה מצומצמת===

'''הגדרה.'''
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הפונקציה '''f מצומצמת לA''' מוגדרת על ידי: <math>f|_A:A\rightarrow Y</math> כך ש-<math>f|_A(a)=f(a)</math>.

'''דוגמא.'''
נביט ב-<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> המוגדרת על ידי <math>f(x)=x^2</math> ואינה חח"ע. נכון לומר שהפונקציה המצומצמת <math>f|_{\mathbb{N}}</math> כן חח"ע.

'''תרגיל.'''
תהי <math>f:X\rightarrow Y</math> פונקציה, הוכח שקיימת קבוצה A כך ש-<math>f|_A</math> חח"ע עם אותה התמונה כמו הפונקציה המקורית (כלומר <math>im(f|_A)=im(f)</math>).

'''פתרון.'''

נגדיר לכל <math>y\in im(f)</math> את הקבוצה של המקורות שלו <math>B_y:=f^{-1}(\{y\})</math>
כעת נבחר מכל <math>B_y</math> איבר יחיד <math>x_y\in B_y</math>. נגדיר <math>A=\{x_y | y\in im (f)\}</math>. כיוון שבחרנו מקור '''לכל''' תמונה, ובחרנו מקור '''אחד''' אזי <math>f|_A</math> חח"ע עם אותו טווח של <math>f</math>.

'''אזהרה!''' ההוכחה מתבססת על אקסיומת הבחירה (נפגש איתה בהמשך)

=== פונקציות המכבדות יחס שקילות ===
'''הגדרה.''' תהי <math>f:A\rightarrow B</math>, ויהי R יחס שקילויות על A. אומרים כי '''f מוגדרת היטב על <math>A/R</math>''' אם <math>\forall a,b\in A:(a,b)\in R\Rightarrow f(a)=f(b)</math>

כלומר אם a שקול ל b אזי <math>f(a)=f(b)</math>.

למה זה טוב?
כדי שנוכל להגדיר פונקציה על קבוצת המנה <math>g:A/R \to B </math> ע"י <math>[a]_R \mapsto f(a) </math>

באופן מפורש <math>g=\{([a],f(a))|a\in A\}</math>.

טענה: g אכן פונקציה

הוכחה:

1. g שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם.

2. g חד ערכית- נניח <math>[a]=[b]</math>, צ"ל <math>g([a])=g([b])</math>. מהנתון ש <math>[a]=[b]</math> נובע ש <math>(a,b)\in R</math>, ולכן, לפי הגדרת f כמוגדרת היטב על קבוצת המנה, מתקיים <math>f(a)=f(b)</math>, ולפי הגדרת g מתקיים <math>g([a])=f(a)=f(b)=g([b])</math>.

'''דוגמא לחידוד'''
האם f על הרציונאליים המוגדרת על ידי <math>f\bigg(\frac{p}{q}\bigg)=p</math> מוגדרת היטב?

'''פתרון'''
לא! כזכור הרציונאליים הם קבוצת מנה של <math>\mathbb{Z}\times \mathbb{N}</math>. לפי היחס שהגדרנו מתקיים <math>\frac{1}{3}=\frac{2}{6}</math> אבל לא מתקיים <math>f\bigg(\frac{1}{3}\bigg)=1\not=2=f\bigg(\frac{2}{6}\bigg)</math>

במילים: לא ברור לאן f שולחת את השבר שליש!

הערה: בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג 'מוגדר היטב' במהלך התואר - יחס השקילויות יהיה מרומז בלבד.